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

算法学习——LeetCode力扣动态规划篇5

算法学习——LeetCode力扣动态规划篇5

在这里插入图片描述

198. 打家劫舍

198. 打家劫舍 - 力扣(LeetCode)

描述

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

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

示例

示例 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 <= nums.length <= 100
0 <= nums[i] <= 400

代码解析

动态规划

dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]

dp[i]取最大值,即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

class Solution {
public:int rob(vector<int>& nums) {if(nums.size()==1) return nums[0];else if(nums.size()==2) return max(nums[0],nums[1]);vector<int> dp(nums.size() , 0);dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);for(int i=2 ; i<nums.size() ;i++){dp[i] = max( dp[i-1] , dp[i-2] + nums[i]);}return dp[nums.size()-1];}
};

213. 打家劫舍 II

213. 打家劫舍 II - 力扣(LeetCode)

描述

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

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

示例

示例 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

代码解析

其实就是把环拆成两个队列,一个是从0到n-1,另一个是从1到n,然后返回两个结果最大的。

class Solution {
public:int robRange(vector<int>& nums, int start, int end) {if((end - start) == 1 ) return nums[start];if((end - start) == 2) return max(nums[start],nums[start+1]);vector<int> dp((end - start) , 0);dp[0] = nums[start];dp[1] = max(nums[start],nums[start+1]);for(int i=2 ; i<(end - start) ;i++){dp[i] = max(dp[i-1],dp[i-2]+nums[start+i]);}// for(auto it:dp) cout<<it<<' ';// cout<<endl;return dp[end-start-1];}int rob(vector<int>& nums) {if(nums.size()==0) return 0;if(nums.size()==1) return nums[0];int result1 = robRange(nums,0,nums.size()-1);int result2 = robRange(nums,1,nums.size());// cout<<result1<<' '<<result2;return max(result1,result2);}
};

337. 打家劫舍 III

337. 打家劫舍 III - 力扣(LeetCode)

描述

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

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

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

示例

示例 1:
在这里插入图片描述

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

在这里插入图片描述

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

提示

树的节点数在 [1, 104] 范围内
0 <= Node.val <= 104

代码解析

动态规划

返回数组就是dp数组。

  • 下标为0记录:不偷该节点所得到的的最大金钱
  • 下标为1记录:偷该节点所得到的的最大金钱。
    在遍历的过程中,如果遇到空节点的话,无论偷还是不偷都是0,

首先明确的是使用后序遍历。 因为通过递归函数的返回值来做下一步计算。

  • 通过递归左节点,得到左节点偷与不偷的金钱。
  • 通过递归右节点,得到右节点偷与不偷的金钱。

单层递归的逻辑

  • 如果是偷当前节点,那么左右孩子就不能偷,
    val1 = cur->val + left[0] + right[0]; (

  • 如果不偷当前节点,那么左右孩子就可以偷,至于到底偷不偷一定是选一个最大的
    val2 = max(left[0], left[1]) + max(right[0], right[1]);

  • 最后当前节点的状态就是{val2, val1};
    即:{不偷当前节点得到的最大金钱,偷当前节点得到的最大金钱}

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public://返回数组。0是不偷,1是偷vector<int> backtracking(TreeNode* cur){//空节点,偷和不偷都是0if(cur == nullptr )return vector<int>(2,0);vector<int> left = backtracking(cur->left);vector<int> right = backtracking(cur->right);//不偷,在左右子节点选最大的int val0 = max(left[0],left[1]) + max(right[0] , right[1]);//偷,当前节点加上左右不偷int val1 = cur->val + left[0] + right[0];return vector<int>{val0 ,val1};}int rob(TreeNode* root) {vector<int> result =  backtracking(root);//偷和不偷选最大return max(result[0],result[1]);}
};
回溯
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int result = 0;unordered_map<TreeNode* , int> my_map;int trak_back(TreeNode* cur){if(cur == nullptr) return 0;if(my_map[cur] != 0) return my_map[cur];else if(cur->left==nullptr && cur->right==nullptr) return cur->val;int value = cur->val;if(cur->left != nullptr ) value += trak_back(cur->left->left) + trak_back(cur->left->right);if(cur->right != nullptr ) value += trak_back(cur->right->left) + trak_back(cur->right->right);my_map[cur] = max( value , trak_back(cur->left) + trak_back(cur->right));return my_map[cur];}int rob(TreeNode* root) {return trak_back(root);}
};
树形递归
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> track_back(TreeNode* cur){if(cur == nullptr) return {0,0};vector<int> dp(2,0);vector<int> left_dp = track_back(cur->left);vector<int> right_dp = track_back(cur->right);//不偷当前节点,左右节点可偷可不偷,选大的dp[0] = max(left_dp[0],left_dp[1]) + max(right_dp[0],right_dp[1]);//偷当前节点dp[1] = cur->val + left_dp[0] + right_dp[0];return dp;}int rob(TreeNode* root) {//dp[0]为当前节点不偷的值,dp[1]为偷vector<int> dp = track_back(root);return max(dp[0] , dp[1]);}
};

