【贪心算法】贪心算法五

贪心算法五

  • 1.跳跃游戏 II
  • 2.跳跃游戏
  • 3.加油站
  • 3.单调递增的数字

在这里插入图片描述

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励,我们一起努力吧!😃😃

1.跳跃游戏 II

题目链接: 45. 跳跃游戏 II

题目分析:

在这里插入图片描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处。这句话特别重要的地方就是 任意

下面举个例子,刚开始在0号位置最大跳跃长度是3,可以跳到下标3的位置。
在这里插入图片描述
你可以跳转到任意 nums[i + j] 处,这句话意思,nums[i]里面存的3是最大跳跃长度,你可以选择跳3步、跳2步、跳1步。

在这里插入图片描述
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

算法原理:

  1. 贪心(X)

刚开始处于0好位置,这里有一个最大跳跃长度,那每次跳跃的时候就非常贪心的跳最长跳跃长度。但是这种贪心是错的。

在这里插入图片描述
2. 动态规划

这个模型无非就是从左往右的一个模型,其实就是动规里面非常常规的线性dp问题。

1.状态表示

dp[i] 表示:从 0 位置开始,到达 i 位置的时候最小跳跃次数

2.状态转移方程

根据最近一步划分情况:

能够到 i 位置的前提是要满足 nums[j] + j >= i,说明能够从 j 位置到达 i 位置,那到达 j 位置的最小跳跃次数 在 加上 从 j 到 i 这一跳跃次,就是到达 i 位置最小跳跃次数,j的位置有很多,因此外面要求dp[i]的最小值。

在这里插入图片描述

3.初始化

dp[0] = 0 初始就在0位置,然后要取dp[i]的最小值,因此0位置之后可以初始化 INT_MAX

4.填表顺序

从左往右

5.返回值

dp[i] 表示:从 0 位置开始,到达 i 位置的时候最小跳跃次数,我们要的是到底n-1位置的最小跳跃次数,因此返回dp[n-1]

class Solution {
public:
    int jump(vector<int>& nums) {

        // 动态规划
        int n = nums.size();
        vector<int> dp(n, INT_MAX);
        dp[0] = 0;
        for(int i = 1; i < n; ++i)
            for(int j = 0; j < i; ++j)
                if(nums[j] + j >= i)
                    dp[i] = min(dp[i], dp[j] + 1);
        return dp[n - 1];
    }
};

虽然可以通过,但是实际复杂度是O(N^2)

  1. 类似于层序遍历的过程

刚开始在2这个位置,此时起跳可以跳到3和1的位置。2这里可以表示第1次起跳的位置,3和1表示第2次起跳的位置。

在这里插入图片描述

通过第2次起跳的位置,我们可以得到第3从起跳的位置,然后把重叠的删除,这里其实也有一点小贪心,如果能从第2次的1起跳,那为什么还要从第3次重叠的1起跳呢?跳跃次数更多了。所以只有1和4是第三次起跳的位置。

在这里插入图片描述

同理从第3次起跳位置,我们可以得到第4次起跳位置,

在这里插入图片描述

你会发现这里类似于层序遍历,每次都能知道起跳的左端点和右端点,然后遍历这一层的时候,又能找到下一层的左端点和右端点。只要发现更新出来下一次起跳位置能够覆盖到n-1位置的时候就停止,因为次数已经可以跳到最后一个位置了

在这里插入图片描述

如何实现呢?
我们仅需搞两个指针,left指向当前起跳的左端点,right指向当前起跳的右端点,把这个区间遍历一遍就可以找到下一个起跳区间,其中找左端点很好找就是right + 1,找右端点就是在遍历的过程中,拿着nums[i] + i 找到其中的最大值就是右端点。

在这个遍历过程中,我们仅需遍历一次就行了,所以时间复杂度是O(N)

class Solution {
public:
    int jump(vector<int>& nums) {
    
        int left = 0, right = 0, maxPos = 0, ret = 0, n = nums.size();
        while(left <= right)// 保险的写法,以防跳不到 n - 1 的位置
        {
            if(maxPos >= n - 1)// 先判断⼀下是否已经能跳到最后⼀个位置
            {
                return ret;
            }
            // 遍历当成层,更新下⼀层的最右端点 
            for(int i = left; i <= right; ++i)
            {
                maxPos = max(maxPos, nums[i] + i);
            }
            left = right + 1;
            right = maxPos;
            ++ret;
        }
        return -1;// 跳不到的情况
    }
};

2.跳跃游戏

题目链接: 55. 跳跃游戏

题目分析:
在这里插入图片描述

