重拾C++之菜鸟刷算法第15篇 --- 贪心算法

这篇具有很好参考价值的文章主要介绍了重拾C++之菜鸟刷算法第15篇 --- 贪心算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

买卖股票的最佳时机 II

题目

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。

返回 你能获得的 最大 利润

122. 买卖股票的最佳时机 II - 力扣(LeetCode)

题解

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 存储相邻两天的股票差价
        vector<int> profit(prices.size() - 1, 0);
        for(int i = 1; i < prices.size(); i++){
            profit.push_back(prices[i] - prices[i - 1]);
        }
        int sum = 0;
        // 累加所有正的利润,即为最大利润    
        for(int i = 0; i < profit.size(); i++){
            if(profit[i] > 0){
                sum += profit[i];
            }
        }
        return sum;
    }
};

跳跃游戏

题目

给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false

55. 跳跃游戏 - 力扣(LeetCode)

题解

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        if(nums.size() <= 1) return true;
        // 当前能够覆盖的最远距离
        for(int i = 0; i <= cover; i++){
            cover = max(i + nums[i], cover);
            if(cover >= nums.size() - 1) return true;
        }
        // 遍历完之后,仍未覆盖所有的数组,返回false
        return false;
    }
};

跳跃游戏 II

题目

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

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

  • 0 <= j <= nums[i]
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]

45. 跳跃游戏 II - 力扣(LeetCode)

题解

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size() == 1) return 0;// 当只有一个元素的时候,不需要跳跃也是终点值
        int curDistance = 0;
        int nextDistance = 0;
        int jumpSize = 0;
        for(int i = 0; i < nums.size(); i++){
            nextDistance = max(nums[i] + i, nextDistance);
            if(i == curDistance){
                jumpSize++;
                curDistance = nextDistance;
                if(nextDistance >= nums.size() - 1) break;
            } 
        }
        return jumpSize;
    }
};

加油站

题目

在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。

给定两个整数数组 gascost ,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1 。如果存在解,则 保证 它是 唯一 的。

134. 加油站 - 力扣(LeetCode)

题解

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int amountOil = 0;
        int min = INT_MAX;
        // 第一次遍历,计算从起点到每个加油站的油量总和,并且更新最小值
        for(int i = 0; i < gas.size(); i++){
            amountOil += (gas[i] - cost[i]);
            if (amountOil < min)
            {
                min = amountOil;// 更新最小值
            }
        }
        // 如果最小值大于等于0,说明一定存在解,而且0就是答案
        if(min >= 0) return 0;
        // 如果总油量少于0,那么一定跑不了全程
        if(amountOil < 0) return -1;
        // 找到从哪个加油站开始能够走完全程
        for(int i = gas.size() - 1; i >= 0; i--){
            min += (gas[i] - cost[i]);
            if(min >= 0) return i;
        }
        return -1;
    }
};

分发糖果

题目

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求,给这些孩子分发糖果:

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目

135. 分发糖果 - 力扣(LeetCode)

题解

从前向后遍历->从后向前遍历

class Solution {
public:
    int candy(vector<int>& ratings) {
    	// 存储孩子分到的糖果数,初始化为1,每个孩子至少分到一个糖果
        vector<int> candySum(ratings.size(), 1);
        // 第一遍遍历,从左往右,确保比左边评分高的孩子得到更多的糖果
        for(int i = 1; i < ratings.size(); i++){
            if(ratings[i - 1] < ratings[i]){
                candySum[i] = candySum[i - 1] + 1; 
            }
        }
		// 第二遍遍历,从右往左,确保比右边评分高的孩子分到更多的糖果
        for(int i = ratings.size() - 2; i >= 0; i--){
            if(ratings[i] > ratings[i + 1]){
            	// 比较右边孩子的糖果数加1和当前孩子的糖果数
            	// 取其中的较大值,确保比右边评分高的孩子分到更多的糖果
                candySum[i] = max(candySum[i + 1] + 1, candySum[i]);
            }
        }
        return accumulate(candySum.begin(), candySum.end(), 0);
    }
};

根据身高重建队列

题目

假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ,前面 正好ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ,其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性(queue[0] 是排在队列前面的人)。

406. 根据身高重建队列 - 力扣(LeetCode)

题解 – vector

class Solution {
public:
    """
    在这个比较函数中,首先比较两个人的身高(a[0]和b[0]表示两人的身高);
    如果身高相同,则按照前面的人数(a[1]和b[1]表示两人前面的人数)升序排列;
    如果身高不同,则按照身高降序排列。
    """
    static bool cmp(const vector<int>& a, const vector<int>& b){
        if(a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }
    
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        vector<vector<int>> queue;
        for(int i = 0; i < people.size(); i++){
            int position = people[i][1];
            // 将当前人插入到que向量中的合适位置,保证队列的前面有正确数量的人。
            queue.insert(queue.begin() + position, people[i]);
        }
        return queue;
    }
};

