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

leetcode之打家劫舍

leetcode 198 打家劫舍
leetcode 213 打家劫舍 II
leetcode 337. 打家劫舍 III
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。

示例 1:

输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。
示例 2:

输入:nums = [1,2,3,1]
输出:4
解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 3:

输入:nums = [1,2,3]
输出:3

提示:

1 <= nums.length <= 100
0 <= nums[i] <= 1000

思路,对于打家劫舍 I, 可以转化成动态规划问题求解,对于打家劫舍 II ,首尾认为是相邻,可以转换成调用 打家劫舍 I 中的问题两次,

class Solution:def maxMoney(self, nums):## dp[i][0] 表示到第 i 位置为止,不偷 i 的最大金额,dp[i][1] 表示偷 i 的最大金额dp = [[0, 0] for i in range(len(nums))]dp[0][1] = nums[0]for i in range(1, len(nums)):dp[i][0] = max(dp[i-1][0], dp[i-1][1])dp[i][1] = dp[i-1][0]+nums[i]return max(dp[-1][0], dp[-1][1])def rob(self, nums: List[int]) -> int:if len(nums) == 1:return nums[0]return max(self.maxMoney(nums[:-1]), self.maxMoney(nums[1:]))

打家劫舍 III, 定义字段 a 和 b,分表表示 盗取(不盗取) 以 当前 root 节点为根节点的最大金额,这样递归就能求解出来。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def __init__(self):self.a = dict()  ## 存放以某个节点为根节点能盗取的最高金额(偷根节点)self.b = dict()  ## 存放以某个节点为根节点能盗取的最高金额(不偷根节点)## f 为 1 时, 表示偷 root 节点, 为 0 表示不偷def dfs(self, root, f):if root == None:return 0res = 0left_0 = self.b[root.left] if root.left in self.b else self.dfs(root.left, 0)right_0 = self.b[root.right] if root.right in self.b else self.dfs(root.right, 0)left_1 = self.a[root.left] if root.left in self.a else self.dfs(root.left, 1)right_1 = self.a[root.right] if root.right in self.a else self.dfs(root.right, 1)res_0 = max(left_0, left_1) + max(right_0, right_1)  ## 不偷  root 节点res_1 = root.val + left_0 + right_0    ## 偷 root 节点self.a[root] = res_1self.b[root] = res_0if f == 1:return res_1else:return res_0def rob(self, root: Optional[TreeNode]) -> int:return max(self.dfs(root, 0), self.dfs(root, 1))

相关文章:

leetcode之打家劫舍

leetcode 198 打家劫舍 leetcode 213 打家劫舍 II leetcode 337. 打家劫舍 III 你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋&#xff0c;每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 &#xff0c;这意味着第一个房屋和最后一个房屋是紧挨着的。同时&#…...

走进Spring的世界 —— Spring底层核心原理解析(一)

文章目录 前言一、Spring中是如何创建一个对象二、Bean的创建过程三、推断构造方法四、AOP大致流程五、Spring事务 前言 ClassPathXmlApplicationContext context new ClassPathXmlApplicationContext("config.xml"); UserService userService (UserService) cont…...

快看看你的手机有没有:谷歌Android全面封杀此类软件!

谷歌坐不住了&#xff0c;因为Android应用商店中&#xff0c;充斥着大量可窃取用户数据的应用&#xff0c;所以必然要出手整治了。 一款名叫“SonicSpy”软件是整个事情的导火索&#xff0c;而该应用是典型的窃取用户数据的应用&#xff0c;其除了可以从手机中提取个人数据外&…...

spark ui 指南

spark ui 指南 1.sparkUI 基本介绍2.jobs页面3.stages 页面4.storage 页面5.environment 页面6.ececutor 页面7 sql 页面  spark ui 是反应一个spark 作业执行情况的页面,通过查看作业的执行情况,分析作业运行的状态. 1.sparkUI 基本介绍 进入运行主页面如下,主要有6各部…...

【分布式事务】

文章目录 解决分布式事务的思路seata四种模式1. XA模式2. AT模式AT模式与XA模式的区别是什么&#xff1f;脏写问题 3. TCC模式事务悬挂和空回滚 4. SAGA模式 四种模式对比口述AT模式与TCC模式高可用 什么是分布式事务&#xff1f; 分布式事务&#xff0c;就是指不是在单个服务或…...

linux 清除卸载jenkins

1、停服务进程 查看jenkins服务是否在运行&#xff0c;如果在运行&#xff0c;停掉 查看服务 ps -ef|grep jenkins 停掉进程 kill -9 XXX2、查找安装目录 find / -name "jenkins*"3、删掉相关目录 删掉相关安装目录 rm -rf /root/.jenkins/# 删掉war包 rm -rf /…...

番外4:VMware安装

step4: 安装过程中&#xff0c;有些选项不需要点&#xff08;安装地址建议选C盘或默认&#xff0c;装载在其他盘后续会报错&#xff09;&#xff0c;如&#xff1a; may error&#xff08;本人猜测安装虚拟机完整版需要C盘的一些桥插件支持&#xff09;: step5: 安装虚拟机成功…...

