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

打家劫舍3

news 来源：原创 2025/7/6 13:01:47

今天和打家讲一下打家劫舍3

题目：

题目链接：337. 打家劫舍 III - 力扣（LeetCode）

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为root。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额。

示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

代码：

class Solution {#define x first#define y second typedef pair<int,int> PII;
public:int rob(TreeNode* root) {if(!root) return 0;auto t =dfs(root);int ans=max(t.x,t.y);return ans;}inline  PII dfs(TreeNode* u){//pair<tou,butou>if(!u) return {0,0};int stolen=u->val;PII l = dfs(u->left);PII r = dfs(u->right);stolen +=l.y+r.y ;int nostolen=0;if (l.x>l.y)  nostolen=l.x;else nostolen =l.y;if (r.x>r.y)  nostolen +=r.x;else nostolen +=r.y;PII t={stolen , nostolen};return t;}
};

运行效率：

宏定义与类型别名:

#define x first    // 用 x 表示 pair 的 first（偷当前节点的最大值）
#define y second   // 用 y 表示 pair 的 second（不偷当前节点的最大值）
typedef pair<int, int> PII;

PII 是一个二元组，存储两个状态：

first（x）：偷当前节点时的最大收益。
second（y）：不偷当前节点时的最大收益。

主函数 rob:

若树为空，直接返回0。

调用dfs递归计算根节点的两种状态，返回较大值。

int rob(TreeNode* root) {if (!root) return 0;auto t = dfs(root);return max(t.x, t.y); // 最终结果取根节点偷或不偷的最大值
}

递归函数 dfs:

PII dfs(TreeNode* u) {if (!u) return {0, 0}; // 空节点返回 {0,0}int stolen = u->val;   // 偷当前节点PII l = dfs(u->left);  // 递归左子树PII r = dfs(u->right); // 递归右子树stolen += l.y + r.y;   // 偷当前节点时，左右子节点必须不偷// 不偷当前节点时，左右子节点可偷或不偷（取各自最大值相加）int nostolen = max(l.x, l.y) + max(r.x, r.y); return {stolen, nostolen}; // 返回当前节点的两种状态
}

偷当前节点（stolen）：
当前节点的值 + 左子节点不偷的最大值（l.y） + 右子节点不偷的最大值（r.y）。
不偷当前节点（nostolen）：
左子节点偷或不偷的最大值（max(l.x, l.y)） + 右子节点偷或不偷的最大值（max(r.x, r.y)）。

动态规划逻辑:

状态定义:

代码通过后序遍历 + 动态规划实现，每个节点返回两个状态：

stolen（偷当前节点的最大收益）
not_stolen（不偷当前节点的最大收益）
最终取根节点的两种状态的最大值。

对每个节点 u，定义两个状态：

stolen（偷 u 时的最大收益）。

nostolen（不偷 u 时的最大收益）。

状态转移：

偷当前节点：
不能偷子节点，因此收益为：

stolen=u.val+left.y+right.ystolen=u.val+left.y+right.y

不偷当前节点：
子节点可自由选择偷或不偷，取最大值相加：

nostolen=max⁡(left.x,left.y)+max⁡(right.x,right.y)nostolen=max(left.x,left.y)+max(right.x,right.y)

递归过程：

从叶子节点向上递推，确保每个节点的状态仅依赖子节点的状态。

示例分析:

假设二叉树如下：

