首页 > 编程语言 >贪心算法之两端贪

贪心算法之两端贪

时间:2024-01-28 10:34:07浏览次数:25  
标签:两端 return ratings int candyVec points 算法 vector 贪心

这类题目一般是当前元素的位置既受前一个元素的影响又受后一个元素的影响。
题目一定是要确定一边之后,再确定另一边,例如比较每一个元素的左边,然后再比较右边,如果两边一起考虑一定会顾此失彼。
当确定一边后,就单独看排完序的数组,因为这时候只需考虑一边,因此容易找规律。
典型题目:
135. 分发糖果

点击查看代码
class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candyVec(ratings.size(), 1);
        // 从前向后
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
        }
        // 从后向前
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] ) {
                candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
            }
        }
        // 统计结果
        int result = 0;
        for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];
        return result;
    }
};

406.根据身高重建队列

点击查看代码
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);
        vector<vector<int>> que;
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1];
            que.insert(que.begin() + position, people[i]);
        }
        return que;
    }
};
  1. 用最少数量的箭引爆气球
点击查看代码
class Solution {
public:
 static bool cmp(vector<int>&a,vector<int>&b){
     return a[0]<b[0];
 }
    int findMinArrowShots(vector<vector<int>>& points) {
int sz=points.size();
sort(points.begin(),points.end(),cmp);
int count=1;
for(int i=1;i<sz;i++){
    if(points[i][0]>points[i-1][1]){++count;}
    else{
        points[i][1]=min(points[i-1][1],points[i][1]);
    }
}
return count;
    }
};

标签:两端,return,ratings,int,candyVec,points,算法,vector,贪心
From: https://www.cnblogs.com/yun-che/p/17992532

相关文章

  • 文心一言 VS 讯飞星火 VS chatgpt (188)-- 算法导论14.1 5题
    五、用go语言,给定n个元素的顺序统计树中的一个元素x和一个自然数i,如何在O(lgn)的时间内确定工在该树线性序中的第i个后继?文心一言,代码正常运行:在顺序统计树(也称为平衡二叉搜索树)中,要找到一个元素x的第i个后继,我们可以使用以下步骤:从根节点开始,使用递归或迭代方式沿......
  • day25 代码随想录算法训练营 17. 电话号码的字母组合
    题目:17.电话号码的字母组合我的感悟:一时间没理解没关系,只要不放弃,就会成长!!!理解难点:index是独立集合的起点,需要理解它。有些东西就是时间的积累代码难点:代码示例:classSolution:def__init__(self):self.letterMap=["",#0......
  • 代码随想录算法训练营第四天| 24. 两两交换链表中的节点 19.删除链表的倒数第N个节
    24.两两交换链表中的节点给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。题目链接:24.两两交换链表中的节点-力扣(LeetCode)建议画图,会更清晰一些。同时注意交换问题要用两个临时节点。class......
  • (坚持每天写算法)算法复习与学习part1基础算法part1-12——双指针算法
    双指针是一种思路,很多题都可能用得到,这里我就只选取Acwing网站的三道题(事实上我最近就是在这里刷题,leetcode反而不怎么去了,刷完这个网站的我就会去leetcode刷了)双指针一般来讲会在数组有序的情况下应用,但是如果是无序的也是有可能的,两个指针会遍历整个数组(如果条件允许的......
  • 文本分类识别Python+卷积神经网络算法+TensorFlow模型训练+Django可视化界面
    一、介绍文本分类系统,使用Python作为主要开发语言,通过选取的中文文本数据集("体育类","财经类","房产类","家居类","教育类","科技类","时尚类","时政类","游戏类","娱乐类"),基于TensorFlow搭建CNN卷积神经网络算法模型,并进行多轮迭代训练最后得到一个识......
  • Dijkstra算法
    \(Dijkstra\algorithm\)\(Principle\)以点为研究对象的贪心策略,和\(Prim\)类似。\(Implementation\step\)将起点标记;找条连接被标记的点集合中一点和没有被标记的点集合中一点最短的边;将该边连接的没有被标记的点加入被标记的点;将该新加入的被标记的点和它的所有邻接点......
  • 链表算法
    目录链表算法初始化节点1.删除链表的第N个节点2.删除链表中倒数第N个节点3.分块反转链表(K个一组翻转链表)4.反转链表I5.反转链表II(给定区间反转)6.判断是否为环形链表7.两数相加(两个链表相同位置相加)8.合并两个有序链表9.删除排序链表中的重复元素II10.旋转链表(将链表每个节......
  • 位运算在算法中的应用
    快速幂问题:给定整数\(a,\b,\p\)计算\(a^b\modp\)\((1\lea,b,p\le10^9)\)分析:我们可以将\(b\)转换成二进制:\[b=c_02^0+c_12^1+c_22^2+...+c_{k-1}2^{k-1}\]其中\(c_n\)的取值为\(0\)或者\(1\)那么有:\[a^b=a^{c_02^0+c_12^1+c_22^2+...+c_{k-1}2^{k-1......
  • 如何学习算法:什么时完全二叉树?完全二叉树有什么特点?
    完全二叉树我们知道树是一种非线性数据结构。它对儿童数量没有限制。二叉树有一个限制,因为树的任何节点最多有两个子节点:左子节点和右子节点。什么是完全二叉树?完全二叉树是一种特殊类型的二叉树,其中树的所有级别都被完全填充,除了最低级别的节点从尽可能左侧填充之外。完全二叉树的......
  • nodejs雪花ID算法(SnowflakeID)
    前言项目中常使用的三种id类型,分别是自增id、uuid、雪花id,这三种各有优劣。本篇主要实现nodejs中snowflake算法的代码。一、Snowflake实现这里需要加入big-integer的模块,下载npminstall--save big-integervarSnowflake=(function(){functionSnowflake(_......