贪心算法基础及leetcode例题

理论

本质:找到每个阶段的局部最优,然后去推导得到全局最优
两个极端:常识&&很难:

很多同学通过了贪心的题目,但都不知道自己用了贪心算法,因为贪心有时候就是常识性的推导,所以会认为本应该就这么做!

套路:
贪心没有套路,说白了就是常识性推导加上举反例
做题的时候,只要想清楚 局部最优 是什么,如果推导出全局最优,其实就够了。

贪心算法一般分为如下四步:

将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解
这个四步其实过于理论化了,我们平时在做贪心类的题目 很难去按照这四步去思考,真是有点“鸡肋”。

Leetcode题目

简单题

455.分发饼干

思路:大饼干 喂 胃口大的kid,才能充分利用
贪心算法基础及leetcode例题

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int j=s.length-1;
        int sum = 0;

        for(int i=g.length-1;i>=0;i--){
            if(j>=0 && s[j]>=g[i]){
                sum++;
                j--;
            }
        }
        return sum;
    }
}

中等题

序列问题---376. 摆动序列

股票问题---122. 买卖股票的最佳时机 II

两个维度权衡问题---135. 分发糖果

原文链接:https://www.cnblogs.com/yunshalee/p/17336137.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:贪心算法基础及leetcode例题 - Python技术站

(0)
上一篇 2023年4月20日
下一篇 2023年4月22日

相关文章

  • python opencv之SURF算法示例

    Python OpenCV之SURF算法示例 本文将介绍如何使用Python OpenCV库实现SURF算法,并提供两个示例说明。 SURF算法简介 SURF(Speeded Up Robust Features)算是一种用于图像特征提取和匹配的算法。它是SIFT算法改进版本,具有更快的速度和更好的鲁棒性。SURF算法的要步骤包括构建尺度空间、算Hessia…

    python 2023年5月14日
    00
  • C#数据结构与算法揭秘三 链表

    作为一本通俗易懂的C#数据结构与算法书籍,其第三章主要介绍链表(Linked List)的概念和基本操作。下面是链表的基本概念: 链表(Linked List)是一种动态数据结构,其中的元素按线性顺序排列,并且每个元素都称为一个结点(Node)。 每个结点都包含一个元素和一个指向下一个结点的指针(Pointer)。 相比于数组,链表的优势在于能够轻松地增加或…

    数据结构 2023年5月17日
    00
  • C语言实现带头结点的链表的创建、查找、插入、删除操作

    C语言实现带头结点的链表的创建、查找、插入、删除操作攻略 一、链表基本概念 链表是一种动态的数据结构,它可以在运行时动态地分配内存,支持数据的插入、删除等操作。链表(Linked List)由多个节点(Node)组成,每个节点包含两部分,一个是数据部分(Data),另一个是指向下一个节点的指针(Next)。 二、带头结点的链表 带头结点的链表是一种特殊的链表…

    数据结构 2023年5月17日
    00
  • Java数据结构之循环队列简单定义与用法示例

    Java数据结构之循环队列简单定义与用法示例 什么是循环队列? 循环队列是一种数据结构,它具有先进先出(FIFO)的特点,即最先进队列的元素总是被最先取出。不同于普通队列,循环队列的尾指针指向数组的头部,因此可以实现循环利用数组空间,提高存储空间的利用率,避免因队列的操作大量移动数组元素而导致的时间浪费。 循环队列的基本操作 循环队列的基本操作包括:入队、出…

    数据结构 2023年5月17日
    00
  • Java数据结构之链表实现(单向、双向链表及链表反转)

    Java数据结构之链表实现 链表基础概念 链表是一种数据结构,它由一系列节点(Node)组成,每个节点包含两个部分,一个是数据域(data),一个是指针域(next)。数据域存储数据信息,指针域指向下一个节点。 链表的种类很多,比如单向链表、双向链表、循环链表等等。 单向链表:链表的每个节点只有一个指针域,指向下一个节点。 双向链表:链表的每个节点有两个指针…

    数据结构 2023年5月17日
    00
  • 带你了解Java数据结构和算法之2-3-4树

    带你了解Java数据结构和算法之2-3-4树 1. 什么是2-3-4树 2-3-4树是一种自平衡二叉查找树,也叫B树的一种,它可以保持树的平衡,使得每个节点的左右子树高度差最多为1。在2-3-4树中,每个节点可以包含2个、3个或4个子节点,这也是其名称的来源。2-3-4树是B树的特殊形式,通常用于内存储存结构。 2. 2-3-4树的特点 2-3-4树的特点如…

    数据结构 2023年5月17日
    00
  • python聚类算法解决方案(rest接口/mpp数据库/json数据/下载图片及数据)

    以下是关于“Python聚类算法解决方案”的完整攻略: 简介 聚类算法是一种常见的机器学习算法,它可以将数据集分成不同的组或簇。在本教程中,我们将介绍如何使用Python实现聚类算法,并提供一些示例说明。 Python聚类算法实现 Python中有多种聚类算法可供选择,包括K-Means、层次聚类、DBSCAN等。以下是使用K-Means算法实现聚类的示例:…

    python 2023年5月14日
    00
  • C++数据结构之文件压缩(哈夫曼树)实例详解

    我来为您详细讲解一下“C++数据结构之文件压缩(哈夫曼树)实例详解”这篇文章的完整攻略: 文章基本信息 标题:C++数据结构之文件压缩(哈夫曼树)实例详解 作者:Coder_XWG 发布时间:2019年12月24日 文章概述 该篇文章主要讲解了哈夫曼树在文件压缩方面的应用。通过实例讲解了如何使用哈夫曼编码将文件进行压缩,以及如何解压缩被压缩的文件,并对文章中…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部