贪心算法基础及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中超简单的字符分割算法记录(车牌识别、仪表识别等)

    Python中超简单的字符分割算法记录 字符分割是图像处理中的一个重要问题,它的主要作用是将一张图像中的字符分割出来,以便进行后续的识别和处理。本文将介绍Python中超简单的字符分割算法,以及两个示例说明。 算法原理 Python中超简单的字符分割算法的基本思想是通过对图像进行二值化处理,然后对二值化后的图像进行连通域分析,最后根据连通域的位置和大小将字符…

    python 2023年5月14日
    00
  • Java数据结构BFS广搜法解决迷宫问题

    Java数据结构BFS广搜法解决迷宫问题 什么是BFS广搜法? 广度优先搜索(BFS)是一种遍历或搜索数据结构(例如树或图)的算法经典方法之一,也是解决迷宫问题的有效解法之一。BFS方法是从图的某个节点出发,以广度优先的方式依次访问与该节点相通的各节点,直到访问所有节点。BFS算法主要借助队列的数据结构来实现。 解决迷宫问题的具体实现 数据准备: 在解决迷宫…

    数据结构 2023年5月17日
    00
  • rsa详解及例题及python算法

    下面是详细讲解“RSA算法详解及例题及Python算法”的完整攻略,包含两个示例说明。 RSA算法简介 RSA算法是一种非对称加密算法,的基本原理是利用两个大质数的乘积作为公钥,而这两个质数的乘积作为私钥。RSA算的优点是安全高,但是加解速度较慢。 RSA算法的实现 下是RSA算法的实现过程: 1. 两个大质数p和q 这两个质数的乘积n=p*q,n的长度就是…

    python 2023年5月14日
    00
  • Java中使用数组实现栈数据结构实例

    下面是Java中使用数组实现栈数据结构实例的完整攻略: 步骤一:定义栈类 我们可以通过定义一个名为 Stack 的类来创建栈类,其中包含以下属性: 一个整型的变量 top,用于存储当前栈顶的位置 一个整型的数组 items,用于存储栈中的元素 一个整型的变量 capacity,用于表示栈的容量 代码如下所示: public class Stack { pri…

    数据结构 2023年5月17日
    00
  • C语言全面梳理结构体知识点

    C语言全面梳理结构体知识点 什么是结构体? 结构体是一种自定义的数据类型,它可以包含多个不同类型的成员变量,并且这些成员变量可以通过一个变量名来访问。结构体的定义需要使用关键字struct,并且需要指定结构体的类型名和成员变量。例如: struct Person { char name[20]; int age; float height; }; 以上代码就…

    数据结构 2023年5月17日
    00
  • python如何实现常用的五种排序算法详解

    下面是关于“Python实现常用的五种排序算法详解”的完整攻略。 1. 排序算法理论基础 排序算法是一种常用的算法,它可以一组数据按照一定的规则进行排序。常用的排序算法有五种,分别是冒泡排序、选择排序、插入排序、速排序和归并排序。 1.1 冒泡排序 冒泡排序是一种简单的排序算法,它的基本思想是通过邻元素之间的较和交换来实现排序。具体实现过程是从第一个元素开始…

    python 2023年5月13日
    00
  • Lua中使用table实现的其它5种数据结构

    Lua中使用table可以实现多种数据结构,除了Lua原生支持的数组、哈希表之外,我们还可以用table来实现其他五种数据结构,这些数据结构包括集合(Set)、队列(Queue)、双端队列(deque)、堆栈(stack)以及链表(List)。 Set 集合数据结构中的元素是无序的、不重复的。使用table来实现集合数据结构,可以将元素作为table的key…

    数据结构 2023年5月17日
    00
  • MySQL数据库体系架构详情

    MySQL数据库体系架构是MySQL数据库自身的发展和演变过程中逐渐形成的一个庞大的体系。这个体系由多个组件构成,包括连接器、查询缓存、解析器、优化器、执行器、存储引擎等多个部分,其中存储引擎是其中最具有代表性的组件之一。在这篇攻略中,我们将详细讲解MySQL数据库体系架构的各个部分,介绍它们各自的功能和作用。 连接器 MySQL的连接器负责与客户端建立连接…

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