中兴笔记题：打家劫舍
中兴笔记题：打家劫舍
❝今天刷牛客网的时候，发现热搜上面的中兴笔试题，大多数大佬遇到的都是打家劫舍的题目，恰巧我一看，我也没做，好久没做题了，看了一下题解，同时把自己的笔记分享给大家，准备下班。 ❞
剑指 Offer II 089. 房屋偷盗[1]
❓题目描述
❝一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 ❞
👉题目示例
示例 1：
输入：nums = [1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。示例 2：
输入：nums = [2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。💡题目解析
❝分情况讨论：
- 当数组为空时获取长度为1时，直接0或者当前数组第一个元素的值
- 当数组长度为2时，这时 需要比较数组第一个元素和第二个元素的，返回最大值
- 当数组长度大于2时，因为相邻就会报警，所以需要比较间隔元素之和与它们之间的元素，也就是nums[i - 2] + nums[i] 与nums[i-1]的最大值
❞
📝代码实现
class Solution {
public int rob(int[] nums) {
//如果为空
if(null == nums || 0 == nums.length){
return 0;
}
int n = nums.length;
//长度为1时，直接返回
if(1 == n){
return nums[0];
}
int[] temp = new int[n];
temp[0] = nums[0];
temp[1] = Math.max(nums[0], nums[1]);
//长度大于2时，比较下标nums[i] + temp[i - 2] 与 temp[i - 1]的最大值
//为什么是 temp[i - 2] ,因为每次最新的元素都是最大值，也就是和
for(int i = 2; i < n; i++){
temp[i] = Math.max(nums[i] + temp[i - 2], temp[i - 1]);
}
return temp[n - 1];
}
}
❝也可以不采用中间数组存储最大值的方式，定义两个中间变量，分别用来保存nums[i - 2]和nums[i - 1]的值 ❞
class Solution {
public int rob(int[] nums) {
//如果为空
if(null == nums || 0 == nums.length){
return 0;
}
int n = nums.length;
//长度为1时，直接返回
if(1 == n){
return nums[0];
}
int first = nums[0];
int sec = Math.max(first, nums[1]);
//长度大于2时，比较下标nums[i] + temp[i - 2] 与 temp[i - 1]的最大值
//为什么是 temp[i - 2] ,因为每次最新的元素都是最大值，也就是和
for(int i = 2; i < n; i++){
int temp = sec;
sec = Math.max(first + nums[i], sec);
first = temp;
}
return sec;
}
}
📈复杂度分析
第一种解法
时间复杂度：O(n)，遍历一次数组的长度
空间复杂度：O(n)，中间数组存储整个比较的和
第二种解法
时间复杂度：O(n)，遍历一次数组的长度
空间复杂度：O(1)，直接返回最大值
剑指 Offer II 090. 环形房屋偷盗[2]
❓题目描述
❝一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。 ❞
👉题目示例
示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。示例 3：
输入：nums = [0]
输出：0💡题目解析
❝这个就是上面那一题的升级版，上面小偷是可以同时偷1号和最后一号房屋的，这里就不能
- 第一种情况，偷1号房屋，那么最后一号就不能偷，遍历的区间就变为（0，n - 1）
- 第二种情况，不偷1号房屋，那么最后一号可以偷，遍历的区间就变为（1，n ）
- 第三种情况，都不偷，但是这种情况你会发现包含在前面两种情况中
❞
📝代码实现
class Solution {
public int rob(int[] nums) {
if(nums == null || 0 == nums.length){
return 0;
}
int n = nums.length;
if(1 == n){
return nums[0];
}else if(2 == n){
return Math.max(nums[0], nums[1]);
}
//偷了1号 与 没偷1号进行对比
return Math.max(rec(nums, 0, n - 1), rec(nums, 1, n));
}
public int rec(int[] nums, int s, int e){
int f = nums[s], sec = Math.max(nums[s + 1], f);
for(int i = s + 2; i < e; i++){
int temp = sec;
sec = Math.max(nums[i] + f, sec);
f = temp;
}
return sec;
}
}
📈复杂度分析
时间复杂度：O(n)，遍历一次数组的长度
空间复杂度：O(1)，直接返回最大值
Reference
[1]
剑指 Offer II 089. 房屋偷盗: https://leetcode.cn/problems/Gu0c2T/
[2]
剑指 Offer II 090. 环形房屋偷盗: https://leetcode.cn/problems/PzWKhm/
![[LeetCode]动态规划之打家劫舍ⅠⅡⅢ](https://ask.qcloudimg.com/http-save/yehe-6557940/ea176eb4ab5e5114421134e427f77801.png)
腾讯云开发者
