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

LeetCode337. 打家劫舍III

// 很好的一道题目,既考察递归又考察动归
// 这个版本超时了,原因是暴搜
// 很显然这里使用的是前序,那是不是应该考虑后序?public int rob(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return root.val;}if (root.left != null && root.right != null) {return Math.max(rob(root.left) + rob(root.right), root.val + rob(root.left.left) + rob(root.left.right) + rob(root.right.left) + rob(root.right.right));}if (root.left != null) {return Math.max(rob(root.left) + rob(root.right), root.val + rob(root.left.left) + rob(root.left.right));}return Math.max(rob(root.left) + rob(root.right), root.val + rob(root.right.left) + rob(root.right.right));}

上面的代码其实非常的丑陋,就算暴搜也不应该这样写,而是这样

public int rob(TreeNode root) {if (root == null)return 0;int money = root.val;if (root.left != null) {money += rob(root.left.left) + rob(root.left.right);}if (root.right != null) {money += rob(root.right.left) + rob(root.right.right);}return Math.max(money, rob(root.left) + rob(root.right));}

但这题说到底是树形DP题目,最优解法应该是使用DP,如下

    public int rob(TreeNode root) {int[] res = robHelper(root);return Math.max(res[0], res[1]); }private int[] robHelper(TreeNode root) {int[] res = new int[2];if (root == null) {return res;}int[] left = robHelper(root.left);int[] right = robHelper(root.right);// 重点:root不偷,下面的结点一定都是偷吗// 分为左右结点,像case1:2偷值为2,不偷为3// 如果root不偷,下面的左右都偷反而不一定是最大值// root不偷,下面的结点有偷与不偷的权利,根据利益最大化选择偷与不偷// 但root偷,下面的结点一定不能偷// res[0] = left[1] + right[1];res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);res[1] = root.val + left[0] + right[0];return res;}

相关文章:

LeetCode337. 打家劫舍III

// 很好的一道题目,既考察递归又考察动归 // 这个版本超时了,原因是暴搜 // 很显然这里使用的是前序,那是不是应该考虑后序?public int rob(TreeNode root) {if (root null) {return 0;}if (root.left null && root.rig…...

python基础(二) 包和import

包的创建 文件创建命令 在 Django 中,python manage.py startapp first_app 这一行命令的作用是创建一个新的应用(app),名为 first_app。在 Django 项目中,"app" 是实现某些功能模块的单独部分&#xff0c…...

选址模型 | 基于混沌模拟退火粒子群优化算法的电动汽车充电站选址与定容(Matlab)

目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 基于混沌模拟退火粒子群优化算法的电动汽车充电站选址与定容(Matlab) 问题建模:首先,需要将电动汽车充电站选址与定容问题进行数学建模,确定目标函数和约束…...

WPF入门教学十 资源与字典

在WPF(Windows Presentation Foundation)中,资源与字典是用于管理和重用UI元素的重要机制。它们不仅有助于保持XAML代码的整洁,还能提升应用程序的性能和可维护性。以下是关于WPF资源与字典的详细说明: 静态资源与动态…...

Ubuntu20.04配置NVIDIA+CUDA12.2+CUDNN【附所有下载资源】【亲测有效】【非常详细】

Ubuntu20.04 安装 cudatookit 12.2 cudnn 安装_ubuntu安装cuda toolkit-CSDN博客【最新】cuDNN在CUDA11.7Ubuntu20.04下的安装及卸载_cuda11.7对应的cudnn-CSDN博客...

Golang | Leetcode Golang题解之第424题替换后的最长重复字符

题目: 题解: func characterReplacement(s string, k int) int {cnt : [26]int{}maxCnt, left : 0, 0for right, ch : range s {cnt[ch-A]maxCnt max(maxCnt, cnt[ch-A])if right-left1-maxCnt > k {cnt[s[left]-A]--left}}return len(s) - left }f…...

软考高级:系统安全 -区块链特点:去中心化、开放性、自治性、安全性、匿名性

讲解 生活化例子 想象一下,你和朋友们玩一个共享账本的游戏。每个人都可以在账本上记账,没人可以单独改动账本,大家都可以随时查看账本内容,也不用再信任某个单独的人来管理账本。这就类似于区块链的工作原理。 概念讲解 去中…...

Pandas 数据分析入门详解

今日内容大纲介绍 DataFrame读写文件 DataFrame加载部分数据 DataFrame分组聚合计算 DataFrame常用排序方式 1.DataFrame-保存数据到文件 格式 df对象.to_数据格式(路径) ​ # 例如: df.to_csv(data/abc.csv) 代码演示 如要保存的对象是计算的中间结果,或者以…...

【网络】高级IO——epoll版本TCP服务器初阶

目录 前言 一,epoll的三个系统调用接口 1.1.epoll_create函数 1.1.1.epoll_create函数干了什么 1.2. epoll_ctl函数 1.2.1.epoll_ctl函数函数干了什么 1.3.epoll_wait函数 1.3.1.epoll_wait到底干了什么 1.4.epoll的工作过程中内核在干什么 二,…...

xml中的转义字符

文章目录 xml中的转义字符 xml中的转义字符 &amp;对应的字符是& <对应的字符是< >对应的字符是> &quot;对应的字符是" &apos;对应的字符是转义的实体引用虽然简单易用&#xff0c;但是需要记忆&#xff0c;而且如果字符串中包含大量的特殊字…...

Webpack:现代前端项目的强大打包工具

在现代前端开发中&#xff0c;随着应用的复杂性不断提高&#xff0c;我们需要一种工具来管理项目的依赖、优化代码结构并打包资源文件。Webpack 就是这样一个强大的打包工具&#xff0c;它为前端开发者提供了灵活、强大且可扩展的功能。本文将介绍 Webpack 的基本概念、安装与使…...

以root用户登陆ubuntu的桌面环境

去我的个人博客观看&#xff0c;观感更佳哦&#xff0c;&#x1f619;&#x1f619; 前言 在学习Linux的时候&#xff0c;经常都需要使用sudo权限来对配置文件进行修改&#xff0c;常用的方法就是用vim编辑器在命令行界面进行修改&#xff0c;比如sudo vim /etc/profile&#…...

《系统架构设计师教程(第2版)》第17章-通信系统架构设计理论与实践-04-其他网络架构(存储网络架构、软件定义网络架构)

文章目录 1. 存储网络架构1.1 网络连接存储 (NAS)1.2 存储区域网络&#xff08;SAN&#xff09; 2. 软件定义网络架构2.1 软件定义网络&#xff08;SDN&#xff09;2.2 SDN架构2.3 相关技术2.3.1 控制平面技术2.3.2 数据平面技术1&#xff09; 硬件处理方式4&#xff09; 软件处…...

大话Python|基础语法(上)

一、单行注释 以下代码输出一个Hello World&#xff01;字符串 在Python代码中&#xff0c;注释会自动被Python解析器忽略 print(Hello World) 二、多行注释 在Python代码中&#xff0c;注释一共有两种形式&#xff1b; 1、单行注释&#xff1a;注释的内容只有一行 2、多行…...

crosscrossover24支持的游戏有那些

CrossOver刚刚更新了24版本&#xff0c;支持《地平线零之曙光》、《以撒的结合&#xff1a;重生》等游戏。一起来看看它有哪些更新吧&#xff01;之前买过23版的用户可以在1年之内免费升级哦&#xff0c;点击这里查看升级教程。 一、功能优化 - 更新 Wine 至最新的稳定版 Wine …...

如何免费调用GPT API进行自然语言处理

在当今这个信息爆炸的时代&#xff0c;自然语言处理&#xff08;NLP&#xff09;技术正逐步渗透到我们生活的各个方面&#xff0c;从智能客服到内容创作&#xff0c;无一不彰显着其强大的应用价值。而GPT&#xff08;Generative Pre-trained Transformer&#xff09;作为NLP领域…...

vue无感刷新Token并重新请求

vue 拦截器拦截401重新请求Token 无感刷新Token 之后重新请求报401的接口 instance.interceptors.response.use(async (response) > {let { data } response;if (data.code 401 || data.code 403) {return await handleExpiredToken(response.config);}if (data.code ! …...

C++和OpenGL实现3D游戏编程【连载10】——纹理的半透明显示

1、本节实现的内容 上一节课我们讲到了图片的镂空显示,它能在显示图片时去除指定颜色的背景,那么这节课我们来说一下图片的半透明显示效果,半透明效果能给画面带来更高质量的提升,使图片显示的更自然,产生更真实的效果。下面是一个气泡向上漂浮的效果。 气泡效果 2、非纹…...

50页PPT麦肯锡精益运营转型五步法

读者朋友大家好&#xff0c;最近有会员朋友咨询晓雯&#xff0c;需要《 50页PPT麦肯锡精益运营转型五步法》资料&#xff0c;欢迎大家下载学习。 知识星球已上传的资料链接&#xff1a; 企业架构 企业架构 (EA) 设计咨询项目-企业架构治理(EAM)现状诊断 105页PPTHW企业架构设…...

Fyne ( go跨平台GUI )中文文档-小部件 (五)

本文档注意参考官网(developer.fyne.io/) 编写, 只保留基本用法 go代码展示为Go 1.16 及更高版本, ide为goland2021.2 这是一个系列文章&#xff1a; Fyne ( go跨平台GUI )中文文档-入门(一)-CSDN博客 Fyne ( go跨平台GUI )中文文档-Fyne总览(二)-CSDN博客 Fyne ( go跨平台GUI…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...