代码随想录算法训练营day48 | LeetCode 198. 打家劫舍 213. 打家劫舍 II 337. 打家劫舍 III
198. 打家劫舍(题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台)
思路:dp题除背包外的另外一类题目,重点不在于看前面的情况,而在于考虑本节点的情况。一种情况,选择本节点;另一种情况,不选择本节点,看哪种情况下的值最大。初始化也有所不同,不是简单地dp[0]=0,dp[1]=1诸如此类,dp[1]要考虑dp[0]的大小才能决定。
int rob(vector<int>& nums) {int size = nums.size();if(size == 1) return nums[0];vector<int> dp(size, 0);dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for(int i=2; i<size; i++){dp[i] = max(dp[i-2] + nums[i], dp[i-1]);}return dp[size-1];
}
213. 打家劫舍 II(题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台)
思路:环形数组,第一次见dp中这样的设置,其实很简单,总体上考虑两种情况:情况一:考虑除数组头外的其他所有元素;情况二:考虑除数组尾外的其他所有元素。最后取这两个里面的最大值就好。
int robRange(vector<int>& nums, int start, int end){if(end==start) return nums[end];vector<int> dp(nums.size(), 0);dp[start] = nums[start];dp[start+1] = max(nums[start], nums[start+1]);for(int i=start+2; i<=end; i++){dp[i] = max(dp[i-2]+nums[i], dp[i-1]);}return dp[end];
}int rob(vector<int>& nums) {int size = nums.size();if(size==1) return nums[0];int result1 = robRange(nums, 0, size-2);int result2 = robRange(nums, 1, size-1);return max(result1, result2);
}
337. 打家劫舍 III(题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台)
思路:树形dp,dp的做法和二叉树的遍历的做法没有很大差异,或者说dp的做法就是基于二叉树的遍历做了一点点的改进,只是为了让它更像是动态规划。
递归遍历做法:
unordered_map<TreeNode*, int> umap;
int rob(TreeNode* root) {if(root == NULL) return 0;if(root->left==NULL && root->right==NULL) return root->val;if(umap[root]) return umap[root];int val1 = root->val;if(root->left) val1 += rob(root->left->left)+rob(root->left->right);if(root->right) val1 += rob(root->right->left)+rob(root->right->right);int val2=rob(root->left)+rob(root->right);umap[root] = max(val1, val2);return max(val1, val2);
}
其中用umap是为了让树中每个节点只遍历一遍,避免反复求值。
dp做法:
int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);
}vector<int> robTree(TreeNode* cur){if(cur==NULL) return {0,0};vector<int> left = robTree(cur->left);vector<int> right = robTree(cur->right);int val1 = cur->val + left[1] + right[1];int val2 = max(left[0], left[1]) + max(right[0], right[1]);return {val1, val2};
}
相关文章:
代码随想录算法训练营day48 | LeetCode 198. 打家劫舍 213. 打家劫舍 II 337. 打家劫舍 III
198. 打家劫舍(题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台) 思路:dp题除背包外的另外一类题目,重点不在于看前面的情况,而在于考虑本节点的情况。一种情况…...
【已解决】Java 后端使用数组流 Array.stream() 将数组格式的 Cookie 转换成字符串格式
🎉工作中遇到这样一个场景:远程调用某个接口,该接口需要用户的 Cookie 信息进行权限认证,认证通过之后才可以打通并返回数据。 在后端拿到 httpServletRequest 后,调用 getCookies() 方法,返回的是一个 Coo…...
Redis——》如何评估锁过期时间
推荐链接: 总结——》【Java】 总结——》【Mysql】 总结——》【Redis】 总结——》【Kafka】 总结——》【Spring】 总结——》【SpringBoot】 总结——》【MyBatis、MyBatis-Plus】 总结——》【Linux】 总结——》【MongoD…...
完整开发实现公众号主动消息推送,精彩内容即刻到达
🏆作者简介,黑夜开发者,CSDN领军人物,全栈领域优质创作者✌,CSDN博客专家,阿里云社区专家博主,2023年6月CSDN上海赛道top4。 🏆数年电商行业从业经验,历任核心研发工程师…...
获取ip(公网和内网) 前端通过高德api获取位置信息
获取ip(公网和内网) 前端通过高德api获取位置信息 获取ip //获取公网ip getIp() {this.$axios.get(http://api.ipify.org).then((res) > {if (res) {console.log(res, 公网ip);}}).catch((e) > {console.log(e, e);}); },//获取内网ip this.getIP(…...
linux打开端口命令是什么
linux打开端口命令是什么 linux开启端口的命令是 1 firewall-cmd --zonepublic --add-port端口/通讯协议 --permanent 需要注意的是,我们在开启指定端口后需要重启防火墙。 示例如下: 1、开启防火墙 1 systemctl start firewalld 2、开放指定端…...
从《孤注一掷》出发,聊聊 SSL 证书的重要性
你去看《孤注一掷》了吗?相信最近大家的朋友圈和抖音都被爆火电影《孤注一掷》成功刷屏。取材于上万真实案例的《孤注一掷》揭露了缅甸诈骗园区残暴的统治,以及电信诈骗中系统性极强的诈骗技巧,引发了大量讨论。 图片来源于电影《孤注一掷》…...
专题:曲面的切平面、法线
假设曲面方程为隐函数 F ( x , y , z ) 0 ,点 M ( x 0 , y 0 , z 0 ) 是其上一点 又在点 M 处任意引一条在曲面上的曲线,设该曲线参数方程为: { x φ ( t ) y ψ ( t ) z ω ( t ) ,且当 t t 0 时, x x 0 , y y…...
数据结构:排序解析
文章目录 前言一、常见排序算法的实现1.插入排序1.直接插入排序2.希尔排序 2.交换排序1.冒泡排序2.快速排序1.hoare版2.挖坑版3.前后指针版4.改进版5.非递归版 3.选择排序1.直接选择排序2.堆排序 4.归并排序1.归并排序递归实现2.归并排序非递归实现 5.计数排序 二、排序算法复杂…...
Revit SDK:AutoJoin 自动合并体量
前言 Revit 有一套完整的几何造型能力,每一个体量都是一个GenericForm,这些体量可以通过拉伸、扫掠等创建。这个例子介绍如何将他们合并成一个体量。 内容 合并体量的关键接口: // Autodesk.Revit.DB.Document public GeomCombination Com…...
MYSQL(索引、事务)
文章目录 一、索引二、事务 一、索引 数据库中的表、数据、索引之间的关系,类似于书架上的图书、书籍内容和书籍目录的关系 1. 概述 概念:相当于是一本书的目录,是以‘列’为维度进行建立的使用场景:如果我们要查询一个表中的某个…...
部署问题集合(二十三)设置Docker容器内的中文字符集,解决某些情况下中文乱码的问题
前言: 同事给了一个服务,在Windows环境下怎么跑都正常,但一到Linux虚拟机里就中文乱码起初就想到了可能是字符集的问题,但调整了半天也没见效果,最后隔了几天突然想到,我是构建Docker跑的,而且…...
Web AP—PC端网页特效
PC端网页特效 代码下载 元素偏移量 offset 系列 offset 翻译过来就是偏移量, 我们使用 offset系列相关属性可以动态的得到该元素的位置(偏移)、大小等。 获得元素距离带有定位父元素的位置获得元素自身的大小(宽度高度&#x…...
Spring线程池ThreadPoolTaskExecutor使用
为什么使用线程池? 降低系统资源消耗,通过重用已存在的线程,降低线程创建和销毁造成的消耗;提高系统响应速度,当有任务到达时,通过复用已存在的线程,无需等待新线程的创建便能立即执行…...
spring mvc的执行流程
请求拦截。用户发起请求,请求先被sevlet拦截,转发给spring mvc框架请求转发。spring mvc里面的DispcherServlet会接收到请求并转发给HandlerMapping匹配接口。HandlerMapping负责解析请求,根据请求信息和配置信息找到匹配的controller类&…...
docker作业
目录 1、使用mysql:5.6和 owncloud 镜像,构建一个个人网盘。 1.1启动镜像 1.2启动cloud镜像 1.3浏览器访问 编辑 2、安装搭建私有仓库 Harbor 2.1下载docker-compose 2.2 磁盘挂载,保存harbor 2.3 修改配置文件 2.4安装 2.5浏览器访问 2.6 新…...
java实现本地文件转文件流发送到前端
java实现本地文件转文件流发送到前端 Controller public void export(HttpServletResponse response) {// 创建file对象response.setContentType("application/octet-stream");// 文件名为 sresponse.setHeader("Content-Disposition", "attachment;…...
2020ICPC南京站
K K Co-prime Permutation 题意:给定n和k,让你构造n的排列,满足gcd(pi, i)1的个数为k。 思路:因为x和x-1互质,1和任何数互质,任何数和它本身不互质 当k为奇数时,p11,后面k-1个数…...
Linux 中的 chsh 命令及示例
介绍 bash shell 是 Linux 最流行的登录 shell 之一。但是,对于不同的命令行操作,可以使用替代方法。chshLinux 中的( change shell )命令使用户能够修改登录 shell 。 以下教程...
JavaScript 数组如何实现冒泡排序?
冒泡排序是一种简单但效率较低的排序算法,常用于对小型数据集进行排序。它的原理是多次遍历数组,比较相邻元素的大小,并根据需要交换它们的位置,将最大(或最小)的元素逐渐“冒泡”到数组的一端。这个过程会…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
数据结构:递归的种类(Types of Recursion)
目录 尾递归(Tail Recursion) 什么是 Loop(循环)? 复杂度分析 头递归(Head Recursion) 树形递归(Tree Recursion) 线性递归(Linear Recursion)…...
ZYNQ学习记录FPGA(一)ZYNQ简介
一、知识准备 1.一些术语,缩写和概念: 1)ZYNQ全称:ZYNQ7000 All Pgrammable SoC 2)SoC:system on chips(片上系统),对比集成电路的SoB(system on board) 3)ARM:处理器…...
从零开始了解数据采集(二十八)——制造业数字孪生
近年来,我国的工业领域正经历一场前所未有的数字化变革,从“双碳目标”到工业互联网平台的推广,国家政策和市场需求共同推动了制造业的升级。在这场变革中,数字孪生技术成为备受关注的关键工具,它不仅让企业“看见”设…...
