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+篇,