这道题和上面几乎一模一样,无非上面问的是跳到最后一个位置最小跳跃次数,这道题问的是能否跳到最后一个位置。

算法原理:

完全参考上面的解法3:利用层序遍历的过程

class Solution {
public:
    bool canJump(vector<int>& nums) {

        int left = 0, right = 0, maxPos = 0, n = nums.size();
        while(left <= right)
        {
            if(maxPos >= n - 1)
            {
                return true;
            }

            for(int i = left; i <= right; ++i)
            {
                maxPos = max(maxPos, nums[i] + i);
            }
            left = right + 1;
            right = maxPos;
        }
        return false;

    }
};

3.加油站

题目链接: 134. 加油站

题目分析:

在这里插入图片描述

选择某个加油站为出发点,环绕一周看是否能回到出发点。如果可以就返回对应的下标,不能就返回-1。

在这里插入图片描述

初始时油箱是空的,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i],油箱容量是无限的。

假设从3位置出发,刚开始油箱为空,此时可以补充1升汽油,但是需要3升汽油才能到下一个位置。所以这个位置不可以,同理4和5都不可以。
在这里插入图片描述
可以从1位置出发 ,从这里可以补充4升汽油,仅需消耗1升就可以到下一个位置,到下一个位置还剩下3升

在这里插入图片描述

到2的位置,补充5升,现在共有8升,消耗2升,到下一个位置还有6升

在这里插入图片描述
然后补充1升,消耗3升,到下一个位置还剩4,在补充2升,消耗4升,到下一个位置还剩2升,在补充3升,消耗5升,到出发点正好剩下0,可以到达,返回3。

在这里插入图片描述

算法原理:

解法一:暴力解法 -> 枚举

首先可以想到一个优化,仅需考虑g和c的差就可以了,比如第一个位置会加1升油,消耗3升油,它们的差就是从这个加油站获得的净收益。如果从负开始走绝对是走不到下一个位置的,所以肯定会选择净收益为正的作为出发点。

在这里插入图片描述

我们这道题其实特别像是一道模拟的题,任意枚举一个位置看看从这个位置能不能绕一圈会回来就可以。如果不能就去枚举下一个位置。

所以我们的暴力策略就很简单:

  1. 依次枚举所有的起点
  2. 从起点开始,模拟一遍加油的流程即可

虽然策略很简单,但是要注意这里是有环的,所以写代码的时候要考虑如何从最后一个位置回到0位置。

在这里插入图片描述
我们的贪心就是根据暴力优化来的,所以先搞定暴力的代码。然后优化的时候仅需加一句代码,就能将时间复杂度从O(N^2)变成O(N)

如何实现暴力的代码?

这里我们主要考虑就是如何从最后一个位置回到第一个位置,其实这里两层for循环就可以搞定,我们创建一个变量step,用这个变量表示从 i 往后走了多少步,step变化是从 0 ~ n - 1。然后 (i + step)% n (数组大小) 就可以从最后一个位置回到第一个位置。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        int n = gas.size();
        for(int i = 0; i < n; ++i)// 依次枚举所有的起点
        {
            int rest = 0;// 标记一下净收益
            int step = 0;
            for(; step < n; ++step)// 枚举往后走的步数
            {
                int index = (i + step) % n;// 求出走 step 步之后的下标
                rest = rest + gas[index] - cost[index];
                if(rest < 0) break;
            }
            if(rest >= 0) return i;
        }
        return -1;       
    }
};

解法二:优化 -> 找规律(贪心)

diff表示g-c的差,我们的暴力解法是依次固定一个位置为起点,从这个起点开始模拟加油流程,其实就是把净收益加一下。

在这里插入图片描述

如果发现从a加到f小于0了,说明从f这个位置开始就不能往后走了,所以从a为起来最多能到f这个位置。这里有一个等式。

在这里插入图片描述
我们的暴力是枚举下一个起点然后在走。然后我们这里也有个不等式,

在这里插入图片描述

我们要想从a走到b,一定是a>=0的,从a加到f < 0,现在第二个不等式又少了a,那更是< 0

在这里插入图片描述

同理从c为起点也是越不过f的,a + b >= 0才能到c,等式少了a+b,那更小于0

在这里插入图片描述
所以说发现有一个起点点都跑不到某个位置,那中间的都不用在考虑了,不用在枚举了。直接让 i 指针更新到 五角星 后面的一个位置,也就是 i = i + step + 1

在这里插入图片描述

我们最差会遍历数组两遍,假设还是以a为起点,发现到h走不到了,下一个位置就是i,最差我们绕回去在遍历一遍再走到h位置,相当于遍历了数组两遍,然后接下来更新 i 的时候 是 i + step + 1 此时就已经越界了。所以最差遍历数组两遍,时间复杂度O(N)

