打劫房屋 · House Robber

[抄题]:

假设你是一个专业的窃贼,准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是:相邻的房子装着相互联系的防盗系统,且 当相邻的两个房子同一天被打劫时,该系统会自动报警

给定一个非负整数列表,表示每个房子中存放的钱, 算一算,如果今晚去打劫,你最多可以得到多少钱 在不触动报警装置的情况下

给定 [3, 8, 4], 返回 8.

[暴力解法]:

时间分析:

空间分析:把结果数组的值都mod2,结果数组的空间就节省为2了

[思维问题]:

[一句话思路]:

结果只和2种状态有关,因此结果f数组要成为滚动数组,mod2

[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):

[画图]:

打劫房屋 · House Robber

[一刷]:

  1. 前0个不包括第0个,前0个加了也没事,所以i应该从2开始。i = 1,i<=n时操作,序列型记住等号不能丢
  2. 前i -2个不包括第i -2个,所以应该再加第i - 1个

[二刷]:

[三刷]:

[四刷]:

[五刷]:

[五分钟肉眼debug的结果]:

状态函数f和数组搞混了

[总结]:

偷东西第0位没有意义,所以还是类似“爬楼梯”的坐标型

[复杂度]:Time complexity: O(n) Space complexity: O(1)

空间节约成定值了

[英文数据结构或算法,为什么不用别的数据结构或算法]:

偷东西可以有“偷了前0家”的概念,所以是序列型。

走路没有“走了前0步”的概念,所以是坐标型。

[关键模板化代码]:

4步即可。

[其他解法]:

[Follow Up]:

[LC给出的题目变变变]:

打劫房屋 II · House Robber II 循环时加一点限制条件

打劫房屋 III · House Robber III 二叉树

[代码风格] :

数组取值题的corner case不是没有对象的null,而是判断数组长度为0时应该怎么取数,要理解

public class Solution {
/*
* @param A: An array of non-negative integers
* @return: The maximum amount of money you can rob tonight
*/
public int rob(int[] A) {
//corner case
int n = A.length;
if (n == 0) {
return 0;
}
//state
int[] f = new int[2];
//initialization
f[0] = 0;
f[1] = A[0];
//function
for (int i = 2; i <= n; i++) {
f[i % 2] = Math.max(f[(i - 1) % 2], f[(i - 2) % 2] + A[i - 1]);
}
//answer
return f[n % 2];
}
}
上一篇:《浏览器工作原理与实践》<06>渲染流程(下):HTML、CSS和JavaScript,是如何变成页面的?


下一篇:《浏览器工作原理与实践》<08>调用栈:为什么JavaScript代码会出现栈溢出?