貪心算法套路模板+詳細適用場景+經典題目清單

1. 排序 + 貪心選擇

適用場景:

  • 任務調度問題:需要安排多個任務,盡量完成更多任務或最小沖突。

  • 區間調度問題:選出最多互不重疊的區間。

  • 區間覆蓋問題:用最少區間覆蓋某個范圍。

  • 合并區間問題:合并重疊區間。

  • 區間拆分、區間選擇優化等。

貪心思路:

  • 先按結束時間(或起始時間)排序

  • 依次選擇滿足條件的區間(如不重疊)

  • 局部選擇結束最早或起點最晚,給后續留最大空間

詳細題目:

    1. 無重疊區間(最少移除使區間不重疊)

    1. 用最少數量的箭射爆氣球(區間覆蓋)

    1. 合并區間(合并所有重疊區間)

    1. 會議室 II(最少會議室數量)

    1. 插入區間(插入一個區間并合并)

    1. 劃分字母區間(分割字符串使字符只出現一次)

func GreedyIntervalScheduling(intervals [][]int) int {if len(intervals) == 0 {return 0}// 1. 按區間結束時間排序sort.Slice(intervals, func(i, j int) bool {return intervals[i][1] < intervals[j][1]})count := 1             // 至少選一個區間end := intervals[0][1] // 當前選擇區間的結束時間// 2. 遍歷所有區間,選擇開始時間 >= 當前end的區間for i := 1; i < len(intervals); i++ {if intervals[i][0] >= end {count++end = intervals[i][1]}}return count
}

2. 最遠可達/跳躍類

適用場景:

  • 跳躍游戲(判斷能否跳到末尾)

  • 計算最少跳躍次數達到終點

  • 加油站問題(能否繞圈一周)

  • 投擲覆蓋范圍問題

貪心思路:

  • 維護當前最遠可達位置

  • 每一步更新最遠可達距離或當前位置

  • 檢查能否繼續前進

詳細題目:

    1. 跳躍游戲(能否到達末尾)

    1. 跳躍游戲 II(最少跳躍次數)

    1. 加油站(找到起點)

    1. 會議室 II(類似區間最大重疊數,也可用貪心管理資源)

    1. 用最少數量的箭射爆氣球(與跳躍范圍相似)

