当前位置: 首页 > 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…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

MySQL:分区的基本使用

目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区&#xff08;Partitioning&#xff09;是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分&#xff08;分区&#xff09;可以独立存储、管理和优化&#xff0c;…...

ZYNQ学习记录FPGA(一)ZYNQ简介

一、知识准备 1.一些术语,缩写和概念&#xff1a; 1&#xff09;ZYNQ全称&#xff1a;ZYNQ7000 All Pgrammable SoC 2&#xff09;SoC:system on chips(片上系统)&#xff0c;对比集成电路的SoB&#xff08;system on board&#xff09; 3&#xff09;ARM&#xff1a;处理器…...

Java多线程实现之Runnable接口深度解析

Java多线程实现之Runnable接口深度解析 一、Runnable接口概述1.1 接口定义1.2 与Thread类的关系1.3 使用Runnable接口的优势 二、Runnable接口的基本实现方式2.1 传统方式实现Runnable接口2.2 使用匿名内部类实现Runnable接口2.3 使用Lambda表达式实现Runnable接口 三、Runnabl…...

【汇编逆向系列】六、函数调用包含多个参数之多个整型-参数压栈顺序,rcx,rdx,r8,r9寄存器

从本章节开始&#xff0c;进入到函数有多个参数的情况&#xff0c;前面几个章节中介绍了整型和浮点型使用了不同的寄存器在进行函数传参&#xff0c;ECX是整型的第一个参数的寄存器&#xff0c;那么多个参数的情况下函数如何传参&#xff0c;下面展开介绍参数为整型时候的几种情…...