leedcode算法解题思路

1.两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

思路1：暴力解题：固定一个数nums[i],然后让target减nums[i] 如果在数组中且下标不等于i则返回[i,nums.index(target-nums[i)].

　　　时间复杂度： $O(n^2)$ ，对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 $O (n)$ 的时间。因此时间复杂度为 $O(n^2)$ 。

　　空间复杂度O(1)

 1 class Solution(object):
 2     def twoSum(self, nums, target):
 3         """
 4         :type nums: List[int]
 5         :type target: int
 6         :rtype: List[int]
 7         """
 8     
 9         for i in range(len(nums)):
10             if (target-nums[i]) in nums and i!=nums.index(target-nums[i]):
11                 return [i,nums.index(target-nums[i])]

思路2：借助python的字典(内部实现借助hash表) 把数组的下标放在字典的键，数组元素放在字典的值中。时间复杂度O(n) 准确来说是O(2*n)

 1 class Solution(object):
 2     def twoSum(self, nums, target):
 3         """
 4         :type nums: List[int]
 5         :type target: int
 6         :rtype: List[int]
 7         """
 8         data = {}
 9         for idx, val in enumerate(nums):
10             if val not in data:
11                 data[val] = [idx]
12             else:
13                 tem=data[val]
14                 tem.append(idx)
15                 data[val] = tem
16         for each in data:
17             if (target - each in data) :
18                 if data[target - each] != data[each]:
19                     return [data[target - each][0], data[each][0]]
20                 if len(data[each])==2:
21                     return data[each]
22

思路3：在创建字典的同时一边判断字典中是否存在这个元素，一边往字典中添加元素时间复杂度O(n) 比思路2 大约快20%

 1 class Solution(object):
 2     def twoSum(self, nums, target):
 3         """
 4         :type nums: List[int]
 5         :type target: int
 6         :rtype: List[int]
 7         """
 8         data={}
 9         for i in range(len(nums)):
10             if target-nums[i] in data:
11                 return [i,data[target-nums[i]]]
12             data[nums[i]]=i

371 两个整数之和

不使用运算符 + 和 - ，计算两整数 a 、b 之和。

思路1：xor异或运算不产生进位，&元算结束后左移一位

 1 class Solution(object):
 2     def getSum(self, a, b):
 3         """
 4         :type a: int
 5         :type b: int
 6         :rtype: int
 7         """
 8         while b != 0:
 9             carry = a & b
10             a = (a ^ b) % 0x100000000
11             b = (carry << 1) % 0x100000000
12         return a if a <= 0x7FFFFFFF else a | (~0x100000000+1)

633 两个平方数之和

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。

思路：如果用指针指向一个数，用c-a**2 然后开方，如果为整数返回true 时间复杂度O(根号下n)

 1 import math
 2 class Solution(object):
 3     def judgeSquareSum(self, c):
 4         """
 5         :type c: int
 6         :rtype: bool
 7         """
 8         if c==0:
 9             return True
10         for i in range(1,int(math.sqrt(c))+1):
11             tem=math.sqrt(c-i**2)
12             if tem.is_integer():
13                 return True
14             else:
15                 continue
16         return False
17

15 三数之和(双指针解法)

思路：每次固定一个变量i，然后使用两个指针指向数组的i+1，数组尾部，如果三个数相加等于0返回，同时让lr指针同时移动，如果s小于0，让r减去1,否则让l加1

　　时间复杂度O(n**2)

 1 class Solution:
 2     def threeSum(self, nums):
 3         nums.sort()
 4         res=[]
 5         for i in range(len(nums)):
 6             if i == 0 or nums[i]>nums[i-1]:
 7                 l = i+1
 8                 r = len(nums)-1
 9                 while l<r:
10                     s=nums[i]+nums[l]+nums[r]
11                     if s==0:
12                         res.append([nums[i],nums[l],nums[r]])
13                         l+=1
14                         r-=1
15                         while l<r and nums[l]==nums[l+1]:
16                             l+=1
17                         while l<r and nums[r]==nums[r+1]:
18                             r-=1
19                     elif s>0:
20                         r-=1
21                     else:
22                         l+=1
23         return res

16 最接近的三数之和

思路：双指针法：固定一个变量i，然后分别移动l和r 时间复杂度O(n**2)

 1 class Solution(object):
 2     def threeSumClosest(self, nums, target):
 3         """
 4         :type nums: List[int]
 5         :type target: int
 6         :rtype: int
 7         """
 8         nums.sort()
 9         tem=1000000
10         res=0
11         for i in range(len(nums)):
12             if i==0 or nums[i]>nums[i-1]:
13                 l=i+1
14                 r=len(nums)-1
15                 while l<r:
16                     s = nums[i]+nums[l]+nums[r]
17                     if abs(s-target) < tem:
18                         tem = abs(s-target)
19                         res=s
20                     elif s<target:
21                         l+=1
22                     else:
23                         r-=1
24         return res

18 四数之和

 1 class Solution:
 2     def fourSum(self, nums, target):
 3         """
 4         :type nums: List[int]
 5         :type target: int
 6         :rtype: List[List[int]]
 7         """
 8 
 9         if not nums:
10             return []
11 
12         _4_sum_list = []
13         nums.sort()
14         if nums[-1] * 4 < target:
15             return []
16         for i in range(len(nums) - 3):
17             if nums[i] * 4 > target:
18                 break
19             if i == 0 or nums[i] != nums[i - 1]:
20                 ele = nums[i]
21                 target_3_sum = target - ele
22                 if nums[-1] * 3 < target_3_sum:
23                     continue
24                 for j in range(i + 1, len(nums) - 2):
25                     ele2 = nums[j]
26                     if ele2 * 3 > target_3_sum:
27                         break
28                     if j == i + 1 or ele2 != nums[j - 1]:
29                         target_2_sum = target_3_sum - ele2
30                         point_left = j + 1
31                         point_right = len(nums) - 1
32                         while point_left < point_right:
33                             if nums[point_left] + nums[point_right] > target_2_sum:
34                                 point_right -= 1
35                             elif nums[point_left] + nums[point_right] < target_2_sum:
36                                 point_left += 1
37                             else:
38                                 aaa = [ele, ele2, nums[point_left], nums[point_right]]
39                                 _4_sum_list.append(aaa)
40                                 point_left += 1
41                                 point_right -= 1
42                                 while point_left < point_right and nums[point_left] == nums[point_left - 1]:
43                                     point_left += 1
44                                 while point_left < point_right and nums[point_right] == nums[point_right + 1]:
45                                     point_right -= 1
46 
47         return _4_sum_list

445 两数相加

思路：把列表中元素变成整数加减，然后重新构建链表（头插法）

 1 # Definition for singly-linked list.
 2 # class ListNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution(object):
 8     def addTwoNumbers(self, l1, l2):
 9         """
10         :type l1: ListNode
11         :type l2: ListNode
12         :rtype: ListNode
13         """
14         res = " "
15         res1 = " "
16         while l1:
17             res += str(l1.val)
18             l1=l1.next
19         while l2:
20             res1+=str(l2.val)
21             l2=l2.next
22         res.lstrip()
23         res1.lstrip()
24         tem=int(res1)+int(res)
25         first_node=ListNode(tem%10)
26         tem=tem//10
27         while tem:
28             node=ListNode(tem % 10)
29             tem=tem/10
30             node.next=first_node
31             first_node=node    
32         return first_node

394两个数组交集

给定两个数组，编写一个函数来计算它们的交集。

set的交集（&）并集（|）

1 class Solution(object):
2     def intersection(self, nums1, nums2):
3         """
4         :type nums1: List[int]
5         :type nums2: List[int]
6         :rtype: List[int]
7         """
8         return set(nums1)&set(nums2)
9

167两数之和

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

 1 class Solution(object):
 2     def twoSum(self, numbers, target):
 3         """
 4         :type numbers: List[int]
 5         :type target: int
 6         :rtype: List[int]
 7         """
 8         for i in range(len(numbers)):
 9             if i==0:
10                 l,r=i,len(numbers)-1
11                 while l<r:
12                     tem=numbers[l]+numbers[r]
13                     if tem==target:
14                         return [l+1,r+1]
15                     elif tem<target:
16                         l+=1
17                     else:
18 
19                         r-=1
20

20.有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

思路：用栈

 1 class Solution(object):
 2     def isValid(self, s):
 3         """
 4         :type s: str
 5         :rtype: bool
 6         """
 7         res=[]
 8         for each in s:
 9             if each=="(" or each=="{" or each =="[":
10                 res.append(each)
11             if each==")" or each=="}" or each =="]":
12                 if len(res)==0:
13                     return False
14                 tem=res.pop()
15                 xx = ""
16                 if tem=="(":
17                     xx=")"
18                 if tem=="{":
19                     xx="}"
20                 if tem=="[":
21                     xx="]"
22                 if xx==each:
23                     continue
24                 else:
25                     return False
26         if len(res)==0:
27             return True
28         else:
29             return False
30                 
31                     
32             
33         
34

42 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

思路：

 1 class Solution(object):
 2     def trap(self, height):
 3         if not height: return 0
 4         n, res = len(height), 0
 5         left_max, right_max = [0] * n, [0] * n
 6 
 7         left_max[0] = height[0]
 8         for i in range(1, n):  # 从左向右扫描一遍，求出每个位置左边最高的边
 9             left_max[i] = max(height[i], left_max[i - 1])
10        
11         right_max[n - 1] = height[n - 1]
12         for i in range(n - 2, -1, -1):  # 从右向左扫描一遍，求出每个位置右边最高的边
13             right_max[i] = max(height[i], right_max[i + 1])
14         
15         for i in range(1, n - 1):  # 扫描每一个位置，用当前位置左右最短的边，作为长度，并减去当前位置的值，就是当前位置的容量
16             res += min(left_max[i], right_max[i]) - height[i]
17         return res

2两数相加

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

 1 # Definition for singly-linked list.
 2 # class ListNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution(object):
 8     def addTwoNumbers(self, l1, l2):
 9         """
10         :type l1: ListNode
11         :type l2: ListNode
12         :rtype: ListNode
13         """
14         res = " "
15         res1 = " "
16         while l1:
17             res += str(l1.val)
18             l1=l1.next
19         while l2:
20             res1+=str(l2.val)
21             l2=l2.next
22         res.lstrip()
23         res=res[::-1]
24         res1.lstrip()
25         res1=res1[::-1]
26         tem=int(res1)+int(res)
27         first_node=ListNode(tem%10)
28         first=first_node
29         tem=tem//10
30         while tem:
31             node=ListNode(tem % 10)
32             tem=tem/10
33             first_node.next=node
34             first_node=first_node.next
35         return first
36

5最长回文字符串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

动态规划：时间复杂度O(n**2)

 1 class Solution(object):
 2     def longestPalindrome(self, s):
 3         n = len(s)
 4         res= [[0]*n for x in range(n)]
 5         max_len=-1
 6         max_val=""
 7         for i in range(n):
 8             for j in range(i,-1,-1):
 9                 if s[i]==s[j] and(i-j<2 or res[i-1][j+1]):
10                     res[i][j]=1
11                 if res[i][j] and i-j+1>max_len:
12                     max_len=i-j+1
13                     max_val=s[j:i+1]
14         return max_val

214 最短回文

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

思路字符串翻转与源字符串比较

1 class Solution:
2     def shortestPalindrome(self, s: str) -> str:
3         if(len(s)==0):
4             return ""
5         s_reverse = s[::-1]
6         for i in range(len(s)):
7             if(s_reverse[i:len(s)] == s[0:len(s)-i]):
8                 break
9         return s_reverse[0:i]+s

3. 无重复字符的最长子串

 1 class Solution:
 2     def lengthOfLongestSubstring(self, s):
 3         """
 4         :type s: str
 5         :rtype: int
 6         """
 7         max_number = 0
 8         number = 0
 9         test = ''
10         for i in s:
11             if i not in test:
12                 test += i
13                 number += 1
14             else:
15                 if number >= max_number:
16                     max_number = number
17                 index = test.index(i)
18                 test = test[(index+1):] + i
19                 number = len(test)
20         if number > max_number:
21             max_number = number
22         return max_number

14. 最长公共前缀

思路：

 1 class Solution(object):
 2     def longestCommonPrefix(self, strs):
 3         """
 4         :type strs: List[str]
 5         :rtype: str
 6         """
 7         res=''
 8         if len(strs)==0:
 9             return res
10         lens=min([len(x) for x in strs])
11         for i in range(lens):
12             tem=strs[0][i]
13             for j in range(1,len(strs)):
14                 if strs[j][i]!=tem:
15                     return res
16             res+=tem
17         return res
18             
19         
20         
21

7.整数翻转

 1 class Solution(object):
 2     def reverse(self, x):
 3         
 4         flag=False
 5         if x < 0:
 6             flag = True
 7         temp = abs(x)
 8         
 9         temp = int(str(temp)[::-1])
10         if temp>2147483647:
11             return 0
12         if flag:
13             return -temp
14         else:
15             return temp
16

9回文数

 1 class Solution(object):
 2     def isPalindrome(self, x):
 3         """
 4         :type x: int
 5         :rtype: bool
 6         """
 7         s1=str(x)
 8         s2=s1[::-1]
 9         if s2==s1:
10             return True
11         else:
12             return False
13

11.最多盛水容器

给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

 1 class Solution(object):
 2     def maxArea(self, height):
 3         res=0
 4         l,r=0,len(height)-1
 5         while l < r:
 6             res = max(res, min(height[l],height[r])*(r-l))
 7             if height[l]<height[r]:
 8                 l += 1
 9             else:
10                 r-=1
11         return res
12

6.N字形变换

思路：真难

 1 class Solution(object):
 2     def convert(self, s, numRows):
 3         """
 4         :type s: str
 5         :type numRows: int
 6         :rtype: str
 7         """
 8         if numRows == 1:
 9             return s
10         zigzag = ['' for i in range(numRows)]  # 初始化zigzag为['','','']
11         row = 0                                # 当前的行数
12         step = 1                               # 步数：控制数据的输入
13         for c in s:
14             if row == 0:
15                 step = 1
16             if row == numRows - 1:
17                 step = -1
18             zigzag[row] += c
19             row += step
20         return ''.join(zigzag)

21. 合并两个有序链表

 1 # Definition for singly-linked list.
 2 # class ListNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution(object):
 8     def mergeTwoLists(self, l1, l2):
 9         """
10         :type l1: ListNode
11         :type l2: ListNode
12         :rtype: ListNode
13         """
14         
15         node=ListNode(None)
16         first=node
17         while l1 and l2:
18             if l1.val<=l2.val:
19                 node.next=l1
20                 l1=l1.next
21               
22             else:
23                 node.next=l2
24                 l2=l2.next
25             node=node.next
26         if l1:
27             node.next=l1
28         if l2:
29             node.next=l2
30         return first.next
31                 
32

23. 合并K个排序链表

 1 # Definition for singly-linked list.
 2 # class ListNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution(object):
 8     def mergeKLists(self, lists):
 9         """
10         :type lists: List[ListNode]
11         :rtype: ListNode
12         """
13         res=[]
14         for each in lists:
15             while each:
16                 res.append(each.val)
17                 each=each.next
18         res.sort()
19         first=ListNode(None)
20         nodes=first
21         for each in res:
22             node=ListNode(each)
23             first.next=node
24             first=first.next
25         return nodes.next
26

39组合总数

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

 1 class Solution(object):
 2     def combinationSum(self, candidates, target):
 3         """
 4         :type candidates: List[int]
 5         :type target: int
 6         :rtype: List[List[int]]
 7         """
 8         self.resList = []
 9         candidates = sorted(candidates)
10         self.dfs(candidates,[],target,0)
11         return self.resList
12     def dfs(self, candidates, sublist, target, last):
13         if target == 0:
14             self.resList.append(sublist[:])
15         if target< candidates[0]:
16             return 
17         for n in candidates:
18             if n > target:
19                 return
20             if n < last:
21                 continue
22             sublist.append(n)
23             self.dfs(candidates,sublist,target - n, n)
24             sublist.pop()
25

17. 电话号码的字母组合

思路一：递归 93 131

 1 class Solution(object):
 2    
 3     def letterCombinations(self, digits):
 4         """
 5         :type digits: str
 6         :rtype: List[str]
 7         """
 8         self.res=[]
 9          
10         self.data={'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
11        
12         if len(digits)==0:
13             return []
14         teem=""
15         self.f(digits,0,teem)
16         return self.res
17         
18     
19     def f(self,digits,index,ss):
20         if index==len(digits):
21             self.res.append(ss)
22             return 
23         chars= self.data[digits[index]]
24         for i in range(len(chars)):
25             self.f(digits,index+1,ss+chars[i])
26         return 
27             
28  
29         
30

93. 复原IP地址

思路：回溯法+剪枝

 1 class Solution(object):
 2     def restoreIpAddresses(self, s):
 3         """
 4         :type s: str
 5         :rtype: List[str]
 6         """
 7         res = []
 8         self.dfs(s, [], res)
 9         return res
10         
11     def dfs(self, s, path, res):
12         if len(s) > (4 - len(path)) * 3:
13             return
14         if not s and len(path) == 4:
15             res.append('.'.join(path))
16             return
17         for i in range(min(3, len(s))):
18             curr = s[:i+1]
19             if (curr[0] == '0' and len(curr) >= 2) or int(curr) > 255:
20                 continue
21             self.dfs(s[i+1:], path + [s[:i+1]], res)

131. 分割回文串

思路：回溯

 1 class Solution(object):
 2     def partition(self, s):
 3         self.isPalindrome = lambda s : s == s[::-1]
 4         res = []
 5         self.helper(s, res, [])
 6         return res
 7         
 8     def dfs(self, s, res, path):
 9         if not s:
10             res.append(path)
11             return
12         for i in range(1, len(s) + 1): #注意起始和结束位置
13             if self.isPalindrome(s[:i]):
14                 self.dfs(s[i:], res, path + [s[:i]])

46. 全排列

思路：回溯

 1 class Solution(object):
 2     def permute(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: List[List[int]]
 6         """
 7         visited = [0] * len(nums)
 8         res = []
 9         
10         def dfs(path):
11             if len(path) == len(nums):
12                 res.append(path)
13             else:
14                 for i in range(len(nums)):
15                     if not visited[i]:
16                         visited[i] = 1
17                         dfs(path + [nums[i]])
18                         visited[i] = 0
19         
20         dfs([])
21         return res

思路2:

1 from itertools import permutations
2 class Solution(object):
3     def permute(self, nums):
4         """
5         :type nums: List[int]
6         :rtype: List[List[int]]
7         """
8         return list(permutations(nums))

784. 字母大小写全排列

思路：回溯

 1 class Solution(object):
 2     def letterCasePermutation(self, S):
 3 
 4         self.res = []
 5         if len(S) == 0:
 6             return [ ]
 7         self.dfs(0, "",S)
 8         return self.res
 9 
10     def dfs(self,start, temp,S):
11         if start == len(S) or len(temp) == len(S):
12             self.res.append(temp)
13             return
14         # print start, temp
15         if S[start].isdigit():  
16             self.dfs(start + 1, temp + S[start],S)
17 
18         elif S[start].islower():  
19             self.dfs(start + 1, temp + S[start],S)
20             self.dfs(start + 1, temp + S[start].upper(),S)
21 
22         elif S[start].isupper():
23             self.dfs(start + 1, temp + S[start],S)
24             self.dfs(start + 1, temp + S[start].lower(),S)
25         return
26

77. 组合

思路：回溯法+DFS

 1 class Solution(object):
 2     def combine(self, n, k):
 3         self.res = []
 4         data=list(range(1,n+1))
 5         ss=[]
 6         self.dfs(data,ss,k)
 7         return self.res
 8     def dfs(self,s,ss,k):
 9         if k == 0:
10             self.res.append(ss)
11             return
12         for i in range(len(s)):
13             self.dfs(s[i+1:],ss+[s[i]],k-1)
14         return

78子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

1 class Solution(object):
2     def subsets(self, nums):
3         res = [[]]
4         for num in nums:
5             for temp in res[:]:
6                 x = temp[:]
7                 x.append(num)
8                 res.append(x)
9         return res

216组合数3

思路：回溯+DFS

 1 class Solution(object):
 2     def combinationSum3(self, k, n):
 3         self.res=[]
 4         self.dfs([],k,n)
 5         return self.res
 6     def dfs(self,ss,k,n):
 7         if k == 0 and sum(ss) == n:
 8             self.res.append(ss)
 9             return
10         start = ss[-1] if ss else 0
11         for i in range(start+1,10):
12             if sum(ss)+i>n:
13                 continue
14             self.dfs(ss+[i],k-1,n)
15         return

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。

思路：回溯+DFS

 1 class Solution(object):
 2     def combinationSum2(self, candidates, target):
 3         self.res = []
 4         candidates.sort()
 5         self.dfs(candidates,target,0,[])
 6         return self.res
 7     def dfs(self,data,target,index,ss):
 8         if target == 0 and ss not in self.res:
 9             self.res.append(ss)
10         for i in range(index, len(data)):
11             if data[i] > target:
12                 return
13             self.dfs(data, target - data[i], i + 1, ss + [data[i]])

94 二叉树中序遍历

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution(object):
 9     def inorderTraversal(self, root):
10         """
11         :type root: TreeNode
12         :rtype: List[int]
13         """
14         res=[]
15         if root==None:
16             return []
17         if root.left:
18             res+=self.inorderTraversal(root.left)
19         res.append(root.val)
20         if root.right:
21             res+=self.inorderTraversal(root.right)
22         return res
23         
24         
25

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

 1 class Solution(object):
 2     def maxSubArray(self, nums):
 3         max_val=-float("inf")
 4         maxendinghere=-float("inf")
 5         for i in range(len(nums)):
 6             max_val=max(max_val+nums[i],nums[i])
 7             maxendinghere = max(max_val, maxendinghere)
 8         return maxendinghere
 9         
10

62. 不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

思路：动态规划构建dp表

 1 class Solution(object):
 2     def uniquePaths(self, m, n):
 3         data=[[0]*n for x in range(m)]
 4         for i in range(m):
 5             
 6             for j in range(n):
 7                 if i==0 or j==0:
 8                     data[i][j]=1
 9                 else:
10                     data[i][j]=data[i-1][j]+data[i][j-1]
11         return data[m-1][n-1]
12                     
13         
14         
15

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

思路;动态规划

 1 class Solution(object):
 2     def uniquePathsWithObstacles(self, obstacleGrid):
 3         m = len(obstacleGrid)
 4         n = len(obstacleGrid[0])
 5         data = [[0]*n for x in range(m)]
 6         if obstacleGrid[0][0] == 1:
 7             data[0][0] = 0
 8         else:
 9             data[0][0] = 1
10 
11         for i in range(1,m):
12             if obstacleGrid[i][0]==1:
13                 data[i][0]=0
14             else:
15                 data[i][0] = data[i-1][0]
16 
17         for i in range(1,n):
18             if obstacleGrid[0][i]== 1:
19                 continue
20             else:
21                 data[0][i]=data[0][i-1]
22 
23         for i in range(1,m):
24             for j in range(1,n):
25                 if obstacleGrid[i][j]==1:
26                     data[i][j]=0
27                 else:
28                     data[i][j]=data[i-1][j]+data[i][j-1]
29         return data[m-1][n-1]

64. 最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

思路：动态规划

 1 class Solution(object):
 2     def minPathSum(self, grid):
 3         m = len(grid)
 4         n = len(grid[0])
 5         data = [[0] * n for x in range(m)]
 6         data[0][0] = grid[0][0]
 7         for i in range(1, m):
 8             data[i][0] = data[i - 1][0] + grid[i][0]
 9         for j in range(1, n):
10             data[0][j] = data[0][j - 1] + grid[0][j]
11 
12         for i in range(1, m):
13             for j in range(1, n):
14                 data[i][j] = min(data[i - 1][j], data[i][j - 1])+grid[i][j]
15         return data[m-1][n-1]

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

思路：递归时间复杂度不行还是动态规划

 1 class Solution(object):
 2     def climbStairs(self, n):
 3         a,b,tem=1,2,0
 4         if n<=2:
 5             return n
 6         
 7         for i in range(3,n+1):
 8             tem=a+b
 9             a=b
10             b=tem
11         return tem
12 
13

79. 单词搜索

思路：回溯法

 1 class Solution(object):
 2     def exist(self, board, word):
 3         if not word:
 4             return True
 5         if not board:
 6             return False
 7 
 8         self.m = len(board)
 9         self.n = len(board[0])
10         self.indexs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
11 
12         self.visit = [[0]*self.n for _ in range(self.m)]
13         for i in range(self.m):
14             for j in range(self.n):
15                 if self.search(board, word, 0, i, j):
16                     return True
17         return False
18 
19     def search(self,board, word, cur, row, col):
20         if word[cur] == board[row][col] :
21             if cur == len(word)-1:
22                 return True
23             self.visit[row][col] = 1
24             for i in range(4):
25                 new_x = row + self.indexs[i][0]
26                 new_y = col + self.indexs[i][1]
27                 if self.inArea(new_x, new_y) and not self.visit[new_x][new_y]:
28                     if self.search(board, word, cur+1, new_x, new_y):
29                         return True
30             self.visit[row][col] = 0
31         return False
32 
33     def inArea(self, x, y):
34         return x >= 0 and x < self.m and y >= 0 and y < self.n

200. 岛屿的个数

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

 1 class Solution(object):
 2     def numIslands(self, grid):
 3         self.m = len(grid)
 4         if len(grid)==0:
 5             return 0
 6         self.n = len(grid[0])
 7         self.res = 0
 8         self.indexs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
 9         self.visit = [[0] * self.n for _ in range(self.m)]
10         for i in range(self.m):
11             for j in range(self.n):
12 
13                 if grid[i][j] == "1" and not self.visit[i][j]:
14                     self.res += 1
15                     self.f(grid, i,  j)
16         return self.res
17 
18     def inArea(self, x, y):
19         return x >= 0 and x < self.m and y >= 0 and y < self.n
20 
21     def f(self,grid,start_x,start_y):
22         self.visit[start_x][start_y]=1
23         for i in range(4):
24             new_x = start_x + self.indexs[i][0]
25             new_y = start_y + self.indexs[i][1]
26             if self.inArea(new_x,new_y) and not self.visit[new_x][new_y] and grid[new_x][new_y]=="1":
27                 self.f(grid,new_x,new_y)
28         return

130. 被围绕的区域

思路：递归+floodfill

 1 class Solution(object):
 2     def solve(self, board):
 3         if not len(board) or not len(board[0]):
 4             return
 5         self.m = len(board)
 6         self.n = len(board[0])
 7 
 8         self.indexs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
 9         self.visit = [[0] * self.n for _ in range(self.m)]
10         for i in range(self.m):
11             if i == 0 or i == self.m-1:
12                 for j in range(self.n):
13                     self.f(board, i, j)
14             else:
15                 self.f(board, i, 0)
16                 self.f(board, i, self.n-1)
17 
18         for i in range(self.m):
19             for j in range(self.n):
20                 board[i][j] = "O" if board[i][j] == "*" else "X"
21         return board
22     def f(self, board, start_x, start_y):
23         if start_x < 0 or start_y < 0 or start_x >= self.m or start_y >= self.n or \
24                         board[start_x][start_y] == 'X' or board[start_x][start_y] == '*':
25             return
26         board[start_x][start_y] = "*"
27         for i in range(4):
28             self.f(board, start_x + self.indexs[i][0], start_y + self.indexs[i][1])

417. 太平洋大西洋水流问题

思路：从四个边界入手采用floodfill进行填充

 1 class Solution(object):
 2     def pacificAtlantic(self, matrix):
 3         if not matrix or not matrix[0]:
 4             return []
 5         self.m, self.n = len(matrix), len(matrix[0])
 6         self.indexs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
 7         p_visited = [[0] * self.n for _ in range(self.m)]
 8         a_visited = [[0] * self.n for _ in range(self.m)]
 9         for i in range(self.m):
10             self.dfs(p_visited, matrix,  i, 0)
11             self.dfs(a_visited, matrix, i, self.n - 1)
12         for j in range(self.n):
13             self.dfs(p_visited, matrix,  0, j)
14             self.dfs(a_visited, matrix, self.m - 1, j)
15         res = []
16         for i in range(self.m):
17             for j in range(self.n):
18                 if p_visited[i][j] and a_visited[i][j]:
19                     res.append([i, j])
20         return res
21 
22     def dfs(self, visited, matrix, i, j):
23         visited[i][j] = 1
24         for each in self.indexs:
25             x, y = i + each[0], j + each[1]
26             if x < 0 or x >= self.m or y < 0 or y >= self.n or visited[x][y] or matrix[x][y] < matrix[i][j]:
27                 continue
28             self.dfs(visited, matrix, x, y)

51. N皇后

思路：DFS+回溯保证列两个对角线上只有一个元素即可

 1 class Solution(object):
 2     def solveNQueens(self, n):
 3         self.res=[]
 4         self.f([],[],[],n)
 5         return [["."*i+"Q"+"."*(n-i-1) for i in each ] for each in self.res]
 6     def f(self,queens,diff,sum,n):
 7         p=len(queens)
 8         if p==n:
 9             self.res.append(queens)
10             return 
11         for q in range(n):
12             if q not in queens and q+p not in sum and p-q not in diff:
13                 self.f(queens+[q],diff+[p-q],sum+[p+q],n)
14             
15         
16

52 N皇后II

思路：同上

 1 class Solution(object):
 2     def totalNQueens(self, n):
 3         self.res = []
 4         self.f([], [], [], n)
 5         return len(self.res)
 6     def f(self, queens, diff, sum, n):
 7         p = len(queens)
 8         if p == n:
 9             self.res.append(queens)
10             return
11         for q in range(n):
12             if q not in queens and q + p not in sum and p - q not in diff:
13                 self.f(queens + [q], diff + [p - q], sum+[p + q], n)
14       
15

37. 解数独

思路：DFS+回溯检查行列以及3*3的小方格

 1 class Solution:
 2     def solveSudoku(self, board):
 3         self.board = board
 4         self.solve()
 5 
 6     def solve(self):  # 主递归函数
 7         row, col = self.findUnassigned()  # 获取一个未被分配的方格
 8         if row == -1 and col == -1:  # 没有找到，说明已经填好
 9             return True
10         for num in ['1', '2', '3', '4', '5', '6', '7', '8', '9']:
11             if self.isSafe(row, col, num):  # 循环填入数字，并判断是否满足要求
12                 self.board[row][col] = num
13                 if self.solve():  # 递归进入下一个方格
14                     return True
15                 self.board[row][col] = '.'  # 后续不满足，那么现在要回复当前环境，并进行下一个数字试探
16         return False
17 
18     def findUnassigned(self):  # 依次查找未被分配的方格
19         for row in range(9):
20             for col in range(9):
21                 if self.board[row][col] == '.':
22                     return row, col
23         return -1, -1
24 
25     def isSafe(self, row, col, ch):  # 判断是否当前方格填入的数字是否满足要求
26         boxrow = row - row % 3  # 确定3x3小宫格的开始坐标，就是3x3小宫格第一个方格索引
27         boxcol = col - col % 3
28         if self.checkrow(row, ch) and self.checkcol(col, ch) and self.checksquare(boxrow, boxcol, ch):
29             return True
30         return False
31 
32     def checkrow(self, row, ch):  # 检查一行是否符合条件
33         for col in range(9):
34             if self.board[row][col] == ch:
35                 return False
36         return True
37 
38     def checkcol(self, col, ch):  # 检查一列是否符合条件
39         for row in range(9):
40             if self.board[row][col] == ch:
41                 return False
42         return True
43 
44     def checksquare(self, row, col, ch):  # 检查3x3小宫格是否符合条件
45         for r in range(row, row + 3):
46             for c in range(col, col + 3):
47                 if self.board[r][c] == ch:
48                     return False
49         return True
50 
51 
52 if __name__ == '__main__':
53     board = [
54         ['5', '3', '.', '.', '7', '.', '.', '.', '.'],
55         ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
56         ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
57         ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
58         ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
59         ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
60         ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
61         ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
62         ['.', '.', '.', '.', '8', '.', '.', '7', '9']]
63 
64     solu = Solution()
65     solu.solveSudoku(board)
66 
67     for v in board:
68         print(v)

343整数分解

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。

思路1：递归（超时）

1 class Solution(object):
2     def integerBreak(self, n):
3         if n == 2 or n == 1:
4             return 1
5         res = -1
6         for i in range(1, n):
7             res = max(res, i*(n-i), i*self.integerBreak(n-i))
8         return res
9

思路2：记忆化搜索（超时）

 1 class Solution(object):
 2     def integerBreak(self, n):
 3         memo=[-1 for x in range(n+1)]
 4         if n == 1:
 5             return 1
 6         if memo[n]!= -1:
 7             return memo[n]
 8         res = -1
 9         for i in range(1,n-1):
10             res = max(res, i*(n-i), i*self.integerBreak(n-i))
11         memo[n]=res
12         return res

思路3：动态规划

1 class Solution(object):
2     def integerBreak(self, n):
3         memo=[-1 for x in range(n+1)]
4         memo[1]=1
5         for i in range(2,n+1):
6             for j in range(1,i):
7                 memo[i]=max(memo[i],j*(i-j),j*self.integerBreak(i-j))
8         return memo[n]

思路：上面不通过竟然因为“memo=[-1 for x in range(n+1)]”

1 class Solution(object):
2     def integerBreak(self, n):
3         dp = [-1]*(n+1)
4         dp[1] = 1
5         for i in range(2, n+1):
6             for j in range(1, i):
7                 dp[i] = max(dp[i], j*(i-j), j*dp[i-j])
8         return dp[n]

思路5：dp[i] = dp[i - 3] * 3，当n >= 7时成立

1 class Solution(object):
2     def integerBreak(self, n):
3         dp = [0, 0, 1, 2, 4, 6, 9]
4         for i in range(7, n + 1):
5             dp.append(dp[i - 3] * 3)
6         return dp[n]

198. 打家劫舍

思路：回溯（超时）

 1 class Solution(object):
 2     def rob(self, nums):
 3         return self.tryrob(nums,0)
 4     def tryrob(self,data,index):
 5         if index>=len(data):
 6             return 0
 7         res=0
 8         for i in range(index,len(data)):
 9             res=max(res,data[i]+self.tryrob(data,i+2))
10         return res

思路：记忆话搜索（通过）

 1 class Solution(object):
 2     def rob(self, nums):
 3         self.memo=[-1]*(len(nums)+1)
 4         return self.tryrob(nums,0)
 5     def tryrob(self,nums,index):
 6         if index>=len(nums):
 7             return 0
 8         if self.memo[index]!=-1:
 9             return self.memo[index]
10         res = 0
11         for i in range(index,len(nums)):
12             res=max(res,nums[i]+self.tryrob(nums,i+2))
13         self.memo[index]=res
14         return res

思路：动态规划（通过）公式：dp[i] = max(dp[i-2]+nums[i], dp[i-1])

 1 class Solution(object):
 2     def rob(self, nums):
 3         if len(nums)==0:
 4             return 0
 5         self.memo = [-1]*len(nums)
 6         self.memo[-1] = nums[-1]
 7         for i in range(len(nums)-2,-1,-1):
 8             for j in range(i,len(nums)):
 9                 self.memo[i] = max(self.memo[i],
10                                    nums[j]+(self.memo[j+2] if j+2 < len(nums) else 0))
11         return self.memo[0]

思路：动态规划（不太懂）公式：dp[i] = max(dp[i-2]+nums[i], dp[i-1])

 1 class Solution(object):
 2     def rob(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: int
 6         """
 7         last = 0 
 8         now = 0
 9         for i in nums: 
10             #这是一个动态规划问题
11             last, now = now, max(last + i, now)
12         return now
13

213 打击结社2

思路：针对于环形问题可以把数据分成【0：n-1】和【1:n】即可

 1 class Solution(object):
 2     def rob(self, nums):
 3         if len(nums)==1:
 4             return nums[0]
 5         if len(nums)==2:
 6             return max(nums)
 7         n=len(nums)
 8         return max(self.f(nums[0:n-1]),self.f(nums[1:n]))
 9 
10     def f(self,nums):
11         if len(nums)==1:
12             return nums[0]
13         if len(nums)==2:
14             return max(nums)
15         n=len(nums)
16         dp=[0]*n
17         dp[0]=nums[0]
18         dp[1]=max(nums[0:2])
19         for i in range(2,n):
20             dp[i]=max(dp[i-1],dp[i-2]+nums[i])
21         return dp[-1]

300. 最长上升子序列

思路：动态规划

 1 class Solution(object):
 2     def lengthOfLIS(self, nums):
 3         if len(nums)==0:
 4             return 0
 5         dp=[1]*len(nums)
 6         for i in range(1,len(nums)):
 7             for j in range(i):
 8                 if nums[j]<nums[i]:
 9                     dp[i]=max(dp[i],dp[j]+1)
10         return max(dp)

139 单词拆分

动态规划

 1 class Solution(object):
 2     def wordBreak(self, s, wordDict):
 3         """
 4         :type s: str
 5         :type wordDict: List[str]
 6         :rtype: bool
 7         """
 8         if len(s)==1:
 9             return False
10         n=len(s)
11         dp=[0]*(n+1)
12         dp[0]=1
13         for i in range(1,n+1):
14             for j in range(i):
15                 if s[j:i] in wordDict and dp[j]:
16                     dp[i]=1

91解码方式

思路:动态规划

 1 class Solution(object):
 2     def numDecodings(self, s):
 3         if not s or s[0] == '0':
 4             return 0
 5         dp = [1, 1]
 6         for i in range(1, len(s)):
 7             if s[i] == '0':
 8                 if (s[i-1] == '1' or s[i-1] == '2'): #匹配“10”和“20”
 9                     dp.append(dp[-2])
10                 else:
11                     return 0
12             elif s[i-1] == '1' or (s[i-1] == '2' and s[i] <= '6'): #匹配“1x”和“2x"情况，当然得小于26;
13                 dp.append(dp[-1] + dp[-2]) 
14             else:
15                 dp.append(dp[-1])
16         return dp[-1]
17

152. 乘积最大子序列

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

 1 class Solution(object):
 2     def maxProduct(self, nums):
 3         if len(nums)==0:
 4             return 0
 5         if len(nums)==1:
 6             return nums[0]
 7         tem_max,tem_min=0,0
 8         res=nums[0]
 9         for each in nums:
10             temp=tem_max
11             tem_max=max(each ,each*tem_max,each*tem_min)
12             tem_min=min(each ,each*tem_min,each*temp)
13             res=max(res,tem_min,tem_max)
14         return res
15

110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution(object):
 9     def isBalanced(self, root):
10         """
11         :type root: TreeNode
12         :rtype: bool
13         """
14         if not root:
15             return True
16         rights=self.getdepth(root.right)
17         lefts=self.getdepth(root.left)
18         if abs(rights-lefts)>1:
19             return False
20         return self.isBalanced(root.left) and self.isBalanced(root.right) 
21     def getdepth(self,root):
22         if not root:
23             return 0
24         return max(self.getdepth(root.left),self.getdepth(root.right))+1
25

100. 相同的树

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution(object):
 9     def isSameTree(self, p, q):
10         """
11         :type p: TreeNode
12         :type q: TreeNode
13         :rtype: bool
14         """
15         if p==None and q==None:
16             return True
17         if p!=None and q!=None and q.val==p.val:
18             return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
19         else:
20             return False
21        
22         
23

101 对称二叉树

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution(object):
 9     def isSymmetric(self, root):
10         """
11         :type root: TreeNode
12         :rtype: bool
13         """
14         return self.isMirror(root,root)
15     def isMirror(self,t1,t2):
16         if not t1 and not t2:
17             return True
18         elif t1 != None and t2 != None:
19             if t1.val == t2.val:
20                 return self.isMirror(t1.right,t2.left) and self.isMirror(t1.left,t2.right)
21             else:   
22                 return False
23         else:
24             return False
25

111. 二叉树的最小深度

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution(object):
 9     def minDepth(self, root):
10         """
11         :type root: TreeNode
12         :rtype: int
13         """
14         if not root:
15             return 0
16         left=self.minDepth(root.left)
17         right=self.minDepth(root.right)
18         return 1+min(left,right) if (left and right) else 1+left+right

112. 路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution(object):
 9     def hasPathSum(self, root, sum):
10         """
11         :type root: TreeNode
12         :type sum: int
13         :rtype: bool
14         """
15         
16         if  not root :
17             return False
18         if root.left==None and root.right==None:
19             return sum-root.val==0
20         return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)

257. 二叉树的所有路径

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        res=[]  # 不能用self.res[]，因为每一个实例只有一个该属性。然而本题需要不断递归调用需要创建很多的res 
        if not root:
            return res
        if not root.left and not root.right:
            res.append(str(root.val))
            return res
        for each in self.binaryTreePaths(root.left):
            res.append(str(root.val)+"->"+each)
        for each in self.binaryTreePaths(root.right):
            res.append(str(root.val)+"->"+each)
        return res

129. 求根到叶子节点数字之和

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution(object):
 9     def sumNumbers(self, root):
10         """
11         :type root: TreeNode
12         :rtype: int
13         """
14         num=0
15         res=self.binaryTreePaths(root)
16         for each in res:
17             num+=int(each)
18         return num
19         
20     def binaryTreePaths(self, root):
21       
22         res=[]  
23         if not root:
24             return res
25         if not root.left and not root.right:
26             res.append(str(root.val))
27             return res
28         for each in self.binaryTreePaths(root.left):
29             res.append(str(root.val)+each)
30         for each in self.binaryTreePaths(root.right):
31             res.append(str(root.val)+each)
32         return res

113. 路径总和 II

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution(object):
 9     def pathSum(self, root, sum):
10         """
11         :type root: TreeNode
12         :type sum: int
13         :rtype: List[List[int]]
14         """
15         if not root:
16             return []
17         def dfs(root,sum,ans,temp):
18             if root==None:
19                 return []
20             temp.append(root.val)
21             if root.left==None and root.right==None and sum==root.val:
22                 ans.append(temp[:])
23             dfs(root.left,sum-root.val,ans,temp)
24             dfs(root.right,sum-root.val,ans,temp)
25             temp.pop()
26         ans=[]
27         temp=[]
28         dfs(root,sum,ans,temp)
29         return ans
30             
31             
32             
33             
34

437. 路径总和 III

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution(object):
 9     def pathSum(self, root, sum):
10         """
11         :type root: TreeNode
12         :type sum: int
13         :rtype: int
14         """
15         if not root:
16             return 0
17         res=self.findPath(root,sum)
18         res+=self.pathSum(root.left,sum)
19         res+=self.pathSum(root.right,sum)
20         return res
21     def findPath(self,root,sum):
22         if not root:
23             return 0
24         res=0
25         if root.val==sum:
26             res+=1
27         res+=self.findPath(root.left,sum-root.val)
28         res+=self.findPath(root.right,sum-root.val)
29         return res
30         
31

235. 二叉搜索树的最近公共祖先

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution(object):
 9     def lowestCommonAncestor(self, root, p, q):
10         """
11         :type root: TreeNode
12         :type p: TreeNode
13         :type q: TreeNode
14         :rtype: TreeNode
15         """
16         if not root:
17             return 
18         if p.val<root.val and q.val<root.val:
19             return self.lowestCommonAncestor(root.left,p,q)
20         if p.val>root.val and q.val>root.val:
21             return self.lowestCommonAncestor(root.right,p,q)
22         return root
23

98. 验证二叉搜索树

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution(object):
 9     def __init__(self):  
10         self.last=-float("inf")  # 放在内部每次都会生成
11     def isValidBST(self, root):
12         """
13         :type root: TreeNode
14         :rtype: bool
15         """
16         if not root:
17             return True
18         if self.isValidBST(root.left):
19             if root.val>self.last:
20                 self.last=root.val
21                 return self.isValidBST(root.right)
22         return False

45. 跳跃游戏 II

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums)==1:
            return 0
        reach=0
        step=0
        next_search=nums[0]
        for i in range(len(nums)):
            next_search=max(nums[i]+i,next_search)
            if next_search>=len(nums)-1:
                return step+1
            if reach==i:
                step+=1
                reach=next_search
        return step

347. 前K个高频元素

 1 class Solution(object):
 2     def topKFrequent(self, nums, k):
 3         """
 4         :type nums: List[int]
 5         :type k: int
 6         :rtype: List[int]
 7         """
 8         d = {}
 9         for val in nums:
10             if val not in d:
11                 d[val] = 0
12             else:
13                 d[val] += 1
14         return [x[0] for x  in  sorted(d.items(), reverse=True, key=lambda x: x[1])[:k]]
15 
16 
17

思路：

1 from collections import Counter
2 class Solution(object):
3     def topKFrequent(self, nums, k):
4         return [x[0] for x in Counter(nums).most_common(k)]

337. 打家劫舍 III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

思路：递归：python超时 java c++可以通过

 1 class Solution(object):
 2     def rob(self, root):
 3         """
 4         :type root: TreeNode
 5         :rtype: int
 6         """
 7         if not root:
 8             return 0
 9         res = 0
10         if root.left != None:
11             res = res + self.rob(root.left.left) + self.rob(root.left.right)
12         if root.right:
13             res=res+self.rob(root.right.left)+self.rob(root.right.right)
14         return max(root.val+res,self.rob(root.left)+self.rob(root.right))

思路2：动态规划

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution(object):
 9     def rob(self, root):
10         """
11         :type root: TreeNode
12         :rtype: int
13         """
14         res=self.f(root)
15         return max(res)
16     def f(self,root):
17         if not root:
18             return [0,0]
19         left=self.f(root.left)
20         right=self.f(root.right)
21         res=[0]*2
22 
23         res[0]=max(left[0],left[1])+max(right[0],right[1])
24         res[1]=root.val+left[0]+right[0]
25         return res

365. 水壶问题

 1 class Solution(object):
 2     def canMeasureWater(self, x, y, z):
 3         """
 4         :type x: int
 5         :type y: int
 6         :type z: int
 7         :rtype: bool
 8         """
 9         if z == 0:
10             return True
11         if x+y < z:
12             return False
13         if x>y:
14             x,y=y,x
15         if x == 0:
16             return y==z
17         while y%x != 0:
18             y,x = x,y%x
19         return z%x==0
20

583. 两个字符串的删除操作

 1 class Solution(object):
 2     def minDistance(self, word1, word2):
 3 
 4         dp = [[0] * (len(word2)+1) for x in range(len(word1)+1)]
 5         dp[0][0]=0
 6        
 7         for i in range(1,len(word1)+1):
 8             for j in range(1,len(word2)+1):
 9                 if word1[i-1]==word2[j-1]:
10                     dp[i][j]=dp[i-1][j-1]+1
11                 else:
12                     dp[i][j]=max(dp[i-1][j],dp[i][j-1])
13         return len(word2)+len(word1)-2*dp[-1][-1]

1011. 在 D 天内送达包裹的能力

思路：取列表中最大元素和平均D天运出去的均值的最大值作为出发点，进行遍历。运行时间有点慢

 1 class Solution(object):
 2     def shipWithinDays(self, weights, D):
 3         """
 4         :type weights: List[int]
 5         :type D: int
 6         :rtype: int
 7         """
 8         res=max(sum(weights)//D,max(weights))
 9         while True:
10             n=1
11             temp=0
12             for each in weights:
13                 if temp+each<=res:
14                     temp+=each
15                 else:
16                     temp=each
17                     n+=1
18                     if n>D:
19                         break
20             if n<=D:
21                 return res
22             else:
23                 res+=1
24         return res
25

1010. 总持续时间可被 60 整除的歌曲

思路：建立一个包含60个元素的字典，键代表歌曲播放时间对60取余数，值是出现的次数

class Solution(object):
    def numPairsDivisibleBy60(self, time):
        """
        :type time: List[int]
        :rtype: int
        """
        if len(time)<2:
            return 0
        c=dict(zip(range(60),[0]*60))
        for each in time:
            c[each%60]+=1
        ans=c[0]*(c[0]-1)/2+c[30]*(c[30]-1)/2
        for i in range(1,30):
            ans+=c[i]*c[60-i]
        return ans

c++代码

 1 class Solution {
 2 public:
 3     int numPairsDivisibleBy60(vector<int>& time) {
 4         int a[60]={0};
 5         for (int t:time){
 6             a[t%60]++;
 7         }
 8         int ans=a[0]*(a[0]-1)/2+a[30]*(a[30]-1)/2;
 9         for (int i=1;i<30;i++)
10             ans+=a[i]*a[60-i];
11         return ans;
12     }
13    
14 };

leedcode算法解题思路

思路：用栈

相关文章