56 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort()ans = [intervals[0]]for s,e in intervals[1:]:if ans[-1][1] < s:ans.append([s,e])else:ans[-1][1]=max(ans[-1][1], e)return ans

198 打家劫舍

​你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

class Solution:def rob(self, nums: List[int]) -> int:if not nums:return 0length = len(nums)if length==1:return nums[0]dp=[0]*lengthdp[0]=nums[0]dp[1]=max(nums[0],nums[1])for i in range(2, length):dp[i] = max(dp[i-2]+nums[i], dp[i-1])return dp[length-1]

199 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

  • BFS
# 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 = rightclass Solution:def rightSideView(self, root: Optional[TreeNode]) -> List[int]:if not root:return []res = []que = collections.deque([root])while que:length = len(que)for i in range(length):node = que.popleft()if i == length-1:res.append(node.val)if node.left:que.append(node.left)if node.right:que.append(node.right)return res
  • DFS
# 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 = rightclass Solution:def rightSideView(self, root: Optional[TreeNode]) -> List[int]:global resres = []self.dfs(root,0)return resdef dfs(self, node, depth):if not node:returnif depth==len(res):res.append(node.val)depth+=1self.dfs(node.right, depth)self.dfs(node.left, depth)

200 岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

class Solution:def numIslands(self, grid: List[List[str]]) -> int:r = len(grid)c = len(grid[0])num_islands = 0for i in range(r):for j in range(c):if(grid[i][j]=="1"):num_islands+=1self.dfs(grid,i,j)return num_islandsdef dfs(self, grid, r, c):if not self.inArea(grid, r,c):returnif grid[r][c]!="1":returngrid[r][c]="2"self.dfs(grid,r-1,c)self.dfs(grid,r+1,c)self.dfs(grid, r, c-1)self.dfs(grid,r,c+1)def inArea(self, grid, r,c):return 0<=r<len(grid) and 0<=c<len(grid[0])

228 汇总区间

给定一个 无重复元素 的 有序 整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

“a->b” ，如果 a != b
“a” ，如果 a == b

class Solution:def summaryRanges(self, nums: List[int]) -> List[str]:def f(i,j):return str(nums[i]) if i==j else f'{nums[i]}->{nums[j]}'i,n =0, len(nums)ans=[]while i<n:j=iwhile j+1<n and nums[j+1]==nums[j]+1:j+=1ans.append(f(i,j))i=j+1return ans