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

代码随想录算法训练营第四十七天丨198. 打家劫舍、​ 213. 打家劫舍 II​、337. 打家劫舍 III

198. 打家劫舍

自己的思路:

初始化两个dp数组,dp[i][0]表示不偷第i户,在0-i户可以偷到的最大金额,dp[i][1]表示偷i户在0-i户可以偷到的最大金额。

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)dp = [[0] * 2 for _ in range(n)]dp[0][1] = nums[0]for i in range(1, n):dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])dp[i][1] = dp[i - 1][0] + nums[i]return max(dp[n - 1][0], dp[n - 1][1])

优化:

有一点臃肿,可以优化。dp[i][1]实际上跟dp[i-1][1]就没啥关系,直接把dp数组初始化成一维的就行了。

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)if n == 1:return nums[0]if n == 2:return max(nums[0], nums[1])dp = [0] * ndp[0] = nums[0]dp[1] = max(nums[0], nums[1])for i in range(2, n):dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])return dp[n - 1]

更优化:

想起了斐波那契数列...

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)if n == 1:return nums[0]if n == 2:return max(nums[0], nums[1])prev = nums[0]cur = max(nums[0], nums[1])for i in range(2, n):prev, cur = cur, max(cur, prev + nums[i])return cur

 213. 打家劫舍 II

还是比较容易想到的,把环展成两个线性的,一个去头一个去尾即可。

class Solution:def rob(self, nums: List[int]) -> int:n = len(nums)if n == 1:return nums[0]if n == 2:return max(nums[0], nums[1])def helper(n, nums):dp = [0] * ndp[0] = nums[0]dp[1] = max(nums[0], nums[1])for i in range(2, n):dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])return dp[n - 1]return max(helper(n-1, nums[1:]), helper(n-1, nums[:-1]))

337. 打家劫舍 III

我的思路:

有点类似贪心的最后一题。

一顿操作AC了,中间遗漏了几种情况,修改后正确了。

class Solution:def rob(self, root: Optional[TreeNode]) -> int:def helper(root):if not root.left and not root.right:return 0, root.valelif root.left and root.right:left_without_self, left_with_self = helper(root.left)right_without_self, right_with_self = helper(root.right)return max(left_without_self + right_without_self, left_with_self + right_with_self, left_without_self + right_with_self, left_with_self + right_without_self), left_without_self + right_without_self + root.valelif root.left and not root.right:left_without_self, left_with_self = helper(root.left)return max(left_with_self, left_without_self), left_without_self + root.valelif root.right and not root.left:right_without_self, right_with_self = helper(root.right)return max(right_with_self, right_without_self), right_without_self + root.valreturn max(helper(root))

优化:

终止条件从叶子节点改成空节点,可以将之后的情况全部统一起来。

class Solution:def rob(self, root: Optional[TreeNode]) -> int:def helper(root):if not root:return 0, 0left = helper(root.left)right = helper(root.right)not_include = max(left) + max(right)include = left[0] + right[0] + root.valreturn not_include, includereturn max(helper(root))

带备忘的递归:

class Solution:def rob(self, root: Optional[TreeNode]) -> int:memo = {}def helper(node):if not node:return 0if node in memo:return memo[node]val = node.val# 如果偷当前节点,则不能偷其直接的左右子节点,但可以偷其孙子节点if node.left:val += helper(node.left.left) + helper(node.left.right)if node.right:val += helper(node.right.left) + helper(node.right.right)# 不偷当前节点,可以偷其左右子节点not_steal = helper(node.left) + helper(node.right)# 对于当前节点,选择偷与不偷的最大值result = max(val, not_steal)memo[node] = resultreturn resultreturn helper(root)

今日总结:

自己写能AC,都能get到要点~~~精简的代码还是得看题解。

相关文章:

代码随想录算法训练营第四十七天丨198. 打家劫舍、​ 213. 打家劫舍 II​、337. 打家劫舍 III