     3/ \2   3\   \ 3   1

叶子节点（值为3和1的节点）：

stolen = 3（或1），nostolen = 0（不偷叶子节点时无收益）。

中间节点（值为2的节点）：

偷：2 + 0（左子不偷） + 0（右子不偷） = 2。
不偷：max(0, 3)（左子偷或不偷的最大值） + 0 = 3。

根节点（值为3）：

偷：3 + 3（左子不偷） + 1（右子不偷） = 7。
不偷：max(2, 3)（左子状态） + max(3, 1)（右子状态） = 3 + 3 = 6。

最终结果：max(7, 6) = 7。

关键点：

确保子节点状态传递正确，尤其是“不偷当前节点”时，子节点可自由选择偷或不偷。
后序遍历确保先处理子节点再处理父节点。

打家劫舍3

今天和打家讲一下打家劫舍3 题目： 题目链接：337. 打家劫舍 III - 力扣（LeetCode） 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为root。除了 root 之外，每栋房子有且只有一个“父“…...

编程日记 2025/7/6 13:01:47

第三个Qt开发实例:利用之前已经开发好的LED驱动在Qt生成的界面中控制LED2的亮和灭

前言上一篇博文 https://blog.csdn.net/wenhao_ir/article/details/145459006 中，我们是直接利用GPIO子系统控制了LED2的亮和灭，这篇博文中我们利用之前写好的LED驱动程序在Qt的生成的界面中控制LED2的亮和灭。之前已经在下面两篇博文中实现了LED驱动…...

编程日记 2025/7/6 11:55:57

归一化与伪彩：LabVIEW图像处理的区别

在LabVIEW的图像处理领域，归一化（Normalization）和伪彩（Pseudo-coloring）是两个不同的概念，虽然它们都涉及图像像素值的调整，但目的和实现方式截然不同。归一化用于调整像素值的范围&#xff0c…...

编程日记 2025/7/2 11:01:54

DeepSeek-V2 论文解读：混合专家架构的新突破

论文链接：DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Model 目录一、引言二、模型架构（一）多头部潜在注意力（MLA）：重塑推理效率（二）DeepSeekM…...

编程日记 2025/7/6 10:31:06

基于布谷鸟算法实现率定系数的starter

布谷鸟算法（Cuckoo Search, CS）是一种基于群体智能的优化算法，灵感来源于布谷鸟的繁殖行为以及宿主鸟发现外来蛋的概率。该算法由 Xin-She Yang 和 Suash Deb 在2009年提出。它结合了莱维飞行（Lvy flight）这一随机漫步…...

编程日记 2025/6/28 13:23:30

Java之自定义注解

介绍：在Java中，自定义注解是通过 interface 关键字定义的。注解是一种元数据，可以附加到类、方法、字段等代码元素上，用于提供额外的信息或配置。 1. 自定义注解的基本语法使用 interface 关键字定义注解，注解中可以…...

编程日记 2025/7/1 19:51:44

SpringCloud面试题----Nacos和Eureka的区别

功能特性服务发现 Nacos：支持基于 DNS 和 RPC 的服务发现，提供了更为灵活的服务发现机制，能满足不同场景下的服务发现需求。Eureka：主要基于 HTTP 的 RESTful 接口进行服务发现，客户端通过向 Eureka Server 发送 HT…...

编程日记 2025/7/3 18:42:32

1、prometheus配置大盘 kube-prometheus-stack 定义 dashboard https://stackoverflow.com/questions/77271449/persist-grafana-dashboard-on-kube-prometheus-and-expose-itAlso to persist dashboards to outlive pod deletion follow the below steps: Create your cust…...

编程日记 2025/7/3 0:49:48

记录 | WPF创建和基本的页面布局

目录前言一、创建新项目注意注意点1注意点2 解决方案名称和项目名称二、布局2.1 Grid2.1.1 RowDefinitions 行分割2.1.2 Row & Column 行列定位区分 2.1.3 ColumnDefinitions 列分割 2.2 StackPanel2.2.1 Orientation 修改方向三、模板水平布局【Grid中套StackPanel】中…...

编程日记 2025/7/4 11:42:49

git代理设置

在 Git 中，可以通过以下命令查看当前设置的代理配置： 查看 HTTP 代理 git config --get http.proxy查看 HTTPS 代理 git config --get https.proxy查看全局代理设置如果你设置了全局代理，可以通过以下命令查看： git config …...

编程日记 2025/7/6 11:45:12

使用 Axios ——个人信息修改与提示框实现

目录详细介绍：个人信息设置与修改页面实现 1. HTML 结构 2. CSS 样式 3. JavaScript 核心逻辑 a. 信息渲染与表单提交 b. 头像上传与预览 4. 功能详解 5. 总结提示： 这段代码展示了如何创建一个简单的个人信息设置页面，包含用户个…...

编程日记 2025/6/28 12:07:15

(done) openMP学习 (Day11: 可怕的东西:内存模型,Atomics,Flush(Pairwise同步))

url: https://dazuozcy.github.io/posts/introdution-to-openmp-intel/#19-%E6%8A%80%E8%83%BD%E8%AE%AD%E7%BB%83%E9%93%BE%E8%A1%A8%E5%92%8Copenmp 这一节介绍了一些概念，包括 OpenMP 内存模型，串行一致性的概念，以及 Flush 操作&#xff…...

编程日记 2025/7/6 12:03:35

docker数据持久化的意义

Docker 数据持久化是指在 Docker 容器中保存的数据不会因为容器的停止、删除或重启而丢失。Docker 容器本身是临时性的，默认情况下，容器内的文件系统是临时的，容器停止或删除后，其中的数据也会随之丢失。为了确保重要数据&#xf…...

编程日记 2025/7/6 12:14:54

【漫话机器学习系列】084.偏差和方差的权衡（Bias-Variance Tradeoff）

偏差和方差的权衡（Bias-Variance Tradeoff） 1. 引言在机器学习模型的训练过程中，我们常常面临一个重要的挑战：如何平衡偏差（Bias） 和方差（Variance），以提升模型的泛…...

编程日记 2025/6/30 7:04:59

android的Compose 简介

Jetpack Compose 简介 Jetpack Compose 是 Android 官方推出的声明式 UI 工具包，用于替代传统 XML 布局，简化界面开发流程。它基于 Kotlin 语言，通过函数式编程实现高效、灵活的 UI 构建，支持实时预览和更直观的状态管理。优势…...

编程日记 2025/7/6 12:19:30

git学习

报错504：代理有问题查看代理： 法1 export | grep proxy 法2 env | grep xxx设置代理HTTPS_PROXY为空： export HTTPS_PROXY重进入git bash，HTTPS_PROXYxxx，又出现了有效的办法无效的办法： #取消htt…...

编程日记 2025/7/2 12:58:47

Spring Boot 对接深度求索接口实现知识问答功能

Spring Boot 对接深度求索接口实现知识问答功能一、概述本文将详细介绍如何使用 Spring Boot 对接深度求索（DeepSeek）接口，实现知识问答功能。深度求索是一个强大的自然语言处理平台，提供多种 API 接口，包括知识问…...

编程日记 2025/7/2 10:13:16

探索Scikit-learn：Python中的机器学习宝库

探索Scikit-learn：Python中的机器学习宝库引言在数据科学和机器学习的世界中，Python无疑是最受欢迎的编程语言之一。而在Python的众多机器学习库中，Scikit-learn无疑是最闪耀的明星之一。Scikit-learn是一个开源的Python库，它…...

编程日记 2025/6/30 1:31:07

活动预告 | Power Hour: Copilot 引领商业应用的未来

课程介绍智能化时代，商业应用如何实现突破？微软全球副总裁 Charles Lamanna 将为您深度解析，剖析其中关键因素。在本次线上研讨会中，Charles Lamanna 将分享他在增强商业运营方面的独到见解与实战策略，深度解读商业…...

编程日记 2025/7/6 12:08:15

MIT6.824 Lecture 2-RPC and Threads Lecture 3-GFS

Lecture 2-RPC and Threads Go语言在多线程、同步，还有很好用的RPC包《Effective Go》线程是实现并发的重要工具在分布式系统里关注多线程的原因： I/O concurrencyParallelismConvenience Thread challenges 用锁解决race问题 Coordination channel…...

编程日记 2025/7/6 12:26:48

MariaDB MaxScale实现mysql8读写分离

1.MaxScale 是干什么的？ MaxScale是maridb开发的一个mysql数据中间件，其配置简单，能够实现读写分离，并且可以根据主从状态实现写库的自动切换，对多个从服务器能实现负载均衡。 2.MaxScale 实验环境中间件192.168.12…...

编程日记 2025/7/6 12:35:49

Linux之Http协议分析以及cookie和session

Linux之Http协议分析以及cookie和session 一.分析请求行与响应行1.1请求行1.1.1资源的URL路径1.1.2常见的方法1.2响应行二.cookie和session2.1cookie2.2session 一.分析请求行与响应行在我们简单了解了请求和响应的格式以及模拟实现了请求和响应后我们已经可以通过网页来访问…...

编程日记 2025/7/6 12:29:32

Python Pandas（5）：Pandas Excel 文件操作

Pandas 提供了丰富的 Excel 文件操作功能，帮助我们方便地读取和写入 .xls 和 .xlsx 文件，支持多表单、索引、列选择等复杂操作，是数据分析中必备的工具。操作方法说明读取 Excel 文件pd.read_excel()读取 Excel 文件，返回 DataF…...

编程日记 2025/7/6 13:00:45

iOS主要知识点梳理回顾-3-运行时

运行时（runtime） 运行时是OC的重要特性，也是OC动态性的根本支撑。动态，如果利用好了，扩展性就很强。当然了，OC的动态性只能算是一个一般水平。与swift、java这种强类型校验的语言相比，OC动态性很…...

编程日记 2025/7/6 5:23:24

[渗透测试]热门搜索引擎推荐— — shodan篇

[渗透测试]热门搜索引擎推荐— — shodan篇免责声明：本文仅用于分享渗透测试工具，大家使用时，一定需要遵守相关法律法规。除了shodan，还有很多其他热门的，比如：fofa、奇安信的鹰图、钟馗之眼等&#xff0…...

编程日记 2025/7/5 21:25:47

java-初识List

List： List 是一个接口，属于 java.util 包，用于表示有序的元素集合。List 允许存储重复元素，并且可以通过索引访问元素。它是 Java 集合框架（Java Collections Framework）的一部分特点： 有序…...

编程日记 2025/7/4 5:55:02

ElasticSearch集群因索引关闭重打开导致飘红问题排查

背景某组件向 ElasticSearch 写入数据，从最近某一天开始写入速度变慢，数据一直有积压。推测是 ElasticSearch 集群压力导致的，查看 ElasticSearch 集群状态，发现集群确实处于 red 状态。本文记录 ElasticSearch 集群因索引关闭…...

编程日记 2025/7/6 6:13:21

idea 如何使用deepseek 保姆级教程

1.安装idea插件codegpt 2.注册deepseek并生成apikey deepseek 开发平台： DeepSeek 3.在idea进行codegpt配置打开idea的File->Settings->Tools->CodeGPT->Providers->Custom OpenAI Chat Completions的URL填写 https://api.deepseek…...

编程日记 2025/7/2 21:21:22

【大模型】硅基流动对接DeepSeek使用详解

目录一、前言二、硅基流动介绍 2.1 硅基流动平台介绍 2.1.1 平台是做什么的 2.2 主要特点与功能 2.2.1 适用场景三、硅基流动快速使用 3.1 账户注册 3.2 token获取 3.2.1 获取token技巧四、Cherry-Studio对接DeepSeek 4.1 获取 Cherry-Studio 4.2 Cherry-Stud…...

编程日记 2025/7/6 11:47:11

机器学习数学基础：14.矩阵的公式

1. 操作顺序可交换对于矩阵 A A A，若存在两种运算 ? ? ?和 ? ? ?，使得 ( A ? ) ? ( A ? ) ? (A^{?})^{?}\ (A^{?})^{?} (A?)? (A?)?，这意味着这两种运算的顺序可以交换。由此我们得到以下三个重要等式： ( A …...

编程日记 2025/7/5 22:46:28

t113-qt

修改QT配置: # # qmake configuration for building with arm-linux-gnueabi-g ## MAKEFILE_GENERATOR UNIX # CONFIG incremental # QMAKE_INCREMENTAL_STYLE sublib# include(../common/linux.conf) # include(../common/gcc-base-unix.conf) # inc…...

编程日记 2025/7/6 12:39:06

SQL自学，mysql从入门到精通 --- 第 14天，主键、外键的使用

1.主键 PRIMARY KEY 主键的使用字段值不允许重复，且不允许赋NULL值创建主键 root@mysqldb 10:11: [d1]> CREATE TABLE t3(-> name varchar(10) PRIMARY KEY,-> age int,-> class varchar(8)-> ); Query OK, 0 rows affected (0.01 sec)root@mysqldb 10:…...

编程日记 2025/7/6 11:50:05

整合 Redis 分布式锁：从数据结构到缓存问题解决方案

引言在现代分布式系统中，Redis 作为高性能的键值存储系统，广泛应用于缓存、消息队列、实时计数器等多种场景。然而，在高并发和分布式环境下，如何有效地管理和控制资源访问成为一个关键问题。Redis 分布式锁正是为了解决这一问题…...

编程日记 2025/7/2 19:43:53

ASP.NET Core WebSocket、SignalR

目录 WebSocket SignalR SignalR的基本使用 WebSocket WebSocket基于TCP协议，支持二进制通信，双工通信。性能和并发能力更强。WebSocket独立于HTTP协议，不过我们一般仍然把WebSocket服务器端部署到Web服务器上，因为可以借助HT…...

编程日记 2025/6/30 19:51:22

array_walk. array_map. array_filter

1. array_walk 函数 array_walk 用于遍历数组并对每个元素执行回调函数。它不会受到数组内部指针位置的影响，会遍历整个数组。回调函数接收的前两个参数分别是元素的值和键名，如果有第三个参数，则数组所有的值都共用这个参数。示例代码&am…...

编程日记 2025/7/6 12:49:38

解锁国内主流前端与后端框架

前端框架大揭秘在当今的 Web 开发领域，前端框架的地位愈发举足轻重。随着用户对 Web 应用交互性和体验性要求的不断攀升，前端开发不再仅仅是简单的页面布局与样式设计，更需要构建复杂且高效的用户界面。前端框架就像是一位得力助手&#xf…...

编程日记 2025/7/3 21:24:55

Nginx进阶篇 - nginx多进程架构详解

文章目录 1. nginx的应用特点2. nginx多进程架构2.1 nginx多进程模型2.2 master进程的作用2.3 进程控制2.4 worker进程的作用2.5 worker进程处理请求的过程2.6 nginx处理网络事件 1. nginx的应用特点 Nginx是互联网企业使用最为广泛的轻量级高性能Web服务器，其特点是…...

编程日记 2025/7/2 7:25:41

【PDF提取内容】如何批量提取PDF里面的文字内容，把内容到处表格或者批量给PDF文件改名，基于C++的实现方案和步骤

以下分别介绍基于 C 批量提取 PDF 里文字内容并导出到表格，以及批量给 PDF 文件改名的实现方案、步骤和应用场景。批量提取 PDF 文字内容并导出到表格应用场景文档数据整理：在处理大量学术论文、报告等 PDF 文档时，需要提取其中的关键信…...

编程日记 2025/7/6 12:13:03

HTML之CSS定位、浮动、盒子模型

HTML之CSS定位、浮动、盒子模型定位 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document<…...

编程日记 2025/7/2 15:26:37

【Java基础】为什么不支持多重继承？方法重载和方法重写之间区别、Exception 和 Error 区别？

Hi~！这里是奋斗的明志，很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~~ 🌱🌱个人主页：奋斗的明志 🌱🌱所属专栏：Java基础面经 📚本系列文章为个…...

编程日记 2025/7/3 10:46:18

使用scoop 下载速度慢怎么办

在国内使用 Scoop 下载速度慢是一个常见问题，主要是因为 Scoop 默认的软件源（bucket）和下载服务器通常位于国外。以下是一些提高下载速度的方法： 1. 更换 Scoop 镜像源（Bucket 镜像）： 原理&…...

编程日记 2025/7/2 10:00:10

使用Redis解决使用Session登录带来的共享问题

在学习项目的过程中遇到了使用Session实现登录功能所带来的共享问题，此问题可以使用Redis来解决，也即是加上一层来解决问题。接下来介绍一些Session的相关内容并且采用Session实现登录功能（并附上代码），进行分析其存在…...

编程日记 2025/7/3 13:38:04

OnlyOffice docker 运行（详细）

下载镜像推荐使用 GitHub Action 方式下载： Action 地址：https://github.com/Shixuebin/DockerTarBuilder 教程地址：https://www.bilibili.com/video/BV1EZ421M7mL/ docker 镜像安装 docker load -i xxx.tar镜像运行 docker run -i -t -…...

编程日记 2025/7/3 2:31:17

CNN 卷积神经网络处理图片任务 | PyTorch 深度学习实战

前一篇文章，学习率调整策略 | PyTorch 深度学习实战本系列文章 GitHub Repo: https://github.com/hailiang-wang/pytorch-get-started CNN 卷积神经网络 CNN什么是卷积工作原理深度学习的卷积运算提取特征不同特征核的效果比较卷积核感受野共享权重池化示例源码 …...

编程日记 2025/7/2 5:53:58

自动驾驶数据集三剑客：nuScenes、nuImages 与 nuPlan 的技术矩阵与生态协同

目录 1、引言 2、主要内容 2.1、定位对比：感知与规划的全维覆盖 2.2、数据与技术特性对比 2.3、技术协同：构建全栈研发生态 2.4、应用场景与评估体系 2.5、总结与展望 3、参考文献 1、引言随着自动驾驶技术向全栈化迈进，Motional 团…...

编程日记 2025/7/1 17:30:12

02.07 TCP服务器与客户端的搭建

一.思维导图二.使用动态协议包实现服务器与客户端 1. 协议包的结构定义首先，是协议包的结构定义。在两段代码中，pack_t结构体都被用来表示协议包： typedef struct Pack {int size; // 记录整个协议包的实际大小enum Type type; …...

编程日记 2025/7/1 21:18:57

基于机器学习时序库pmdarima实现时序预测

目录一、Pmdarima实现单变量序列预测1.1 核心功能与特性1.2 技术优势对比1.3 python案例1.3.1 时间序列交叉验证1.3.1.1 滚动交叉验证1.3.1.2 滑窗交叉验证时间序列相关参考文章： 时间序列预测算法—ARIMA 基于VARMAX模型的多变量时序数据预测基于机器学习时序库…...

编程日记 2025/7/1 16:16:42

计算机视觉的研究方向、发展历程、发展前景介绍

以下将分别从图像分类、目标检测、语义分割、图像分割（此处应主要指实例分割）四个方面，为你介绍研究生人工智能计算机视觉领域的应用方向、发展历程以及发展前景。文章目录 1.图像分类应用方向发展历程发展前景 2.目标检测应用方向发展历程…...

编程日记 2025/7/5 4:01:39

NLP_[2]-认识文本预处理

文章目录 1 认识文本预处理1 文本预处理及其作用2. 文本预处理中包含的主要环节2.1 文本处理的基本方法2.2 文本张量表示方法2.3 文本语料的数据分析2.4 文本特征处理2.5数据增强方法2.6 重要说明 2 文本处理的基本方法1. 什么是分词2 什么是命名实体识别3 什么是词性标注 1 认…...

编程日记 2025/7/6 2:44:53

单硬盘槽笔记本更换硬盘

背景本人的笔记本电脑只有一个硬盘槽，而且没有M.2的硬盘盒，只有一个移动硬盘旧硬盘：512G 新硬盘：1T 移动硬盘：512G 参考链接：https://www.bilibili.com/video/BV1iP41187SW/?spm_id_from333.1007.t…...

编程日记 2025/7/5 23:30:16

题目：

代码：

动态规划逻辑:

示例分析:

相关文章：