力扣刷题之贪心算法(c++)(代码片段)

哈喽喔德 哈喽喔德     2022-12-28     272

关键词:

(学习参考书:LeetCode101)

贪心算法

贪心算法采用贪心的策略,保证每次操作都是局部最优的,从而使最后得到是全局最优的。

解题步骤:

  1. 将问题分解为若干个子问题,寻找合适的贪心策略
  2. 求解每一个子集的最优解
  3. 将局部最优解迭代成全局最优解

力扣例题

455.分发饼干

分析:

因为饥饿度最小的孩子最容易吃饱,所以优先考虑这个孩子。为了使剩下的饼干尽可能的满足饥饿度更大的孩子,所以应该把大于等于这个孩子饥饿度的且最小的饼干给这个孩子。然后采取同样的策略,直到没有满足的饼干为止。

题解:

class Solution 
public:
    int findContentChildren(vector<int>& g, vector<int>& s) 
		//将饼干和孩子从小到大排序
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());

		//初始化辅助变量
        int cnt = 0;
        int j = 0;

		//循环至一方没有剩余
        while(cnt<g.size()&&j<s.size())
			//当孩子能吃饱时,同时++进行下一组比对
			//当孩子不能吃饱时,这个孩子继续和下一个饼干匹配
            if(g[cnt]<=s[j])
                ++cnt;
            
            ++j;
        

        return cnt;
    
;

135.分发糖果

分析:

只需要两次遍历,把所有孩子糖果数初始化为1;先从左到右遍历一遍,如果右边孩子的评分比左边的高,则右边更新为左边的糖果数+1;再从右往左遍历,如果左边的右边高,且左边孩子的糖果数不大于右边孩子的糖果数,则左边更新为右边的+1。

题解:

class Solution 
public:
    int candy(vector<int>& ratings) 
        int size = ratings.size();
		//如果只有一个孩子返回1即可
        if(size==1)
            return size;
        
				
		//创建一个数组,表示每个孩子对应的糖果数,初始值都为1
        vector<int> v(size,1);

		//从左往右遍历
        for(int i=1;i<size;++i)
            if(ratings[i-1]<ratings[i])
                v[i] = v[i-1]+1;
            
        

		//从右往左遍历
        for(int i=size-1;i>0;--i)
            if(ratings[i-1]>ratings[i])
				//需要判断是否左边已经大于右边
                v[i-1] = max(v[i-1],v[i]+1);
            
        
				
		//求和得出需要的总糖果数
        return accumulate(v.begin(),v.end(),0);
    
;

435.无重叠区间

分析:

选择的区间结尾越小,余留给其他区间的空间就越大,就能保留更多的区间。因此采取的贪心策略是,优先保留结尾笑且不相交的区间。先把区间按照结尾大小排序,每次选择结尾最小且与前一个选择的区间不重叠的区间。

题解:

class Solution 
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) 
		//无区间直接返回0
        if(intervals.empty())
            return 0;
        
				
		//使用自定义规则的sort函数对区间按照结尾大小排序
		//这里定义规则的vector<int> a用法没错,但是在力扣上超时
		//应该替换为const auto& a
        sort(intervals.begin(),intervals.end(),
        [](vector<int> a,vector<int> b)
            return a[1]<b[1];
        );

	    int cnt = 0;//计数器
        int start = intervals[0][1];//初始设置为第一个区间的结尾
        for(int i=1;i<intervals.size();++i)
            if(intervals[i][0]<start)
				//当下一个区间的开始与上一个区间的结尾重合时,应该删除该区间
                ++cnt;
            
            else
				//当不重合时,更新需要比较的区间的结尾
                start = intervals[i][1];
            
        

        return cnt;
    
;

力扣刷题之双指针(c++&java)(代码片段)

(学习参考书:LeetCode101)双指针双指针主要用于遍历数组,两个指针指向不同的元素,从而协同完成任务。也可以延申多个数组的多个指针。若两个指针指向同一数组,遍历方向相同且不会相交,则... 查看详情

leetcode刷题之贪心算法(c++&java)(代码片段)

