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

代码随想录算法训练营第47天 || 198.打家劫舍 || 213.打家劫舍II || 337.打家劫舍III

代码随想录算法训练营第47天 || 198.打家劫舍 || 213.打家劫舍II || 337.打家劫舍III

198.打家劫舍

题目介绍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

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

示例 1:

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

示例 2:

输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

个人思路

动规五部曲

  1. 确定dp数组及其下标含义

    dp[j]:从下标0到下标j的房间中,能偷的最大金额

  2. 确定递推公式

    dp[i] = Integer.max(dp[i - 1], dp[i - 2] + nums[i]);

    表示偷或不偷当前房间对应的金额,其中取较大的那个;

  3. 初始化dp数组

    dp[0] = nums[0];
    dp[1] = Integer.max(dp[0], nums[1]);
    

    适应递推公式,从而初始化前两个dp数组元素

  4. 确定遍历顺序

    正序遍历即可(结合递推公式)

  5. 打印dp数组检验

代码:

class Solution {public int rob(int[] nums) {if (nums.length == 1)return nums[0];int[] dp = new int[nums.length];dp[0] = nums[0];dp[1] = Integer.max(dp[0], nums[1]);for (int i = 2; i < nums.length; i++) {dp[i] = Integer.max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[dp.length - 1];}
}

213.打家劫舍II

题目介绍

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

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

示例 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/-1用一个变量存储即可),不过还是较为麻烦

题解解析

这个问题大致可以分为三种情况

  • 去掉头尾的非环问题
  • 去掉头的非环问题
  • 去掉尾的非环问题

实际上情况2、3已经包括1了,因为dp[j]:表示的就是从头到j下标的最大偷盗价值,如果边界取不到,那就刚好等同于情况一。所以本题,我们只需要考虑后两种情况,然后取最大值即可(封装函数,调用两次,比较两个结果)

动规五部曲

  1. 确定dp数组及其下标含义

    dp[j]:前j+1家能偷到的最大价值

  2. 确定递推公式

    dp[i] = Integer.max(dp[i - 1], dp[i - 2] + nums[i+left]);
    

    还是与之前一样,偷与不偷当前房子的比较

  3. 初始化dp数组

    dp[0] = nums[left];
    dp[1] = Integer.max(dp[0], nums[left+1]);
    
  4. 确定遍历顺序

    正序遍历即可

  5. 打印dp数组检验

代码:

class Solution {public int rob(int[] nums) {if (nums.length == 1)return nums[0];int rob_max1 = rob_(nums, 1, nums.length - 1);int rob_max2 = rob_(nums, 0, nums.length - 2);return Integer.max(rob_max1,rob_max2);}public int rob_(int[] nums,int left,int right){if (right - left == 0)return nums[left];int[] dp = new int[right-left+1];dp[0] = nums[left];dp[1] = Integer.max(dp[0], nums[left+1]);for (int i = 2; i < dp.length; i++) {dp[i] = Integer.max(dp[i - 1], dp[i - 2] + nums[i+left]);}return dp[dp.length - 1];}
}

337.打家劫舍III

题目介绍

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

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

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

示例 1:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AM0FWPIY-1677057886054)(null)]

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

示例 2:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ubZdCCUF-1677057886010)(null)]

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

思路解析

结合动态规划和二叉树遍历的知识,每个结点都有偷和不被偷两种情况,那么我们分别记录每个节点的这两种情况的最优解,由下往上返回最优解,从子树最优得到全局最优(有点小贪心吧)

