首页 > 编程语言 >「代码随想录算法训练营」第二十三天 | 贪心算法 part1

「代码随想录算法训练营」第二十三天 | 贪心算法 part1

时间:2024-07-29 16:17:35浏览次数:14  
标签:题目 nums int res 随想录 part1 算法 https com

455. 分发饼干

题目链接:https://leetcode.cn/problems/assign-cookies/
题目难度:简单
文章讲解:https://programmercarl.com/0455.分发饼干.html
视频讲解:https://www.bilibili.com/video/BV1MM411b7cq
题目状态:初次有贪心算法的总体概念,有点懵

思路:

先将饼干尺寸大的满足胃口大的小孩,直到遍历完。

代码:

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = s.size() - 1;
        int res = 0;
        for(int i = g.size() - 1; i >= 0; --i) {
            if(index >= 0 && s[index] >= g[i]) {
                res++;
                index--;
            }
        }
        return res;
    }
};

376. 摆动序列

题目链接:https://leetcode.cn/problems/wiggle-subsequence/
题目难度:中等
文章讲解:https://programmercarl.com/0376.摆动序列.html
视频讲解:https://www.bilibili.com/video/BV17M411b7NS
题目状态:贪心好难,只能看题解,自己做一点思路也没有

思路:

记录一下每个元素的前后坡度(有正负的),然后判断前后坡度符号是否一致,如果不一致就加1,如果一致就跳过。
注意:当有平坡出现的时候,只需要记录一次,并且前坡只有在发生改变的时候在需要变化。

代码:

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() == 1) return 1;
        int res = 1;
        int prediff = 0;
        int curdiff = 0;
        for(int i = 0; i < nums.size() - 1; ++i) {
            curdiff = nums[i + 1] - nums[i];
            if((prediff >= 0 && curdiff < 0) ||
               (prediff <= 0 && curdiff > 0)) {
                res++;
                prediff = curdiff;
            }
        }
        return res;
    }
};

53. 最大子数组和

题目链接:https://leetcode.cn/problems/maximum-subarray/
题目难度:中等
文章讲解:https://programmercarl.com/0053.最大子序和.html
视频讲解:https://www.bilibili.com/video/BV1aY4y1Z7ya
题目状态:还是学习思路...

思路:

先遍历前面的和,当前面的和为负数的时候,那个前面所有的内容相加就对后面的元素没有作用,直接从后面元素开始,一直遍历结束。期间会记录所有遍历的最大值。

代码:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int count = 0;
        int res = INT_MIN;
        for(int i = 0; i < nums.size(); ++i) {
            count += nums[i];
            if(count > res) res = count;
            if(count <= 0) count = 0;
        }
        return res;
    }
};

标签:题目,nums,int,res,随想录,part1,算法,https,com
From: https://www.cnblogs.com/frontpen/p/18330357

相关文章

  • C语言基础算法
    C语言基础算法目录C语言基础算法1、阶乘递归实现循环实现2、排序冒泡排序选择排序3、斐波那契数列4、ASCII码的使用1、阶乘递归实现#include<stdio.h>//递归函数计算阶乘intfactorial(intn){if(n==0||n==1)return1;elsereturnn......
  • 代码随想录day13 || 树定义以及遍历
    二叉树定义和种类二叉树是一种树形数据结构,其中每个节点最多有两个子节点,通常称为“左子节点”和“右子节点”。二叉树在计算机科学中有广泛的应用,比如表达式解析、排序算法、搜索算法等。二叉树的定义一个二叉树由一组节点组成,其中每个节点至多有两个子节点,分别称为左子节点和......
  • Day13 二叉树Part1 遍历
    递归遍历要理解递归,可以借助二叉树的递归遍历来理解。下面是二叉树递归遍历,以这个为例,来阐述下递归的原理。#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,val=0,left=None,right=None):#self.val=val#self.left=......
  • 《关于登甲智能建筑图像生成大模型算法的分析报告》
    一、算法全周期行为分析(一)算法安全                    信息内容安全:在生成图片的过程中,需要确保所生成的图片内容不包含违法、有害、侵权或违背社会道德的元素。例如,不能生成具有暴力、色情、歧视等不良内容的图片。信息源安全:对......
  • 问题 E: 深入浅出学算法060-友好城市
    题目描述有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸,而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市,但是由于河上雾太大,政府决定避免任意两条航道交叉,以避......
  • 【数据结构】排序算法
    目录排序冒泡排序选择排序直接插入排序希尔排序堆排序归并排序快速排序排序排序的概念:假设含有n个记录的序列为{R1,R2,R3,···,Rn},其相应的关键字分别为{K1,K2,K3,···Kn},需确定1,2,3,···,n的一种排列P1,P2,···,Pn,使其相应的关键字满足Kp1<=Kp2<=K......
  • 山东大学数据结构与算法实验13最小生成树(Prim算法/Kruskal算法)
    A : Prim算法题目描述使用prim算法实现最小生成树输入输出格式输入第一行两个整数n,e。n(1≤n≤200000)代表图中点的个数,e(0≤m≤500000)代表边的个数。接下来e行,每行代表一条边:ijw 表示顶点i和顶点j之间有一条权重为w的边输出最小生成树所有边的......
  • 烧录算法制作
    前言在使用Keil的时候,我们一般会通过一个下载器与目标芯片连接,这样就可以实现的代码下载或调试。那么下载器是如何将我们的应用程序烧写在我们芯片内部Flash当中的呢,是否可以同样的方式烧录在外部Flash上呢?这是此片文章所要说明的。MDK下载算法原理通过MDK创建一批与地址信息无......
  • 算法
    算法库函数next_permutation(start,end)prev_permutation(start,end)(全排列函数)[库函数介绍](C++中全排列函数next_permutation用法-CSDN博客)[库函数原理](C++中next_permutation函数的使用方法、原理及手动实现_c++next_permutation-CSDN博客)库函数原理基本解释:......
  • 最细哈希表相关的力扣题和讲解和Java、C++常用的数据结构(哈希法)来源于代码随想录,十分
    20240725一、什么时候适用什么样的结构。1.java中1.1HashSet:1.2TreeSet:1.3LinkedHashSet:1.4HashMap:1.5TreeMap:1.6LinkedHashMap:1.7总结2.c++中2.1std::unordered_set:2.2std::set:2.3std::multiset:2.4std::unordered_map:2.5std::map:2.6std::multimap:3代码......