你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。
示例 1:
输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。
示例 2:
输入:nums = [1,2,3,1]
输出:4
解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 3:
输入:nums = [1,2,3]
输出:3
提示:
1 <= nums.length <= 100
0 <= nums[i] <= 1000
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/house-robber-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
本题是https://www.cnblogs.com/allWu/p/16978811.html这一题的进阶,区别是本题多了收尾相接的附加条件。
即(设总共有 n 个房间):
如果从第 0 间房开始偷窃,需要在第 n - 2 或者第 n - 1 个房间停止。 如果从第 1 间房开始偷窃,需要在第 n - 1 或者第 n 个房间停止。
利用之前的思路,分别从第 0 个房间开始偷窃,到第 n - 1 个房间结束;以及从第 1 个房间开始偷窃,到第 n 个房间结束。遍历两遍,取最大值即可。
代码如下:
1 class Solution { 2 public int rob(int[] nums) { 3 if (nums.length == 1) { 4 return nums[0]; 5 } else if (nums.length == 2) { 6 return Math.max(nums[0], nums[1]); 7 } 8 return Math.max(tem(nums, 0, nums.length - 1), tem(nums, 1, nums.length)); 9 } 10 private int tem(int[] nums, int start, int end) { 11 int max1 = nums[start]; 12 int max2 = Math.max(nums[start + 1], nums[start]); 13 int tem = 0; 14 for (int i = start + 2; i < end; i ++) { 15 tem = Math.max(max1 + nums[i], max2); 16 max1 = max2; 17 max2 = tem; 18 } 19 return max2; 20 } 21 }
运行结果如下:
标签:---,偷窃,tem,nums,int,力扣,start,II,房屋 From: https://www.cnblogs.com/allWu/p/16983910.html