day 34 贪心算法

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

1005.K次取反后最大化的数组和
第一步:将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小
第二步:从前向后遍历,遇到负数将其变为正数,同时K–
第三步:如果K还大于0,那么反复转变数值最小的元素,将K用完
第四步:求和

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        for(int i=0; i<nums.size(); i++){
            if(nums[i]<0 && k){
                nums[i] = -nums[i];
                k--;
            }
            sum += nums[i];
        }
        if(k%2==0) return sum;
        sort(nums.begin(), nums.end());
        return sum - 2 * nums[0];
    }   
};

134. 加油站

  1. 暴力求解, 从每一个位置作为起始点,遍历。会超时。
  2. (1) 每个加油站的剩余量rest[i]为gas[i] - cost[i]。
    (2) curSum 累加剩余量rest[i]
    (3) curSum < 0 时 起始位置至少要是i+1
    解释: curSum>0 curSum + gas[i] > gas[i] 也就是说每次都有剩余油加成的前提下,在i处依旧断油了,那么没有剩余油加成,更会断油。也就是说明[0, i]区间都不能作为起始位置
    (4)找到可以跑一圈的起始位置

解法一:按部就班
i 指向起始位置, j指向站点 如果当前sum<0 i = j+1; 否则继续加下去。直到 绕弯完整的一圈或者是 i 指向的位置超过了 n。前者是找到start 后者是-1

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int cursum = 0;
        int n = gas.size();
        int i = 0, j=0;
        while(i < n && j<2*n -1){
            cursum  = cursum + gas[j%n] - cost[j%n];
            if(cursum < 0){
                cursum = 0;
                i = j+1;
            }
            j++;
        }
        if(i >=n ) return -1;
        else return i;
    }
};

解法 2 省略绕完整一圈的工作
将加油站点抽象为前后两个部分

0------ j j+1 -------size()-1
curSum[0 , j] < 0 curSum[j+1, size()-1] > 0
且curSum[0 , j] + curSum[j+1, size()-1] >= 0
前半部分最后一个到不了的站点缺少的油就是后半部分剩下的油来补充的,也就是说可以走通

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = 0;
        for (int i = 0; i < gas.size(); i++) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum < 0) {   // 当前累加rest[i]和 curSum一旦小于0
                start = i + 1;  // 起始位置更新为i+1
                curSum = 0;     // curSum从0开始
            }
        }
        if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
        return start;
    }
};

135. 分发糖果
1 . 每个小孩至少有一个糖果 vectorcandies(ratings.size(), 1);
4. 确保右边比左边大时 糖果比左边多 for(int i=1; i<ratings.size(); i++)
5. 确保左边比右边大时 糖果比右边大 for(int i=ratings.size()-2; i>=0; i–)
注意此时 在左边大于右边前提下 判断是否糖果已经比右边大
if(ratings[i] > ratings[i+1] && candies[i] <= candies[i+1])文章来源地址https://www.toymoban.com/news/detail-515999.html

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

        for(int i=ratings.size()-2; i>=0; i--){
            if(ratings[i] > ratings[i+1] && candies[i] <= candies[i+1]){
                candies[i] = candies[i+1] + 1;
            }
        }
        int sum=0;
        for(int i=0; i<ratings.size(); i++){
            sum += candies[i];
        }
        return sum;
    }
};

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

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

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

相关文章

  • DAY34——贪心part3

    1. 2.  代码随想录 (programmercarl.com)  3.

    2024年02月11日
    浏览(33)
  • 算法刷题day34:并查集

    今天写的题集是并查集,其实感觉有两个难点,一个是,要维护多余的信息和路径压缩,另一个难点则是抽象出来合并集合的这个操作,还是要不断地练习,看别人怎么去做,加油! 标签:并查集 思路: 模板题,没啥说的 题目描述: 示例代码: 标签:并查集 思路: 其实

    2024年03月21日
    浏览(65)
  • 算法记录 | Day37 贪心算法

    思路: 1.一旦出现strNum[i - 1] strNum[i]的情况(非单调递增),首先想让strNum[i - 1]–,然后strNum[i]给为9,这样这个整数就是89,即小于98的最大的单调递增整数。 2.向后遍历 从前向后遍历的话,遇到strNum[i - 1] strNum[i]的情况,让strNum[i - 1]减一,但此时如果strNum[i - 1]减一了,可能

    2023年04月22日
    浏览(32)
  • #算法记录 | Day33 贪心算法

    如果加油站提供的油总和大于等于消耗的汽油量,则必定可以绕环路行驶一周 假设先不考虑油量为负的情况,我们从「第 0 个加油站」出发,环行一周。记录下汽油量 gas[i] 和 cost[i] 差值总和 sum_diff,同时记录下油箱剩余油量的最小值 min_sum。 如果差值总和 sum_diff 0,则无论

    2023年04月18日
    浏览(41)
  • day27 贪心算法

    1.什么是贪心? 比如10张钞票,有1,5,20,100等面额,取五张,如何取得到数额最多的钱?每次取面额最大的那张钞票;就是每个阶段的局部最优;全局最优就是最后拿到的钞票数最大;局部最优推出全局最优; 题目描述 题目描述 题目描述 分析:摆动序列,就是前后相减保

    2024年02月16日
    浏览(34)
  • 贪心算法练习day.1

    贪心算法是一种常见的解决优化问题的方法,其基本思想就是在问题的每个决策阶段,都选择当前看起来最优的选择,即 贪心地做出局部的最优决策,以此得到全局的最优解, 例如在十张面额不同的钞票,让我们去取5张,那如何拿到最多的钱呢?那我们每次取钞票时只需要

    2024年04月27日
    浏览(35)
  • Day 37 贪心算法 6

    代码随想录  1. 思路 从后向前判断,如果不呈现单调递增的状态,后一位变成9,前一位-1。这里局部最优是每两位的最优解,从后向前线性遍历能得到全局最优。 但是有一点没有想清楚 。如果出现了上述的两位数倒序情况,之后的所有数字都应该变成9。例如52583,最小的递

    2024年02月01日
    浏览(39)
  • 贪心算法练习day2

    1)初始化最小字母为‘Z’,确保任何字母都能与之比较 2)遍历单词,找到当前未删除字母中的最小字母 3)获取当前位置的字母  current = word.charAt(i); 4)删除最小字母之前的所有字母  word=word.substring(index+1); 5)  将最小字母添加到结果字符,更新剩余可删除字母数量 t -=

    2024年02月20日
    浏览(40)
  • DAY40:贪心算法(九)单调递增的数字(贪心的思路)

    本题暴力解法也需要看一下,虽然暴力解法超时了,但是这种思路是一种很基础的思路,需要了解 数字是没有办法直接采用下标遍历的 ,如果 要for循环遍历每个位置的数字,需要把数字转成字符串string 当且仅当每个相邻位数上的数字 x 和 y 满足 x = y 时,我们称这个整数是

    2024年02月12日
    浏览(50)
  • Day37 贪心算法part06

    前面都想到了,结果最后n[i]给写错了直接写成9了,得把后面的全都改成9才行 摄像头的覆盖范围是上中下 遇到叶子结点,放到叶子结点的父节点 每隔两个空节点放一个摄像头 所以要用后序遍历 把结点分为三个状态:0无覆盖1有摄像头2有覆盖 空节点要设置为有覆盖的状态

    2024年02月19日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包