Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >中兴笔记题:打家劫舍

中兴笔记题:打家劫舍

作者头像
小熊学Java
发布于 2023-07-16 06:23:15
发布于 2023-07-16 06:23:15
17900
代码可运行
举报
文章被收录于专栏:全栈学习之路全栈学习之路
运行总次数:0
代码可运行

❝今天刷牛客网的时候,发现热搜上面的中兴笔试题,大多数大佬遇到的都是打家劫舍的题目,恰巧我一看,我也没做,好久没做题了,看了一下题解,同时把自己的笔记分享给大家,准备下班。 ❞

剑指 Offer II 089. 房屋偷盗[1]

❓题目描述

❝一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组 nums ,请计算 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 ❞

👉题目示例

示例 1:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:nums = [1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4

示例 2:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: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]的最大值

📝代码实现
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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]的值 ❞

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2, 因为他们是相邻的。

示例 2:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:nums = [1,2,3,1]
输出:4
解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4

示例 3:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:nums = [0]
输出:0
💡题目解析

❝这个就是上面那一题的升级版,上面小偷是可以同时偷1号和最后一号房屋的,这里就不能

  • 第一种情况,偷1号房屋,那么最后一号就不能偷,遍历的区间就变为(0,n - 1)
  • 第二种情况,不偷1号房屋,那么最后一号可以偷,遍历的区间就变为(1,n )
  • 第三种情况,都不偷,但是这种情况你会发现包含在前面两种情况中

📝代码实现
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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/

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-08-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 小熊学Java 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
画解算法:198. 打家劫舍
https://leetcode-cn.com/problems/house-robber/
灵魂画师牧码
2019/07/11
4910
画解算法:198. 打家劫舍
力扣198——打家劫舍
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
健程之道
2020/02/19
2850
☆打卡算法☆LeetCode 213. 打家劫舍 II 算法解析
大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。
恬静的小魔龙
2022/09/27
3280
☆打卡算法☆LeetCode 213. 打家劫舍 II  算法解析
[LeetCode]动态规划之打家劫舍ⅠⅡⅢ
在文章[LeetCode]动态规划及LeetCode题解分析中,Jungle介绍到求解动态规划类问题,一般分为三个步骤:
用户6557940
2022/07/24
3030
[LeetCode]动态规划之打家劫舍ⅠⅡⅢ
每日算法题——打家劫舍
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
用户2802329
2020/03/04
4910
LeetCode131|打家劫舍
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
码农王同学
2020/11/16
2230
力扣213——打家劫舍 II
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
健程之道
2020/02/19
3050
每日一题 | Python3 实战 LeetCode 「198. 打家劫舍 」& 「213. 打家劫舍 II」
https://leetcode-cn.com/problems/house-robber/
与你一起学算法
2021/04/28
7210
LeetCode-198-打家劫舍
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
benym
2022/07/14
1970
198 打家劫舍
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
木瓜煲鸡脚
2021/03/09
2590
leetcode刷题(92)——198. 打家劫舍
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
老马的编程之旅
2022/06/22
1480
LeetCode213. 打家劫舍II
相比打家取舍一,不能同时偷第一家和最后家。就是多了个选择,要不偷第一家,要不偷最后家。 动态规划问题就是要在题目中找出选择,得出状态。
Yuyy
2022/06/28
1260
198. 打家劫舍
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 示例 1: 输入:[1,2,3,1] 输出:4 解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 2:
编程张无忌
2021/06/24
3230
快手面试题:1分钟读题,3分钟做题,10分钟乐呵
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
宫水三叶的刷题日记
2023/12/13
1810
快手面试题:1分钟读题,3分钟做题,10分钟乐呵
☆打卡算法☆LeetCode 198. 打家劫舍 算法解析
大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。
恬静的小魔龙
2022/09/21
2220
☆打卡算法☆LeetCode 198. 打家劫舍 算法解析
213. 打家劫舍 II
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。 输入:nums = [1,2,3,1] 输出:4 解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
编程张无忌
2021/06/24
4860
LeetCode 198. 打家劫舍
https://leetcode-cn.com/problems/house-robber/
freesan44
2021/11/14
1570
LeetCode 198. 打家劫舍
力扣每日一刷(2023.9.15)
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
用户11097514
2024/05/30
1310
力扣每日一刷(2023.9.15)
leetcode刷题(93)——213. 打家劫舍 II
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
老马的编程之旅
2022/06/22
2460
leetcode刷题(93)——213. 打家劫舍 II
LeetCode198. 打家劫舍
这是典型的动态规划问题。要想得到最优策略,就得在每个选择时刻最出最优决策。选择产生状态,合并状态得到结果。 开始认为,求最优选择时,只计算某一个选择。导致不知道怎么得出某一个。后来发现,应该把所有选择都计算,得到多个状态,取最优的状态。
Yuyy
2022/06/28
1500
相关推荐
画解算法:198. 打家劫舍
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验