在这里插入图片描述

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        int n = gas.size();
        for(int i = 0; i < n; ++i)// 依次枚举所有的起点
        {
            int rest = 0;// 标记一下净收益
            int step = 0;
            for(; step < n; ++step)// 枚举往后走的步数
            {
                int index = (i + step) % n;// 求出走 step 步之后的下标
                rest = rest + gas[index] - cost[index];
                if(rest < 0) break;
            }
            if(rest >= 0) return i;
            i = i + step;//优化
        }
        return -1;

        
    }
};

3.单调递增的数字

题目链接: 738. 单调递增的数字

题目分析:

在这里插入图片描述

算法原理:

解法一:暴力解法 -> 暴力枚举

不是给了我们一个n,然后让找到小于等于n的最大数字,且数字是单调递增的。
所以我们可以从n枚举到0,只要找到数字是单调递增的,就返回。因为我们是从大到小枚举所以这个数一定是小于等于n并且是最大的那个数。

  1. 从大到小的顺序,枚举 [n,0] 区间内的数字
  2. 判断数字是否是 “单调递增的”

这里最主要的就是判断一个数是单调递增的。肉眼很好判断,但是让计算机不好判断,这里我们有两个常用方法:

第一种方法:我们遇到有个数字的时候,如果想处理某一位的时候,最常用的方式就是将数字转化为字符串。

比如要找数字中的每一位,如果单看数字1234你很难找每一位,但是我们可以将1234 转化为 “1234”,此时就可以用指针来遍历每一位

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
    
        for(int i = n; i >= 0; --i)
        {
            string nums = to_string(i);
            int j = 0, m = nums.size();
            for(; j < m - 1; ++j)
            {
                if(nums[j] > nums[j + 1]) break;
            }
            if(j == m - 1) return i;
        }
        return -1;   
    }
};

第二种方法:% 10 , / 10

prev记录之前%10得到的数字,cur记录/10之后然后当前%10得到的数字。

class Solution {
public:
    int monotoneIncreasingDigits(int n) {

        for(int i = n; i >= 0; --i)
        {
            int prev = INT_MAX, cur = 0, num = i;
            while(num)
            {
                cur = num % 10;
                if(cur > prev) break;
                prev = cur;
                num /= 10;
            }
            if(num == 0) return i;
        }
        return -1;
    }
};

这两种方法都会超时!时间复杂度是O(nlogn),O(logn)表示把数字中的每一位都提取出来时间复杂度是O(logn)

解法二:贪心(找规律)

假设有下面这样一个数,我们观察1-5是递增的,从5后面开始就是递减的。此时第一个贪心,如果前面的数是递增的我们会不会去修改它?肯定不会!修改高位势必会给高位某个数减小,影响太大了。

  1. 如果高位单调递增的话,我们不去修改

在这里插入图片描述

从5之后开始下降,我们最终要想找一个单调递增的话,调整一下后面的数使它从5开始递增并且尽可能的大,但是这个想法是实现不了的,你是会让4变成5,但是整个数相比之前就变大了。所以这个策略不行,调整4367使它从5之后开始递增是实现不了的。原因就是后面数的变化受到5的限制。如何解除这个限制呢?让这个5减小1变成4,然后的数都变成9,绝对是最大递增的。

  1. 从左往右,找到第一个递减的位置,使其减小1,后面的数全部修改成 9

在这里插入图片描述

但是这里还有个问题,比如下面这个数,5是重复的,从左到右扫描到最后一个5的位置,但是执行刚才的策略是让最后一个5减少1,后面数都变成9,但是不行啊,你让最后一个5变成4,这个数就不是一个递增的了。其实我们应该调整第一个5变成4,后面的数都变成9

  1. 从左往右,找到第一个递减的位置,从这个位置向前推,推到相同区域的最左段使其减小1,后面的数全部修改成 9

在这里插入图片描述

class Solution {
public:
    int monotoneIncreasingDigits(int n) {

        string s = to_string(n);// 把数字转化成字符串

        int i = 0, m = s.size();
        // 找第⼀个递减的位置
        while(i + 1 < m && s[i] <= s[i + 1]) ++i;

        if(i + 1 == m) return n;// 判断⼀下特殊情况

        // 回推
        while(i - 1 >= 0 && s[i] == s[i - 1]) --i;

        s[i]--;
        for(int j = i + 1; j < m; ++j) s[j] = '9';
        return stoi(s);
        
    }
};

证明:

