C国演义 [第十二章]

这篇具有很好参考价值的文章主要介绍了C国演义 [第十二章]。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

打家劫舍

力扣链接

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

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

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

题目理解

不能在相邻的房屋进行偷窃, 还要求一夜之间能够偷窃的最高金额
那小偷到这个房屋偷还是不偷?

⇒ 偷窃到第 i 个房屋的最大金额 取决于上一次偷窃的是哪个房屋(取决于 第 i -1 个房屋的偷取状态 和 第 i - 2 个房屋的偷取状态)
⇒ 我们可以采用 动态规划的思想

步骤

dp数组

影响因素只有一个, 上一次偷窃的是哪个房屋⇒ dp数组用 一维 的就可以
dp[i] — — [0, i]房屋所得到的最大金额

递推公式

偷窃到第 i 个房屋, 我们能够进行的操作有哪一些:

  1. 所相邻的房屋并没有偷窃, 那我们这个房屋就能进行偷窃 — — dp[i-2] + nums[i]
  2. 所相邻的房屋已经偷窃了, 那我们这个房屋就不能进行偷窃 — — dp[i-1]

最后的结果, 是取两者的最大值⇒ dp[i] = max(dp[i-1], dp[i-2] + nums[i])

初始化

根据递归公式, 我们发现最基础的是 dp[0] 和 dp[1]
dp[0] — — 第一个房屋所能偷窃的最大价值, 那肯定是偷了它 — — dp[0] = nums[0]
dp[1] — — 前两个房屋所能偷窃的最大价值, 那肯定是偷它们之间的最大价值的那个 — — dp[1] = max(nums[0], nums[1])

遍历顺序

根据递归公式, 第 i 天的状态是由前面决定的
⇒ 那么是 由前到后的遍历方向

代码

class Solution {
public:
    int rob(vector<int>& nums) 
    {
        // dp[i] -- -- 区间[0, i]的最大价值
        vector<int> dp(nums.size() + 1, 0);
        dp[0] = nums[0];
        if(nums.size() > 1)
            dp[1] = max(nums[0], nums[1]);
        
        for(int i = 2; i < nums.size(); i++)
        {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        
        return dp[nums.size() - 1];
    }
};

C国演义 [第十二章],leetcode,算法,数据结构,c++


打家劫舍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 <= nums.length <= 100
    0 <= nums[i] <= 1000

题目理解

这个题目跟上面的很相似, 但是有一个点是不同的:
上面是个线性的, 这个题目是圆形的

那么, 我们能不能用上一个题目的解法来解决这个题目呢?
首先, 先将圆形转化为线性的

在区间[0, i]中, 我们发现:

  • 0为开端, 那么 i 是不能是结尾 (最大是 i - 1结尾)
  • 1为开端, 那么 i 是能是结尾的
    ⇒ 那么我们就可以划分为两个区间:
    [0, i - 1] 和 [1, i]

步骤

递推公式

偷窃到第 i 个房屋, 我们能够进行的操作有哪一些:

  1. 所相邻的房屋并没有偷窃, 那我们这个房屋就能进行偷窃 — — dp[i-2] + nums[i]
  2. 所相邻的房屋已经偷窃了, 那我们这个房屋就不能进行偷窃 — — dp[i-1]

最后的结果, 是取两者的最大值⇒ dp[i] = max(dp[i-1], dp[i-2] + nums[i])

初始化

  • 区间为[0, n - 1]:
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

