LeetCode第213题 – 打家劫舍 II

47 views

题目

解答

class Solution {
    public int rob(int[] nums, int start, int length) {
        int[] robValues = new int[length];

        robValues[0] = nums[start];
        robValues[1] = Math.max(nums[start], nums[start + 1]);

        for (int i = 2, j = start + 2; i < length; ++i, ++j) {
            robValues[i] = Math.max(nums[j] + robValues[i - 2], robValues[i - 1]);
        }

        return robValues[length - 1];
    }

    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        if (nums.length < 2) {
            return nums[0];
        }

        if (nums.length < 3) {
            return Math.max(nums[0], nums[1]);
        }

        int a1 = rob(nums, 0, nums.length - 1);
        int a2 = rob(nums, 1, nums.length - 1);
        return Math.max(a1, a2);
    }
}

要点
依据题目要求,房子首尾相接,即:

  • 假如位置0的房屋被访问,则位置n-1的房屋则不可以访问。
  • 假如位置0的房屋没有被访问,则位置n-1的房屋则可以访问。

因而将本问题简化,分别求[0, n - 1)[1, n - 1]两个序列的最大值,然后再取二者的最大值,作为最终的结果。

准备的用例,如下

@Before
public void before() {
    t = new Solution();
}

@Test
public void test001() {
    assertEquals(3, t.rob(new int[] { 2, 3, 2 }));
}

@Test
public void test002() {
    assertEquals(4, t.rob(new int[] { 1, 2, 3, 1 }));
}

@Test
public void test003() {
    assertEquals(2, t.rob(new int[] { 2 }));
}

@Test
public void test004() {
    assertEquals(7, t.rob(new int[] { 2, 7 }));
}

@Test
public void test005() {
    assertEquals(7, t.rob(new int[] { 7, 2 }));
}

@Test
public void test006() {
    assertEquals(4, t.rob(new int[] { 1, 2, 3, 1 }));
}

@Test
public void test007() {
    assertEquals(0, t.rob(new int[] { 0 }));
}

@Test
public void test008() {
    assertEquals(10, t.rob(new int[] { 1, 7, 9, 2 }));
}


若非注明,均为原创,欢迎转载,转载请注明来源:LeetCode第213题 – 打家劫舍 II

关于 JackieAtHome

基层程序员,八年之后重新启航

此条目发表在 Java, LeetCode 分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Protected with IP Blacklist CloudIP Blacklist Cloud