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

代码随想录算法训练营第52天(动态规划09 ● 198.打家劫舍 ● 213.打家劫舍II ● 337.打家劫舍III

动态规划part09

  • 198.打家劫舍
    • 解题思路
  • 213.打家劫舍II
    • 解题思路
  • 337.打家劫舍III
    • 解题思路

今天就是打家劫舍的一天,这个系列不算难,大家可以一口气拿下。

198.打家劫舍

题目链接: 198.打家劫舍
视频讲解: 198.打家劫舍
文章讲解: 198.打家劫舍

解题思路

递归五部曲

  1. 确定dp数组以及下标的含义
    dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。
  2. 确定递推公式
    dp[i] = dp[i - 2] + nums[i] ,即:第i-1房一定是不考虑的,找出 下标i-2(包括i-2)以内的房屋,最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
  3. dp数组如何初始化
    递推公式的基础就是dp[0] 和 dp[1]
    dp[0] = nums[0],dp[1] = max(nums[0], nums[1]);
  4. 遍历顺序
    从前到后
  5. 举例推导dp数组
// 动态规划
class Solution {public int rob(int[] nums) {if(nums == null || nums.length == 0) return 0;if(nums.length == 1) return nums[0];int[] dp = new int[nums.length];dp[0] = nums[0];dp[1] = Math.max(dp[0], nums[1]);for(int i = 2; i < nums.length; i++){dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[nums.length - 1];}
}

213.打家劫舍II

题目链接: 213.打家劫舍II
视频讲解: 213.打家劫舍II
文章讲解: 213.打家劫舍II

解题思路

对于一个数组,成环的话主要有如下三种情况:
情况一:考虑不包含首尾元素
情况二:考虑包含首元素,不包含尾元素
情况三:考虑包含尾元素,不包含首元素
而情况二 和 情况三 都包含了情况一了,所以只考虑情况二和情况三就可以了。
分析到这里,剩下的和198.打家劫舍就是一样的了。

class Solution {public int rob(int[] nums) {if(nums == null || nums.length == 0) return 0;if(nums.length == 1) return nums[0];return Math.max(robAction(nums, 0, nums.length - 1), robAction(nums, 1, nums.length));}int robAction(int[] nums, int start, int end) {int dp3 = 0;int dp2 = 0;int dp1 = 0;for(int i = start; i < end; i++){dp1 = dp3;dp3 = Math.max(dp1, dp2 + nums[i]);dp2 = dp1;}return dp3;}// 运行没通过 不知道为啥// int robAction(int[] nums, int start, int end) {//     int[] dp = new int[nums.length];//     dp[start] = nums[start];//     dp[start + 1] = Math.max(dp[0], nums[start + 1]);//     for(int i = start + 2; i < end; i++){//         dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);//     }//     return dp[end - 1];// }
}

337.打家劫舍III

题目链接: 337.打家劫舍III
视频讲解: 337.打家劫舍III
文章讲解: 337.打家劫舍III

解题思路

动态规划和二叉树的结合
动态规划其实就是使用状态转移容器来记录状态的变化,这里可以使用一个长度为2的数组,记录当前节点偷与不偷所得到的的最大金钱。
递归三部曲

  1. 确定递归函数的参数和返回值
    长度为2的dp数组
    dp[0]0记录不偷该节点所得到的的最大金钱,dp[1]1记录偷该节点所得到的的最大金钱。
  2. 确定终止条件
    在遍历的过程中,如果遇到空节点的话,很明显,无论偷还是不偷都是0,所以就返回
  3. 确定遍历顺序
    首先明确的是使用后序遍历。 因为要通过递归函数的返回值来做下一步计算。
    通过递归左节点,得到左节点偷与不偷的金钱。
    通过递归右节点,得到右节点偷与不偷的金钱。
  4. 确定单层递归的逻辑
    如果是偷当前节点,那么左右孩子就不能偷,val1 = cur->val + left[0] + right[0]; (如果对下标含义不理解就再回顾一下dp数组的含义)
    如果不偷当前节点,那么左右孩子就可以偷,至于到底偷不偷一定是选一个最大的,所以:val2 = max(left[0], left[1]) + max(right[0], right[1]);
    最后当前节点的状态就是{val2, val1}; 即:{不偷当前节点得到的最大金钱,偷当前节点得到的最大金钱}
  5. 举例推导dp数组
 // 动态规划
class Solution {public int rob(TreeNode root) {int[] res = robAction(root);return Math.max(res[0], res[1]);}int[] robAction(TreeNode root){int res[] = new int[2]; // res[0] 代表不偷时的价值 res[1]代表偷的时候的价值// 终止递归条件if(root == null){return res;}// 后序遍历// 左右int[] left = robAction(root.left);int[] right = robAction(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;}
}

相关文章:

代码随想录算法训练营第52天(动态规划09 ● 198.打家劫舍 ● 213.打家劫舍II ● 337.打家劫舍III

动态规划part09 198.打家劫舍解题思路 213.打家劫舍II解题思路 337.打家劫舍III解题思路 今天就是打家劫舍的一天&#xff0c;这个系列不算难&#xff0c;大家可以一口气拿下。 198.打家劫舍 题目链接&#xff1a; 198.打家劫舍 视频讲解&#xff1a; 198.打家劫舍 文章讲解&…...

微服务篇之负载均衡

一、Ribbon负载均衡流程 二、Ribbon负载均衡策略 1. RoundRobinRule&#xff1a;简单轮询服务列表来选择服务器。 2. WeightedResponseTimeRule&#xff1a;按照权重来选择服务器&#xff0c;响应时间越长&#xff0c;权重越小。 3. RandomRule&#xff1a;随机选择一个可用的服…...

wayland(xdg_wm_base) + egl + opengles 使用FBO渲染到纹理实例(六)

文章目录 前言一、FBO介绍1. FBO 简介2. FBO的关键组成部分3. FBO的基本工作流程4. FBO 实现渲染到纹理5. FBO 实现离屏渲染二、FBO 实现渲染到纹理的代码实例1. egl_wayland_texture3_2.c2. xdg-shell-client-protocol.h 和 xdg-shell-protocol.c3. 编译4. 运行总结参考资料前…...

基于 RisingWave、Instaclustr 和 Apache Superset 对维基百科实时监控

得益于 RisingWave 和 Kafka 等流处理工具&#xff0c; 数据工程师能实时洞察流数据中的重要信息。这能够助力制定决策&#xff0c;并在多个层面改善用户体验&#xff0c;包括推荐系统、金融、物流、汽车、制造业、 IIOT 设备和零售。 在这篇博客中&#xff0c;我们会把 Risin…...

建站用帝国CMS好还是WordPress好

随着互联网的迅猛发展&#xff0c;内容管理系统(CMS)在网站建设中扮演着越来越重要的角色。在众多CMS中&#xff0c;帝国CMS和WordPress因其强大的功能和广泛的用户基础而备受关注。本文将对这两种CMS进行详细比较&#xff0c;分析它们的优势与不足&#xff0c;以便用户能够根据…...

深度学习基础之《TensorFlow框架(2)—图》

一、什么是图结构 1、图包含了一组tf.Operation代表的计算单元对象和tf.Tensor代表的计算单元之间流动的数据 图结构&#xff1a;数据(Tensor) 操作(Operation) 二、图相关操作 1、默认图 通常TensorFlow会默认帮我们创建一张图 查看默认图的两种方法&#xff1a; &#x…...

Web3区块链游戏:创造虚拟世界的全新体验

随着区块链技术的不断发展&#xff0c;Web3区块链游戏正逐渐崭露头角&#xff0c;为玩家带来了全新的虚拟世界体验。传统游戏中的中心化结构和封闭经济体系已经被打破&#xff0c;取而代之的是去中心化的游戏环境和真实所有权的数字资产。本文将深入探讨Web3区块链游戏的特点、…...

单机启动/开机启动SpringBoot服务的正确方式

此操作只针对于测试环境或单机部署的情况下&#xff0c;使用Jenkins自动化部署或docker部署SpringBoot服务请忽略。 SpringBoot单机启动和集群启动的区别&#xff1a; 部署方式&#xff1a;单机启动可以直接运行jar文件或使用IDE启动应用程序&#xff0c;而双机集群启动需要将…...

[C#]winform基于opencvsharp结合CSRNet算法实现低光图像增强黑暗图片变亮变清晰

【算法介绍】 "Conditional Sequential Modulation for Efficient Global Image Retouching" 是一种图像修饰方法&#xff0c;主要用于对图像进行全局的高效调整。该方法基于深度学习技术&#xff0c;通过引入条件向量来实现对图像特征的调制&#xff0c;以达到改善…...

抓包分析 TCP 协议

TCP 协议是在传输层中&#xff0c;一种面向连接的、可靠的、基于字节流的传输层通信协议。 环境准备 对接口测试工具进行分类&#xff0c;可以如下几类&#xff1a; 网络嗅探工具&#xff1a;tcpdump&#xff0c;wireshark 代理工具&#xff1a;fiddler&#xff0c;charles&…...

代码随想录算法训练营day27 | 93.复原IP地址、78.子集、90.子集II

93.复原IP地址 和C不同&#xff0c;使用列表存储已经分割的数据&#xff0c;而不是直接操作字符串。为了使用这个列表搞了老久&#xff0c;主要问题出在&#xff0c;在判断终止条件的时候&#xff0c;path也需要回溯一下 class Solution:def __init__(self):self.result []s…...

RuntimeError: CUDA out of memory.【多种场景下的解决方案】

RuntimeError: CUDA out of memory.【多种场景下的解决方案】 &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;【Matplotlib之旅&#xff1a;零基础精通数据可视化】 &#x1f3c6;&#x1f3c6;关注博主&#xff0c;随时获取更多关于深度学…...

LeetCode刷题| Leetcode 45. 跳跃游戏,1190. 反转每对括号间的子串,781. 森林中的兔子,739. 每日温度

45. 跳跃游戏 题目链接&#xff1a; 45. 跳跃游戏 II - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a;这道题思路不难记&#xff0c;遍历数组每个位置&#xff0c;更新下一次的范围&#xff0c;当当前位置已经在当前范围之外时&#xff0c;步数一定得加一&#xff…...

Redis(03)——发布订阅

基础命令 基于频道 publish channel message&#xff1a;将信号发送到指定的频道pubsub subcommand [argument [argyment]]&#xff1a;查看订阅或发布系统状态subscribe channel [channel]&#xff1a;订阅一个或多个频道的信息unsubscribe [channel [channel]]&#xff1a;退…...

⭐北邮复试刷题LCR 034. 验证外星语词典__哈希思想 (力扣119经典题变种挑战)

LCR 034. 验证外星语词典 某种外星语也使用英文小写字母&#xff0c;但可能顺序 order 不同。字母表的顺序&#xff08;order&#xff09;是一些小写字母的排列。 给定一组用外星语书写的单词 words&#xff0c;以及其字母表的顺序 order&#xff0c;只有当给定的单词在这种外…...

ECMAScript 6+ 新特性 ( 二 )

2.12. class类 ES6 提供了更接近传统语言的写法&#xff0c;引入了 Class&#xff08;类&#xff09;这个概念&#xff0c;作为对象的模板。通过 class 关键字&#xff0c;可以定义类。 ES6 的 class 可以看作只是一个语法糖&#xff0c;它的绝大部分功能ES5 都可以做到&…...

JS游戏项目合集【附源码】

文章目录 一&#xff1a;迷宫小游戏二&#xff1a;俄罗斯方块三&#xff1a;压扁小鸟 一&#xff1a;迷宫小游戏 【迷宫游戏】是一款基于HTML5技术开发的游戏&#xff0c;玩法简单。玩家需要在一个迷宫中找到出口并成功逃脱&#xff0c;本项目还有自动寻路&#xff08;Track&a…...

React中hooks使用限制及保存函数组件状态

React Hooks 的限制主要有两条&#xff1a; 不要在循环、条件或嵌套函数中调用 Hook&#xff1b; 在 React 的函数组件中调用 Hook。 首先&#xff0c;Hooks是一个对象&#xff0c;大致结构如下&#xff1a; const hook: Hook {memoizedState: null,baseState: null,baseQ…...

用git命令来上传项目到GitHub我自己的仓库

目录 在GitHub上创建仓库并使用git命令上传到仓库的步骤如下&#xff1a; 其他操作 怎么退出git/COMMIT_EDITMSG [unix] 相关报错 error: src refspec main does not match any error: failed to push some refs to https://github.com/Liu22Jun16Liang/MyQt error: fail…...

.NET有哪些微服务框架

1.概述 想要对.net的微服务方案进行一下调查&#xff0c;看有什么可选的方案和框架&#xff0c;与spring clound相比.net 创建微服务是相对较麻烦的。 ID名称说明1Service FabricSteeltoe是帮助.NET开发的服务接入Spring Cloud技术栈的官方支持工具。也就是说&#xff0c;微服…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分&#xff1a; 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...

小木的算法日记-多叉树的递归/层序遍历

&#x1f332; 从二叉树到森林&#xff1a;一文彻底搞懂多叉树遍历的艺术 &#x1f680; 引言 你好&#xff0c;未来的算法大神&#xff01; 在数据结构的世界里&#xff0c;“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的&#xff0c;它…...