证明方法:反证法

假设贪心解是错误的,那必定会存在一个最优解,证明一下这个最优解是不存在的,那我们的贪心解就是最优的。

在这里插入图片描述
这里我们分开讨论,第一种贪心解得到的数和原数个数是匹配的,第二种个数不匹配。

先看第一种情况,假设贪心解不是最优解,那势必会存在一个最优解,最优解是严格大于贪心解并且是严格递增的。其次位数是一样的,贪心解位数都一样,最优解比贪心解大,位数肯定也是一样的。位数一样,从左扫描最优解肯定存在某一位是大于贪心解某一位的。

这里可以分为3个区域,递增区域,让原数减1区域,以及后面的区域。不过如果前两个区域都是一样的话,第三个区域肯定不存在比999还大的。因此我们只考虑前两个区域最优解的某个数大于贪心解

在这里插入图片描述

第一块区域,要么大于1、要么大于2、要么大于3,但是都是不存在的,因为这个数是单调递增的,最小的1333333都比原解还大了。

在这里插入图片描述

第二块区域,如果中间这个数比贪心解的这个数大最低就是4,但是也是不存在的,最优解也是一个递增的数如果这个是数4,后面即使全是4,最小的是1234444还比原数大,所以也是不存在的。

在这里插入图片描述
那后面的区域更别提了,不可能有大于999的数。所以说如果贪心解是错的,根本找不到一个最优解比贪心解大,所以说刚才的假设是错误的,因此我们的贪心解是正确的。

在这里插入图片描述

接下来我们看位数减少的情况,我们会发现位数减少的这个数正好是最大的减少位数中的最大数,你想找一个最优解比贪心解还大的情况那必定是6位数,如果是6位数还想保证比原数小,那这个数只能是1111111但是比原数大,因此这个最优解也是不存在的,所以我们的贪心就是最优的。都找不到一个最优解大于贪心解。

在这里插入图片描述

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

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

相关文章

计算机毕业设计Python医疗问答系统 医疗可视化 BERT+LSTM+CRF深度学习识别模型 机器学习 深度学习 爬虫 知识图谱 人工智能 大数据毕业设计

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…

QT 中 sqlite 数据库使用

一、前提 --pro文件添加sql模块QT core gui sql二、使用 说明 --用于与数据库建立连接QSqlDatabase--执行各种sql语句QSqlQuery--提供数据库特定的错误信息QSqlError查看qt支持的驱动 QStringList list QSqlDatabase::drivers();qDebug()<<list;连接 sqlite3 数据库 …

总结的一些MySql面试题

目录 一&#xff1a;基础篇 二&#xff1a;索引原理和SQL优化 三&#xff1a;事务原理 四&#xff1a;缓存策略 一&#xff1a;基础篇 1&#xff1a;定义&#xff1a;按照数据结构来组织、存储和管理数据的仓库&#xff1b;是一个长期存储在计算机内的、有组织的、可共享 的…

Mac 录制电脑系统内的声音的具体方法?

1.第一步&#xff1a;下载BlackHole 软件 方式1&#xff1a;BlackHole官方下载地址 方式2&#xff1a; 百度云下载 提取码: n5dp 2.第二步&#xff1a;安装BlackHole 双击下载好的BlackHole安装包&#xff0c;安装默认提示安装。 3.第三步&#xff1a;在应用程序中找到音频…

什么是分库?分表?分库分表?

分库分表&#xff0c;是企业里面比较常见的针对高并发、数据量大的场景下的一种技术优化方案&#xff0c;所谓“分库分表”&#xff0c;根本不是一回事&#xff0c;而是三件事&#xff0c;他们要解决的问题也都不一样。 这三个事分别是“只分库不分表”、“只分表不分库”、以…

前端常用缓存技术深度剖析

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

A3026 Java+jsp+servlet+mysql高校学生请假管理系统

高校学生请假管理系统 1.摘要2. 绪论3.功能结构4.界面展示5.源码获取 1.摘要 高校学生请假管理系统 摘要&#xff1a;随着计算机的发展与不断进步&#xff0c;各个领域都出现了新的技术&#xff0c;曾经各种规模之间的竞争已经发展成为技术之间的竞争&#xff0c;管理和人才之…

机器学习周报(12.2-12.8)

文章目录 摘要Abstract Vision Transformer1 原理2 代码 摘要 本周学习了Vision Transformer (ViT) 的基本原理及其实现&#xff0c;并完成了基于PyTorch的模型训练、验证和预测任务。深入理解了ViT如何将图像分割成patch作为输入序列&#xff0c;并结合Transformer Encoder处…

