大家好，欢迎来到IT知识分享网。
1.两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
思路1：暴力解题：固定一个数nums[i],然后让target减nums[i] 如果在数组中且下标不等于i则返回[i,nums.index(target-nums[i)].
时间复杂度：O(n2)， 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n) 的时间。因此时间复杂度为 O(n2)。
空间复杂度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 };
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/31103.html
