Leetcode: House Robber II
LeetCode II
2023-09-11 14:14:07 时间
Note: This is an extension of House Robber. After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Analysis:
if the last one is not robbed, then you are free to choose whether to rob the first one. you can break the circle by assuming the first house is not robbed.
For example, 1 -> 2 -> 3 -> 1 becomes 2 -> 3 if 1 is not robbed.
Since every house is either robbed or not robbed and at least half of the houses are not robbed, the solution is simply the larger of two cases with consecutive houses, i.e. house i not robbed, break the circle, solve it, or house i + 1 not robbed. Hence, the following solution. I chose i = n and i + 1 = 0 for simpler coding. But, you can choose whichever two consecutive ones.
1 class Solution { 2 public int rob(int[] nums) { 3 if (nums == null || nums.length == 0) return 0; 4 if (nums.length == 1) return nums[0]; 5 return Math.max(helper(nums, 0, nums.length - 2), helper(nums, 1, nums.length - 1)); 6 } 7 8 public int helper(int[] nums, int lo, int hi) { 9 int prev2 = 0; 10 int prev1 = nums[lo]; 11 for (int i = lo + 1; i <= hi; i++) { 12 int temp = prev1; 13 prev1 = Math.max(prev1, prev2 + nums[i]); 14 prev2 = temp; 15 } 16 return prev1; 17 } 18 }
相关文章
- Java实现 LeetCode 709 转换成小写字母(ASCII码处理)
- Java实现 LeetCode 561 数组拆分 I(通过排序算法改写PS:难搞)
- Java实现 LeetCode 541 反转字符串 II(暴力大法)
- Java实现 LeetCode 530 二叉搜索树的最小绝对差(遍历树)
- Java实现 LeetCode 496 下一个更大元素 I
- Java实现 LeetCode 445 两数相加 II
- Java实现 LeetCode 324 摆动排序 II
- Java实现 LeetCode 240 搜索二维矩阵 II(二)
- Java实现 LeetCode 190 颠倒二进制位
- Java实现 LeetCode 190 颠倒二进制位
- LeetCode(59):螺旋矩阵 II
- 每日一道 LeetCode (37):两数之和 II - 输入有序数组
- Leetcode.剑指 Offer II 022 链表中环的入口节点
- 139. 单词拆分 ——【Leetcode每日一题】
- Leetcode 2000. 反转单词前缀
- Leetcode 剑指 Offer II 032. 有效的变位词
- Leetcode 47. 全排列 II
- LeetCode 122 Best Time to Buy and Sell Stock II