【leetcode】贪心算法介绍

news/2025/1/20 20:59:32/

详细且全面地分析贪心算法常用的解题套路、数据结构和代码逻辑如下:

  1. 找最值型:

    • 每一步选择都是局部最优解,最后得到的结果就是全局最优解。
    • 常用于找零钱问题、区间覆盖问题等。
    • 一般情况下,可以通过排序将数据进行处理,然后逐步选择最优解。
  2. 区间问题:

    • 将问题转化为区间覆盖或区间选取问题,按照某种规则选择区间。
    • 例如活动安排问题、最小会议室数量问题等。
    • 一般情况下,可以通过排序将区间按照起始位置或结束位置进行处理,然后按照规则选择区间。
  3. 贪心选择法:

    • 从问题的某个初始解出发,通过一系列迭代的过程,每次都选择当前最优解,逐步构建起问题的解。
    • 例如霍夫曼编码问题、任务调度问题等。
    • 一般情况下,可以通过优先队列(堆)来维护当前的最优解,每次选择最小(大)的元素。

常用的数据结构:

  1. 堆(优先队列):

    • 用于维护当前的最小值或最大值。
    • 常用于求Top K大(小)问题、合并K个有序链表等。
  2. 排序:

    • 排序算法可以帮助解决一些贪心算法问题。
    • 例如贪心选择法中每次选择当前最优解,可以通过对数据进行排序来实现。
    • 常用的排序算法有快速排序、归并排序、堆排序等。
  3. 哈希表:

    • 用于存储和查找元素。
    • 可以帮助解决一些贪心算法问题,例如最小覆盖子串问题、两数之和等。
    • 常用的哈希表实现有HashMap、HashSet等。

常用的代码逻辑:

  1. 循环:

    • 贪心算法常常需要通过遍历来选择当前最优解。
    • 使用循环进行遍历是常见的代码逻辑。
    • 常用的循环结构有for循环、while循环等。
  2. 递归:

    • 某些问题可以通过递归的方式来进行解决。
    • 例如将问题拆分为子问题进行求解。
    • 递归可以通过函数自身的调用来实现。
  3. 双指针:

    • 有些问题可以通过使用双指针的方式来进行解决。
    • 例如区间问题中的区间选取。
    • 双指针使用两个指针分别指向不同的位置,并根据问题的规则进行移动。

综上所述,贪心算法常用的解题套路、数据结构和代码逻辑包括找最值型、区间问题、贪心选择法、堆、排序、哈希表、循环、递归和双指针等。这些都是贪心算法解题过程中常用的技巧和方法,根据具体问题的特点选择适合的解题套路和数据结构,使用相应的代码逻辑来实现解题过程。


http://www.ppmy.cn/news/1356907.html

相关文章

探索AI视频生成新纪元:文生视频Sora VS RunwayML、Pika及StableVideo——谁将引领未来

探索AI视频生成新纪元:文生视频Sora VS RunwayML、Pika及StableVideo——谁将引领未来 sora文生视频,探索AI视频生成新纪元 由于在AI生成视频的时长上成功突破到一分钟,再加上演示视频的高度逼真和高质量,Sora立刻引起了轰动。在S…

如何确定分库还是 分表?

分库分表 分库分表使用的场景不一样: 分表因为数据量比较大,导致事务执行缓慢;分库是因为单库的性能无法满足要求。 分片策略 1、垂直拆分 水平拆分 3 范围分片(range) 垂直水平拆分 4 如何解决数据查询问题&a…

c++类和对象新手保姆级上手教学(中)

前言: 类和对象中篇,这里讲到的前4个默认成员函数,是类和对象中的重难点,许多资料上的讲法都非常抽象,难以理解,所以我作出这篇总结,分享学习经验,以便日后复习。 目录 6个默认成员…

DNS服务器出现异常如何解决

DNS,全称为域名系统(Domain Name System),是由解析器和域名服务器组成的。它的主要作用是将域名(如http://www.dexunyun.com)转换为对应的IP地址(如192.168.1.1),使得人们…

Kubernetes基础(二十二)-K8S的PV/PVC/StorageClass详解

1 概述 先来个一句话总结:PV、PVC是K8S用来做存储管理的资源对象,它们让存储资源的使用变得可控,从而保障系统的稳定性、可靠性。StorageClass则是为了减少人工的工作量而去自动化创建PV的组件。所有Pod使用存储只有一个原则:先规…

基础antdesign的业务型 短时间控件封装(复制即可使用)

{/* startFieldName 开始时间标识 endFieldName 结束时间标识 label 同form lable rules 是否开启规则校验 默认开启 detailData 详情数据,用于编辑回显 dateRange 限制结束时间的范围 例如:开始时间选择了 2024-02-05 ,加上 dateRange3 后 只…

THM学习笔记——Basic Pentesting

Find the services exposed by the machine What is the name of the hidden directory on the web server User brute-forcing to find the username & password What is the username? 有SMB,进行枚举 enum4linux -a 10.10.136.231 What is the password? Enumerate …

国密SSL证书怎么样?和普通算法证书有区别吗?

目前 99% 的互联网网站使用的是传统 RSA 算法的 SSL 证书。也许你会问,使用传统证书有什么影响吗?现阶段而言,确实没有什么影响。但我国绝大多数网站系统使用的都是传统 SSL 证书,一旦外国对我们执行断供、吊销此类产品&#xff0…