首页 > 编程语言 >代码随想录算法训练营第二十九天(贪心 三)

代码随想录算法训练营第二十九天(贪心 三)

时间:2024-08-28 22:54:17浏览次数:14  
标签:ratings 10 money candyVec 随想录 第二十九 size 糖果 贪心

力扣题部分:

134. 加油站

题目链接:. - 力扣(LeetCode)

题面:

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

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

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

 思路:

  如果总油量减去总消耗大于等于零那么一定可以跑完一圈,说明 各个站点的加油站 剩油量(gas[i] - cost[i])相加一定是大于等于零的。i从0开始累加省油量,和记为tank,(也就是油箱里的油量)一旦tank小于零,说明[0, i]区间都不能作为起始位置,因为这个区间选择任何一个位置作为起点,到i这里都会断油,那么起始位置从i+1算起,再从0计算count。

那么为什么一旦[0,i] 区间和为负数,起始位置就可以是i+1呢,i+1后面就不会出现更大的负数?

如果出现更大的负数,就是更新i,那么起始位置又变成新的i+1了。

那有没有可能 [0,i] 区间 选某一个作为起点,累加到 i这里 curSum是不会小于零呢? 如图:

如果 curSum<0 说明 区间和1 + 区间和2 < 0, 那么 假设从上图中的位置开始计数curSum不会小于0的话,就是 区间和2>0。

区间和1 + 区间和2 < 0 同时 区间和2>0,只能说明区间和1 < 0, 那么就会从假设的箭头初就开始从新选择其实位置了。

那么局部最优:当前累加rest[i]的和curSum一旦小于0,起始位置至少要是i+1,因为从i之前开始一定不行。全局最优:找到可以跑一圈的起始位置

局部最优可以推出全局最优,找不出反例,试试贪心!

其实这么严谨的求证想起来真的挺不容易的,我自己AC是在数据过多超时了才往那方面去假设的,不得不说贪心确实挺玄乎的,比较考察阅读题目发现内在联系规律的,大胆猜想也是重要的一环。

代码实现:

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int i, j, count, tank, countall = 0;
        for(i = 0, j = 0;countall < gas.size(); i = (i + 1) % gas.size())
        {
            if(gas[i] - cost[i] >= 0)
            {
                for(j = i, tank = 0;count < gas.size();j = (j + 1) % gas.size())
                {
                    tank += (gas[j] - cost[j]);
                    count ++;
                    countall ++;
                    if(tank < 0) break;
                }
                if(tank >= 0) return i;
            }
            if(count != 0) i = j, count = 0;
            else countall ++;
        }
        return -1;
    }
};

135. 分发糖果

题目链接:. - 力扣(LeetCode)

题面:

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

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

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

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

思路:

这道题目一定是要确定一边之后,再确定另一边,例如比较每一个孩子的左边,然后再比较右边,如果两边一起考虑一定会顾此失彼

先确定右边评分大于左边的情况(也就是从前向后遍历)

此时局部最优:只要右边评分比左边大,右边的孩子就多一个糖果,全局最优:相邻的孩子中,评分高的右孩子获得比左边孩子更多的糖果

如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个,所以贪心:candyVec[i] = candyVec[i - 1] + 1,如图。

代码如下:

for (int i = 1; i < ratings.size(); i++) {
    if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
}

