LeetCode算法题-House Robber(Java实现)

LeetCode算法题-House Robber(Java实现)

这是悦乐书的第187次更新,第189篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第46题(顺位题号是198)。你是一个专业的强盗,计划在街上抢劫房屋。 每个房子都藏着一定数量的钱,阻止你抢劫他们的唯一限制因素是相邻的房屋有连接的安全系统,如果两个相邻的房子在同一个晚上被闯入,它将自动联系警方。给出一个代表每个房子的金额的非负整数列表,确定今晚可以抢劫的最大金额而不警告警察。例如:

输入:[1,2,3,1]
输出:4
说明:Rob house 1(money = 1)然后抢房子3(钱= 3)。您可以抢夺的总金额= 1 + 3 = 4。

输入:[2,7,9,3,1]
输出:12
说明:Rob house 1(money = 2),rob house 3(money = 9)和rob house 5(money = 1)。您可以抢夺的总金额= 2 + 9 + 1 = 12。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

初始思路是偶数、奇数下标的元素分别求和,然后判断其中的最大值,但是有个问题,此思路只考虑了隔一个元素,那要是隔两个、三个甚至更多呢?在每次算完奇数或者偶数下标元素之和之后,还要和已有的偶数下标元素和或者奇数下标元素和做最大值判断,最后再取偶数下标元素和、奇数下标元素和中的最大值。

特殊情况:当数组为null或者数组中没有任何元素时,直接返回0。

public int rob(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int sum = 0;
    int sum2 = 0;
    for(int i=0; i<nums.length; i++){
        if (i%2 == 0) {
            sum = Math.max(sum+nums[i], sum2);
        } else {
            sum2 = Math.max(sum2+nums[i], sum);
        }
    }
    return Math.max(sum, sum2);
}

此解法的时间复杂度是O(n),空间复杂度是O(1)。

03 第二种解法

使用动态规划算法。

第一步,我们找到此问题的递归关系,强盗有两种选择:

a)抢劫当前的房子i

b)不抢劫当前的房子i

如果选择选项“a”,则意味着无法抢夺之前的i-1房屋,但可以安全地前往前一个i-2之前的房屋并获得随后的所有累积战利品。

如果选择了一个选项“b”,强盗将从抢劫i-1和剩下所有建筑物中获得所有可能的战利品。

因此,利益最大的结果就有两种可能:

1)抢劫当前房屋 + 前一次房屋抢劫

2)从之前的房屋抢劫和之前捕获的任何战利品中掠夺

对此,可以得出以下公式:

rob(i) = Math.max( rob(i-2) + currentHouseValue, rob(i-1) )


第二步,在分析出了递归关系后,我们可以得到自顶向下的递归解法,对此,我们可以写出第一版的代码:

public int rob(int[] nums) {
    return rob(nums, nums.length-1);
}
private int rob(int[] nums, int i) {
    if (i < 0) {
        return 0;
    }
    return Math.max(rob(nums, i-2) + nums[i], rob(nums, i-1));
}


第三步,上面的递归算法,会造成大量的重复计算,对此可以使用备忘录算法来记录前一步的值,同样是使用自顶向下的递归算法。

public int rob(int[] nums) {
    int[] memo = new int[nums.length + 1];
    Arrays.fill(memo, -1);
    return rob(nums, nums.length - 1);
}

private int rob(int[] nums, int i) {
    if (i < 0) {
        return 0;
    }
    if (memo[i] >= 0) {
        return memo[i];
    }
    int result = Math.max(rob(nums, i-2) + nums[i], rob(nums, i-1));
    memo[i] = result;
    return result;
}

Arrays.fill(memo, -1)方法表示memo数组的元素全部由-1来填充。

第四步,备忘录算法不变,可以将递归算法用迭代替代,变成自底向上的方式。

public int rob(int[] nums) {
    if (nums.length == 0) return 0;
    int[] memo = new int[nums.length + 1];
    memo[0] = 0;
    memo[1] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int val = nums[i];
        memo[i+1] = Math.max(memo[i], memo[i-1] + val);
    }
    return memo[nums.length];
}


第五步,可以注意到,在上一步中我们只使用memo[i]和memo[i-1],所以只需要两步。我们可以将它们保存在2个变量中,而不必使用备忘录算法。

public int rob(int[] nums) {
    if (nums.length == 0) return 0;
    int prev1 = 0;
    int prev2 = 0;
    for (int num : nums) {
        int tmp = prev1;
        prev1 = Math.max(prev2 + num, prev1);
        prev2 = tmp;
    }
    return prev1;
}

上述解法的思路参考至的说明,写的很好,就按照自己的理解翻译了下,按照这五个步骤基本可以解决类似的动态规划算法问题。最下方的原文链接就是该作者原答案。

04 小结

算法专题目前已连续日更超过一个月,算法题文章46+篇,