1.两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
思路1：暴力解题：固定一个数nums[i],然后让target减nums[i] 如果在数组中且下标不等于i则返回[i,nums.index(target-nums[i)].
时间复杂度：O(n^2)O(n2)， 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)O(n) 的时间。因此时间复杂度为 O(n^2)O(n2)。
空间复杂度O(1)
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
""" for i in range(len(nums)):
if (target-nums[i]) in nums and i!=nums.index(target-nums[i]):
return [i,nums.index(target-nums[i])]
思路2：借助python的字典(内部实现借助hash表) 把数组的下标放在字典的键，数组元素放在字典的值中 。时间复杂度O(n) 准确来说是O(2*n)
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
data = {}
for idx, val in enumerate(nums):
if val not in data:
data[val] = [idx]
else:
tem=data[val]
tem.append(idx)
data[val] = tem
for each in data:
if (target - each in data) :
if data[target - each] != data[each]:
return [data[target - each][0], data[each][0]]
if len(data[each])==2:
return data[each]
思路3：在创建字典的同时一边判断字典中是否存在这个元素，一边往字典中添加元素时间复杂度O(n) 比思路2 大约快20%
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
data={}
for i in range(len(nums)):
if target-nums[i] in data:
return [i,data[target-nums[i]]]
data[nums[i]]=i
371 两个整数之和
不使用运算符 + 和 - ，计算两整数 a 、b 之和。
思路1：xor异或运算不产生进位，&元算结束后左移一位
class Solution(object):
def getSum(self, a, b):
"""
:type a: int
:type b: int
:rtype: int
"""
while b != 0:
carry = a & b
a = (a ^ b) % 0x100000000
b = (carry << 1) % 0x100000000
return a if a <= 0x7FFFFFFF else a | (~0x100000000+1)
633 两个平方数之和
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。
思路：如果用指针指向一个数，用c-a**2 然后开方，如果为整数返回true 时间复杂度O(根号下n)
import math
class Solution(object):
def judgeSquareSum(self, c):
"""
:type c: int
:rtype: bool
"""
if c==0:
return True
for i in range(1,int(math.sqrt(c))+1):
tem=math.sqrt(c-i**2)
if tem.is_integer():
return True
else:
continue
return False
15 三数之和(双指针解法)
思路：每次固定一个变量i，然后使用两个指针指向数组的i+1，数组尾部，如果三个数相加等于0返回，同时让lr指针同时移动，如果s小于0，让r减去1,否则让l加1
时间复杂度O(n**2)
class Solution:
def threeSum(self, nums):
nums.sort()
res=[]
for i in range(len(nums)):
if i == 0 or nums[i]>nums[i-1]:
l = i+1
r = len(nums)-1
while l<r:
s=nums[i]+nums[l]+nums[r]
if s==0:
res.append([nums[i],nums[l],nums[r]])
l+=1
r-=1
while l<r and nums[l]==nums[l+1]:
l+=1
while l<r and nums[r]==nums[r+1]:
r-=1
elif s>0:
r-=1
else:
l+=1
return res
16 最接近的三数之和
思路：双指针法：固定一个变量i，然后分别移动l和r 时间复杂度O(n**2)
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.sort()
tem=1000000
res=0
for i in range(len(nums)):
if i==0 or nums[i]>nums[i-1]:
l=i+1
r=len(nums)-1
while l<r:
s = nums[i]+nums[l]+nums[r]
if abs(s-target) < tem:
tem = abs(s-target)
res=s
elif s<target:
l+=1
else:
r-=1
return res
18 四数之和
class Solution:
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
""" if not nums:
return [] _4_sum_list = []
nums.sort()
if nums[-1] * 4 < target:
return []
for i in range(len(nums) - 3):
if nums[i] * 4 > target:
break
if i == 0 or nums[i] != nums[i - 1]:
ele = nums[i]
target_3_sum = target - ele
if nums[-1] * 3 < target_3_sum:
continue
for j in range(i + 1, len(nums) - 2):
ele2 = nums[j]
if ele2 * 3 > target_3_sum:
break
if j == i + 1 or ele2 != nums[j - 1]:
target_2_sum = target_3_sum - ele2
point_left = j + 1
point_right = len(nums) - 1
while point_left < point_right:
if nums[point_left] + nums[point_right] > target_2_sum:
point_right -= 1
elif nums[point_left] + nums[point_right] < target_2_sum:
point_left += 1
else:
aaa = [ele, ele2, nums[point_left], nums[point_right]]
_4_sum_list.append(aaa)
point_left += 1
point_right -= 1
while point_left < point_right and nums[point_left] == nums[point_left - 1]:
point_left += 1
while point_left < point_right and nums[point_right] == nums[point_right + 1]:
point_right -= 1 return _4_sum_list
445 两数相加
思路：把列表中元素变成整数加减，然后重新构建链表（头插法）
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
res = " "
res1 = " "
while l1:
res += str(l1.val)
l1=l1.next
while l2:
res1+=str(l2.val)
l2=l2.next
res.lstrip()
res1.lstrip()
tem=int(res1)+int(res)
first_node=ListNode(tem%10)
tem=tem//10
while tem:
node=ListNode(tem % 10)
tem=tem/10
node.next=first_node
first_node=node
return first_node
394两个数组交集
给定两个数组，编写一个函数来计算它们的交集。
set的交集（&）并集（|）
class Solution(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
return set(nums1)&set(nums2)
167两数之和
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
for i in range(len(numbers)):
if i==0:
l,r=i,len(numbers)-1
while l<r:
tem=numbers[l]+numbers[r]
if tem==target:
return [l+1,r+1]
elif tem<target:
l+=1
else: r-=1
20.有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
思路：用栈
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
res=[]
for each in s:
if each=="(" or each=="{" or each =="[":
res.append(each)
if each==")" or each=="}" or each =="]":
if len(res)==0:
return False
tem=res.pop()
xx = ""
if tem=="(":
xx=")"
if tem=="{":
xx="}"
if tem=="[":
xx="]"
if xx==each:
continue
else:
return False
if len(res)==0:
return True
else:
return False
42 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
思路：
class Solution(object):
def trap(self, height):
if not height: return 0
n, res = len(height), 0
left_max, right_max = [0] * n, [0] * n left_max[0] = height[0]
for i in range(1, n): # 从左向右扫描一遍，求出每个位置左边最高的边
left_max[i] = max(height[i], left_max[i - 1]) right_max[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1): # 从右向左扫描一遍，求出每个位置右边最高的边
right_max[i] = max(height[i], right_max[i + 1]) for i in range(1, n - 1): # 扫描每一个位置，用当前位置左右最短的边，作为长度，并减去当前位置的值，就是当前位置的容量
res += min(left_max[i], right_max[i]) - height[i]
return res
2两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
res = " "
res1 = " "
while l1:
res += str(l1.val)
l1=l1.next
while l2:
res1+=str(l2.val)
l2=l2.next
res.lstrip()
res=res[::-1]
res1.lstrip()
res1=res1[::-1]
tem=int(res1)+int(res)
first_node=ListNode(tem%10)
first=first_node
tem=tem//10
while tem:
node=ListNode(tem % 10)
tem=tem/10
first_node.next=node
first_node=first_node.next
return first
5最长回文字符串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
动态规划：时间复杂度O(n**2)
class Solution(object):
def longestPalindrome(self, s):
n = len(s)
res= [[0]*n for x in range(n)]
max_len=-1
max_val=""
for i in range(n):
for j in range(i,-1,-1):
if s[i]==s[j] and(i-j<2 or res[i-1][j+1]):
res[i][j]=1
if res[i][j] and i-j+1>max_len:
max_len=i-j+1
max_val=s[j:i+1]
return max_val
214 最短回文
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
思路 字符串翻转与源字符串比较
class Solution:
def shortestPalindrome(self, s: str) -> str:
if(len(s)==0):
return ""
s_reverse = s[::-1]
for i in range(len(s)):
if(s_reverse[i:len(s)] == s[0:len(s)-i]):
break
return s_reverse[0:i]+s
3. 无重复字符的最长子串
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
max_number = 0
number = 0
test = ''
for i in s:
if i not in test:
test += i
number += 1
else:
if number >= max_number:
max_number = number
index = test.index(i)
test = test[(index+1):] + i
number = len(test)
if number > max_number:
max_number = number
return max_number
14. 最长公共前缀
思路：
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
res=''
if len(strs)==0:
return res
lens=min([len(x) for x in strs])
for i in range(lens):
tem=strs[0][i]
for j in range(1,len(strs)):
if strs[j][i]!=tem:
return res
res+=tem
return res
7.整数翻转
class Solution(object):
def reverse(self, x): flag=False
if x < 0:
flag = True
temp = abs(x) temp = int(str(temp)[::-1])
if temp>2147483647:
return 0
if flag:
return -temp
else:
return temp
9回文数
class Solution(object):
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
s1=str(x)
s2=s1[::-1]
if s2==s1:
return True
else:
return False
11.最多盛水容器
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
class Solution(object):
def maxArea(self, height):
res=0
l,r=0,len(height)-1
while l < r:
res = max(res, min(height[l],height[r])*(r-l))
if height[l]<height[r]:
l += 1
else:
r-=1
return res
6.N字形变换
思路：真难
class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
if numRows == 1:
return s
zigzag = ['' for i in range(numRows)] # 初始化zigzag为['','','']
row = 0 # 当前的行数
step = 1 # 步数：控制数据的输入
for c in s:
if row == 0:
step = 1
if row == numRows - 1:
step = -1
zigzag[row] += c
row += step
return ''.join(zigzag)
21. 合并两个有序链表
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
""" node=ListNode(None)
first=node
while l1 and l2:
if l1.val<=l2.val:
node.next=l1
l1=l1.next else:
node.next=l2
l2=l2.next
node=node.next
if l1:
node.next=l1
if l2:
node.next=l2
return first.next
23. 合并K个排序链表
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
res=[]
for each in lists:
while each:
res.append(each.val)
each=each.next
res.sort()
first=ListNode(None)
nodes=first
for each in res:
node=ListNode(each)
first.next=node
first=first.next
return nodes.next
39组合总数
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
self.resList = []
candidates = sorted(candidates)
self.dfs(candidates,[],target,)
return self.resList
def dfs(self, candidates, sublist, target, last):
if target == :
self.resList.append(sublist[:])
if target< candidates[]:
return
for n in candidates:
if n > target:
return
if n < last:
continue
sublist.append(n)
self.dfs(candidates,sublist,target - n, n)
sublist.pop()
17. 电话号码的字母组合
思路一：递归 93 131
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
self.res=[]
self.data={'':'abc','':'def','':'ghi','':'jkl','':'mno','':'pqrs','':'tuv','':'wxyz'}
if len(digits)==0:
return []
teem=""
self.f(digits,0,teem)
return self.res
def f(self,digits,index,ss):
if index==len(digits):
self.res.append(ss)
return
chars= self.data[digits[index]]
for i in range(len(chars)):
self.f(digits,index+1,ss+chars[i])
return
93. 复原IP地址
思路：回溯法+剪枝
class Solution(object):
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
res = []
self.dfs(s, [], res)
return res def dfs(self, s, path, res):
if len(s) > (4 - len(path)) * 3:
return
if not s and len(path) == 4:
res.append('.'.join(path))
return
for i in range(min(3, len(s))):
curr = s[:i+1]
if (curr[0] == '' and len(curr) >= 2) or int(curr) > 255:
continue
self.dfs(s[i+1:], path + [s[:i+1]], res)
131. 分割回文串
思路：回溯
class Solution(object):
def partition(self, s):
self.isPalindrome = lambda s : s == s[::-1]
res = []
self.helper(s, res, [])
return res def dfs(self, s, res, path):
if not s:
res.append(path)
return
for i in range(1, len(s) + 1): #注意起始和结束位置
if self.isPalindrome(s[:i]):
self.dfs(s[i:], res, path + [s[:i]])
46. 全排列
思路：回溯
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
visited = [0] * len(nums)
res = [] def dfs(path):
if len(path) == len(nums):
res.append(path)
else:
for i in range(len(nums)):
if not visited[i]:
visited[i] = 1
dfs(path + [nums[i]])
visited[i] = 0 dfs([])
return res
思路2:
from itertools import permutations
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
return list(permutations(nums))
784. 字母大小写全排列
思路：回溯
class Solution(object):
def letterCasePermutation(self, S): self.res = []
if len(S) == 0:
return [ ]
self.dfs(0, "",S)
return self.res def dfs(self,start, temp,S):
if start == len(S) or len(temp) == len(S):
self.res.append(temp)
return
# print start, temp
if S[start].isdigit():
self.dfs(start + 1, temp + S[start],S) elif S[start].islower():
self.dfs(start + 1, temp + S[start],S)
self.dfs(start + 1, temp + S[start].upper(),S) elif S[start].isupper():
self.dfs(start + 1, temp + S[start],S)
self.dfs(start + 1, temp + S[start].lower(),S)
return
77. 组合
思路：回溯法+DFS
class Solution(object):
def combine(self, n, k):
self.res = []
data=list(range(1,n+1))
ss=[]
self.dfs(data,ss,k)
return self.res
def dfs(self,s,ss,k):
if k == 0:
self.res.append(ss)
return
for i in range(len(s)):
self.dfs(s[i+1:],ss+[s[i]],k-1)
return
78子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
class Solution(object):
def subsets(self, nums):
res = [[]]
for num in nums:
for temp in res[:]:
x = temp[:]
x.append(num)
res.append(x)
return res
216组合数3
思路：回溯+DFS
class Solution(object):
def combinationSum3(self, k, n):
self.res=[]
self.dfs([],k,n)
return self.res
def dfs(self,ss,k,n):
if k == 0 and sum(ss) == n:
self.res.append(ss)
return
start = ss[-1] if ss else 0
for i in range(start+1,10):
if sum(ss)+i>n:
continue
self.dfs(ss+[i],k-1,n)
return
40. 组合总和 II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
思路：回溯+DFS
class Solution(object):
def combinationSum2(self, candidates, target):
self.res = []
candidates.sort()
self.dfs(candidates,target,0,[])
return self.res
def dfs(self,data,target,index,ss):
if target == 0 and ss not in self.res:
self.res.append(ss)
for i in range(index, len(data)):
if data[i] > target:
return
self.dfs(data, target - data[i], i + 1, ss + [data[i]])
94 二叉树中序遍历
# 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 inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res=[]
if root==None:
return []
if root.left:
res+=self.inorderTraversal(root.left)
res.append(root.val)
if root.right:
res+=self.inorderTraversal(root.right)
return res
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
class Solution(object):
def maxSubArray(self, nums):
max_val=-float("inf")
maxendinghere=-float("inf")
for i in range(len(nums)):
max_val=max(max_val+nums[i],nums[i])
maxendinghere = max(max_val, maxendinghere)
return maxendinghere
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
思路：动态规划 构建dp表
class Solution(object):
def uniquePaths(self, m, n):
data=[[]*n for x in range(m)]
for i in range(m): for j in range(n):
if i== or j==:
data[i][j]=
else:
data[i][j]=data[i-][j]+data[i][j-]
return data[m-][n-]
63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
思路;动态规划
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
m = len(obstacleGrid)
n = len(obstacleGrid[])
data = [[]*n for x in range(m)]
if obstacleGrid[][] == :
data[][] =
else:
data[][] = for i in range(,m):
if obstacleGrid[i][]==:
data[i][]=
else:
data[i][] = data[i-][] for i in range(,n):
if obstacleGrid[][i]== :
continue
else:
data[][i]=data[][i-] for i in range(,m):
for j in range(,n):
if obstacleGrid[i][j]==:
data[i][j]=
else:
data[i][j]=data[i-][j]+data[i][j-]
return data[m-][n-]
64. 最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
思路：动态规划
class Solution(object):
def minPathSum(self, grid):
m = len(grid)
n = len(grid[])
data = [[] * n for x in range(m)]
data[][] = grid[][]
for i in range(, m):
data[i][] = data[i - ][] + grid[i][]
for j in range(, n):
data[][j] = data[][j - ] + grid[][j] for i in range(, m):
for j in range(, n):
data[i][j] = min(data[i - ][j], data[i][j - ])+grid[i][j]
return data[m-][n-]
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
思路：递归时间复杂度不行 还是动态规划
class Solution(object):
def climbStairs(self, n):
a,b,tem=,,
if n<=:
return n for i in range(,n+):
tem=a+b
a=b
b=tem
return tem
79. 单词搜索
思路：回溯法
class Solution(object):
def exist(self, board, word):
if not word:
return True
if not board:
return False self.m = len(board)
self.n = len(board[])
self.indexs = [[-, ], [, ], [, ], [, -]] self.visit = [[]*self.n for _ in range(self.m)]
for i in range(self.m):
for j in range(self.n):
if self.search(board, word, , i, j):
return True
return False def search(self,board, word, cur, row, col):
if word[cur] == board[row][col] :
if cur == len(word)-:
return True
self.visit[row][col] =
for i in range():
new_x = row + self.indexs[i][]
new_y = col + self.indexs[i][]
if self.inArea(new_x, new_y) and not self.visit[new_x][new_y]:
if self.search(board, word, cur+, new_x, new_y):
return True
self.visit[row][col] =
return False def inArea(self, x, y):
return x >= and x < self.m and y >= and y < self.n
200. 岛屿的个数
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
class Solution(object):
def numIslands(self, grid):
self.m = len(grid)
if len(grid)==:
return
self.n = len(grid[])
self.res =
self.indexs = [[-, ], [, ], [, ], [, -]]
self.visit = [[] * self.n for _ in range(self.m)]
for i in range(self.m):
for j in range(self.n): if grid[i][j] == "" and not self.visit[i][j]:
self.res +=
self.f(grid, i, j)
return self.res def inArea(self, x, y):
return x >= and x < self.m and y >= and y < self.n def f(self,grid,start_x,start_y):
self.visit[start_x][start_y]=
for i in range():
new_x = start_x + self.indexs[i][]
new_y = start_y + self.indexs[i][]
if self.inArea(new_x,new_y) and not self.visit[new_x][new_y] and grid[new_x][new_y]=="":
self.f(grid,new_x,new_y)
return
130. 被围绕的区域
思路：递归+floodfill
class Solution(object):
def solve(self, board):
if not len(board) or not len(board[]):
return
self.m = len(board)
self.n = len(board[]) self.indexs = [[-, ], [, ], [, ], [, -]]
self.visit = [[] * self.n for _ in range(self.m)]
for i in range(self.m):
if i == or i == self.m-:
for j in range(self.n):
self.f(board, i, j)
else:
self.f(board, i, )
self.f(board, i, self.n-) for i in range(self.m):
for j in range(self.n):
board[i][j] = "O" if board[i][j] == "*" else "X"
return board
def f(self, board, start_x, start_y):
if start_x < or start_y < or start_x >= self.m or start_y >= self.n or \
board[start_x][start_y] == 'X' or board[start_x][start_y] == '*':
return
board[start_x][start_y] = "*"
for i in range():
self.f(board, start_x + self.indexs[i][], start_y + self.indexs[i][])
417. 太平洋大西洋水流问题
思路：从四个边界入手采用floodfill进行填充
class Solution(object):
def pacificAtlantic(self, matrix):
if not matrix or not matrix[]:
return []
self.m, self.n = len(matrix), len(matrix[])
self.indexs = [[-, ], [, ], [, ], [, -]]
p_visited = [[] * self.n for _ in range(self.m)]
a_visited = [[] * self.n for _ in range(self.m)]
for i in range(self.m):
self.dfs(p_visited, matrix, i, )
self.dfs(a_visited, matrix, i, self.n - )
for j in range(self.n):
self.dfs(p_visited, matrix, , j)
self.dfs(a_visited, matrix, self.m - , j)
res = []
for i in range(self.m):
for j in range(self.n):
if p_visited[i][j] and a_visited[i][j]:
res.append([i, j])
return res def dfs(self, visited, matrix, i, j):
visited[i][j] =
for each in self.indexs:
x, y = i + each[], j + each[]
if x < or x >= self.m or y < or y >= self.n or visited[x][y] or matrix[x][y] < matrix[i][j]:
continue
self.dfs(visited, matrix, x, y)
51. N皇后
思路：DFS+回溯 保证列 两个对角线上只有一个元素即可
class Solution(object):
def solveNQueens(self, n):
self.res=[]
self.f([],[],[],n)
return [["."*i+"Q"+"."*(n-i-1) for i in each ] for each in self.res]
def f(self,queens,diff,sum,n):
p=len(queens)
if p==n:
self.res.append(queens)
return
for q in range(n):
if q not in queens and q+p not in sum and p-q not in diff:
self.f(queens+[q],diff+[p-q],sum+[p+q],n)
52 N皇后II
思路：同上
class Solution(object):
def totalNQueens(self, n):
self.res = []
self.f([], [], [], n)
return len(self.res)
def f(self, queens, diff, sum, n):
p = len(queens)
if p == n:
self.res.append(queens)
return
for q in range(n):
if q not in queens and q + p not in sum and p - q not in diff:
self.f(queens + [q], diff + [p - q], sum+[p + q], n)
37. 解数独
思路：DFS+回溯 检查行列以及3*3的小方格
class Solution:
def solveSudoku(self, board):
self.board = board
self.solve() def solve(self): # 主递归函数
row, col = self.findUnassigned() # 获取一个未被分配的方格
if row == -1 and col == -1: # 没有找到，说明已经填好
return True
for num in ['', '', '', '', '', '', '', '', '']:
if self.isSafe(row, col, num): # 循环填入数字，并判断是否满足要求
self.board[row][col] = num
if self.solve(): # 递归进入下一个方格
return True
self.board[row][col] = '.' # 后续不满足，那么现在要回复当前环境，并进行下一个数字试探
return False def findUnassigned(self): # 依次查找未被分配的方格
for row in range(9):
for col in range(9):
if self.board[row][col] == '.':
return row, col
return -1, -1 def isSafe(self, row, col, ch): # 判断是否当前方格填入的数字是否满足要求
boxrow = row - row % 3 # 确定3x3小宫格的开始坐标，就是3x3小宫格第一个方格索引
boxcol = col - col % 3
if self.checkrow(row, ch) and self.checkcol(col, ch) and self.checksquare(boxrow, boxcol, ch):
return True
return False def checkrow(self, row, ch): # 检查一行是否符合条件
for col in range(9):
if self.board[row][col] == ch:
return False
return True def checkcol(self, col, ch): # 检查一列是否符合条件
for row in range(9):
if self.board[row][col] == ch:
return False
return True def checksquare(self, row, col, ch): # 检查3x3小宫格是否符合条件
for r in range(row, row + 3):
for c in range(col, col + 3):
if self.board[r][c] == ch:
return False
return True if __name__ == '__main__':
board = [
['', '', '.', '.', '', '.', '.', '.', '.'],
['', '.', '.', '', '', '', '.', '.', '.'],
['.', '', '', '.', '.', '.', '.', '', '.'],
['', '.', '.', '.', '', '.', '.', '.', ''],
['', '.', '.', '', '.', '', '.', '.', ''],
['', '.', '.', '.', '', '.', '.', '.', ''],
['.', '', '.', '.', '.', '.', '', '', '.'],
['.', '.', '.', '', '', '', '.', '.', ''],
['.', '.', '.', '.', '', '.', '.', '', '']] solu = Solution()
solu.solveSudoku(board) for v in board:
print(v)
343整数分解
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
思路1：递归（超时）
class Solution(object):
def integerBreak(self, n):
if n == 2 or n == 1:
return 1
res = -1
for i in range(1, n):
res = max(res, i*(n-i), i*self.integerBreak(n-i))
return res
思路2：记忆化搜索（超时）
class Solution(object):
def integerBreak(self, n):
memo=[-1 for x in range(n+1)]
if n == 1:
return 1
if memo[n]!= -1:
return memo[n]
res = -1
for i in range(1,n-1):
res = max(res, i*(n-i), i*self.integerBreak(n-i))
memo[n]=res
return res
思路3：动态规划
class Solution(object):
def integerBreak(self, n):
memo=[-1 for x in range(n+1)]
memo[1]=1
for i in range(2,n+1):
for j in range(1,i):
memo[i]=max(memo[i],j*(i-j),j*self.integerBreak(i-j))
return memo[n]
思路：上面不通过竟然因为“memo=[-1 for x in range(n+1)]”
class Solution(object):
def integerBreak(self, n):
dp = [-1]*(n+1)
dp[1] = 1
for i in range(2, n+1):
for j in range(1, i):
dp[i] = max(dp[i], j*(i-j), j*dp[i-j])
return dp[n]
思路5：dp[i] = dp[i - 3] * 3，当n >= 7时成立
class Solution(object):
def integerBreak(self, n):
dp = [0, 0, 1, 2, 4, 6, 9]
for i in range(7, n + 1):
dp.append(dp[i - 3] * 3)
return dp[n]
198. 打家劫舍
思路：回溯（超时）
class Solution(object):
def rob(self, nums):
return self.tryrob(nums,0)
def tryrob(self,data,index):
if index>=len(data):
return 0
res=0
for i in range(index,len(data)):
res=max(res,data[i]+self.tryrob(data,i+2))
return res
思路：记忆话搜索（通过）
class Solution(object):
def rob(self, nums):
self.memo=[-1]*(len(nums)+1)
return self.tryrob(nums,0)
def tryrob(self,nums,index):
if index>=len(nums):
return 0
if self.memo[index]!=-1:
return self.memo[index]
res = 0
for i in range(index,len(nums)):
res=max(res,nums[i]+self.tryrob(nums,i+2))
self.memo[index]=res
return res
思路：动态规划（通过）公式：dp[i] = max(dp[i-2]+nums[i], dp[i-1])
class Solution(object):
def rob(self, nums):
if len(nums)==0:
return 0
self.memo = [-1]*len(nums)
self.memo[-1] = nums[-1]
for i in range(len(nums)-2,-1,-1):
for j in range(i,len(nums)):
self.memo[i] = max(self.memo[i],
nums[j]+(self.memo[j+2] if j+2 < len(nums) else 0))
return self.memo[0]
思路：动态规划 （不太懂）公式：dp[i] = max(dp[i-2]+nums[i], dp[i-1])
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
last = 0
now = 0
for i in nums:
#这是一个动态规划问题
last, now = now, max(last + i, now)
return now
213 打击结社2
思路：针对于环形问题可以把数据分成【0：n-1】和【1:n】即可
class Solution(object):
def rob(self, nums):
if len(nums)==1:
return nums[0]
if len(nums)==2:
return max(nums)
n=len(nums)
return max(self.f(nums[0:n-1]),self.f(nums[1:n])) def f(self,nums):
if len(nums)==1:
return nums[0]
if len(nums)==2:
return max(nums)
n=len(nums)
dp=[0]*n
dp[0]=nums[0]
dp[1]=max(nums[0:2])
for i in range(2,n):
dp[i]=max(dp[i-1],dp[i-2]+nums[i])
return dp[-1]
300. 最长上升子序列
思路：动态规划
class Solution(object):
def lengthOfLIS(self, nums):
if len(nums)==0:
return 0
dp=[1]*len(nums)
for i in range(1,len(nums)):
for j in range(i):
if nums[j]<nums[i]:
dp[i]=max(dp[i],dp[j]+1)
return max(dp)
139 单词拆分
动态规划
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
if len(s)==1:
return False
n=len(s)
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
for j in range(i):
if s[j:i] in wordDict and dp[j]:
dp[i]=1
91解码方式
思路:动态规划
class Solution(object):
def numDecodings(self, s):
if not s or s[0] == '':
return 0
dp = [1, 1]
for i in range(1, len(s)):
if s[i] == '':
if (s[i-1] == '' or s[i-1] == ''): #匹配“10”和“20”
dp.append(dp[-2])
else:
return 0
elif s[i-1] == '' or (s[i-1] == '' and s[i] <= ''): #匹配“1x”和“2x"情况，当然得小于26;
dp.append(dp[-1] + dp[-2])
else:
dp.append(dp[-1])
return dp[-1]
152. 乘积最大子序列
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
class Solution(object):
def maxProduct(self, nums):
if len(nums)==0:
return 0
if len(nums)==1:
return nums[0]
tem_max,tem_min=0,0
res=nums[0]
for each in nums:
temp=tem_max
tem_max=max(each ,each*tem_max,each*tem_min)
tem_min=min(each ,each*tem_min,each*temp)
res=max(res,tem_min,tem_max)
return res
110. 平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
# 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 isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
rights=self.getdepth(root.right)
lefts=self.getdepth(root.left)
if abs(rights-lefts)>1:
return False
return self.isBalanced(root.left) and self.isBalanced(root.right)
def getdepth(self,root):
if not root:
return 0
return max(self.getdepth(root.left),self.getdepth(root.right))+1
100. 相同的树
# 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 isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if p==None and q==None:
return True
if p!=None and q!=None and q.val==p.val:
return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
else:
return False
101 对称二叉树
# 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 isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.isMirror(root,root)
def isMirror(self,t1,t2):
if not t1 and not t2:
return True
elif t1 != None and t2 != None:
if t1.val == t2.val:
return self.isMirror(t1.right,t2.left) and self.isMirror(t1.left,t2.right)
else:
return False
else:
return False
111. 二叉树的最小深度
# 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 minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
left=self.minDepth(root.left)
right=self.minDepth(root.right)
return 1+min(left,right) if (left and right) else 1+left+right
112. 路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
# 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 hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
""" if not root :
return False
if root.left==None and root.right==None:
return sum-root.val==0
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. 求根到叶子节点数字之和
# 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 sumNumbers(self, root):
"""
:type root: TreeNode
:rtype: int
"""
num=0
res=self.binaryTreePaths(root)
for each in res:
num+=int(each)
return num def binaryTreePaths(self, root): 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
113. 路径总和 II
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
# 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 pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
if not root:
return []
def dfs(root,sum,ans,temp):
if root==None:
return []
temp.append(root.val)
if root.left==None and root.right==None and sum==root.val:
ans.append(temp[:])
dfs(root.left,sum-root.val,ans,temp)
dfs(root.right,sum-root.val,ans,temp)
temp.pop()
ans=[]
temp=[]
dfs(root,sum,ans,temp)
return ans
437. 路径总和 III
# 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 pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
if not root:
return 0
res=self.findPath(root,sum)
res+=self.pathSum(root.left,sum)
res+=self.pathSum(root.right,sum)
return res
def findPath(self,root,sum):
if not root:
return 0
res=0
if root.val==sum:
res+=1
res+=self.findPath(root.left,sum-root.val)
res+=self.findPath(root.right,sum-root.val)
return res
235. 二叉搜索树的最近公共祖先
# 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 lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if not root:
return
if p.val<root.val and q.val<root.val:
return self.lowestCommonAncestor(root.left,p,q)
if p.val>root.val and q.val>root.val:
return self.lowestCommonAncestor(root.right,p,q)
return root
98. 验证二叉搜索树
# 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 __init__(self):
self.last=-float("inf") # 放在内部每次都会生成
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
if self.isValidBST(root.left):
if root.val>self.last:
self.last=root.val
return self.isValidBST(root.right)
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个高频元素
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
d = {}
for val in nums:
if val not in d:
d[val] =
else:
d[val] +=
return [x[] for x in sorted(d.items(), reverse=True, key=lambda x: x[])[:k]]
思路：
from collections import Counter
class Solution(object):
def topKFrequent(self, nums, k):
return [x[] for x in Counter(nums).most_common(k)]
337. 打家劫舍 III
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
思路：递归：python超时 java c++可以通过
class Solution(object):
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
res = 0
if root.left != None:
res = res + self.rob(root.left.left) + self.rob(root.left.right)
if root.right:
res=res+self.rob(root.right.left)+self.rob(root.right.right)
return max(root.val+res,self.rob(root.left)+self.rob(root.right))
思路2：动态规划
# 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 rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
res=self.f(root)
return max(res)
def f(self,root):
if not root:
return [0,0]
left=self.f(root.left)
right=self.f(root.right)
res=[0]*2 res[0]=max(left[0],left[1])+max(right[0],right[1])
res[1]=root.val+left[0]+right[0]
return res
365. 水壶问题
class Solution(object):
def canMeasureWater(self, x, y, z):
"""
:type x: int
:type y: int
:type z: int
:rtype: bool
"""
if z == 0:
return True
if x+y < z:
return False
if x>y:
x,y=y,x
if x == 0:
return y==z
while y%x != 0:
y,x = x,y%x
return z%x==0
583. 两个字符串的删除操作
class Solution(object):
def minDistance(self, word1, word2): dp = [[0] * (len(word2)+1) for x in range(len(word1)+1)]
dp[0][0]=0 for i in range(1,len(word1)+1):
for j in range(1,len(word2)+1):
if word1[i-1]==word2[j-1]:
dp[i][j]=dp[i-1][j-1]+1
else:
dp[i][j]=max(dp[i-1][j],dp[i][j-1])
return len(word2)+len(word1)-2*dp[-1][-1]
1011. 在 D 天内送达包裹的能力
思路：取列表中最大元素和平均D天运出去的均值的最大值作为出发点，进行遍历。运行时间有点慢
class Solution(object):
def shipWithinDays(self, weights, D):
"""
:type weights: List[int]
:type D: int
:rtype: int
"""
res=max(sum(weights)//D,max(weights))
while True:
n=
temp=
for each in weights:
if temp+each<=res:
temp+=each
else:
temp=each
n+=
if n>D:
break
if n<=D:
return res
else:
res+=
return res
1010. 总持续时间可被 60 整除的歌曲
思路：建立一个包含60个元素的字典，键代表歌曲播放时间对60取余数，值是出现的次数
class Solution(object):
def numPairsDivisibleBy60(self, time):
"""
:type time: List[int]
:rtype: int
"""
if len(time)<:
return
c=dict(zip(range(),[]*))
for each in time:
c[each%]+=
ans=c[]*(c[]-)/+c[]*(c[]-)/
for i in range(,):
ans+=c[i]*c[-i]
return ans
c++代码
class Solution {
public:
int numPairsDivisibleBy60(vector<int>& time) {
int a[]={};
for (int t:time){
a[t%]++;
}
int ans=a[]*(a[]-)/+a[]*(a[]-)/;
for (int i=;i<;i++)
ans+=a[i]*a[-i];
return ans;
}
};