DeepSeek LeetCode 213. 打家劫舍 II Java实现

LeetCode 213. 打家劫舍 II - Java 实现题目分析与打家劫舍 I 的区别房屋首尾相连成环第一个和最后一个不能同时偷。核心思路把环形问题拆成两个线性问题偷 [0, n-2] 范围内的房子不偷最后一间偷 [1, n-1] 范围内的房子不偷第一间取两者的最大值。代码实现classSolution{publicintrob(int[]nums){intnnums.length;if(n1)returnnums[0];if(n2)returnMath.max(nums[0],nums[1]);// 情况1考虑 [0, n-2]不偷最后一间// 情况2考虑 [1, n-1]不偷第一间returnMath.max(robRange(nums,0,n-2),robRange(nums,1,n-1));}// 线性打家劫舍处理 nums[start..end] 区间privateintrobRange(int[]nums,intstart,intend){intprev20;// dp[i-2]intprev10;// dp[i-1]for(intistart;iend;i){intcurMath.max(prev1,prev2nums[i]);prev2prev1;prev1cur;}returnprev1;}}复杂度分析· 时间复杂度O(n)两趟线性扫描· 空间复杂度O(1)只用了几个变量滚动数组优化关键点说明边界处理n 1 时直接返回 nums[0]因为此时没有环的约束。拆分逻辑· 由于首尾不能同时偷所以要么不偷最后一间要么不偷第一间。· 两种情况覆盖了所有合法方案取最大值即可。滚动数组dp[i] max(dp[i-1], dp[i-2] nums[i])其中 dp[i] 表示偷到第 i 间房的最大金额。测试示例// 输入: [2,3,2] 输出: 3 偷第2间// 输入: [1,2,3,1] 输出: 4 偷第1、3间// 输入: [1,2,3] 输出: 3