leecode128,最长连续子序列，哈希表枚举，要注意技巧，判断num-1是否在哈希表中，可以降低时间复杂度。
class Solution:def longestConsecutive(self, nums: List[int]) -> int:nums_set = set(nums)long_path = 0for num in nums_set:if num-1 not in nums_set:current_num = numcurrent_path = 1while current_num + 1 in nums_set:current_num += 1current_path += 1long_path = max(long_path,current_path)return long_path
旋转数组
leecode33,搜索旋转数组，二分后两边子数组一个有序一个无序，在有序的那一边继续搜索。但是要考虑重复数字的存在。
class Solution:def search(self, nums,target: int) -> int:if len(nums) == 0:return -1if len(nums) == 1:if nums[0] == target:return 0else:return -1l = 0r = len(nums)while l < r:mid = (l+r)//2if nums[mid] == target:return midif nums[l] == nums[mid] and nums[r-1] == nums[mid]:l += 1r -= 1elif nums[l]<=nums[mid]:if nums[l]<=target<=nums[mid]:r = midelse:l = mid + 1else:if nums[mid]<=target<=nums[r-1]:l = mid + 1else:r = midreturn -1
leecode81，旋转数组，leecode38加强版，有重复数字，难以判断子数组哪个有序，所以碰到nums[l]，nums[mid]，nums[r-1]三数字相等时，l和r分别加减1
class Solution:def search(self, nums,target: int) -> int:if len(nums) == 0:return -1if len(nums) == 1:return nums[0] == targetl = 0r = len(nums)while l < r:mid = (l+r)//2if nums[mid] == target:return Trueif nums[l] == nums[mid] and nums[r-1] == nums[mid]:l += 1r -= 1elif nums[l]<=nums[mid]:if nums[l]<=target<=nums[mid]:r = midelse:l = mid + 1else:if nums[mid]<=target<=nums[r-1]:l = mid + 1else:r = midreturn False
leecode153,查找旋转数组的最小值，二分法。注意起始区间l = 0,r = len(nums)-1，当nums[mid]>nums[r]时，说明mid在左边子区间，那么不考虑左边区间;当nums[mid]<nums[r]时，说明mid在右边区间，那么不考虑右边区间；当nums[mid] == nums[r]的时候，如果有重复元素，则无法区分，此时只能让r -= 1。返回的索引要考虑实际问题，本题就是最小元素的索引，即右边区间的最左边的点。
class Solution:def findMin(self, nums): l,r = 0,len(nums)-1while l < r:mid = (l+r)//2if nums[mid]>nums[r]:l = mid + 1elif nums[mid] < nums[r]:r = midelse:r -= 1return nums[l]#或者nums[r]if __name__ == "__main__":solution = Solution()nums = [3,4,5,1,2]ans = solution.findMin(nums)print(ans)
leecode154,寻找旋转数组的最小值，leecode153加强版本，包含重复元素，二分法。注意起始区间l = 0,r = len(nums)-1，当nums[mid]>nums[r]时，说明mid在左边子区间，那么不考虑左边区间;当nums[mid]<nums[r]时，说明mid在右边区间，那么不考虑右边区间；当nums[mid] == nums[r]的时候，如果有重复元素，则无法区分，此时只能让r -= 1
class Solution:def findMin(self, nums): l,r = 0,len(nums)while l < r:mid = (l+r)//2if nums[mid]>nums[r-1]:l = mid + 1elif nums[mid] < nums[r-1]:r = midelse:r -= 1return nums[l]#或者nums[r]
dfs
leecode695，岛屿的最大面积，dfs，要注意变量、边界条件和递归表达式三要素
class Solution:def dfs(self, grid, cur_i, cur_j) -> int:if cur_i < 0 or cur_j < 0 or cur_i>=len(grid) or cur_j>=len(grid[0]) or grid[cur_i][cur_j] != 1:return 0grid[cur_i][cur_j] = 0ans = 1for next_i,next_j in [0,1],[0,-1],[1,0],[-1,0]:di,dj = cur_i+next_i,cur_j+next_jans += self.dfs(grid,di,dj)return ansdef maxAreaOfIsland(self, grid: List[List[int]]) -> int:ans = 0for i in range(len(grid)):for j in range(len(grid[0])):ans = max(ans,self.dfs(grid,i,j))return ans
leecode200,岛屿数量，dfs，具体代码思路和leecode695岛屿最大面积很相似
class Solution:def dfs(self, grid, cur_i, cur_j) -> int:if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != "1":returngrid[cur_i][cur_j] = "0"for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:next_i, next_j = cur_i + di, cur_j + djself.dfs(grid, next_i, next_j)def numIslands(self, grid: List[List[str]]) -> int:ans = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == "1":ans += 1self.dfs(grid,i,j)return ans
leecode 463，岛屿的周长，遍历判断即可
class Solution:def islandPerimeter(self, grid: List[List[int]]) -> int:ans = 0for i in range(len(grid)):for j in range(len(grid[0])):tmp = 4if grid[i][j] == 1:for next_i,next_j in [1,0],[-1,0],[0,1],[0,-1]:di,dj = i + next_i,j+ next_jif 0<=di<len(grid) and 0<=dj<len(grid[0]) and grid[di][dj] == 1:tmp -= 1ans += tmpreturn ans
反转链表
offer24、leecode206反转链表，双指针的迭代写法+递归写法，注意递归写法中值传递和结束过程。递归写法是不断递归修改节点的next，实质是从尾部节点开始修改。
# Definition for singly-linked list. class ListNode:def __init__(self, x):self.val = xself.next = Noneclass Solution:def reverseList(self, head: ListNode) -> ListNode:if head == None:return headpre = Nonewhile head != None:tmp = head.nexthead.next = prepre = headhead = tmpreturn preclass Solution:def reverseList(self, head: ListNode) -> ListNode:def dfs(head,pre):if head == None:return preres = dfs(head.next,head)head.next = prereturn respre = None return dfs(head,pre)def print_node(node):while node != None:print(node.val)node = node.next if __name__ == "__main__":head = ListNode(1)head.next = ListNode(2)head.next.next = ListNode(3)solution = Solution()ans = solution.reverseList(head)print_node(ans)# [1,2,3,4,5]
leecode92，反转链表2，反转链表的加强版本，反转部分链表，要处理好left=1的边界条件
# Definition for singly-linked list. class Solution:def reverseBetween(self, head, left: int, right: int):if head ==None or head.next ==None:return headi = 1pre = Nonestart = headwhile i < left:pre = startstart = start.nexti += 1j = icur_pre = Nonecur = start# 反转while j <= right:tmp = cur.nextcur.next = cur_precur_pre = curcur = tmpj += 1# 接起来,要考虑从链表开始就反转的情况，这个时候表头变了if pre !=None:pre.next = cur_prestart.next = curif pre == None:head = cur_prereturn head
打家劫舍
leecode198，打家劫舍，优化空间的动态规划
class Solution:def rob(self, nums):if len(nums) == 0:return 0if len(nums) == 1:return nums[0]dp_0 = nums[0]dp_1 = max(nums[0],nums[1])for i in range(2,len(nums)):tmp = dp_0dp_0 = dp_1dp_1 = max(nums[i]+tmp,dp_1)return dp_1
leecode213，打家劫舍，环形数组，对两个子数组进行动态规划，取结果最大的值
class Solution:def robrange(self,nums):dp_0 = nums[0]dp_1 = max(nums[0],nums[1])for i in range(2,len(nums)):tmp = dp_0dp_0 = dp_1dp_1 = max(nums[i]+tmp,dp_1)return dp_1def rob(self, nums):if len(nums) == 0:return 0if len(nums) == 1:return nums[0]if len(nums) == 2:return max(nums[0],nums[1])return max(self.robrange(nums[:len(nums)-1]),self.robrange(nums[1:]))
leecode337,打家劫舍，树形dp，注意模版
# 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 rob(self, root: Optional[TreeNode]) -> int:def dfs(root):if root == None:return 0,0l_rob,l_not_rob = dfs(root.left)r_rob,r_not_rob = dfs(root.right)rob = l_not_rob + r_not_rob + root.valnot_rob = max(l_rob,l_not_rob) + max(r_rob,r_not_rob)return rob,not_robreturn max(dfs(root))
最大化最小值/最小化最大值
leecode2569,打家劫舍，最小化最大值，二分法+dp
class Solution:def minCapability(self, nums: List[int], k: int) -> int:n = len(nums)if n == 1: return nums[0]left, right = 1, 1e9+1# 求最小最大值，所以将初始最大值设置为极大的正数，方便求最小最大值ans = right while left < right:mid = (left + right) // 2 # 窃取能力mid# mid = (left + right) >> 1# dp[i]，表示前 i 个（i从0算起）房间中可窃取金额不超过窃取能力mid的最大房间数dp = [0] * n# base case：第1个房屋dp[0]，如果房屋金额<=窃取能力mid，选择窃取；# 第2个房屋dp[1]，如果1、2间房屋其中一个满足条件，则可偷盗房间数为1，否则为0if nums[0] <= mid: dp[0] = 1dp[1] = 1 if min(nums[0], nums[1]) <= mid else 0for i in range(2, n):# 此房屋的金额nums[i]大于窃取能力mid，无法窃取，只能顺延dp[i-1]保证尽量大if nums[i] > mid:dp[i] = dp[i - 1]# 此房屋可以窃取, 可选择窃取（dp[i-2]+1）和不窃取（dp[i-1]）的最优值else:dp[i] = max(dp[i - 1], dp[i - 2] + 1)# 只要窃取的房屋数量>=k即可成功，保存答案，继续寻找更小的符合条件的窃取能力if dp[n - 1] >= k:ans = midright = midelse:left = mid + 1return int(right)
