【算法挨揍日记】day22——面试题 17.16. 按摩师、213. 打家劫舍 II

 面试题 17.16. 按摩师

面试题 17.16. 按摩师

题目描述: 

一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,替按摩师找到最优的预约集合(总预约时间最长),返回总的分钟数。

注意:本题相对原题稍作改动

 解题思路:

状态表示:f[i],g[i]表示以i为结尾,i预约和i不预约的最长的预约时长

状态转移方程:

f[i]=g[i-1]+nums[i]

g[i]=max(f[i-1],g[i-1])

初始化:

f[0]=nums[0],g[0]=0

填表顺序:左到右

返回值:max(f[n-1],g[n-1]) 

解题代码:

class Solution {
public:
    int massage(vector<int>& nums) {
        int n=nums.size();
        if(n==0)return 0;
        vector<int>f(n,0);
        vector<int>g(n,0);
        f[0]=nums[0];
        for(int i=1;i<n;i++)
        {
            f[i]=g[i-1]+nums[i];
            g[i]=max(f[i-1],g[i-1]);
        }
        return max(f[n-1],g[n-1]);
    }
};

 213. 打家劫舍 II

213. 打家劫舍 II

题目描述:

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

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

 解题思路:

本题分为两种情况:

一种是选第一个位置

一种是不选第一个位置

状态表示:

f[i],g[i]表示以i为结尾,i偷和i不偷的最大金额

状态转移方程:

f[i]=g[i-1]+nums[i]

g[i]=max(f[i-1],g[i-1])

初始化:

f[0]=nums[0],g[0]=0

填表顺序:左到右

返回值:max(f[n-1],g[n-1]) 

 解题代码;

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/163638.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

实用小算法

开头提醒&#xff1a; 打开自己本地任意一个SpringBoot项目&#xff0c;复制代码到test包下跟着敲。 后面几篇文章不再提醒&#xff0c;希望大家养成习惯。看10篇文章&#xff0c;不如自己动手做一次。 我们不执着于一天看多少篇&#xff0c;但求把每一篇都搞懂&#xff0c;…

python 计算最大回撤

1. 什么是最大回撤 最大回撤是评估金融产品收益的一个非常重要的风险指标&#xff0c;它指的是在选定历史周期内任一历史时点往后推&#xff0c;产品净值走到最低点时的收益率回撤幅度的最大值。 以上图为例&#xff0c; 最大回撤 ( V a l u e A − V a l u e B ) V a l u e …

《2020年最新面经》—字节跳动Java社招面试题

文章目录 前言&#xff1a;一面&#xff1a;01、Java基础知识答疑&#xff0c;简单概述一下&#xff1f;02、倒排索引了解吗&#xff1f;使用Java语言怎么实现倒排&#xff1f;03、详细讲解一下redis里面的哈希表&#xff0c;常用的Redis哈希表命名有哪些&#xff0c;举例说明其…

MongoDB相关基础操作(库、集合、文档)

文章目录 一、库的相关操作1、查看数据库2、查看当前库3、创建数据库4、删除数据库 二、集合的相关操作1、查看库中所有集合2、创建集合2.1、显示创建2.2、隐式创建 3、删除集合 三、文档的相关操作1、插入文档1.1、插入单条文档1.2、插入多条文档1.3、脚本方式 2、查询文档3、…

<Linux>权限管理|权限分类|权限设置|权限掩码|粘滞位

文章目录 Linux权限的概念Linux权限管理a. 文件访问者的分类b. 文件类型和访问权限c. 文件权限表示方法d. 文件权限的设置权限掩码file指令粘滞位 权限总结权限作业 Linux权限的概念 Linux下有两种用户&#xff1a;超级用户(root)和普通用户。 超级用户&#xff1a;可以在Lin…

【算法挨揍日记】day29——139. 单词拆分、467. 环绕字符串中唯一的子字符串

139. 单词拆分 139. 单词拆分 题目描述&#xff1a; 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意&#xff1a;不要求字典中出现的单词全部都使用&#xff0c;并且字典中的单词可以重复使用。 解题思路&am…

反弹Shell

概述 反弹shell&#xff08;reverse shell&#xff09;就是控制端监听在某TCP/UDP端口&#xff0c;被控端发起请求到该端口&#xff0c;并将其命令行的输入输出转到控制端。reverse shell与telnet&#xff0c;ssh等标准shell对应&#xff0c;本质上是网络概念的客户端与服务端…

新版mmdetection3d将3D bbox绘制到图像

环境信息 使用 python mmdet3d/utils/collect_env.py收集环境信息 sys.platform: linux Python: 3.7.12 | packaged by conda-forge | (default, Oct 26 2021, 06:08:21) [GCC 9.4.0] CUDA available: True numpy_random_seed: 2147483648 GPU 0,1: NVIDIA GeForce RTX 3090 …

