可以。你这版代码已经写对了而且和我们刚才讲的思路完全一致。下面我按照**“零基础 面试复习”**的方式把这道题整理成一份比较完整的笔记。LeetCode 416分割等和子集一、题目核心给你一个只包含正整数的数组nums。判断能不能把数组分成两个子集使得两个子集的元素和相等例如nums[1,5,11,5]可以分成[1, 5, 5] 11 [11] 11所以返回True二、第一步把题目转换一下假设所有数字的总和是totalsum(nums)如果可以分成两个和相等的部分那么每一部分 total / 2所以问题就变成能不能从 nums 中选出一些数字使它们的和恰好等于 total / 2这就变成了一个经典的0/1 背包问题三、为什么总和是奇数一定不行例如total 11想分成两个相等的整数11 / 2 5.5显然不可能。所以iftotal%21:returnFalse也可以写成iftotal%2!0:returnFalse意思都是如果总和是奇数直接返回False。四、target 是什么如果总和是偶数targettotal//2例如nums [1, 5, 11, 5] total 22 target 11那么我们不需要真的去找两个子集。只需要问能不能从 nums 中找出一些数字使它们的和等于 11如果可以那么剩下的数字自然也是 11。五、dp 数组是什么意思你的代码dp[False]*(target1)dp[0]True这里最重要的是理解dp[i] 表示能不能从已经遍历过的数字中选出一些数字使它们的和恰好等于 i。例如dp[0] → 能不能凑出 0 dp[1] → 能不能凑出 1 dp[2] → 能不能凑出 2 ... dp[11] → 能不能凑出 11六、为什么 dp[0] True因为一个数字都不选和就是 0。所以dp[0]True这是整个动态规划的初始状态。七、最核心的状态转移你的代码dp[i]dp[i]ordp[i-num]这是整道题最重要的一句话。假设当前数字num5现在我们想知道dp[8]也就是能不能凑出 8当前这个5有两种选择。情况一不选 5如果之前就能够凑出 8dp[8]True那么现在当然还是可以凑出 8。情况二选 5如果我们选择当前的 5。那么还差8 - 5 3所以只要之前能够凑出 3dp[3]True那么3 5 8所以dp[8]True因此dp[i]dp[i]ordp[i-num]可以翻译成dp[i] 不选当前 num OR 选当前 num八、为什么是 dp[i-num]这个一定要理解。我们现在要凑i当前数字是num如果决定把num放进去那么剩下需要凑i - num所以dp[i-num]表示之前能不能凑出 i-num。如果可以那么加上当前的num(i-num) num i于是dp[i]True九、为什么i要从大到小你的代码foriinrange(target,num-1,-1):这里非常重要。它表示从 target 开始一直倒着遍历到 num。例如target11num5那么range(11,4,-1)得到11 → 10 → 9 → 8 → 7 → 6 → 5十、为什么必须从后往前因为这道题要求每个数字只能使用一次。也就是典型的0/1 背包假设nums[5]只有一个5。我们绝对不能让它变成5 5 10因为数组里只有一个 5。如果从前往后假设num5如果foriinrange(5,target1):首先dp[5]dp[5]ordp[0]因为dp[0]True所以dp[5] True然后继续dp[10]dp[10]ordp[5]问题来了。刚刚dp[5] True就是使用当前这个5得到的。现在又利用dp[5]来得到dp[10]相当于5 5同一个数字被使用了两次。十一、从后往前为什么可以避免重复使用从11 → 10 → 9 → ... → 5开始。比如现在计算dp[10]dp[10]ordp[5]此时的dp[5]还是上一轮处理数字之前的状态。因为我们还没走到i 5。所以不会使用当前的5两次。这就是0/1 背包为什么要从后往前遍历。十二、为什么是num - 1你的代码range(target,num-1,-1)这里的num - 1只是因为 Python 的range右边界不包含。我们希望i能取到num例如target 11 num 5我们希望11 10 9 8 7 6 5所以必须写range(11,4,-1)也就是range(target,num-1,-1)如果写range(target,num,-1)那么5不会被遍历到。十三、完整代码 注释你的代码可以整理成这样classSolution:defcanPartition(self,nums:List[int])-bool:# 1. 计算所有数字的总和totalsum(nums)# 2. 如果总和是奇数不可能分成两个相等的整数iftotal%21:returnFalse# 3. 每个子集需要达到的目标和targettotal//2# 4. dp[i]# 是否可以从已经遍历过的数字中凑出和 idp[False]*(target1)# 5. 什么都不选时可以凑出 0dp[0]True# 6. 一个一个处理数字fornuminnums:# 7. 从后往前遍历# 保证每个 num 只能使用一次foriinrange(target,num-1,-1):# 8. 两种选择# 不选 numdp[i]# 选 numdp[i-num]dp[i]dp[i]ordp[i-num]# 9. 看能不能凑出 targetreturndp[target]十四、用一句话理解整个算法这道题不要一开始想着代码。先记住这个逻辑原问题 能不能分成两个和相等的集合 ↓ 总和必须是偶数 ↓ 只需要找一个集合使它的和 total / 2 ↓ 变成 0/1 背包问题 ↓ dp[i] 能不能凑出 i ↓ 对于每个 num 选它 or 不选它 ↓ dp[i] dp[i] or dp[i-num] ↓ i 从大到小遍历 保证每个数字只使用一次十五、这道题最应该记住的 4 个知识点① 先判断总和奇偶iftotal%21:returnFalse总和是奇数 → 一定不能平分。② 把问题变成“凑 target”targettotal//2问题从能不能分成两个相等的集合变成能不能凑出target③ dp 定义dp[i] 是否能够凑出和 i这是最重要的。④ 0/1 背包从后往前foriinrange(target,num-1,-1):原因每个数字只能使用一次。状态转移dp[i]dp[i]ordp[i-num]含义不选 num OR 选 num⭐ 最终背下来这一套模板以后再遇到类似的**“每个数字只能用一次能不能凑出某个目标值”**的问题就可以想到dp[False]*(target1)dp[0]Truefornuminnums:foriinrange(target,num-1,-1):dp[i]dp[i]ordp[i-num]其中真正需要理解的只有一句dp[i]dp[i]ordp[i-num]不选当前数字或者选当前数字。以及foriinrange(target,num-1,-1)从后往前保证当前数字不会被重复使用。LeetCode 377组合总和 IV1. 题目给定nums和target求组成target的不同排列数量。例如nums [1,2,3], target 412和21算两种。2. 核心思路动态规划定义dp[i]表示组成数字i的不同排列数量。初始化dp[0]*(target1)dp[0]1dp[0] 1表示什么都不选组成 0有 1 种方法。3. 状态转移dp[i]dp[i-num]含义如果最后选择num那么前面就需要组成i-num。例如组成4最后选 1 → 前面组成 3 → dp[3] 最后选 2 → 前面组成 2 → dp[2] 最后选 3 → 前面组成 1 → dp[1]所以dp[4] dp[3] dp[2] dp[1]4. 为什么可以重复使用数字题目允许一个数字重复使用例如1 1 1 1所以可以不断利用之前计算好的dp[i-num]。5. 为什么顺序不同算不同377 中1 2 2 1算两种。因此采用foriinrange(1,target1):fornuminnums:先枚举目标i再枚举最后选择的数字num。6. 代码模板classSolution:defcombinationSum4(self,nums:List[int],target:int)-int:dp[0]*(target1)dp[0]1foriinrange(1,target1):fornuminnums:ifinum:dp[i]dp[i-num]returndp[target]⭐ 最重要的记忆点dp[i]dp[i-num]就是我要组成i如果最后选num那么前面就要组成i-num。最终dp[0] 1 dp[1] 1 dp[2] 2 dp[3] 4 dp[4] 7所以答案是7。一句话总结377 “求组成 target 的排列数量”核心就是“看最后一个数字是谁”。LeetCode 695岛屿的最大面积1. 题目给定一个二维grid1表示陆地0表示水相邻的1上下左右属于同一个岛屿。要求找到面积最大的岛屿。2. 核心思路DFS遍历整个网格foriinrange(m):forjinrange(n):如果发现grid[i][j]1说明发现了一个新的岛屿就从这个位置进行DFS把整个岛屿找出来并计算面积。3. DFS 的含义dfs(i,j)表示从(i,j)出发把与它连接的所有陆地都找出来。每个位置向四个方向搜索dfs(i-1,j)# 上dfs(i1,j)# 下dfs(i,j-1)# 左dfs(i,j1)# 右4. 防止重复计算访问一个陆地后grid[i][j]0表示这个格子已经访问过了。以后再次遇到它就直接返回0。因此每个陆地只会计算一次。5. DFS 面积计算return(1dfs(i-1,j)dfs(i1,j)dfs(i,j-1)dfs(i,j1))意思当前格子贡献1再加上上下左右能够连接到的陆地面积。6. 完整代码classSolution:defmaxAreaOfIsland(self,grid:List[List[int]])-int:mlen(grid)nlen(grid[0])defdfs(i,j):# 越界或者是水停止搜索ifi0orimorj0orjnorgrid[i][j]0:return0# 标记为已经访问grid[i][j]0# 当前格子 四个方向return(1dfs(i-1,j)dfs(i1,j)dfs(i,j-1)dfs(i,j1))ans0foriinrange(m):forjinrange(n):ifgrid[i][j]1:areadfs(i,j)ansmax(ans,area)returnans⭐ 这道题记住 4 个点1. 发现 1 → 找到一个岛屿 2. DFS → 把整个岛屿找出来 3. grid[i][j] 0 → 标记访问过防止重复 4. ans max(ans, area) → 更新最大岛屿面积一句话总结695 遍历网格 DFS 找连通的 1 统计面积 取最大值。而DFS可以简单记成从一个格子出发上下左右不断深入把所有连通的格子找出来。LeetCode 25K 个一组翻转链表1. 题目给定一个链表每k 个节点一组进行翻转。如果最后剩余节点不足k个保持原顺序不变。例如1 → 2 → 3 → 4 → 5k2 2 → 1 → 4 → 3 → 52. 核心思路每次处理一组① 判断剩余节点够不够 k 个 ② 找到这一组的第 k 个节点 ③ 保存下一组的开始位置 ④ 翻转当前 k 个节点 ⑤ 把翻转后的链表重新接起来 ⑥ 继续处理下一组3.dummy节点dummyListNode(0)dummy.nexthead group_prevdummydummy是辅助节点可以方便处理头节点发生变化的情况。4. 找第 k 个节点kthgroup_prevfor_inrange(k):kthkth.nextifkthisNone:returndummy.next含义从group_prev开始往后走k步如果不到k个节点就结束。5. 保存下一组group_nextkth.next保存下一组的开始位置防止翻转时丢失后面的链表。6. 翻转当前这一组使用之前学过的链表翻转prevgroup_next curgroup_prev.nextwhilecur!group_next:nextcur.nextcur.nextprev prevcur curnext核心仍然是nextcur.nextcur.nextprev prevcur curnext7. 重新连接old_group_startgroup_prev.nextgroup_prev.nextkth group_prevold_group_start注意翻转前的第一个节点翻转后会变成这一组的最后一个节点。所以让它成为下一轮的group_prev。⭐ 最重要的记忆找 k 个 ↓ 保存下一组 ↓ 翻转 k 个 ↓ 重新连接 ↓ 移动到下一组一句话总结25 普通链表翻转 每 k 个分一组 翻转后重新连接。