目录
- 问题1：
- 问题链接：
- 问题描述：
- 实例：
- 代码：
- 问题2：
- 问题链接：
- 问题描述：
- 实例：
- 代码：
- 问题3：
- 问题链接：
- 问题描述：
- 实例：
- 代码：
- 问题4：
- 问题链接：
- 问题描述：
- 实例：
- 代码：
问题1：
问题链接：
191. 位1的个数
问题描述：
给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。实例：
示例1： 输入：n=11输出：3解释：输入的二进制串1011中，共有3个设置位。 示例2： 输入：n=128输出：1解释：输入的二进制串10000000中，共有1个设置位。 示例3： 输入：n=2147483645输出：30解释：输入的二进制串1111111111111111111111111111101中，共有30个设置位。代码：
classSolution:defhammingWeight(self,n:int)->int:res=0whilen:#与操作，只要是1，就是1res+=n&1n>>=1returnres#n &= n - 1 ： 消去数字 n 最右边的 1 。classSolution:defhammingWeight(self,n:int)->int:res=0whilen:res+=1n&=n-1returnres问题2：
问题链接：
198. 打家劫舍
问题描述：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。实例：
示例1： 输入：[1,2,3,1]输出：4解释：偷窃1号房屋(金额=1)，然后偷窃3号房屋(金额=3)。 偷窃到的最高金额=1+3=4。 示例2： 输入：[2,7,9,3,1]输出：12解释：偷窃1号房屋(金额=2),偷窃3号房屋(金额=9)，接着偷窃5号房屋(金额=1)。 偷窃到的最高金额=2+9+1=12。代码：
#时间复杂度：O(n)，其中 n 是 nums 的长度。#空间复杂度：O(n)。classSolution:defrob(self,nums:List[int])->int:# dfs(i) 表示从 nums[0] 到 nums[i] 最多能偷多少@cache# 缓存装饰器，避免重复计算 dfs 的结果defdfs(i:int)->int:ifi<0:# 递归边界（没有房子）return0returnmax(dfs(i-1),dfs(i-2)+nums[i])returndfs(len(nums)-1)# 从最后一个房子开始思考直接翻译的话，dfs(i)翻译成 f[i]。 但记忆化搜索会访问dfs(−2)和dfs(−1)，f[−2]和 f[−1]下标越界了。 解决办法：在 f 数组的前面插入两个0，把 f 数组整体往右偏移2位。偏移后，dfs(i)翻译成 f[i+2]。#1：1翻译成堆#时间复杂度：O(n)。其中 n 是 nums 的长度。#空间复杂度：O(n)。classSolution:defrob(self,nums:List[int])->int:f=[0]*(len(nums)+2)fori,xinenumerate(nums):f[i+2]=max(f[i+1],f[i]+x)returnf[-1]#空间优化#时间复杂度：O(n)。其中 n 是 nums 的长度。#空间复杂度：O(1)。classSolution:defrob(self,nums:List[int])->int:f0=f1=0forxinnums:f0,f1=f1,max(f1,f0+x)returnf1问题3：
问题链接：
199. 二叉树的右视图
问题描述：
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。实例：
代码：
先递归右子树，再递归左子树，当某个深度首次到达时，对应的节点就在右视图中。
时间复杂度：O(n)，其中 n 是二叉树的节点个数。 空间复杂度：O(h)，其中 h 是二叉树的高度。递归需要O(h)的栈空间。最坏情况下，二叉树退化成一条链，递归需要O(n)的栈空间。# 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 = rightclassSolution:defrightSideView(self,root:Optional[TreeNode])->List[int]:#递归，先递归右子树，再递归左子树，当某个深度首次到达时，对应的节点就在右视图中。ans=[]defdfs(node:Optional[TreeNode],depth:int)->None:ifnodeisNone:returnifdepth==len(ans):#这个深度首次遇到ans.append(node.val)dfs(node.right,depth+1)#先递归右子树，保证首次遇到的一定是最右边的节点dfs(node.left,depth+1)dfs(root,0)returnans问题4：
问题链接：
200. 岛屿数量
问题描述：
给你一个由'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。实例：
示例1： 输入：grid=[['1','1','1','1','0'],['1','1','0','1','0'],['1','1','0','0','0'],['0','0','0','0','0']]输出：1示例2： 输入：grid=[['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']]输出：3代码：
时间复杂度：O(mn)，其中 m 和 n 分别是 grid 的行数和列数。由于 DFS 中修改了 grid[i][j]='2'，当我们访问一个访问过的格子时，会触发ifgrid[i][j]!='1':return。只有首次访问一个格子时，才会继续递归，其余情况不会继续递归。每次插上一个旗子只需要O(1)的时间，插上至多 mn 个旗子，就需要O(mn)的时间。 空间复杂度：O(mn)。最坏情况下，对于蛇形陆地、蚊香型陆地等，递归需要O(mn)的栈空间。classSolution:defnumIslands(self,grid:List[List[str]])->int:m,n=len(grid),len(grid[0])defdfs(i:int,j:int)->None:#出界，或者不是1，就不再往下递归ifi<0ori>=morj<0orj>=norgrid[i][j]!="1":returngrid[i][j]="2"dfs(i,j-1)#往左走dfs(i,j+1)#往右走dfs(i-1,j)#往上走dfs(i+1,j)#往下走ans=0fori,rowinenumerate(grid):forj,cinenumerate(row):ifc=="1":dfs(i,j)ans+=1returnans
)