动规五部曲、递归三部曲

  1. 确定参数及返回值

    参数:结点

    返回值:int[2],偷与不偷当前结点的最大金额

  2. 确定终止条件

    if (root == null)return new int[]{0, 0};
    
  3. 确定递归顺序

    后序遍历

  4. 确定单层递归逻辑

    1. 确定dp数组及其下标含义

      dp[0]:表示已当前结点为根的二叉树中,当前结点的最大金额

      dp[1]:表示已当前结点为根的二叉树中,不偷当前结点的最大金额

    2. 确定递推公式

      dp[0] = root.val + dp_left[1] + dp_right[1];//偷自己的情况下,子树只能取不偷的情况
      //不偷自己的情况下,取偷或不偷左右孩子的最大值
      dp[1] = Integer.max(dp_left[0], dp_left[1]) + Integer.max(dp_right[0], dp_right[1]);
      
  5. 最后取偷或不偷根节点的最大金额即可

class Solution {public int rob(TreeNode root) {int[] dp = traversal(root);return Integer.max(dp[0], dp[1]);}public int[] traversal(TreeNode root) {if (root == null)return new int[]{0, 0};int[] dp_left = traversal(root.left);int[] dp_right = traversal(root.right);int[] dp = new int[2];//0表示偷自己,1表示不偷自己dp[0] = root.val + dp_left[1] + dp_right[1];//不偷自己的情况下,取偷或不偷左右孩子的最大值dp[1] = Integer.max(dp_left[0], dp_left[1]) + Integer.max(dp_right[0], dp_right[1]);return dp;}
}

t.right);
int[] dp = new int[2];//0表示偷自己,1表示不偷自己
dp[0] = root.val + dp_left[1] + dp_right[1];
//不偷自己的情况下,取偷或不偷左右孩子的最大值
dp[1] = Integer.max(dp_left[0], dp_left[1]) + Integer.max(dp_right[0], dp_right[1]);
return dp;
}
}


相关文章:

代码随想录算法训练营第47天 || 198.打家劫舍 || 213.打家劫舍II || 337.打家劫舍III

代码随想录算法训练营第47天 || 198.打家劫舍 || 213.打家劫舍II || 337.打家劫舍III 198.打家劫舍 题目介绍 你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金&#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统&…...

JVM调优方式

对JVM内存的系统级的调优主要的目的是减少GC的频率和Full GC的次数。 1.Full GC 会对整个堆进行整理&#xff0c;包括Young、Tenured和Perm。Full GC因为需要对整个堆进行回收&#xff0c;所以比较慢&#xff0c;因此应该尽可能减少Full GC的次数。 2.导致Full GC的原因 1)年老…...

机器学习模型监控的 9 个技巧

机器学习 (ML) 模型是非常敏感的软件&#xff1b;它们的成功使用需要进行仔细监控以确保它们可以正常工作。当使用所述模型的输出自动做出业务决策时尤其如此。这意味着有缺陷的模型通常会对终端客户的体验产生真正的影响。因此&#xff0c;监控输入数据&#xff08;和输出&…...

Linux 实现鼠标侧边键实现代码与网页的前进、后退

前言 之前一直是使用windows进行开发&#xff0c;最近转到linux后使用VsCode编写代码。 但是不像在win环境下&#xff0c;使用鼠标侧边键可以实现代码的前向、后向跳转。浏览网页时也不行&#xff08;使用Alt Left可以后退&#xff09;。 修改键盘映射实在没有那么方便&…...

健身蓝牙耳机推荐,推荐五款适合健身的蓝牙耳机

出门运动健身&#xff0c;有音乐的陪伴是我们坚持运动的不懈动力&#xff0c;在健身当中佩戴的耳机&#xff0c;佩戴舒适度以及牢固程度是我们十分需要注意的&#xff0c;还不知道如何选择健身蓝牙耳机&#xff0c;可以看看下面这些运动蓝牙耳机分享。 1、南卡Runner Pro4骨传…...

Type-c诱骗取电芯片大全

随着Type-C的普及和推广&#xff0c;目前市面上的电子设备正在慢慢淘汰micro-USB接口&#xff0c;逐渐都更新成了Type-C接口&#xff0c;micro-USB接口从2007年上市&#xff0c;已经陪伴我们走过十多个年头&#xff0c;如今也慢慢退出舞台。 今天我们评测的产品是市面上Type-C…...