  • 区间为[1, n]:
    dp[1] = nums[1]
    dp[2] = max(nums[1], nums[2])

遍历顺序

根据递归公式, 第 i 天的状态是由前面决定的
⇒ 那么是 由前到后的遍历方向

代码

class Solution {
public:
    int rob(vector<int>& nums) 
    {
        // 将环形问题拆分为线性问题
        // 将区间[0, n] 拆分为 包含第一个节点,不包含最后一个节点 和 不包含第一个节点,包含最后一个节点
        // 即将区间[0, n] 拆分为 [0, n-1] 和 [1, n] 两个区间
        // 最后返回两个区间最大值的最大值
        
        if(nums.size() == 1)  return nums[0];
        if(nums.size() == 2)  return max(nums[0], nums[1]);
        
        vector<int> dp(nums.size() + 1, 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        for(int i = 2; i < nums.size() - 1; i++)
        {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        int max1 = dp[nums.size() - 2];
        
        dp[1] = nums[1];
        dp[2] = max(nums[1], nums[2]);
        for(int i = 3; i < nums.size(); i++)
        {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        int max2 = dp[nums.size() - 1];
        
        return max(max1, max2);
    }
};

C国演义 [第十二章],leetcode,算法,数据结构,c++


连伟人的一生都充满了那么大的艰辛,一个平凡的人吃点苦又算得了什么呢? — — 路遥文章来源地址https://www.toymoban.com/news/detail-581669.html

到了这里,关于C国演义 [第十二章]的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第十二章Session

    注意:前面的Cookie是保存在客户端,而session是在服务端的 这里Session与cookie的样式基本一样的 下面加一个base标签 再次点击,id不变,isNew变为false 30分钟 下面这个设置可以改变session的默认时长 下面我们设置session的时长(上面是默认时长) 本来第二次点击session的创建和获取

    2024年01月24日
    浏览(40)
  • 第十二章 kafka

    Producer :Producer即生产者,消息的产生者,是 消息的入口 。 kafka cluster :          Broker :Broker是 kafka实例 ,每个服务器上有一个或多个kafka的实例,我们姑且认为每个broker对应一台服务器。每个kafka集群内的broker都有一个不重复的编号,如图中的broker-0、broker-1等…… 主

    2024年02月13日
    浏览(43)
  • 第十二章 外观模式

    `

    2023年04月25日
    浏览(40)
  • 第十二章:泛型(Generic)

    目录 12.1:为什么要有泛型? 12.2:在集合中使用泛型 12.3:自定义泛型结构 12.4:泛型在继承上的体现 12.5:通配符的使用 12.1:为什么要有泛型?         泛型:(标签)允许在定义类、接口时候通过一个标识来表示类中某个属性的类型或者是某个方法的返回值及参数类

    2024年02月07日
    浏览(40)
  • 第十二章 elk

    1、ELK可以帮助我们解决哪些问题 日志分布在多台不同的服务器上,业务一旦出现故障,需要一台台查看日志 单个日志文件巨大,无法使用常用的文本工具分析,检索困难; 2、架构设计分析 Filebeat和Logstash ELK架构中使用 Logstash收集、解析日志 ,但是Logstash对 内存、cpu、io等资

    2024年02月13日
    浏览(33)
  • 第十二章 sys模块

    什么是Python 解释器 当编写Python 代码时,通常都会得到一个包含Python 代码的以.py 为扩展名的文件。要运行编写的代码,就需要使用Python 解释器去执行.py 文件。因此,Python 解释器就是用来执行Python 代码的一种工具。常见的Python 解释器有以下几种: CPython:Python 的官方解释器

    2024年02月09日
    浏览(41)
  • python 第十二章 面向对象

    第一章 初识python 第二章 变量 第三章 基础语句 第四章 字符串str 第五章 列表list [] 第六章 元组tuple ( ) 第七章 字典dict {} 第八章 集合set {} 第九章 常用操作 第十章 函数 第十一章 文件操作 理解面向对象 面向对象是一种抽象化的编程思想,很多编程语言中都有的一种思想。

    2024年02月13日
    浏览(47)
  • 【OpenCV】第十二章: 图像轮廓

    第十二章: 图像轮廓 图像边缘和图像轮廓的区别 前面我们在图像形态学操作里,用cv2.morphologyEx()这个函数实现图像梯度的提取,就是用膨胀图像-腐蚀图像,获取一个图像中前景图像的边缘。还有我们的礼帽黑帽一定程度也能提取图像的边缘信息。 我们还在图像梯度里面详细

    2024年02月04日
    浏览(61)
  • 第十二章 Transform组件(下)

    上一章节中我们介绍了Transform组件的属性和方法。我们发现 Transform 中有right,up和forward,而 Vector3 类中也有right,up和forward,他们是一回事嘛?我们使用Forward来说明两者之间的区别。我们知道,改变游戏对象的position位置,就可以形成移动效果。如果我们让游戏对象沿着for

    2024年02月01日
    浏览(35)
  • 11.第十二章.采购管理

    1、基于组织的经营目标和经营政策展开项目采购相应的运营活动,包括采购战略合作管理、釆购过程管理、采购管理技术和工具等3个方面。 2、企业仅依靠自身无力应对激烈的竞争。因此,必须摈弃“以企业为中心”的传统管理模式,代之以现代战略合作的管理模式。战略合

    2024年02月04日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包