❝今天刷牛客网的时候,发现热搜上面的中兴笔试题,大多数大佬遇到的都是打家劫舍的题目,恰巧我一看,我也没做,好久没做题了,看了一下题解,同时把自己的笔记分享给大家,准备下班。 ❞
❝一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组 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 。
❝分情况讨论:
❞
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),直接返回最大值
❝一个专业的小偷,计划偷窃一个环形街道上沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组 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号和最后一号房屋的,这里就不能
❞
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),直接返回最大值
[1]
剑指 Offer II 089. 房屋偷盗: https://leetcode.cn/problems/Gu0c2T/
[2]
剑指 Offer II 090. 环形房屋偷盗: https://leetcode.cn/problems/PzWKhm/
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有