LeetCode 1.两数之和 131.分割回文串




题目1:

happysneaker.com



思路:

① 考虑 target-num1=num2 的形式来进行判断

② 用字典来存储nums,k存储num,v存储num的index

③ 使用字典时,并非全部存储完再进行①的判断,而是存一个进行一次判断,这样时间复杂度为N

③ 代码中要先进行判断,再进行字典存num:

     如果先存值,那么 if target-num1 in d 进行判断时,num1已经存储到了 d 中,若target为4,num1为2,那么就发生了错误。因此应该判断(target-即将存储进字典的num1)的值即num2,是否已经存在于字典中。在的话,直接返回结果;如果不在,OK将num1及其index存储到字典里

④ 技巧是用到python的 enumerate(List) 枚举函数,for i,num in enumerate(list1) ,可以同时遍历list的值、index



解:

class Solution(object):
    def twoSum(self, nums, target):
        d={}
        for i,num in enumerate(nums):
            if target-num in d:
                return [i,d[target-num]]
            d[num]=i


happysneaker.com



题131 分割回文串

happysneaker.com


思路:




解:

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        res,len_s = [],len(s)

        def dfs(re,index):
            if index==len_s:
                res.append(re)            
            for i in range(1,len_s-index+1):
                hel = s[index:index+i]
                if hel==hel[::-1]:
                    dfs(re+[hel],index+i)
        dfs([],0)
        return res







Web安全技术分享
请先登录后发表评论
  • 最新评论
  • 总共0条评论