柚子快報(bào)邀請碼778899分享：算法 C++貪心

http://yzkb.51969.com/

前言

C++算法與數(shù)據(jù)結(jié)構(gòu) 打開打包代碼的方法兼述單元測試

簡介

貪心算法（Greedy Algorithm）是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)（即最有利）的選擇，從而希望導(dǎo)致結(jié)果是全局最好或最優(yōu)的算法策略。貪心算法的正確性必須證明。常見的證明方法有五種：一，反證法。二，數(shù)學(xué)歸納法。三，決策包容性。 四，擴(kuò)展決策范圍。五，臨項(xiàng)交換。

決策包容性

如果存在最優(yōu)解，增加某種條件限制后，仍然有最優(yōu)解。故只需要考慮此種條件下的最優(yōu)解。

【C++二分查找 貪心 決策包容性】826. 安排工作以達(dá)到最大收益1708【C++棧 貪心 決策包容性】3170. 刪除星號以后字典序最小的字符串1772【C++二分查找 貪心 決策包容性】2576. 求出最多標(biāo)記下標(biāo)1843【C++二分查找 貪心 決策包容性】1488. 避免洪水泛濫1973【貪心 決策包容性】2561. 重排水果2221【貪心 決策包容性 】757. 設(shè)置交集大小至少為2348

臨項(xiàng)交換（微擾）

證明在任意局面下，任何對局部最優(yōu)策略的微小改變都會造成整體結(jié)果變差。經(jīng)常用于以“排序”為貪心策略的證明。

【C++貪心 臨項(xiàng)交換】3219. 切蛋糕的最小總開銷 II1789【 貪心 臨項(xiàng)交換 多指針】2931. 購買物品的最大開銷1822【C++貪心 臨項(xiàng)交換 】1665. 完成所有任務(wù)的最少初始能量1900【反悔堆 優(yōu)先隊(duì)列 臨項(xiàng)交換 決策包容性】630. 課程表 II無

擴(kuò)展決策范圍（放縮法）

在思考貪心算法時(shí)，有時(shí)候不容易直接證明局部最優(yōu)決策的正確性，此時(shí)可以往后多擴(kuò)展一步，進(jìn)而對當(dāng)前的決策進(jìn)行驗(yàn)證。擴(kuò)展決策范圍，即往后多看一步。

數(shù)學(xué)歸納法

【C++貪心 數(shù)學(xué)歸納法】1054. 距離相等的條形碼|1701

常見場景

中位數(shù)貪心：

pos[0…n-1]升序，記錄了所有房間的位置，將郵筒放在何處，郵筒到各戶的距離最短。 結(jié)論：如果n為偶數(shù)，則pos[n/2-1]到pos[n/2]之間；如果n為奇數(shù)，pos[n/2]。 下面用分組法和擴(kuò)展決策范圍來證明。 先假定n是偶數(shù)，分組法：pos[i]和pos[n-1-i]一組，任意一組最小距離為pos[n-1-i]-pos[i]，放在兩者的中間，可以取最小值。 當(dāng)n =2時(shí)，放在中間可以取最小值。 當(dāng) n=4,放置pos[1]和pos[2]中間可以取最小值。

?

\cdots

? 放置到pos[n/2-1]和pos[n/2]可以取最小值。 當(dāng)n為奇數(shù)時(shí)：郵箱放到pos[i]，各組取最小值，pos[i]為0。

【動(dòng)態(tài)規(guī)劃】【中位數(shù)貪心】【C++算法】1478. 安排郵筒2190【貪心算法】【中位貪心】2968.執(zhí)行操作使頻率分?jǐn)?shù)最大2444【動(dòng)態(tài)規(guī)劃】【前綴和】【中位數(shù)貪心】2463. 最小移動(dòng)總距離2453【對頂隊(duì)列】【中位數(shù)貪心】【前綴和】3086. 拾起 K 個(gè) 1 需要的最少行動(dòng)次數(shù)2672

臨項(xiàng)不同

n個(gè)字符，能否讓相鄰的字符不同。 性質(zhì)一：出現(xiàn)次數(shù)最多的字符出現(xiàn)次數(shù)<= n/2。則限制隊(duì)首不為指定字符也可以讓相鄰不相等。 性質(zhì)二：n是奇數(shù)。出現(xiàn)最多的條形碼出現(xiàn)n/2+1次。如果隊(duì)首可以為此條形碼，則可以讓相鄰不相等。 下面用數(shù)學(xué)歸納法來證明。 n為1成立：{a} n為2成立：{a,b},{b,a} n為3成立：{a,b,a} {a,b,c}{a,c,b} 從小到大證明n = 4 To

∞

\infty

∞ n為偶數(shù)： 如果存在兩個(gè)眾數(shù)為n/2，將任意眾數(shù)放到隊(duì)首，余下的符合性質(zhì)二。 否則，將任意眾數(shù)放到隊(duì)首，余下的符合性質(zhì)一。 n為奇數(shù)： 如果眾數(shù)為n/2+1，則只有一個(gè)眾數(shù)。否則兩個(gè)眾數(shù)的數(shù)量為n+1，與n個(gè)數(shù)矛盾。 將眾數(shù)放到隊(duì)首，余下的符合性質(zhì)一。 從上面的證明過程得知：如果有解，則將眾數(shù)放到最前面，一定存在解。

【C++貪心 數(shù)學(xué)歸納法】1054. 距離相等的條形碼1701【C++二分查找 貪心】2856. 刪除數(shù)對后的最小數(shù)組長度1749【C++貪心】1953. 你可以工作的最大周數(shù)1803

反悔貪心