再确定左孩子大于右孩子的情况(从后向前遍历

遍历顺序这里有同学可能会有疑问,为什么不能从前向后遍历呢?

因为 rating[5]与rating[4]的比较 要利用上 rating[5]与rating[6]的比较结果,所以 要从后向前遍历。

如果从前向后遍历,rating[5]与rating[4]的比较 就不能用上 rating[5]与rating[6]的比较结果了 。如图:

所以确定左孩子大于右孩子的情况一定要从后向前遍历!

如果 ratings[i] > ratings[i + 1],此时candyVec[i](第i个小孩的糖果数量)就有两个选择了,一个是candyVec[i + 1] + 1(从右边这个加1得到的糖果数量),一个是candyVec[i](之前比较右孩子大于左孩子得到的糖果数量)。

那么又要贪心了,局部最优:取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量,保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优:相邻的孩子中,评分高的孩子获得更多的糖果。

局部最优可以推出全局最优。

所以就取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量,candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多,也比右边candyVec[i + 1]的糖果多

代码实现:

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

860.柠檬水找零

题目链接:. - 力扣(LeetCode)

题面:

在柠檬水摊上,每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。

每位顾客只买一杯柠檬水,然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5 美元。

注意,一开始你手头没有任何零钱。

给你一个整数数组 bills ,其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零,返回 true ,否则返回 false 。

思路:

这道题算里面比较好想的。用数组money[3]记录三种钞票的数量(其实最大额的不需要记录,因为不会参与找零)

然后就是遍历数组bills,也就三种情况:

  • 情况一:账单是5,直接收下。
  • 情况二:账单是10,消耗一个5,增加一个10
  • 情况三:账单是20,优先消耗一个10和一个5,如果不够,再消耗三个5

可能有人问了,贪心体现在哪里呢?

体现的不多,也就情况三的优先(加粗部分)

如果有10尽量用10找零,因为美元10只能给账单20找零,而美元5可以给账单10和账单20找零,美元5更万能!

局部最优:遇到账单20,优先消耗美元10,完成本次找零。全局最优:完成全部账单的找零。

代码实现:

class Solution {
public:    
    bool lemonadeChange(vector<int>& bills) 
    {
        int money[3] = {0};
        for(int i = 0; i < bills.size(); i ++)
        {
            if(bills[i] == 5) money[0] ++;
            else if(bills[i] == 10)
            {
                if(money[0] == 0)return false;
                money[0] --, money[1] ++;
            }
            else
            {
                if(money[0] == 0)return false;
                if(money[1] > 0) 
                {
                    money[1] --, money[0] --;
                }
                else if(money[0] >= 3)
                {
                    money[0] -= 3;
                }
                else return false;
            }
        } 
        return true;  
    }
};

题目406暂且跳过。

标签:ratings,10,money,candyVec,随想录,第二十九,size,糖果,贪心
From: https://blog.csdn.net/b1ankwall/article/details/141639222

相关文章

  • 力扣热题100_贪心算法_45_跳跃游戏
    文章目录题目链接解题思路解题代码题目链接45.跳跃游戏II给定一个长度为n的0索引整数数组nums。初始位置为nums[0]。每个元素nums[i]表示从索引i向前跳转的最大长度。换句话说,如果你在nums[i]处,你可以跳转到任意nums[i+j]处:0<=j<=nums[i]......
  • 代码随想录 -- 哈希表 -- 四数之和
    18.四数之和-力扣(LeetCode)思路:(与三数之和类似,在外面加一层循环)    1. 先将nums 按升序排序    2. 初始状态:k=0,i= k+1,left= i+1,right= len(nums)-1        3. 进入第一层for循环:        如果 nums[k]>0andtarget>0 ......
  • 重头开始嵌入式第二十九天(Linux系统编程 网络通信 tcp)
    目录1.常见网络模型1.bs2.p2p3.cs2.网络编程之TCP(传输控制协议)1.TCP模型2.服务器端:1.socket();2、bind();3、listen();4、accept();5、接受函数:/发送函数:6、close()  ===>关闭指定的套接字id;3.客户端:1.connect();2、send()3、客户端信息获取4、客户端的信息bin......
  • 代码随想录算法day1-数组1
    题目1704.二分查找题目描述:给定一个n个元素有序的(升序)整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果目标值存在返回下标,否则返回-1。示例1:输入:nums=[-1,0,3,5,9,12],target=9输出:4解释:9出现在nums中并且下标为4示例2:......
  • 代码随想录算法训练营第一天 | 数组part01:数组理论基础,704. 二分查找,27. 移除元素 97
    数组理论基础数组是存放在连续内存空间上的相同类型数据的集合数组徐璈注意的是:数组的下标都是从0开始的数组内存空间是的地址是连续的正因为舒适的内存空间是连续的,所以在删除和增添元素的时候,需要移动其他元素的地址。在c++中,vector的底层实现是array,严格来说,vector是容......
  • 给自己复盘的随想录笔记-链表练习题(在整理ing)
    删除链表的倒数第N个节点双指针的经典应用,如果要删除倒数第n个节点,让fast移动n步,然后让fast和slow同时移动,直到fast指向链表末尾。删掉slow所指向的节点就可以了。思路是这样的,但要注意一些细节。分为如下几步:推荐大家使用虚拟头结点,这样方便处理删除实际头结点的逻辑,定......
  • 代码随想录day43 || 300 最长递增子序列,674 最长连续递增子序列,718 最长重复子数组
    300最长递增子序列varpath[]intvarresintfunclengthOfLIS(nums[]int)int{ //尝试回溯思路 iflen(nums)==1{ return1 } path=[]int{} res=0 backtracking(nums) returnres}funcbacktracking(nums[]int){ iflen(nums)==0{ iflen(pat......
  • 代码随想录算法day24 | 贪心算法part02 | 122.买卖股票的最佳时机II,55. 跳跃游戏,45.跳
    122.买卖股票的最佳时机II本题解法很巧妙,本题大家可以先自己思考一下然后再看题解,会有惊喜!力扣题目链接(opensnewwindow)给定一个数组,它的第 i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次......
  • 代码随想录训练营 Day42打卡 动态规划 part09 188.买卖股票的最佳时机IV 309. 最佳买
    代码随想录训练营Day42打卡动态规划part09一、力扣188.买卖股票的最佳时机IV给你一个整数数组prices和一个整数k,其中prices[i]是某支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成k笔交易。也就是说,你最多可以买k次......
  • 《第二十九章 性能优化 - 界面流畅度优化》
    一、引言在Android应用开发中,界面的流畅度直接影响着用户体验。一个卡顿、不流畅的界面可能会导致用户的不满和流失。在这一章中,我们将重点探讨如何通过减少布局层级和避免过度绘制来优化界面流畅度。二、减少布局层级(一)布局层级过多的影响布局层级过多会导致以下问......