相关文章:

算法学习——LeetCode力扣动态规划篇5

算法学习——LeetCode力扣动态规划篇5 198. 打家劫舍 198. 打家劫舍 - 力扣&#xff08;LeetCode&#xff09; 描述 你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金&#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统…...

C语言-文件

目录 1.什么是文件&#xff1f;1.1 程序文件1.2 数据文件 2.二进制文件和文本文件&#xff1f;3.文件的打开和关闭4.文件的顺序读写5.文件的随机读写5.1 fseek5.2 ftell5.3 rewind 6.文件读取结束的判定7.文件缓冲区 1.什么是文件&#xff1f; 磁盘上的文件就是文件 一般包含两…...

牛客NC30 缺失的第一个正整数【simple map Java,Go,PHP】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/50ec6a5b0e4e45348544348278cdcee5 核心 Map参考答案Java import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定&#xff0c;请勿修改&#xff0c;直接返回方法规定的值即可…...

Unity 基于Rigidbody2D模块的角色移动

制作好站立和移动的动画后 控制器设计 站立 移动 角色移动代码如下&#xff1a; using System.Collections; using System.Collections.Generic; using Unity.VisualScripting; using UnityEngine;public class p1_c : MonoBehaviour {// 获取动画组件private Animator …...

Stata 15 for Mac:数据统计分析新标杆,让研究更高效!

Stata 是一种统计分析软件&#xff0c;适用于数据管理、数据分析和绘图。Stata 15 for Mac 具有以下功能&#xff1a; 数据管理&#xff1a;Stata 提供强大的数据管理功能&#xff0c;用户可以轻松导入、清洗、整理和管理数据集。 统计分析&#xff1a;Stata 提供了广泛的统计…...

vue配置代理proxy