func CanJump(nums []int) bool {maxReach := 0for i := 0; i < len(nums); i++ {if i > maxReach {// 當前位置不可達return false}maxReach = max(maxReach, i+nums[i])}return true
}func max(a, b int) int {if a > b {return a}return b
}

3. 區間合并 / 覆蓋類

適用場景:

  • 合并重疊區間

  • 劃分區間或字符串

  • 最小覆蓋子串(雙指針配合貪心)

貪心思路:

  • 按起點排序

  • 合并或擴展覆蓋區間

  • 利用當前區間更新狀態

詳細題目:

    1. 合并區間

    1. 劃分字母區間

    1. 最小覆蓋子串

    1. 區間列表的交集

    1. 插入區間

func MergeIntervals(intervals [][]int) [][]int {if len(intervals) == 0 {return [][]int{}}sort.Slice(intervals, func(i, j int) bool {return intervals[i][0] < intervals[j][0]})merged := [][]int{intervals[0]}for i := 1; i < len(intervals); i++ {last := merged[len(merged)-1]if intervals[i][0] <= last[1] {// 重疊,合并區間if intervals[i][1] > last[1] {last[1] = intervals[i][1]}} else {// 無重疊,加入merged = append(merged, intervals[i])}}return merged
}

4. 買賣股票系列

適用場景:

  • 買賣股票問題求最大利潤

  • 允許買賣次數有限/無限

  • 買入賣出時機貪心選擇

貪心思路:

  • 對于無限次買賣,累積所有上漲差價

  • 對于有限次買賣,結合動態規劃和貪心

詳細題目:

    1. 買賣股票的最佳時機

    1. 買賣股票的最佳時機 II

    1. 買賣股票的最佳時機 III(結合DP)

    1. 買賣股票的最佳時機 IV(結合DP)

    1. 最佳買賣股票時機含冷凍期(DP)

func MaxProfit(prices []int) int {profit := 0for i := 1; i < len(prices); i++ {if prices[i] > prices[i-1] {profit += prices[i] - prices[i-1]}}return profit
}

5. 零錢兌換貪心(適用特定硬幣集)

適用場景:

  • 面額有貪心最優結構,如常見硬幣(1、5、10、25)

  • 求最少硬幣數

  • 注意非標準面額需DP

貪心思路:

  • 按面額降序,盡可能多用最大面額

  • 直到滿足目標金額或無法找零

詳細題目:

    1. 零錢兌換(DP推薦,貪心不一定適用)

  • 零錢兌換問題變形:只用特定面額找零問題

func CoinChangeGreedy(coins []int, amount int) int {// 降序排列面額sort.Slice(coins, func(i, j int) bool {return coins[i] > coins[j]})count := 0for _, coin := range coins {if amount == 0 {break}count += amount / coinamount %= coin}if amount != 0 {return -1}return count
}


6. 字符串貪心類

適用場景:

  • 生成字典序最小/最大字符串

  • 拼接最大數

  • 匹配模式(解碼字符串)

  • 字符串劃分問題

貪心思路:

  • 按字符優先級選擇

  • 利用棧或雙指針輔助選擇

  • 維護當前最優局部狀態

詳細題目:

    1. 拼接最大數

    1. 字符串解碼

    1. 去除重復字母

    1. 不同字符的最小子序列

    1. 劃分字母區間(字符串貪心和區間結合)

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/81498.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/81498.shtml
英文地址,請注明出處:http://en.pswp.cn/web/81498.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Qt QPaintEvent繪圖事件painter使用指南

繪制需在paintEvent函數中實現 用圖片形象理解 如果加了刷子再用筆就相當于用筆畫過的區域用刷子走 防雷達&#xff1a; 源文件 #include "widget.h" #include "ui_widget.h" #include <QDebug> #include <QPainter> Widget::Widget(QWidget…

SIGGRAPH 2025 | 快手可靈團隊提出3D感知的電影級文本到視頻生成框架CineMaster

Sora、可靈等視頻生成模型令人驚艷的性能表現使得創作者僅依靠文本輸入就能夠創作出高質量的視頻內容。然而&#xff0c;我們常見的電影片段通常是由導演在一個場景中精心布置多個目標的運動、攝像機拍攝角度后再剪輯而成的。例如&#xff0c;在拍攝賽車追逐的場景時&#xff0…

在springboot,禁止查詢數據庫種的某字段

使用Mp注解&#xff08;只對Mp提供的基礎方法有效&#xff09; 在注解TableField后面加一個select false,這樣就無法查詢到該表下密碼這個字段了 但需要注意的是如果是自己寫的sql就無法通過這一種方法實現了

Spring Boot + MyBatis-Plus實現操作日志記錄

創建數據庫表 CREATE TABLE sys_operation_log (log_id bigint NOT NULL AUTO_INCREMENT COMMENT 日志ID,operation_type varchar(20) NOT NULL COMMENT 操作類型,operation_module varchar(50) NOT NULL COMMENT 操作模塊,operation_desc varchar(200) DEFAULT NULL COMMENT …

開源多模態新標桿——BAGEL本地部署教程:7B參數撬動萬億數據

一、簡介 BAGEL &#xff0c;這是一個開源的多模態基礎模型&#xff0c;具有 70 億個激活參數&#xff08;總共 140 億個&#xff09;&#xff0c;并在大規模交錯多模態數據上進行訓練。 BAGEL 在標準多模態理解排行榜上超越了當前頂級的開源 VLMs 如 Qwen2.5-VL 和 InternVL…

SD卡+FATFS+Tinyjpeg圖片解碼顯示 (STM32F103VET6通過CubeMX快速建立工程)

先展示最終實現的功能效果如下: 1.目的與意義 為什么選用SD卡? 使用Nor-flash(W25Q系列)進行圖片的存取,需要先把圖片通過對應軟件批量處理為二進制bin文件,再通過SPI等通訊方式將 bin文件燒寫進Nor-flash才能進行使用,使用時還要記住每張圖片的首地址和對應字節數,MC…

數據結構-散列表查找(哈希表)

一&#xff0c;散列表查找定義 散列技術是在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f&#xff0c;使得每個關鍵字key對應一個存儲位置f(key)。查找時&#xff0c;根據這個確定的對應關系找到給定值key的映射f(key)&#xff0c;若查找集中存在這個記錄&#xff0…

Stable Diffusion 簡單了解一下

1. 幫我簡單介紹一下:StableDiffusion ?? Stable Diffusion 是什么? Stable Diffusion 是一個 文本生成圖像(Text-to-Image) 的人工智能模型。你只需要輸入一句話,它就能根據這句話生成一張高質量的圖片。 比如: "一只穿著太空服的貓,在月球上彈吉他"St…

R語言科研編程-標準偏差柱狀圖

生成隨機數據 在R中&#xff0c;可以使用rnorm()生成正態分布的隨機數據&#xff0c;并模擬分組數據。以下代碼生成3組&#xff08;A、B、C&#xff09;隨機數據&#xff0c;每組包含10個樣本&#xff1a; set.seed(123) # 確保可重復性 group_A <- rnorm(10, mean50, sd…

普羅米修斯監控CPU\內存匯聚圖

要找出內存使用率大于80%的主機&#xff0c;你可以使用以下PromQL查詢。這個查詢會計算每個節點的內存使用率&#xff0c;然后篩選出使用率超過80%的節點&#xff1a; (avg by(nodename) ((node_memory_MemTotal_bytes - node_memory_MemAvailable_bytes)* on(instance) group…

飛牛fnNAS手機相冊備份及AI搜圖

目錄 一、相冊安裝應用 二、手機開啟自動備份 三、開始備份 四、照片檢索 五、AI搜圖設置 六、AI搜圖測試 七、照片傳遞 現代的手機,已經成為我們最親密的“伙伴”。自從手機拍照性能提升后,手機已經完全取代了簡單的卡片相機,而且與入門級“單反”相機發起了挑戰。在…

華為高斯數據庫(GaussDB)深度解析:國產分布式數據庫的旗艦之作

高斯數據庫介紹 一、高斯數據庫概述 GaussDB是華為自主研發的新一代分布式關系型數據庫&#xff0c;專為企業核心系統設計。它支持HTAP&#xff08;混合事務與分析處理&#xff09;&#xff0c;兼具強大的事務處理與數據分析能力&#xff0c;是國產數據庫替代的重要選擇。 產…

網頁 CSS美化2(詳解)

這是接著上一篇css基礎的第二篇&#xff1a;主要開始對頁面的布局進行學習 顯示模式&#xff1a; 塊級模式&#xff08;Block&#xff09; 特點 &#xff1a; 元素會獨占一行&#xff0c;在其前后會自動換行&#xff0c;與其他塊級元素在垂直方向上排列。 寬度默認為所在容器…

JSON解析性能優化全攻略:協程調度器選擇與線程池饑餓解決方案

簡介 JSON解析是現代應用開發中的基礎操作,但在使用協程處理時,若調度器選擇不當,會導致性能嚴重下降。特別是當使用Dispatchers.IO處理JSON解析時,可能觸發線程池饑餓,進而引發ANR或系統卡頓。本文將深入剖析這一問題的技術原理,提供全面的性能檢測方法,并給出多種優化…

python打卡第37天

知識點回顧&#xff1a; 過擬合的判斷&#xff1a;測試集和訓練集同步打印指標模型的保存和加載 僅保存權重保存權重和模型保存全部信息checkpoint&#xff0c;還包含訓練狀態 早停策略 作業&#xff1a;對信貸數據集訓練后保存權重&#xff0c;加載權重后繼續訓練50輪&#xf…

【洛谷P9303題解】AC- [CCC 2023 J5] CCC Word Hunt

在CCC單詞搜索游戲中&#xff0c;單詞隱藏在一個字母網格中。目標是確定給定單詞在網格中隱藏的次數。單詞可以以直線或直角的方式排列。以下是詳細的解題思路及代碼實現&#xff1a; 傳送門&#xff1a; https://www.luogu.com.cn/problem/P9303 解題思路 輸入讀取與初始化&…

LangGraph + LLM + stream_mode

文章目錄 LLM 代碼valuesmessagesupdatesmessages updatesmessages updates 2 LLM 代碼 from dataclasses import dataclassfrom langchain.chat_models import init_chat_model from langgraph.graph import StateGraph, STARTfrom langchain_openai import ChatOpenAI # 初…

Pydantic 學習與使用

Pydantic 學習與使用 在 Fastapi 的 Web 開發中的數據驗證通常都是在使用 Pydantic 來進行數據的校驗&#xff0c;本文將對 Pydantic 的使用方法做記錄與學習。 **簡介&#xff1a;**Pydantic 是一個在 Python 中用于數據驗證和解析的第三方庫&#xff0c;它現在是 Python 使…

批量文件重命名工具

分享一個自己使用 python 開發的小軟件&#xff0c;批量文件重命名工具&#xff0c;主要功能有批量中文轉拼音&#xff0c;簡繁體轉換&#xff0c;大小寫轉換&#xff0c;替換文件名&#xff0c;刪除指定字符&#xff0c;批量添加編號&#xff0c;添加前綴/后綴。同時還有文件時…

多語言視角下的 DOM 操作:從 JavaScript 到 Python、Java 與 C#

多語言視角下的 DOM 操作&#xff1a;從 JavaScript 到 Python、Java 與 C# 在 Web 開發中&#xff0c;文檔對象模型&#xff08;DOM&#xff09;是構建動態網頁的核心技術。它將 HTML/XML 文檔解析為樹形結構&#xff0c;允許開發者通過編程方式訪問和修改頁面內容、結構和樣…