213. House Robber II

四刷 06/2022

Version #1 DP

自己做的时候没什么思路 还是看答案才做出来的

Time O(N)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for House Robber II.

Memory Usage: 41.7 MB, less than 40.16% of Java online submissions for House Robber II.

class Solution {

    public int rob(int[] nums) {

        if (nums.length == 0) {

            return 0;

        }

        // if we rob house 0, then we cannot rob the 1 and the last house

        // if we don't rob house 0, we can rob the 1 and the last house

        return Math.max(nums[0] + robHelper(nums, 2, nums.length - 2), robHelper(nums, 1, nums.length - 1));

    }

    

    // The max money to rob from house start to house end

    private int robHelper(int[] nums, int start, int end) {

        if (start >= nums.length) {

            return 0;

        }

        // current house - max{max of previous house, max of prev prev house + nums[currnet]}

        int prevprev = 0, prev = 0;

        for (int i = start; i <= end; i++) {

            int current = Math.max(prev, prevprev + nums[i]);

            prevprev = prev;

            prev = current;

        }

        return prev;

    }

}

Version #1
写一个函数解决任意range之间rob的问题
然后给出包含Index = 0的range 和不包含Index = 0的range的两个值之间的max
注意处理startIndex越界的问题
三刷
100.00 %
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        // nums.length >= 2
        return Math.max(helper(nums, 0, nums.length - 2), helper(nums, 1, nums.length - 1));
    }
   
    private int helper(int[] nums, int start, int end) {
        if (start == end) {
            return nums[start];
        }
        // start < end
        int prevprev = nums[start];
        int prev = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int curr = Math.max(nums[i] + prevprev, prev);
            prevprev = prev;
            prev = curr;
        }
        return prev;
    }
}

二刷
100.00 %
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return Math.max(rob(0, nums.length - 1, nums),
                       rob(1, nums.length, nums));
    }
 
    private int rob(int start, int end, int[] nums) {
        if (start >= nums.length) {
            return 0;
        }
        int prevprev = 0;
        int prev = 0;
        int curr = nums[start];
        for (int i = start + 1; i <= end; i++) {
            curr = Math.max(prev, prevprev + nums[i - 1]);
            prevprev = prev;
            prev = curr;
        }
        return curr;
    }
}

一刷
 6.17 %

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
    }
    private int rob(int[] nums, int start, int end) {
        if (start >= nums.length) return 0;
        int prevPrev = 0;
        int prev = nums[start];
        int curr = prev;
        for (int i = start + 1; i <= end; i++) {
            curr = Math.max(prev, prevPrev + nums[i]);
            prevPrev = prev;
            prev = curr;
        }
        return curr;
    }
}