Scala模式匹配详解(第八章:基本语法、模式守卫、模式匹配类型)(尚硅谷笔记)

模式匹配第 8 章 模式匹配8.1 基本语法8.2 模式守卫8.3 模式匹配类型8.3.1 匹配常量8.3.2 匹配类型8.3.3 匹配数组8.3.4 匹配列表8.3.5 匹配元组8.3.6 匹配对象及样例类8.4 变量声明中的模式匹配8.5 for 表达式中的模式匹配8.6 偏函数中的模式匹配(了解)第 8 章 模式匹配 Scal…...

Linux:基于libevent读写管道代码

基于libevent读写管道代码&#xff1a; 读端&#xff1a; #include <stdlib.h> #include <stdio.h> #include <unistd.h> #include <sys/types.h> #include <sys/stat.h> #include <string.h> #include <event2/event.h> #include…...

2022年中职网络安全逆向题目整理合集

中职网络安全逆向题目整理合集逆向分析&#xff1a;PE01.exe算法破解&#xff1a;flag0072算法破解&#xff1a;flag0073算法破解&#xff1a;CrackMe.exe远程代码执行渗透测试天津逆向re1 re2逆向分析&#xff1a;PE01.exe FTPServer20220509(关闭链接)  FTP用户名:PE01密码…...

Tencent OS下逻辑卷(LVM)增加硬盘扩容

上一篇文章写了逻辑卷创建以及使用剩余空间为已经创建的逻辑卷扩容。 本篇是针对卷组空间已经用尽时的扩容方法。那就是增加硬盘。 首先我们为虚拟机增加硬盘/dev/sdd 使用fdisk为/dev/sdd分区,方法在上一篇文章已经描述,在此不再赘述。 新增的硬盘使用如下命令添加到卷组…...

【Java】Spring的创建和使用

Spring的创建和使用 Spring就是一个包含众多工具方法的IOC容器。既然是容器&#xff0c;那么就具备两个最主要的功能&#xff1a; 将对象存储到容器中从容器中将对象取出来 在Java语言当中对象也叫作Bean。 1. 创建Spring项目 创建一个普通maven项目添加Spring框架支持(spri…...

【HTML】HTML 表单 ④ ( textarea 文本域控件 | select 下拉列表控件 )

文章目录一、textarea 文本域控件二、select 下拉列表控件一、textarea 文本域控件 textarea 文本域 控件 是 多行文本输入框 , 标签语法格式如下 : <textarea cols"每行文字字符数" rows"文本行数">多行文本内容 </textarea>实际开发中 并不…...

MySQL 操作 JSON 数据类型

MySQL 从 v5.7.8 开始支持 JSON 数据类型。 JSON 数据类型和传统数据类型的操作还是有很大的差别&#xff0c;需要单独学习掌握。好在 JSON 数据类型的学习成本不算太高&#xff0c;只是在 SQL 语句中扩展了 JSON 函数&#xff0c;操作 JSON 数据类型主要是对函数的学习。 新…...

关于vue3生命周期的使用、了解以及用途(详细版)

生命周期目录前言组合式写法没有 beforeCreate / created 生命周期&#xff0c;并且组合式写生命周期用哪个先引哪个beforeCreatecreatedbeforeMount/onBeforeMountmounted/onMountedbeforeUpdate/onBeforeUpdateupdated/onUpdatedbeforeUnmount/onBeforeUnmountunmounted/onUn…...

2月,真的不要跳槽。

新年已经过去&#xff0c;马上就到金三银四跳槽季了&#xff0c;一些不满现状&#xff0c;被外界的“高薪”“好福利”吸引的人&#xff0c;一般就在这时候毅然决然地跳槽了。 在此展示一套学习笔记 / 面试手册&#xff0c;年后跳槽的朋友可以好好刷一刷&#xff0c;还是挺有必…...

Vulnhub靶场----4、DC-4