發(fā)現(xiàn)無法貪心時(shí)，再更改。如：完成第i個(gè)任務(wù)需要task[i]塊磚頭或一個(gè)梯子。問最多能完成多少個(gè)任務(wù)，必須依次次完成任務(wù)。兩種反悔貪心法：一，優(yōu)先用磚頭，磚頭不夠，就用梯子完成需要磚頭最多的任務(wù)。二，優(yōu)先用梯子，梯子不夠。將需要磚頭最少的梯子換成磚頭。

【反悔貪心 反悔堆】1642. 可以到達(dá)的最遠(yuǎn)建筑1962【大根堆】【反悔堆】【反悔貪心】【C++算法】871 最低加油次數(shù)2074【反悔堆 反悔貪心】2813. 子序列最大優(yōu)雅度2582【反悔貪心】【優(yōu)先隊(duì)列】3049. 標(biāo)記所有下標(biāo)的最早秒數(shù) II3111

未分類（2024年10月24整理)

【排序 貪心】3107. 使數(shù)組中位數(shù)等于 K 的最少操作數(shù)1604【C++貪心】2522. 將字符串分割成值不超過 K 的子字符串1604【C++貪心】2567. 修改兩個(gè)元素的最小分?jǐn)?shù)1608【C++貪心】2086. 喂食倉鼠的最小食物桶數(shù)1622【C++貪心 位運(yùn)算】2571. 將整數(shù)減少到零需要的最少操作數(shù)1649【C++二分查找 貪心】792. 匹配子序列的單詞數(shù)1695【C++貪心】2498. 青蛙過河 II1759【C++ 貪心 滑動(dòng)窗口 前后綴分解】948. 令牌放置1762【C++貪心】1262. 可被三整除的最大和1762【C++貪心】2712. 使所有字符相等的最小成本1791【C++貪心】1953. 你可以工作的最大周數(shù)1803【C++ 貪心 雙指針】2576. 求出最多標(biāo)記下標(biāo)1843【C++貪心】1775. 通過最少操作次數(shù)使數(shù)組的和相等1850【C++ 貪心】1616. 分割兩個(gè)字符串得到回文串1868【C++貪心 分治】1717. 刪除子字符串的最大得分1867【C++貪心】1536. 排布二進(jìn)制網(wǎng)格的最少交換次數(shù)1880【貪心 堆 】3081. 替換字符串中的問號使分?jǐn)?shù)最小1904【C++前綴和 位運(yùn)算 貪心 】2680. 最大或值1912【C++貪心 DFS】2673. 使二叉樹所有路徑值相等的最小代價(jià)1917【C++二分查找 貪心】1552. 兩球之間的磁力1919【C++貪心 單調(diào)?！?727. 重新排列后的最大子矩陣1926【C++前綴和 動(dòng)態(tài)規(guī)劃 貪心】813. 最大平均值和的分組1936【貪心 臨項(xiàng)交換 博弈論】1686. 石子游戲 VI2000【位運(yùn)算 貪心】2835. 使子序列的和等于目標(biāo)的最少操作次數(shù)2207【C++前綴和 數(shù)論 貪心】2245. 轉(zhuǎn)角路徑的乘積中最多能有幾個(gè)尾隨零2036【C++二分查找 貪心】1648. 銷售價(jià)值減少的顏色球2050【C++ 同余 裴蜀定理 中位數(shù)貪心 并集查找】2607. 使子數(shù)組元素和相等2071【字符串】【貪心】【 樹狀數(shù)組】2193. 得到回文串的最少操作次數(shù)2090【貪心】【二分查找】【動(dòng)態(tài)規(guī)劃】1739放置盒子2198【解析幾何】 【多源路徑】 【貪心】1520 最多的不重疊子字符串2362【貪心】【回溯】【字符串】2014. 重復(fù) K 次的最長子序列2558【貪心】【分類討論】2499. 讓數(shù)組不相等的最小總代價(jià)2633【貪心算法】2071:你可以安排的最多任務(wù)數(shù)目2648前綴和+單調(diào)雙隊(duì)列+貪心：2945:找到最大非遞減數(shù)組的長度2943【貪心]【字符串】【分類討論】420 強(qiáng)密碼檢驗(yàn)器無難度分【貪心 堆 優(yōu)先隊(duì)列】502. IPO無難度分

擴(kuò)展閱讀

我想對大家說的話工作中遇到的問題，可以按類別查閱鄙人的算法文章，請點(diǎn)擊《算法與數(shù)據(jù)匯總》。學(xué)習(xí)算法：按章節(jié)學(xué)習(xí)《喜缺全書算法冊》，大量的題目和測試用例，打包下載。重視操作有效學(xué)習(xí)：明確的目標(biāo) 及時(shí)的反饋 拉伸區(qū)（難度合適） 專注聞缺陷則喜(喜缺)是一個(gè)美好的愿望，早發(fā)現(xiàn)問題，早修改問題，給老板節(jié)約錢。子墨子言之：事無終始，無務(wù)多業(yè)。也就是我們常說的專業(yè)的人做專業(yè)的事。如果程序是一條龍，那算法就是他的是睛失敗+反思=成功 成功+反思=成功

視頻課程

先學(xué)簡單的課程，請移步CSDN學(xué)院，聽白銀講師（也就是鄙人）的講解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成戰(zhàn)斗了，為老板分憂，請學(xué)習(xí)C#入職培訓(xùn)、C++入職培訓(xùn)等課程 https://edu.csdn.net/lecturer/6176

測試環(huán)境

操作系統(tǒng)：win7 開發(fā)環(huán)境： VS2019 C++17 或者 操作系統(tǒng)：win10 開發(fā)環(huán)境： VS2022 C++17 如無特殊說明，本算法用**C++**實(shí)現(xiàn)。

柚子快報(bào)邀請碼778899分享：算法 C++貪心

http://yzkb.51969.com/

文章來源