2021春招冲刺攻略

2021春招冲刺攻略

【概述】

56.合并区间

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:ans = list()intervals.sort(key=lambda x:x[0]) # 按照区间的下限排列之后，就能保证有重叠的区间一定是相邻的。因为题目中没有说是只有连续的区间重叠for interval in intervals:if not ans or ans[-1][1] < interval[0]: # 因为已经按照区间下限排列了，因此只需要判断上限是否大于后者下限。ans.append(interval)else:ans[-1][1] = max(ans[-1][1], interval[1]) #有可能出现[1,4][2,3],即后者包含于前者的情况，不应改变前者的上限return ans

1248.统计优美子数组

class Solution:def numberOfSubarrays(self, nums: List[int], k: int) -> int:odd = [-1]ans = 0for i in range(len(nums)):if nums[i]%2==1:odd.append(i)odd.append(len(nums))for i in range(1, len(odd)-k):ans += (odd[i] - odd[i-1])*(odd[i+k]-odd[i+k-1])return ans        

Ⅰ.数组与字符串

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

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:# 哈希集合，记录不重复的字符。occ = set()n = len(s)# 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动rk, ans = -1, 0for i in range(n): # 左指针iif i != 0: # i如果是0，说明现在occ里面还没有东西不用删除。# 左指针向右移动一格，移除左边第一个字符，假设左边第一个是被重复的字符ve(s[i - 1]) # ve(a)删除set中的a元素while rk + 1 < n and s[rk + 1] not in occ: # 当右指针还没有到尾部，并且下一个元素不在occ里面（不重复）occ.add(s[rk + 1]) # set.add() == list.append()rk += 1 # 不断地移动右指针# 第 i 到 rk 个字符是一个极长的无重复字符子串ans = max(ans, rk - i + 1) # 记录当前最大无重复字符串大小return ans

4.寻找两个正序数组中的中位数

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:nums = nums1+nums2list.sort(nums)n = len(nums)if n % 2 == 1:return nums[int((n-1)/2)]else:return (nums[int(n/2)]+nums[int(n/2-1)])/2

7. 三数之和

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums.sort()print(nums)ans = []n = len(nums)if not nums or n <3:return []for i in range(n):left = i+1right = n-1while left < right and right < n:if nums[left]+nums[right]+nums[i] == 0:if [nums[i], nums[left], nums[right]] not in ans:ans.append([nums[i], nums[left], nums[right]])left += 1elif nums[left]+nums[right]+nums[i] < 0:left += 1else:right -= 1return ans

238. 除自身以外数组的乘积

        ans=[0 for _ in range(len(nums))]ans[0] = 1R = 1for i in range(1, len(nums)):ans[i] = ans[i-1] * nums[i-1] # 前缀之积，就是前n个元素的积for i in range(len(nums)-1, -1, -1):ans[i] = ans[i] * R #前缀×后缀（不包括当前的）R = R * nums[i] #后缀之积，就是后n个元素的积return ans 

415.字符串相加

7.1做过。呜呜呜又不太记得了

class Solution:def addStrings(self, num1: str, num2: str) -> str:i, j, carry = len(num1)-1, len(num2)-1, 0ans = ''while i>= 0 or j >= 0 or carry > 0:if i >=0:carry += ord(num1[i]) - ord("0")if j >=0:carry += ord(num2[j]) - ord("0")ans += str(carry%10)carry = carry//10i -= 1j -= 1return ans[::-1]

Ⅱ.哈希表

974. 和可被 K 整除的子数组

如果两个数的差能被K整除，就说明这两个数 mod K得到的结果相同（余数），
只要找有多少对 mod k 相同的数就可以得到结果。

class Solution:def subarraysDivByK(self, nums: List[int], k: int) -> int:res=[0 for _ in range(len(nums)+1)]ans=[0 for _ in range(k)]res[0]=0for i in range(len(nums)):res[i+1] = res[i] + nums[i] # 求前缀和，其中第一位是0，最后一位是nums所有元素的和for term in res:ans[term % k] += 1 # term%k代表前缀中各元素➗k之后的余数，余数为0就在ans[0]记1，余数为1就在ans[1]记1，这样就可以得到前缀和中➗k的余数相同的有几个return sum(x*(x-1)//2 for x in ans) # 最终的结果是找到两个前缀和➗k的余数相同的组合有多少个 # x*(x-1)//2 其实是C（x，2），从x中取出2两个有多少种组合方式

146. LRU 缓存机制