如何配置代理 在 vue devServer服务器配置文件 vue.config.js 的 devServer 选项中配置 proxy module.exports {// publicPath:process.env.NODE_ENV production ? /vue_workspac/aihuhuproject/ : /,//基本路径publicPath: ./,//默认的/是绝对路径&#xff0c;如果不确定在…...

.NET DES加密算法实现

简介&#xff1a; DES&#xff08;Data Encryption Standard&#xff09;加密算法作为一种历史悠久的对称加密算法&#xff0c;自1972年由美国国家标准局&#xff08;NBS&#xff09;发布以来&#xff0c;广泛应用于各种数据安全场景。本文将从算法原理、优缺点及替代方案等方…...

构建操作可靠的数据流系统

文章目录 前言数据流动遇到的困难先从简单开始可靠性延迟丢失 性能性能损失性能——分层重试 可扩展性总结 前言 在流式架构中&#xff0c;任何对非功能性需求的漏洞都可能导致严重后果。如果数据工程师没有将可伸缩性、可靠性和可操作性等非功能性需求作为首要考虑因素来构建…...

awesome-cheatsheets:超级速查表 - 编程语言、框架和开发工具的速查表

awesome-cheatsheets&#xff1a;超级速查表 - 编程语言、框架和开发工具的速查表&#xff0c;单个文件包含一切你需要知道的东西 官网&#xff1a;GitHub - skywind3000/awesome-cheatsheets: 超级速查表 - 编程语言、框架和开发工具的速查表&#xff0c;单个文件包含一切你需…...

GFW不起作用

闲着折腾&#xff0c;刷openwrt到一个小米3G路由器后&#xff0c;GFW不起作用。后面发现是自己电脑设置了DNS&#xff0c;解析完IP后&#xff0c;在经过代代&#xff0c;IP不在GFW的清单里&#xff0c;所以转发控制就没有起作用。 结论 在经过代代前的所有节点&#xff0c;都…...

AndroidStudio出现类似 Could not create task ‘:app:ToolOperatorDemo.main()‘. 错误

先看我们的报错 翻译过来大概意思是:无法创建任务:app:ToolOperatorDemo.main()。 没有找到名称为“main”的源集。 解决方法&#xff1a; 在.idea文件夹下的gradle.xml文件中 <GradleProjectSettings>标签下添加<option name"delegatedBuild" value"f…...

一些常见的ClickHouse问题和答案

什么是ClickHouse&#xff1f;它与其他数据库系统有什么区别&#xff1f; ClickHouse是一个开源的列式数据库管理系统&#xff08;DBMS&#xff09;&#xff0c;专门用于高性能、大规模数据分析。与传统的行式数据库相比&#xff0c;ClickHouse具有更高的查询性能、更高的数据…...

第九届蓝桥杯大赛个人赛省赛(软件类)真题C 语言 A 组-分数

solution1 直观上的分数处理 #include <iostream> using namespace std; int main() {printf("1048575/524288");return 0; }#include<stdio.h> #include<math.h> typedef long long ll; struct fraction{ll up, down; }; ll gcd(ll a, ll b){if…...

并发编程——4.线程池

这篇文章我们来讲一下线程池的相关内容 目录 1.什么是线程池 1.1为什么要用线程池 1.2线程池的优势 2.线程池的使用 3.线程池的关闭 4.线程池中的execute和submit方法的一些区别 5.线程池的参数和原理 6.自定义线程池 7.总结 1.什么是线程池 1.1为什么要用线程池 首…...

阿里云魔搭发起“ModelScope-Sora开源计划”,将为中国类Sora模型开发提供一站式工具链

在2024年3月23日的全球开发者先锋大会上&#xff0c;阿里云的魔搭社区宣布了一个新计划&#xff1a;“ModelScope-Sora开源计划”。这个计划旨在通过开源方式&#xff0c;帮助中国在Sora模型类型上做出更多创新。这个计划提供了一整套工具&#xff0c;包括处理数据的工具、多模…...

大模型与数据分析:探索Text-to-SQL

当今大模型如此火热&#xff0c;作为一名数据同学&#xff0c;持续在关注LLM是如何应用在数据分析中的&#xff0c;也关注到很多公司推出了AI数智助手的产品&#xff0c;比如火山引擎数智平台VeDI—AI助手、 Kyligence Copilot AI数智助理、ThoughtSpot等&#xff0c;通过接入人…...

Unity VisionOS开发流程

Unity开发环境 Unity Pro, Unity Enterprise and Unity Industry 国际版 Mac Unity Editor(Apple silicon) visionOS Build Support (experimental) 实验版 Unity 2022.3.11f1 NOTE: 国际版与国服版Pro账通用&#xff0c;需要激活Pro的许可证。官方模板v0.6.2,非Pro版本会打…...

聊聊k8s服务发现的优缺点

序 本文主要研究一下使用k8s服务发现的优缺点 spring cloud vs kubernetes 这里有张spring cloud与kubernetes的对比&#xff0c;如果将微服务部署到kubernetes上面&#xff0c;二者有不少功能是重复的&#xff0c;可否精简。 这里主要是讲述一下如果不使用独立的服务发现&am…...

Tomcat是如何处理并发请求的?

Tomcat处理请求流程&#xff1a; Tomcat是采用了扩展JDK线程池的方案 :先启动若干数量的线程&#xff0c;并让这些线程都处于睡眠状态&#xff0c;当客户端有一个新请求时&#xff0c;就会唤醒线程池中的某一个睡眠线程&#xff0c;让它来处理客户端的这个请求&#xff0c;当处…...

H12-831_561

单选题561、如图所示&#xff0c;R1使用Loopback0接口(IP地址为10.0.1.1/32)与R2的物理接口(IP地址为10.0.12.2/24)建立EBGP邻居关系,以下描述中正确的是哪一项? A.无需在R1和R2的BGP进程下指定ebgp-max-hop B.在R2的BGP进程下配置peer 10.0.1.1 ebgp-max-hop 2&#xff0c;且…...

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

目录 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…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)

+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...

网页端 js 读取发票里的二维码信息(图片和PDF格式)

起因 为了实现在报销流程中&#xff0c;发票不能重用的限制&#xff0c;发票上传后&#xff0c;希望能读出发票号&#xff0c;并记录发票号已用&#xff0c;下次不再可用于报销。 基于上面的需求&#xff0c;研究了OCR 的方式和读PDF的方式&#xff0c;实际是可行的&#xff…...