文章目录一、环境搭建二、渗透流程三、思路总结一、环境搭建 DC-4下载地址&#xff1a;https://download.vulnhub.com/dc/DC-4.zip kali&#xff1a;192.168.144.148 DC-4&#xff1a;192.168.144.152 二、渗透流程 端口扫描&#xff1a;nmap -T5 -p- -sV -sT -A 192.168.144.1…...

51单片机学习笔记_12 LCD1602 原理及其模块化代码

LCD1602 liquid crystal display 液晶显示屏&#xff0c;一种字符型液晶显示模块&#xff0c;可以显示 16*2 个字符&#xff0c;每个字符是 5*7 点阵。 P0 P2 会和数码管、LED 一定程度上冲突。 地。 Vcc。 调对比度的。 RS&#xff1a;数据指令端。1代表 DB 是数据&#x…...

科技 “新贵”ChatGPT 缘何 “昙花一现” ,仅低代码风靡至今

恍惚之间&#xff0c;ChatGPT红遍全网&#xff0c;元宇宙沉入深海…… 在科技圈&#xff0c;见证了太多“昙花一现”&#xff0c;“新贵” ChatGPT 的爆火几乎复制了元宇宙的路径&#xff0c;它会步元宇宙的后尘&#xff0c;成为下一个沉入深海的工具吗&#xff1f; 不可否认的…...

redis基本入门| 怎么安装redis?什么的是redis?怎么使用?

目录 一、Redis下载与安装 二、基本概念 1.什么是Redis? 2.Redis端口多少&#xff1f; 3.Redis是单线程还是多线程&#xff1f; 4.Redis为什么单线程还这么快&#xff1f; 三、Redis的基本操作 四、Redis的五个基本类型 1.Redis-key 2.字符串 string 3.列表 list …...

kubernetes traefik ingress 安装部署以及使用和注意点

1、简介 Traefik 是一款 open-source 边缘路由器&#xff0c;可让您轻松地发布服务. 它接收来自您的系统请求&#xff0c;并找出负责处理它们的后端服务组件。 traefik 与众不同在于它能够自动发现适合您服务的配置。 当 Traefik 检查您的基础设施时&#xff0c;它会发现相关信…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...

HTTPS证书一年多少钱?

HTTPS证书作为保障网站数据传输安全的重要工具&#xff0c;成为众多网站运营者的必备选择。然而&#xff0c;面对市场上种类繁多的HTTPS证书&#xff0c;其一年费用究竟是多少&#xff0c;又受哪些因素影响呢&#xff1f; 首先&#xff0c;HTTPS证书通常在PinTrust这样的专业平…...

C++11 constexpr和字面类型:从入门到精通

文章目录 引言一、constexpr的基本概念与使用1.1 constexpr的定义与作用1.2 constexpr变量1.3 constexpr函数1.4 constexpr在类构造函数中的应用1.5 constexpr的优势 二、字面类型的基本概念与使用2.1 字面类型的定义与作用2.2 字面类型的应用场景2.2.1 常量定义2.2.2 模板参数…...

零基础在实践中学习网络安全-皮卡丘靶场(第十一期-目录遍历模块)

经过前面几期的内容我们学习了很多网络安全的知识&#xff0c;而这期内容就涉及到了前面的第六期-RCE模块&#xff0c;第七期-File inclusion模块&#xff0c;第八期-Unsafe Filedownload模块。 什么是"遍历"呢&#xff1a;对学过一些开发语言的朋友来说应该知道&…...

AI书签管理工具开发全记录(十八):书签导入导出

文章目录 AI书签管理工具开发全记录&#xff08;十八&#xff09;&#xff1a;书签导入导出1.前言 &#x1f4dd;2.书签结构分析 &#x1f4d6;3.书签示例 &#x1f4d1;4.书签文件结构定义描述 &#x1f523;4.1. ​整体文档结构​​4.2. ​核心元素类型​​4.3. ​层级关系4.…...