Oracle 19.20 patch 注意事项

1. 打patch 用root 打 /u01/app/19.0.0/grid/OPatch/opatchauto apply /u01/app/patch/35319490 2.打patch 之前 所有NODE上OPatch 版本要一样 3. OPatch 目录不要是root权限 4.打一台&#xff0c;一台自动重启。 有几个node 在几个node 打。patch 都要传到不同的node上 …...

ElementUI之增删改及表单验证

⭐⭐本文章收录与ElementUI原创专栏&#xff1a;ElementUI专栏 ⭐⭐ ElementUI的官网&#xff1a;ElementUI官网 目录 一.前言 二.使用ElementUI完成增删改 2.1 后台代码 2.2 前端代码 三.使用ElementUI完成表单验证 一.前言 本章是继上一篇的基础之上在做完善&#xff0…...

【Java 进阶篇】深入理解 JDBC:Java 数据库连接详解

数据库是现代应用程序的核心组成部分之一。无论是 Web 应用、移动应用还是桌面应用&#xff0c;几乎都需要与数据库交互以存储和检索数据。Java 提供了一种强大的方式来实现与数据库的交互&#xff0c;即 JDBC&#xff08;Java 数据库连接&#xff09;。本文将深入探讨 JDBC 的…...

Web开发-session介绍

目录 session介绍session使用场景session具体使用需要注意的是 session介绍 session 可以被看作是一种缓冲区&#xff0c;用于在多个请求之间存储和传递用户数据。在 Web 应用程序中&#xff0c;session 通常用于存储用户登录信息、购物车数据、用户偏好设置等。当用户在应用程…...

基于Qt Creator开发的坦克大战小游戏

目录 介绍开发环境技术介绍安装说明项目目录设计思想项目介绍运行演示知识点记录Gitee源码链接 介绍 &#xff01;&#xff01;&#xff01;资源图片是从网上免费下载&#xff0c;源码都是原创&#xff0c;供个人学习使用&#xff0c;非盈利&#xff01;&#xff01;&#xff…...

小说推文和短剧推广以及电影达人带货电影票

小说推文、短剧推广、电影达人&#xff08;带或电影票&#xff09;都可以通过“巨量推文“进行申请授权 小说推文和短剧推广是什么&#xff1f; 小说推文和短剧推广的逻辑其实一样&#xff0c;分为cpa拉新和cps分成的推广形式 cpa拉新是你推广的用户必须为新用户&#xff0c…...

朴素贝叶斯分类(下):数据挖掘十大算法之一

⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ 🐴作者:秋无之地 🐴简介:CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作,主要擅长领域有:爬虫、后端、大数据开发、数据分析等。 🐴欢迎小伙伴们点赞👍🏻、收藏⭐️、…...

9.30作业

C语言基础考题&#xff08;40&#xff09; 选择题 20分每题2分 1、已知字母A的ASCII码为十进制数值65&#xff0c;且S为字符型&#xff0c;则执行语句SA6-3&#xff1b;后S中的值为 ( ) A.D B.68 C.不确定的值 D.C 2、若有定义语句&#xff1a;int a12;&#xff0c;则执…...

[GWCTF 2019]枯燥的抽奖

参考 https://www.cnblogs.com/AikN/p/15764428.html [GWCTF 2019]枯燥的抽奖-CSDN博客 打开环境 笑死我了&#xff0c;怎么那么像我高中校长 查看源代码 看到check.php&#xff0c;去访问一下 ok看到源代码了 因为上次做过&#xff0c;看到这个我就想到用php_mt_seed逆推…...

vue3中sync修饰符的使用

props是子组件与父组件进行通信的常用方式&#xff0c;使用步骤主要有以下几个&#xff1a; 1. 在子组件中定义props要从父组件接收的变量&#xff08;变量的类型必须写明&#xff0c;默认值可选&#xff09; // 这里以 document.vue 子组件为例 // 通过 defineProps 宏的方…...

Qt全屏显示与退出

仿照 按Escape键退出程序中的实现&#xff0c;我们在程序开始的时候全屏显示&#xff0c;按esc键的时候退出全屏。 showFullScreen 全屏显示只需要调用QWidget类&#xff08;QMainWindow也是一个QWidget类&#xff09;的 showFullScreen() 成员函数即可。 退出全屏&#x…...

OpenCV之直线曲线拟合

直线拟合fitLine void fitLine( InputArray points, OutputArray line, int distType,double param, double reps, double aeps ); points:二维点的数组或vector line:输出直线,Vec4f (2d)或Vec6f (3d)的vector distType:距离类型 param:距离参数 reps:径向的精度参数 a…...

2023年哪款PDF虚拟打印机好用?

PDF文档想必大家都不陌生&#xff0c;在工作中经常会用到该格式的文档&#xff0c;那么有哪些方法能制作PDF文档呢&#xff1f;一般都是借助PDF虚拟打印机的&#xff0c;那么有哪些好用的软件呢&#xff1f; pdfFactory不仅为用户提供了丰富的PDF文档生成、打印功能&#xff0…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...