...求解每一个子集的最优解将局部最优解迭代成全局最优解力扣例题455.分发饼干分析:因为饥饿度最小的孩子最容易吃 查看详情

力扣刷题:四数之和(c++)(代码片段)

给你一个由n个整数组成的数组nums,和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a],nums[b],nums[c],nums[d]](若两个四元组元素一一对应,则认为两个四元组重复):0<=a,b,c,d<... 查看详情

力扣刷题:四数之和(c++)(代码片段)

给你一个由n个整数组成的数组nums,和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a],nums[b],nums[c],nums[d]](若两个四元组元素一一对应,则认为两个四元组重复):0<=a,b,c,d<... 查看详情

力扣刷题算法笔记(javascript版)(代码片段)

...很多算法这个up主讲的真的非常好适合小白去听算法都是力扣难度中等和简单的b站视频链接1、岛屿最大面积(求两数最大和)解析:提供一个数组,给了一个target要求是在数组中找到两个数的和为target思路:1... 查看详情

力扣刷题:加一(c++和c#)(代码片段)

给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。最高位数字存放在数组的首位,数组中每个元素只存储单个数字。你可以假设除了整数0之外,这个整数不会以零开头。示例1:输入:... 查看详情

力扣刷题:加一(c++和c#)(代码片段)

给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。最高位数字存放在数组的首位,数组中每个元素只存储单个数字。你可以假设除了整数0之外,这个整数不会以零开头。示例1:输入:... 查看详情

力扣刷题每日打卡(代码片段)

​力扣刷题:重新排列数组:/***Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*/int*shuffle(int*nums,intnumsSize,intn,int*returnSize)if(numsSize==1)*returnSize=1;returnnums;in 查看详情

力扣刷题每日打卡(代码片段)

​力扣刷题:重新排列数组:/***Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*/int*shuffle(int*nums,intnumsSize,intn,int*returnSize)if(numsSize==1)*returnSize=1;returnnums;in 查看详情

力扣刷题-搜索插入位置(代码片段)

力扣题目链接题目描述给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。使用时间复杂度为O(logn)的算法。你可以假设数组中无重... 查看详情

力扣刷题算法笔记(javascript版)下(代码片段)

上篇链接:力扣刷题算法笔记(javascript版)上视频链接:人人都能看得懂的Leetcode力扣刷题教程合集在笔记上中一共学习了31道算法题,剩下大概20到算法题在花两天的学习和总结一下1、打家劫舍题目描述࿱... 查看详情

力扣刷题:寻找峰值(java实现)(代码片段)

题目:峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。你可以假设nums[-1]=nums[n]=... 查看详情

力扣刷题(代码片段)

两数之和给定一个整数数组nums和一个目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。示例:给定nums=[2... 查看详情

力扣刷题:快乐数(java实现)(代码片段)

题目描述:编写一个算法来判断一个数n是不是快乐数。「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为1,也可能是无限循环但始终变... 查看详情

力扣刷题详解(含代码动态展示)(代码片段)

(文章目录)一、448.找到所有数组中消失的数字1.完整过程动态展示2.代码实现int*findDisappearedNumbers(int*nums,intnumsSize,int*returnSize)int*ptr=(int*)malloc(sizeof(int)*numsSize);intindex=0;intnoindex=0;while(index<numsSize)if(num 查看详情

力扣刷题:矩阵置零(java实现)(代码片段)

题目:给定一个mxn的矩阵,如果一个元素为0,则将其所在行和列的所有元素都设为0。请使用原地算法。进阶:一个直观的解决方案是使用O(mn)的额外空间,但这并不是一个好的解决方案。一个简单的改进方案... 查看详情

力扣刷题:括号生成(java实现)(代码片段)

数字n代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且有效的括号组合。有效括号组合需满足:左括号必须以正确的顺序闭合。示例1:输入:n=3输出:["((()))","(()())",&... 查看详情

力扣刷题:加一(c++和c#)(代码片段)

给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。最高位数字存放在数组的首位,数组中每个元素只存储单个数字。你可以假设除了整数0之外,这个整数不会以零开头。示例1:输入:... 查看详情