class LRUCache:def __init__(self, capacity: int):d = OrderedDict()self.capacity = capacitydef get(self, key: int) -> int:if key d:tmp = d.pop(d[key] = tmpreturn tmpelse:return -1def put(self, key: int, value: int) -> None:if key d.pop(key)else:if self.capacity:self.capacity -= 1else:a = d.popitem(last=False) # last = False 删除最前面的一个，就是题意删除最旧第一个d[key] = valuereturn

执行：
["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]

record的内容，以及超容量时删除的元素：
put: OrderedDict([(1, 1)])
put: OrderedDict([(1, 1), (2, 2)])
get: OrderedDict([(2, 2), (1, 1)])
OrderedDict([(2, 2), (1, 1)])
(2, 2)
put: OrderedDict([(1, 1), (3, 3)])
OrderedDict([(1, 1), (3, 3)])
(1, 1)
put: OrderedDict([(3, 3), (4, 4)])
get: OrderedDict([(4, 4), (3, 3)])
get: OrderedDict([(3, 3), (4, 4)])

560. 和为 K 的子数组

class Solution:def subarraySum(self, nums: List[int], k: int) -> int:d = {} # 字典d中放着：键（前缀和）：值（该前缀和出现次数）ans = 0acc = 0for num in nums:acc += numif acc ==k : # 如果等于，代表到目前为止的子数组和满足条件ans += 1 # 结果加1if acc-k in d:# 如果存在，代表从前缀和为acc-k到当前位置之间的子数组满足条件ans += d[acc-k] # 结果加上起始位置出现的次数if acc in d:d[acc] += 1 else:d[acc] = 1return ans

Ⅲ.并查集

200. 岛屿数量

class Solution:def numIslands(self, grid: List[List[str]]) -> int:m, n = len(grid), len(grid[0])def dfs(grid, x, y):grid[x][y] = '0' # 记得先将当前位置1-->0for x0, y0 in [[x-1,y], [x+1,y], [x,y-1], [x,y+1]]: # 搜索上下左右四个位置是否有1，都换成0if 0 <= x0 < m and 0 <= y0 < n and grid[x0][y0] == '1':grid[x0][y0] == '0'dfs(grid, x0, y0) # 递归深度搜索 returncount = 0        for x in range(m):for y in range(n):if grid[x][y] == '1': # 因为相连的海岛都被置为1了，所以只要搜索到其他的1就可以算一个新的海岛count += 1dfs(grid, x, y)return count

990. 等式方程的可满足性

相当于将等式两边的字母赋一个编号，如果不等式两边的字母同属一个编号就是错误的。

class Solution:class unionfind:  # 并查集def __init__(self):self.parent = list(range(26)) # 26个英文字母对应的下标def find(self, index):if index == self.parent[index]:return index # 表示没有与其他字母连接，自己仅代表自己return self.find(self.parent[index]) # 有和其他字母连接，所以要返回连接的字母的序号def union(self, index1, index2):self.parent[self.find(index1)] = self.find(index2) # 将index2的下标赋给index1下标的位置，也就是index2是该联合组的编号def equationsPossible(self, equations: List[str]) -> bool:uf = Solution.unionfind()for e in equations:if e[1] == '=':index1 = ord(e[0]) - ord("a") # 字母下标，intindex2 = ord(e[3]) - ord("a")uf.union(index1, index2)for e in equations:if e[1] != '=':index1 = ord(e[0]) - ord("a")index2 = ord(e[3]) - ord("a")if uf.find(index1) == uf.find(index2): #如果两个字母的连接集相同，则falsereturn Falsereturn True

Ⅳ.动态规划

5. 最长回文子串

奇数长度回文子串：aba
偶数长度回文子串：abba
以每一个元素（奇数长度）或者相邻两个元素（偶数长度）为中心向两边扩散，找可能的回文子串，将最长的保留下来。

class Solution:def longestPalindrome(self, s: str) -> str:res = ''for i in range(len(s)):odd = self.find(s, i, i)  even = self.find(s, i, i+1)if  len(even) > len(res):res = evenelif len(odd) > len(res):res = oddreturn resdef find(self, s, i, j):while 0 <= i and j <len(s) and s[i] == s[j]:i -= 1j += 1return s[i+1:j]

53.最大子序和

也是写过的题，我都又忘了呜呜呜
思路是类似于算前缀和，更新到原数组中，不同点是，如果前一个元素小于0就不加到当前元素中，这样如果前缀和为整数就会一直保留，如果是负数，就‘丢弃’，最大的和会存在最大子序的最后一位，输出nums中最大的值就行了。

class Solution:def maxSubArray(self, nums: List[int]) -> int:for i in range(1, len(nums)):if nums[i-1] > 0:nums[i] += nums[i-1]return max(nums)

42. 接雨水

先找出左右的最大边界，然后计算当前位置能装雨水的多少：有点像木桶原理，最小的木板决定了能装的水的多少。
和官方题解的差别在于，不需要用数组储存所有位置的左右的最大值，浪费空间，因为当前能装多少水只和当前位置左右最大值有关系。

class Solution:def trap(self, height: List[int]) -> int:left_max = 0 right_max = 0 ans = 0for i in range(len(height)):left_max = max(height[:i+1]) # 左边最大值right_max = max(height[i:]) # 右边最大值ans = ans + min(left_max, right_max) - height[i]  # 当前位置能接雨水的大小取决于，最短的边界和当前的高度。return ans

1014. 最佳观光组合

class Solution:def maxScoreSightseeingPair(self, values: List[int]) -> int:ans = 0maxval = 0for i in range(len(values)):ans = max(ans, maxval+values[i]-i)maxval = max(maxval, values[i]+i)return ans

121. 买卖股票的最佳时机

也是之前写的也不太记得了呜呜呜

class Solution:def maxProfit(self, prices: List[int]) -> int:ans = 0left_min = int(1e9)for price in prices:ans = max(ans, price-left_min)left_min = min(left_min, price)return ans

139. 单词拆分

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:dp = [False]*(len(s)+1)dp[0] = Truefor i in range(len(s)):for j in range(i+1, len(s)+1):if dp[i] and s[i:j] in wordDict:dp[j] = Truereturn dp[-1]

输入：
"leetcode"
["leet","code"]
print dp：
[True, False, False, False, True, False, False, False, True]

70.爬楼梯

这个也是之前做过的，我记得哈哈哈！！！

class Solution:def climbStairs(self, n: int) -> int:if n < 3:return ndp = [0 for _ in range(n+1) ]dp[1] = 1dp[2] =2for i in range(3, n+1):dp[i] =dp[i-1] +dp[i-2]print(dp)return dp[-1]

Ⅴ.查找类问题

199. 二叉树的右视图

class Solution:def rightSideView(self, root: TreeNode) -> List[int]:def BFS(node): # 广度优先查找if not node:return []queue = deque([])res = []queue.append(node) # 从根开始搜索while queue: n = len(queue)for _ in range(n): # 搜索每一个节点下一层的左右节点node = queue.popleft() # 队列，先进先出，总是左节点先进，右节点在最后面r = node.val if node.left:queue.append(node.left)if node.right:queue.append(node.right) # 一定要先左后右，只有这样才能让最右边的节点存入queue最后一个res.append(r) # 退出for循环的时候，r代表上一层的最右一个节点的值return resreturn BFS(root) 

46. 全排列

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:return list(ritertools.pemutations(nums)) # 迭代器函数

回溯法
思路是，每次从nums中取出一个数字存到res中，将剩下的数字拿去backtrace（重复拿出一个数字到res中），当全部数字被取出放到res之后，就代表一种排列可能的结果出现，存入ans，因为是函数嵌套，因此此时返回，就会回到上一层，即nums中剩下两个数字，这时取i=1的数字，之后会生成一个新的排列可能结果，存入ans，以此类推会继续返回nums剩下3个数字，这时取第二个…

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:ans = []def backtrace(nums, res):if not nums:ans.append(res)returnfor i in range(len(nums)):backtrace(nums[:i]+nums[i+1:], res+[nums[i]]) # nums[:i]+nums[i+1:]代表除了nums[i]之外的数字# nums[i]是整数，res是list，所以需要将整数放到list里面再加，因此是res+[nums[i]]return ansreturn backtrace(nums, [])

33. 搜索旋转排序数组

二分法查找一般只能用在有序数组上，但是此题，是一部分有序一部分可能无序，因此要多一步判断，left到mid之间是不是有序的，如果有序（下图左边）才能用nums[left] <= target < nums[mid]作为判断条件，如果是无序，意味着mid到right之间是有序的（下图右边），此时只能用nums[mid] < target <= nums[right]作为判断查询条件。

class Solution:def search(self, nums: List[int], target: int) -> int:if not nums:return -1left, right = 0, len(nums)-1while left <= right:mid = (right+left)//2if target == nums[mid]:return midif nums[left] <= nums[mid]: # 代表mid左边是有序的if nums[left] <= target < nums[mid]: # target在左边，二分法查找right = mid-1else: # target不在左边，将范围缩小到[mid+1, right]left = mid + 1else: # 左边无序代表mid在分割线右边，右边是有序的if nums[mid] < target <= nums[right]: # target在右边，二分法查找left = mid + 1else: # target不在右边，将范围缩小到[right, mid-1]right = mid -1return -1

79. 单词搜索

class Solution:def exist(self, board: List[List[str]], word: str) -> bool:m = len(board)n = len(board[0])if m == 0:return Falsemark = [[0 for _ in range(n)]for _ in range(m)] #创建一个和board相同大小m行n列的mark，用来标记那些字母用过了for i in range(m):for j in range(n): #扫描整个board，找第一个字母if board[i][j]==word[0]: #找到第一个字母mark[i][j]=1 #用过的字母标记一下if self.backtrace(i, j, mark, board, word[1:]): # 找到剩下的字母return Trueelse: #剩下的字母没有找到，回溯mark[i][j]=0return Falsedef backtrace(self, i, j, mark, board, word):if len(word) == 0: # 一定要加，如果word空了，代表所有的字母都找到了，就返回了return Truefor i0, j0 in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]: # 在下标为[i,j]的字母的上下左右搜索下一个字母if 0 <= i0 < len(board) and 0 <= j0 < len(board[0]) and board[i0][j0] == word[0]: # 如果下标没有超出搜索范围并且，找到了下一个字母if mark[i0][j0]: #如果符合条件的字母是曾经用过的，则不算找到，继续在别的地方找continueelse:mark[i0][j0]=1 #符合条件，标记一下用过了if self.backtrace(i0, j0, mark, board, word[1:]):return True #剩下的字母都找到就返回trueelse: # 剩下字母没有找到就将当前字母也置为0，表示找的不对，退回上一位重找mark[i0][j0]=0return False

297. 二叉树的序列化与反序列化

class Codec:def serialize(self, root):"""Encodes a tree to a single string.:type root: TreeNode:rtype: str"""if not root:return 'None'return str(root.val) + ',' + str(self.serialize(root.right)) +','+ str(self.serialize(root.left))def deserialize(self, data):"""Decodes your encoded data to tree.:type data: str:rtype: TreeNode"""def dfs(datalist):val = datalist.pop(0)if val == 'None':return Noneroot = TreeNode(int(val))root.right = dfs(datalist)root.left = dfs(datalist)return rootdatalist = data.split(',')return dfs(datalist)

1300. 转变数组后最接近目标值的数组和

class Solution:def findBestValue(self, arr: List[int], target: int) -> int:cur_sum = sum(arr)if cur_sum <= target:return max(arr)val = target//len(arr)cur_sum, last = 0, 0while cur_sum < target:last_sum  = cur_sumcur_sum = 0for i in range(len(arr)):if arr[i]<val:cur_sum += arr[i]else:cur_sum += valval += 1return val-2 if abs(last_sum-target) <= abs(cur_sum-target) else val-1

Ⅵ.排序

56. 合并区间

见概述第2题

215. 数组中的第 K 个最大元素

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:# nums.sort(reverse=True) 用封装好的函数倒叙排序# return nums[k-1] n = len(nums)for i in range(0,k): # 冒泡排序法，因为1次冒泡排序得到的是最大的数字在尾部，因此我只需要第1-k个最大的元素按顺序就行for j in range(n-i-1):if nums[j] > nums[j+1]:nums[j], nums[j+1] = nums[j+1], nums[j]return nums[-k]

347. 前 K 个高频元素

class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:import heapq # 小顶堆dict = {}for item in nums:if item in dict:dict[item] += 1else:dict[item] = 1q = []for key, f in dict.items():heappush(q,(f, key)) #一定要按照(f, key)的顺序存，否则就无法按照f的大小弹出if len(q) > k:heappop(q) # 弹出f最小的那一对(f,key)ans = [0]*kfor i in range(k):ans[i] = heappop(q)[1]  # 弹出f最小的那一对(f,key)，并把第二位的元素key赋给ans[i]return ans

Ⅶ.链表

25. K 个一组翻转链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#          = next
class Solution:def reverseKGroup(self, head: ListNode, k: int) -> ListNode:dummy = ListNode( = headpre = dummy # 每组链表的头部之前tail = dummy # 每组链表的尾部while 1:count = k #不可以省略，这个地方意味着每轮都要给count重新赋值while count and tail: #将tail移到尾部count -= 1tail = if not tail: break #如果链表剩下部分不足k个，就会让指向空head =  #head指针会随着cur节点变道该组反转后链表的尾部 != tail: # 还没有到尾部cur =  # 先将需要移动的节点取出  =  #将该节点的前面pre和后面相联 =  # 将该节点与尾部下一个节点相联 = cur # 尾部-->该节点pre = head # head所在的位置是一个被反转到尾部的节点，所以其下一个节点是新的未翻转的链表的开始tail = 

206.反转链表

class Solution:def reverseList(self, head: ListNode) -> ListNode:if not head or :return headstack = []p = headwhile p:stack.append(p.val)p = p.nextnewhead = headwhile stack:head.val = stack.pop()head = turn newhead

21.合并两个有序链表

class Solution:def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:dummy = ListNode(0)p = dummywhile l1 and l2:if l1.val < l2. = l1l1 = l1.nextelse: p.next = l2l2 = l2.nextp = p.nextif not  = l2if not  = 

Ⅷ.递归

124.二叉树中的最大路径和

类似求二叉树的最大直径

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def maxPathSum(self, root: TreeNode) -> int:self.maxval= float("-inf") # 将maxval初始化为最小的浮点数def maxvalpath(node):if not node:return 0 left = max(maxvalpath(node.left), 0) # 大于零才用right = max(maxvalpath(node.right), 0)self.maxval = max(self.maxval, node.val+left+right) # 代表不往上走，选择本节点加左右return node.val+max(left, right) # 代表只选择一个左/右路径往上走（返回就代表跳回到上一层函数，就是往上走）maxvalpath(root)return self.maxval

22.括号生成

class Solution:def generateParenthesis(self, n: int) -> List[str]:ans = []def backtrack(s, left, right):if len(s) == 2*n:return ans.append(''.join(s))if left<n: #如果左括号还没到目标数量s.append('(')backtrack(s, left+1, right) s.pop() # 回溯if right<left:s.append(')')backtrack(s, left, right+1)s.pop() # 回溯backtrack([], 0, 0) return ans

394. 字符串解码

class Solution:def decodeString(self, s: str) -> str:def dfs(s, i):res = ''multi = 0while i<len(s):if '0'<=s[i]<='9': # 如果是数字就转为int类型存着multi = multi*10+int(s[i]) # multi*10是因为可能是100[a]elif s[i] == '[': # 如果是[ 进入新一层递归，会找到[...]之间的字母i, tmp = dfs(s, i+1) # 返回对应的下标和[...]之间的字母res = res + multi*tmp # 将[...]之间的的字母×倍数加到结果中multi = 0 #用后要把乘数置为0，为下一次做好准备elif s[i]==']': # 标志着[...]之间的字母已经记录完了，可以返回该层递归return i, res else:res += s[i] # 按顺序记录每一个字母i += 1 # 下标一直向后移动return resreturn dfs(s, 0) 

236.二叉树的最近公共祖先

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':def dfs(node, target, path):if not node:returnif node == target:path.append(node)return nodeval=dfs(node.left, target, path)if val:path.append(node)return nodeval=dfs(node.right, target, path)if val:path.append(node)return nodep_path = []q_path = []dfs(root, p, p_path)dfs(root, q, q_path)for i in p_path:if i in q_path:return ireturn -1

栈与队列

23. 合并 K 个升序链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#          = next
class Solution:def mergeKLists(self, lists: List[ListNode]) -> ListNode:if not lists: # 考虑[]和[[]]两种特殊情况return None # 记得要返回None而不是[]，因为类型不一样if len(lists)==1: # 考虑只有一个链表的情况，直接返回不用考虑合并return lists[0]dummy = ListNode(0)p = dummyl1 = lists[0] p.next = l1 # 先将第一个链表合并到最终的结果上for i in range(1, len(lists)):l2 = lists[i] # 之后每次取一个链表去合并while l1 and l2: # 以下就是合并两个升序链表的过程if l1.val < l2.val: # l1其实代表的是总链表的头部，l2是每次从lists里面取出来的一个链表p.next = l1l1 = l1.nextelse: p.next = l2l2 = l2.nextp = p.nextif not  = l2if not  = l1 # 以上就是合并两个升序链表的过程p = dummy # 取下一个链表来合并之前，先将指针放回到总链表的头部之前l1 = p.next # 将l1指向总链表第一个节点

20. 有效的括号

这个题是做过的，21天前，我都不记得了呜呜呜，看一遍笔记再写也是报错好几次，回去改了几次才通过。

class Solution(object):def isValid(self, s):""":type s: str:rtype: bool"""mapping = {")":"(", "]":"[", "}":"{"} # 存在的元素：映射后的结果stack = []for i, char in enumerate(s):print(i, char)if char not in mapping: # 确定是左括号先来，mapping中只有右括号stack.append(char)else:if not stack or stack[-1] != mapping[char]: # 1.第一个是右括号，错# 2.是第二个右括号，判断和上一个stack里的左括号是不是一对return Falsea = stack.pop() # 出现了一个对应的右括号，可以消去了print(a)return len(stack) ==0