要去网易实习了，思来想去觉得还是不能给咱老赵丢人，就想着再提升提升自己的工程能力，翻了好几本书都看不进去，还是刷题来的实在，正好最近入坑了VSCode，刷刷Leetcode也是方便的很。复习一下相关的知识点，题目就不放了，大家有兴趣自己去看。
HashTable的使用
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:hashdict = dict()for index1,i in enumerate(nums):if target-i in hashdict:return [hashdict[target-i],index1]hashdict[i] = index1双指针的使用
class Solution:def maxArea(self, height: List[int]) -> int:# maxx = 0# for i in range(len(height)):# for j in range(1,len(height)):# if min(height[i],height[j])*(j-i)>maxx:# maxx = min(height[i],height[j])*(j-i)# return maxx '''若向内移动短板，水槽的短板 min(h[i], h[j])min(h[i],h[j]) 可能变大，因此水槽面积 S(i, j)S(i,j) 可能增大。若向内移动长板，水槽的短板 min(h[i], h[j])min(h[i],h[j]) 不变或变小，下个水槽的面积一定小于当前水槽面积。'''i,j = 0,len(height)-1res = 0while i<j:if height[i]<height[j]:res = max(res,(j-i)*height[i])i +=1else:res = max(res,(j-i)*height[j])j -=1return resclass Solution:def trap(self, height: List[int]) -> int:# 暴力解法# ans =0# for i in range(len(height)):# max_left = 0# for j in range(i):# # 寻找max left# if height[j]> max_left:# max_left = height[j]# max_right = 0# for n in range(i+1,len(height)):# if height[n]>max_right:# max_right = height[n]# if min(max_left,max_right)>height[i]:# ans += min(max_left,max_right)-height[i]# return ans# 重点在于一个单元格一个单元格的思考，要假设水不会侧漏！ans = 0if not height:return 0left,right = 0,len(height)-1max_left = height[left]max_right = height[right]while left <right:max_left = max(height[left],max_left)max_right = max(height[right],max_right)if max_left<max_right:ans += max_left-height[left]left = left +1else:ans+= max_right -height[right]right = right-1return ansand和&不能随便替换
class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums.sort() # 无返回值res =[]k = 0# k<i<jfor k in range(len(nums)-2): # 以k为indexif nums[k]>0:break # k is minestif k>0 and nums[k] == nums[k-1]: # [0,0,0]要排除continuei,j = k+1,len(nums)-1while i<j: # double points = nums[k]+nums[i]+nums[j]if s<0:i+=1while i<j and nums[i] ==nums[i-1]:i = i+1 # 去重elif s>0:j-=1while i<j and nums[j] ==nums[j+1]:j = j-1else:res.append([nums[i],nums[j],nums[k]]) # 找到一个i+=1j-=1while i<j and nums[i] ==nums[i-1]: # and和&不能互相替换i= i+1while i<j and nums[j]==nums[j+1]:j= j-1return res 栈的使用
class Solution:def isValid(self, s: str) -> bool:dic = {'}':'{',']':'[',')':'('}stack = [] # 一定要有动态思维，匹配的已经出栈了for i in s:if stack and i in dic: # i是右括号if dic[i]==stack[-1]: # 如果栈顶是对应左括号stack.pop()else:return Falseelse:stack.append(i)return not stack插入排序和预排序
class Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:# 这个题目不支持直接排序inter = []n = len(intervals)i = 0while i<n and newInterval[0] > intervals[i][0]:inter.append(intervals[i])i+=1inter.append(newInterval)inter = inter+ intervals[i:]res = []for i in inter:if len(res)==0 or i[0]>res[-1][1]:res.append(i)else:res[-1][1] = max(res[-1][1],i[1])return ressplit的使用
class Solution:def simplifyPath(self, path: str) -> str:path = path.split('/') # listres = []for i in path:if not i:continueres.append(i)# [a b c d . . ..]paths = []for i in res:if i not in ['.','..']:paths.append(i)# 实际上.是没有pop的# elif i == '.':# if paths:# # paths.pop()# passelif i == '..':if paths:paths.pop() ans = '/'+'/'.join(paths)return ans
DFS
class Solution:def isValidBST(self, root: TreeNode) -> bool:res = self.dfs_bst(root)return resdef dfs_bst(self,root,lower=float('-inf'),upper = float('inf')):if not root:return Trueval = root.valif val<=lower or val>=upper:return Falseif not self.dfs_bst(root.right,val,upper):return Falseif not self.dfs_bst(root.left,lower,val): # 如果其子树不满足，直接返回Falsereturn Falsereturn Trueclass Solution:def recoverTree(self, root: TreeNode) -> None:"""Do not return anything, modify root in-place instead."""lis = []lis = self.dfs(root,lis)x = Noney = None # 用于保留位置，会有两个位置比后一个数大,前面大的是错，后面小的是错的pre = lis[0]for i in range(1,len(lis)):if pre.val>lis[i].val:y = lis[i] # 保存后一个位置if not x:x = pre # 保存第一个位置pre = lis[i]if x and y:x.val,y.val = y.val,x.valdef dfs(self,root,lis):if not root:return self.dfs(root.left,lis)lis.append(root)self.dfs(root.right,lis)return lisBFS
class Solution:def isSymmetric(self, root: TreeNode) -> bool:if root is None:return True# 左子树左和右子树右对称return self.bfs(root.left,root.right)'''一个新的想法是前序遍历等于后序遍历'''def bfs(self,left,right):if not left and not right:return Trueif not left or not right:return Falseif left.val != right.val:return Falsereturn self.bfs(left.left,right.right) and self.bfs(left.right,right.left)class Solution:def levelOrder(self, root: TreeNode) -> List[List[int]]:import collectionsres = []# 维护一个队列，保存一次结果queue = collections.deque()queue.append(root)while queue:level = []size = len(queue)for _ in range(size):cur = queue.popleft()if not cur:continuelevel.append(cur.val)queue.append(cur.left) queue.append(cur.right)if level:res.append(level)return resclass Solution:def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:res = []import collectionsqueue = collections.deque()queue.append(root)flag = Falsewhile queue:level = []size = len(queue)for _ in range(size):cur = queue.popleft()if not cur:continuelevel.append(cur.val)queue.append(cur.left)queue.append(cur.right)if level:if flag:# 务必注意reversed返回的是iterres.append(list(reversed(level)))else:res.append(level)flag = not flagreturn res