198. 打家劫舍 自己的思路: 初始化两个dp数组,dp[i][0]表示不偷第i户,在0-i户可以偷到的最大金额,dp[i][1]表示偷i户在0-i户可以偷到的最大金额。 class Solution:def rob(self, nums: List[int]) -> int:n len(nums)dp […...

龙蜥Anolis 8.4 anck 安装mysql5.7

el8没有用mysql5.7了,镜像里是mysql8。 禁用 sudo dnf remove mysql sudo dnf module reset mysql sudo dnf module disable mysql 修改Yum源 sudo vi /etc/yum.repos.d/mysql-community.repo [mysql57-community] nameMySQL 5.7 Community Server baseurlhttp:…...

【踩坑】修复xrdp无法关闭Authentication Required验证窗口

转载请注明出处:小锋学长生活大爆炸[xfxuezhang.cn] 问题如下,时不时出现,有时还怎么都关不掉,很烦: 解决方法一:命令行输入 dbus-send --typemethod_call --destorg.gnome.Shell /org/gnome/Shell org.gn…...

python学习笔记 - 标准库常量

Python 中有一些内置的常量,它们是一些特殊的值,通常不会改变。以下是其中一些常见的内置常量及其详细解释以及使用示例: True: 表示布尔值真。给 True 赋值是非法的并会引发 SyntaxError。 x True print(x) # 输出&#xff1a…...

视频和音频使用ffmpeg进行合并和分离(MP4)

1.下载ffmpeg 官网地址:https://ffmpeg.org/download.html 2.配置环境变量 此电脑右键点击 属性 - 高级系统配置 -高级 -环境变量 - 系统变量 path 新增 文件的bin路径 3.验证配置成功 ffmpeg -version 返回版本信息说明配置成功4.执行合并 ffmpeg -i 武家坡20…...

02| JVM堆中垃圾回收的大致过程

如果一直在创建对象,堆中年轻代中Eden区会逐渐放满,如果Eden放满,会触发minor GC回收,创建对象的时GC Roots,如果存在于里面的对象,则被视为非垃圾对象,不会被此次gc回收,就会被移入…...

R语言数据可视化之美专业图表绘制指南(增强版):第1章 R语言编程与绘图基础

第1章 R语言编程与绘图基础 目录 第1章 R语言编程与绘图基础前言1.1 学术图表的基本概念1.1.1 学术图表的基本作用1.1.2基本类别1.1.3 学术图表的绘制原则 1.2 你为什么要选择R1.3 安装 前言 这是我第一次在博客里展示学习中国作者的教材的笔记。我选择这本书的依据是作者同时…...

网站添加pwa操作和配置manifest.json后,没有效果排查问题

pwa技术官网:https://web.dev/learn/pwa 应用清单manifest.json文件字段说明:https://web.dev/articles/add-manifest?hlzh-cn Web App Manifest:Web App Manifest | MDN 当网站添加了manifest.json文件后,也引入到html中了&a…...

MongoDB聚合运算符:$cosh

文章目录 语法使用举例双曲余弦值角度双曲余弦值弧度 $cosh聚合运算符用来计算双曲余弦值&#xff0c;返回指定表达式的双曲余弦值。 语法 { $cosh: <expression> }<expression>为可被解析为数值的表达式$cosh返回弧度&#xff0c;使用$radiansToDegrees运算符可…...

Jenkins配置在远程服务器上执行shell脚本(两种方式)

Jenkins配置在远程服务器上执行shell脚本 方式一&#xff1a;通过SSH免密方式执行 说明&#xff1a;Jenkins部署在ServerA&#xff1a;10.1.1.74上&#xff0c;要运行的程序在ServerB&#xff1a;10.1.1.196 分两步 第一步&#xff1a;Linux Centos7配置SSH免密登录 Linux…...

Java+SpringBoot,打造社区疫情信息新生态

✍✍计算机编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java实战 |…...

js ES6判断字符串是否以某个字符串开头或者结尾startsWith、endsWith

1.前言 startsWith&#xff1a;startsWith方法用于检查字符串是否以指定的字符串开头。 endsWith&#xff1a;endsWith方法用于检查字符串是否以指定的字符串结尾。 2.用法示例 const str Hello, world!;console.log(str.startsWith(Hello)); // true console.log(str.starts…...

预研项目完成后小批量验证(技术变更流程)

...

Bert-as-service 实战

参考&#xff1a;bert-as-service 详细使用指南写给初学者-CSDN博客 GitHub - ymcui/Chinese-BERT-wwm: Pre-Training with Whole Word Masking for Chinese BERT&#xff08;中文BERT-wwm系列模型&#xff09; 下载&#xff1a;https://storage.googleapis.com/bert_models/…...

微信小程序(四十七)多个token存储

注释很详细&#xff0c;直接上代码 新增内容&#xff1a; 1.基础存储模板 2.中括号实现变量名匹配 源码&#xff1a; app.js App({//提前声明的变量名token:wx.getStorageSync(toke),refreshToken:wx.getSystemInfoAsync(refreshToken),setToken(key,token){//保存token到全局…...

机器学习(II)--样本不平衡

现实中&#xff0c;样本&#xff08;类别&#xff09;样本不平衡&#xff08;class-imbalance&#xff09;是一种常见的现象&#xff0c;如&#xff1a;金融欺诈交易检测&#xff0c;欺诈交易的订单样本通常是占总交易数量的极少部分&#xff0c;而且对于有些任务而言少数样本更…...

几个好用的 VUE Table

Vue easytable - 功能恰到好处 无学习成本 上手就用Vue good table - UI 清新 功能直给 适合小项目Vxe table - 宝藏级 table 组件 高级功能低调好用 维护频率高tabulator - 元老级 table 组件 高级功能平民化AG Grid - 媲美 Excel 的 Table 组件 能想到的复杂功能它都能做到...

Vue源码系列讲解——实例方法篇【三】(生命周期相关方法)

目录 0. 前言 1. vm.$mount 1.1 用法回顾 1.2 内部原理 2. vm.$forceUpdate 2.1 用法回顾 2.2 内部原理 3. vm.$nextTick 3.1 用法回顾 3.2 JS的运行机制 3.3 内部原理 能力检测 执行回调队列 4. vm.$destory 4.1 用法回顾 4.2 内部原理 0. 前言 与生命周期相关…...

百度SEO工具,自动更新网站的工具

在网站SEO的过程中&#xff0c;不断更新网站内容是提升排名和吸引流量的关键之一。而对于大多数网站管理员来说&#xff0c;频繁手动更新文章并进行SEO优化可能会是一项繁琐且耗时的任务。针对这一问题&#xff0c;百度自动更新文章SEO工具应运而生&#xff0c;它能够帮助网站管…...

供应链|NUS覃含章MS论文解读:数据驱动下联合定价和库存控制的近似方法 (二)

编者按 本次解读的文章发表于 Management Science&#xff0c;原文信息&#xff1a;Hanzhang Qin, David Simchi-Levi, Li Wang (2022) Data-Driven Approximation Schemes for Joint Pricing and Inventory Control Models. https://doi.org/10.1287/mnsc.2021.4212 文章在数…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...