记录-2023/11/18

1. 序列器中可以定义update方法 2. 分页之后前端获取数据的方式要进行改变 JavaScript的switch语法2 situation "a"switch (situation) {case "a":console.log("a")breakcase "b":console.log("b")breakcase "c&quo…

小美的树上染色

美团2024届秋招笔试第一场编程真题 先提一个小知识&#xff1a;题目中凡是提到树结构都要使用图的存储方式&#xff0c;只有二叉树例外。 分析&#xff1a;在树结构中&#xff0c;孩子和父节点是相邻节点&#xff0c;而父节点可能有多个孩子节点。在染色的过程中&#xff0c;…

【linux】补充:高效处理文本的命令学习(tr、uniq、sort、cut)

目录 一、tr——转换、压缩、删除 1、tr -s “分隔符” &#xff08;指定压缩连续的内容&#xff09; 2、tr -d 想要删除的东西 ​编辑 3、tr -t 内容1 内容2 将内容1全部转换为内容2&#xff08;字符数需要一一对应&#xff09; 二、cut——快速剪裁命令 三、uniq——去…

MongoDB之索引和聚合

文章目录 一、索引1、说明2、原理3、相关操作3.1、创建索引3.2、查看集合索引3.3、查看集合索引大小3.4、删除集合所有索引&#xff08;不包含_id索引&#xff09;3.5、删除集合指定索引 4、复合索引 二、聚合1、说明2、使用 总结 一、索引 1、说明 索引通常能够极大的提高查…

Python3.7+PyQt5 pyuic5将.ui文件转换为.py文件、Python读取配置文件、生成日志

1.实际开发项目时&#xff0c;是使用Qt Designer来设计UI界面&#xff0c;得到一个.ui的文件&#xff0c;然后利用PyQt5安装时自带的工具pyuic5将.ui文件转换为.py文件&#xff1a; pyuic5 -o mywindow.py mywindow.ui #先是py文件名&#xff0c;再是ui文件名样式图 QT5 UI&am…

端口号大揭秘:网络世界的“门牌号”有多牛?

大家好&#xff0c;今天我们来聊一聊网络中的端口号。如果你以为端口号只是冷冰冰的数字&#xff0c;那你就大错特错了。端口号&#xff0c;这些看似枯燥的数字背后&#xff0c;隐藏着一个个生动的故事。 1. 80/tcp - HTTP&#xff1a;数字版的美食街 首先&#xff0c;让我们迈…

6.9平衡二叉树(LC110-E)

绝对值函数&#xff1a;abs() 算法&#xff1a; 高度和深度的区别&#xff1a; 节点的高度&#xff1a;节点到叶子节点的距离&#xff08;从下往上&#xff09; 节点的深度&#xff1a;节点到根节点的距离&#xff08;从上往下&#xff09; 逻辑&#xff1a;一个平衡二叉树…

对象与this

作者简介&#xff1a;大家好&#xff0c;我是smart哥&#xff0c;前中兴通讯、美团架构师&#xff0c;现某互联网公司CTO 联系qq&#xff1a;184480602&#xff0c;加我进群&#xff0c;大家一起学习&#xff0c;一起进步&#xff0c;一起对抗互联网寒冬 最近想再聊聊Java的对象…

JVM 调优指南

文章目录 为什么要学 JVM一、JVM 整体布局二、Class 文件规范三、类加载模块四、执行引擎五、GC 垃圾回收1 、JVM内存布局2 、 JVM 有哪些主要的垃圾回收器&#xff1f;3 、分代垃圾回收工作机制 六、对 JVM 进行调优的基础思路七、 GC 情况分析实例 JVM调优指南 -- 楼兰 ​ JV…

系列七、GC垃圾回收【四大垃圾算法-标记压缩算法】

一、原理 在整理压缩阶段&#xff0c;不再对标记的对象回收&#xff0c;而是通过所有存活对象都向一端移动。可以看到&#xff0c;标记的存活对象将会被整理&#xff0c;按照内存地址依次排列。如此一来&#xff0c;当我们需要给新对象分配内存时&#xff0c;JVM只需要持有一个…

永久关机windows系统自动更新

1、打开cmd执行 reg add "HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\WindowsUpdate\UX\Settings" /v FlightSettingsMaxPauseDays /t reg_dword /d 3000 /f2、设置&#xff0c;打开windows更新高级选项 修改暂停日期&#xff0c;可长达十年。 3、你小子

解锁数据安全之门:探秘迅软DSE的文件权限控制功能

企业管理者在进行数据安全管控时通常只关注到文件的加密方式&#xff0c;却忽略了以下问题&#xff1a;对于企业内部文档&#xff0c;根据其所承载的涉密程度不同&#xff0c;重要程度也不相同&#xff0c;需要由不同涉密等级的的人员进行处理&#xff0c;这就需要对涉密文档和…
最新文章