Jmeter Address already in use: connect 解决

做压测接口时&#xff0c;并发一段时间后&#xff0c;会报java.net.BindException: Address already in use: connect 原因&#xff1a; windows提供给TCP/IP链接的端口为 1024-5000&#xff0c;并且要四分钟来循环回收它们&#xff0c;就导致在短时间内跑大量的请求时将端口占…

深入解析 HTML Input 元素:构建交互性表单的核心

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

力扣打卡10:K个一组翻转链表

链接&#xff1a;25. K 个一组翻转链表 - 力扣&#xff08;LeetCode&#xff09; 这道题需要在链表上&#xff0c;每k个为一组&#xff0c;翻转&#xff0c;链接。 乍一看好像比较容易&#xff0c;其实有很多细节。比如每一组反转后怎么找到上一组的新尾&#xff0c;怎么找到…

【银河麒麟操作系统真实案例分享】内存黑洞导致服务器卡死分析全过程

了解更多银河麒麟操作系统全新产品&#xff0c;请点击访问 麒麟软件产品专区&#xff1a;https://product.kylinos.cn 开发者专区&#xff1a;https://developer.kylinos.cn 文档中心&#xff1a;https://documentkylinos.cn 现象描述 机房显示器连接服务器后黑屏&#xff…

Android显示系统(04)- OpenGL ES - Shader绘制三角形

Android显示系统&#xff08;02&#xff09;- OpenGL ES - 概述 Android显示系统&#xff08;03&#xff09;- OpenGL ES - GLSurfaceView的使用 Android显示系统&#xff08;04&#xff09;- OpenGL ES - Shader绘制三角形 Android显示系统&#xff08;05&#xff09;- OpenGL…

Ubuntu 22.04安装Nessus(离线激活模式)

Ubuntu 22.04安装Nessus 一、 Nessus 简介二、Nessus下载安装三、激活Nessus四、创建一个基础扫描五、 破解Nessus只能扫描16个地址的限制六、更新插件 一、 Nessus 简介 Nessus 官网&#xff1a; https://www.tenable.com/ Nessus号称世界上最流行的扫描程序&#xff0c;Nessu…

OpenAI 发布 o1 LLM,推出 ChatGPT Pro

OpenAI正式发布了专为复杂推理而构建的 OpenAI o1大型语言模型(LLM)。 该公司还推出了 ChatGPT Pro&#xff0c;这是一项每月 200 美元的套餐&#xff0c;包括无限制访问 OpenAI o1、o1-mini、GPT-4o 和高级语音对话。 OpenAI o1 从 9 月 12 日起在 ChatGPT 中推出预览版&…

上海理工大学《2024年867自动控制原理真题》 (完整版)

本文内容&#xff0c;全部选自自动化考研联盟的&#xff1a;《上海理工大学867自控考研资料》的真题篇。后续会持续更新更多学校&#xff0c;更多年份的真题&#xff0c;记得关注哦~ 目录 2024年真题 Part1&#xff1a;2024年完整版真题 2024年真题

汽配行业数字化解决方案(一)

汽配行业数字化解决方案&#xff0c;是通过整合云计算、大数据、人工智能、物联网等先进技术&#xff0c;构建一个全面、高效、智能的数字化生态系统&#xff0c;以实现汽配供应链的全程可视化与智能化管理。该解决方案涵盖了从供应商管理、库存优化、订单处理、物流跟踪到客户…

华为开源自研AI框架昇思MindSpore应用案例:基于MindSpore框架的SGD优化器案例实现

SGD优化器基本原理讲解 随机梯度下降&#xff08;SGD&#xff09;是一种迭代方法&#xff0c;其背后基本思想最早可以追溯到1950年代的Robbins-Monro算法&#xff0c;用于优化可微分目标函数。 它可以被视为梯度下降优化的随机近似&#xff0c;因为它用实际梯度&#xff08;从…

集成学习综合教程

一、前置知识 一个分类器的分类准确率在60%-80%&#xff0c;即&#xff1a;比随机预测略好&#xff0c;但准确率却不太高&#xff0c;我们可以称之为 “弱分类器”&#xff0c;比如CART&#xff08;classification and regression tree 分类与回归树&#xff09;。 反之&#x…

大语言模型技术相关知识-笔记整理

系列文章目录 这个系列攒了很久。主要是前段之间面试大语言模型方面的实习&#xff08;被拷打太多次了&#xff09;&#xff0c;然后每天根据面试官的问题进行扩展和补充的这个笔记。内容来源主要来自视频、个人理解以及官方文档中的记录。方便后面的回顾。 2024-12-7: 对公式…