当前位置: 首页 > news >正文

代码随想录算法训练营第三十九天

LeetCode.198 打家劫舍

题目链接 打家劫舍

题解

class Solution {public int rob(int[] nums) {if(nums.length == 1) return nums[0];int[] dp = new int[nums.length+1];dp[0] = nums[0];dp[1] = Math.max(nums[0],nums[1]);for(int i = 2;i<nums.length;i++){dp[i] = Math.max(dp[i-2] + nums[i],dp[i-1]);}return dp[nums.length-1];}
}

解题思路

这是一个用动态规划解决 “打家劫舍” 问题的代码。

问题背景是:有沿街的房屋,每间房有一定现金,相邻房屋不能同时偷窃(否则报警),要计算不触发警报时能偷到的最高金额。

代码的思路如下:

首先处理边界情况,如果只有一间房屋,那么能偷到的最高金额就是这间房屋的现金数,直接返回即可。

然后定义一个动态规划数组 dp,其中 dp [i] 表示偷窃前 i+1 间房屋(也就是从下标 0 到 i 的房屋)能得到的最高金额。

接着初始化数组的前两个元素:dp [0] 就是第一间房屋的现金数,因为只有这一间房;dp [1] 则是前两间房屋中现金较多的那间的金额,因为不能同时偷相邻的,所以选大的那个。

之后从第三间房屋(下标 2)开始循环计算:对于第 i 间房屋,有两种选择,要么偷这间,那么就不能偷第 i-1 间,此时能得到的金额是偷前 i-2 间的最高金额加上第 i 间的现金;要么不偷这间,那么能得到的金额就是偷前 i-1 间的最高金额。这两种情况取最大值,就是 dp [i] 的值。

最后,数组的最后一个元素 dp [nums.length-1] 就是偷窃所有房屋能得到的最高金额,将其返回。

这个解法的时间复杂度是 O (n),因为只需要遍历一次房屋数组;空间复杂度是 O (n),因为使用了一个长度为 n 的 dp 数组(不过可以优化到 O (1),只需要用两个变量来存储前两个状态即可)。

LeetCode.213 打家劫舍Ⅱ

题目链接 打家劫舍Ⅱ

题解

class Solution {public int rob(int[] nums) {int len = nums.length;if(len == 1) return nums[0];int[] tmpNums = new int[len];for(int i = 0;i<len - 1;i++){tmpNums[i] = nums[i];}    int value1 = rob1(tmpNums);for(int i = 1;i<len;i++){tmpNums[i-1] = nums[i];}int value2 = rob1(tmpNums);return Math.max(value1,value2);}public int rob1(int[] nums) {if(nums.length == 1) return nums[0];int[] dp = new int[nums.length+1];dp[0] = nums[0];dp[1] = Math.max(nums[0],nums[1]);for(int i = 2;i<nums.length;i++){dp[i] = Math.max(dp[i-2] + nums[i],dp[i-1]);}return dp[nums.length-1];}
}

解题思路

这是解决「打家劫舍 II」问题的代码,在原问题基础上增加了一个约束:房屋围成一圈(即第一间和最后一间也视为相邻,不能同时偷窃)。

代码的核心思路是将环形问题转化为两个线性问题:

  1. 不考虑最后一间房,只计算从第一间到倒数第二间的最高金额(value1)
  2. 不考虑第一间房,只计算从第二间到最后一间的最高金额(value2)
  3. 最终结果取这两个值中的较大者

具体实现步骤:

  • 先处理边界情况:如果只有一间房,直接返回该房屋的金额
  • 构造第一个临时数组 tmpNums,包含除最后一间外的所有房屋
  • 调用 rob1 方法计算这个临时数组的最高金额(value1)
  • 重新构造临时数组 tmpNums,包含除第一间外的所有房屋
  • 再次调用 rob1 方法计算这个临时数组的最高金额(value2)
  • 返回 value1 和 value2 中的最大值

其中 rob1 方法就是解决「打家劫舍 I」的动态规划函数:

  • 用 dp [i] 表示前 i+1 间房屋能偷到的最高金额
  • 状态转移方程为:dp [i] = max (dp [i-2] + nums [i], dp [i-1])
  • 即对于第 i 间房,要么偷(加上前 i-2 间的最高金额),要么不偷(取前 i-1 间的最高金额)