题解 — list文章来源地址https://www.toymoban.com/news/detail-841827.html

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b){
        if(a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        list<vector<int>> queue;
        for(int i = 0; i < people.size(); i++){
            int position = people[i][1];
            list<vector<int>>::iterator it = queue.begin();
            while(position--){
                it++;
            }
            queue.insert(it, people[i]);
        }
        return vector<vector<int>> (queue.begin(), queue.end());
    }
};

到了这里,关于重拾C++之菜鸟刷算法第15篇 --- 贪心算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • c++—0/1背包问题--贪心算法(详解)

    贪心算法的基本思想 •贪心算法的特点是每个阶段所作的选择都是局部最优的,它期望通过所作的局部最优选择产生出一个全局最优解。 贪心与动态规划: 与动态规划不同的是,贪心是 鼠目寸光 ; 动态规划是 统揽全局 。 贪心:每个阶段产生的都是局部最优解 贪心算法的

    2024年02月04日
    浏览(42)
  • C++ 求最大子序列和(贪心算法)

    #include \\\"iostream\\\" #include \\\"vector\\\" using namespace std; class Solution { // 得到一个最大的负数 int isAllLow(vectorint nums){ int max=nums[0]; for (int i = 1; i nums.size(); ++i) { if(maxnums[i]){ max=nums[i]; } } return max; } public: // 求最大子序列 int maxSubArray(vectorint nums) { int sum=0; int maxsum=this-isAllLow(nums); // 如果是一个

    2024年02月07日
    浏览(43)
  • 秒懂百科,C++如此简单丨第二十天:贪心算法2

    目录 Everyday English 前言 洛谷 P1031 均分纸牌 题目描述 思路点拨 AC代码 洛谷 P1094 纪念品分组 题目描述 样例输入 样例输出  思路点拨 AC代码 洛谷 P2660 zzc 种田  题目描述 思路点拨 AC Code 结尾 Don\\\'t miss the opportunity. 机不可失,时不再来。 这节课是贪心算法的习题课,我们会讲解

    2024年02月20日
    浏览(40)
  • 2023华为OD机试真题【区间交叠/贪心算法】【Python Java C++】

    给定坐标轴上的一组线段,线段的起点和终点均为整数并且长度不小于1,请你从中找到最少数量的线段,这些线段可以覆盖住所有线段。 输入描述 第一行输入为所有线段的数量,不超过10000,后面每行表示一条线段,格式为”x,y”, x和y 分别表示起点和终点,取值范围是

    2024年02月13日
    浏览(56)
  • 算法分析与设计-会场安排问题(贪心)(通俗易懂,附源码和图解,含贪心选择性质和最优子结构性质的证明)(c++)

    (一)题目 问题描述 假设在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点有着不同颜色的最小着色数,相当于

    2024年02月07日
    浏览(95)
  • C++(15): STL算法:排序(sort)

            std::sort 是 C++ 标准库 algorithm 中提供的一个函数,用于对容器(如数组、向量等)中的元素进行排序。它基于比较操作对元素进行排序,通常使用高效的排序算法,如快速排序、归并排序或堆排序等。         在实际应用中,std::sort 通常会根据输入数据的大

    2024年04月12日
    浏览(35)
  • 菜鸟教程《Python 3 教程》笔记(15):数据结构

    笔记带有个人侧重点,不追求面面俱到。 出处: 菜鸟教程 - Python3 数据结构 在列表的最后添加或者弹出元素速度快,然而在列表里插入或者从头部弹出速度却不快(因为所有其他的元素都得一个一个地移动)。 遍历字典: 遍历列表: 遍历多个序列: 反向遍历:

    2024年02月10日
    浏览(48)
  • 《算法导论》15.5 最优二叉搜索树(含C++代码)

    给定一个n个不同的已排序的序列K=k1,k2, … kn(因此k1k2…kn),我们希望用这 些构造一棵二叉搜索树。对每个k,都有一个概率p,表示其搜索频率。有些要搜 索的值可能不在K中,因此我们还有n+1个“伪\\\"d0,d1,d2, …dn,表示不在K中的值。d 0 表示所有小

    2024年02月03日
    浏览(38)
  • 缓存替换策略:LRU-K算法详解及其C++实现 CMU15-445 Project#1

    CMU 15-445 (FALL 2022) Project #1 Task#2 LRU-K 替换策略详解实现,尽量提供思路,也可以为其他同学实现LRU-K算法做参考 参考文献:The LRU-K page replacement algorithm for database disk buffering (acm.org) 在网上都找不到其他参考,只有这一篇1993年的论文 LRU-K替换策略 LRU-K是LRU算法的一种衍生。强烈

    2023年04月12日
    浏览(37)
  • 贪心算法问题实验:贪心算法解决TSP问题

    TSP问题是指旅行商问题,即给定一组城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题,在运筹学和理论计算机科学中有着广泛的应用。 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最

    2024年02月03日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包