首页 > 代码库 > 213. House Robber II
213. House Robber II
题目:
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.
链接: http://leetcode.com/problems/house-robber-ii/
7/16/2017
没想明白,照别人写的
注意,其实包括House Robber在内,第11行并不保证小偷一定会偷间隔为1的房子,robber选择的是当前为止,能抢到的最多的而已。因此这道题只要分为2部分:包括头不包括尾+包括尾不包括头,二者选大即可。
另外,robLastHouse并不是说一定rob current house at the end of each loop,而是说我们考虑到了当前的情况。
1 public class Solution { 2 public int rob(int[] nums) { 3 if (nums == null) return 0; 4 if (nums.length == 1) return nums[0]; 5 return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1)); 6 } 7 8 private int rob(int[] nums, int lo, int hi) { 9 int res = 0, robLastHouse = 0, notRobLast = 0; 10 for (int i = lo; i <= hi; i++) { 11 res = Math.max(robLastHouse, notRobLast + nums[i]); 12 notRobLast = robLastHouse; 13 robLastHouse = res; 14 } 15 return res; 16 } 17 }
别人的答案
https://discuss.leetcode.com/topic/14375/simple-ac-solution-in-java-in-o-n-with-explanation
https://discuss.leetcode.com/topic/14504/9-lines-0ms-o-1-space-c-solution
更多讨论
https://discuss.leetcode.com/category/221/house-robber-ii
213. House Robber II