通过这种拆分方式,成功将环形约束转化为两个线性问题,从而复用了原问题的解法。

LeetCode.337 打家劫舍III

题目链接 打家劫舍III

题解

class Solution {public int rob(TreeNode root) {int[] res = dfs(root);return Math.max(res[0],res[1]);}public int[] dfs(TreeNode root){int[] res = new int[2];if(root == null) return res;int[] left = dfs(root.left);int[] right = dfs(root.right);res[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);res[1] = root.val + left[0] + right[0];return res;} 
}

解题思路

这是解决「打家劫舍 III」问题的代码,该问题将房屋排列成二叉树结构,约束条件为:不能偷窃相连的节点(父节点和子节点视为相邻,不能同时偷窃),需要计算能偷到的最高金额。

代码采用了深度优先搜索(DFS)结合动态规划的思路,核心是对每个节点考虑两种状态:

  1. 定义返回数组 res,其中:

    • res [0] 表示不偷当前节点时,以该节点为根的子树能偷到的最高金额
    • res [1] 表示偷当前节点时,以该节点为根的子树能偷到的最高金额
  2. 递归处理逻辑:

    • 若当前节点为空,返回两个元素都为 0 的数组
    • 递归计算左子树和右子树的结果(left 和 right 数组)
    • 不偷当前节点时(res [0]):可以偷或不偷左右子节点,取左右子树两种状态的最大值之和
    • 偷当前节点时(res [1]):不能偷左右子节点,金额为当前节点值加上左右子树不偷时的金额之和
  3. 最终结果:根节点两种状态的最大值,即 max (res [0], res [1])

这种解法通过后序遍历方式,从叶子节点向根节点计算,每个节点只需要处理一次,时间复杂度为 O (n)(n 为节点数量),空间复杂度为 O (h)(h 为树的高度,递归栈空间)。

http://www.lryc.cn/news/608726.html

相关文章:

  • 【内容规范】关于标题中【】标记的使用说明
  • 【机器学习③】 | CNN篇
  • k8s日志收集
  • Node.js 操作 MySQL
  • [硬件电路-129]:模拟电路 - 继电器的工作原理、关键指标、常用芯片与管脚定义
  • OSPF知识点整理
  • Flutter 函数的基本使用
  • OpenCV轻松入门_面向python(第一章OpenCV入门)
  • 企业IT管理——集团IT项目实施管理办法模板
  • Linux Deepin深度操作系统应用商店加载失败,安装星火应用商店
  • 学习笔记《区块链技术与应用》第六天 问答 匿名技术 零知识证明
  • 机器翻译的分类:规则式、统计式、神经式MT的核心区别
  • 基于单片机火灾报警系统/防火防盗系统设计
  • 块三角掩码(Block-Triangular Masking)
  • MySQL的创建管理表:
  • Memcached Slab分配器:零碎片的极速内存管理
  • [spring-cloud: 服务发现]-源码解析
  • Day 30:模块和库的导入
  • 风光储综合能源系统双层优化规划设计【MATLAB模型实现】
  • 第九章:了解特殊场景下的redis
  • 控制建模matlab练习07:比例积分控制-③PI控制器的应用
  • Spring 03 Web springMVC
  • ESP32学习-I2C(IIC)通信详解与实践
  • C++:STL中的栈和队列的适配器deque
  • Spring Boot AOP 优雅实现异常重试机制
  • AD方案(OpenLDAP或微软AD)适配信创存在的不足以及可能优化方案
  • Nvidia Orin DK 刷机CUDA TensorRT+硬盘扩容+ROS+Realsense+OpenCV+Ollama+Yolo11 一站式解决方案
  • CUDA杂记--nvcc使用介绍
  • Elastic 9.1/8.19:默认启用 BBQ,ES|QL 支持跨集群搜索(CCS)正式版,JOINS 正式版,集成 Azure AI Foundry
  • Jupyter Notebook 中高效处理和实时展示来自 OpenCV 和 Pillow 的图像数据探究