摘要 通過(guò)取模運(yùn)算來(lái)模擬在數(shù)組中循環(huán)搜索元素旧蛾，這比在數(shù)組后拼接一個(gè)相同數(shù)組更方便叼架，空間復(fù)雜度更低汁尺。 “接雨水”和“柱狀圖中的最大矩形”通今，都可以看成是對(duì)每個(gè)柱子里逆，找一組 3 個(gè)...
發(fā)簡(jiǎn)信
IP屬地：江蘇
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day59&60 | LeetCode503 下一個(gè)更大元素II、LeetCode42 接雨水、LeetCode84 柱狀圖中最大的矩形 -
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day58 | LeetCode739 每日溫度往枣、LeetCode496 下一個(gè)更大元素I摘要 單調(diào)棧方法的時(shí)間復(fù)雜度是O(n)伐庭，只需要一層循環(huán)遍歷一次輸入數(shù)組，代碼更簡(jiǎn)潔分冈，邏輯更巧妙圾另。 棧內(nèi)元素從棧頂?shù)綏５走f增（或非遞減），找的是任意一個(gè)元素的右邊第一個(gè)比該元素...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day57 | LeetCode647 回文子串雕沉、LeetCode516 最長(zhǎng)回文子序列
摘要 今天的兩道題目是區(qū)間 dp 的入門題目集乔，以每一個(gè)區(qū)間作為一個(gè)狀態(tài)來(lái)定義 dp 數(shù)組和遞推公式。 子串（子字符串）要求元素在原序列（原字符串）中連續(xù)坡椒，子序列不要求元素在原...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day56 | LeetCode583 兩個(gè)字符串的刪除操作扰路、LeetCode72 編輯距離
摘要 編輯距離問(wèn)題中，插入一個(gè)字符和刪除一個(gè)字符肠牲，對(duì)于使得兩個(gè)字符串相等的作用是一樣的幼衰，都是使得兩個(gè)字符串更加接近，所以可以統(tǒng)一只使用“插入”或者只使用“刪除” 可以進(jìn)行”修...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day55 | LeetCode392 判斷子序列缀雳、LeetCode115 不同的子序列摘要 套用“最長(zhǎng)公共子序列”的思路渡嚣，LeetCode392 判斷子序列可以轉(zhuǎn)化為：求s和t的最長(zhǎng)公共子序列的長(zhǎng)度，并判斷這個(gè)最長(zhǎng)公共子序列的長(zhǎng)度是否和s的長(zhǎng)度相等。 Leet...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day53 | LeetCode1143 最長(zhǎng)公共子序列识椰、LeetCode1035 不相交的線绝葡、LeetCode53 最大子數(shù)組和摘要 如果不要求子序列中的元素在原序列中連續(xù)，相比于要求“連續(xù)”腹鹉，dp數(shù)組的定義和遞推公式是不一樣的藏畅。 如果要求“連續(xù)”，那dp數(shù)組定義為以具體的元素結(jié)尾功咒；如果不要求連續(xù)愉阎，那...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day52 | LeetCode300 最長(zhǎng)遞增子序列、LeetCode674 最長(zhǎng)連續(xù)遞增子序列力奋、LeetCode718 最長(zhǎng)重復(fù)子數(shù)組摘要 如果答案在dp數(shù)組中的位置不是固定的榜旦，可以在dp數(shù)組的更新過(guò)程中記錄可能的答案，簡(jiǎn)化代碼景殷，例如今天的三道題溅呢，都可以在每次更新dp數(shù)組后來(lái)記錄最大值。 通過(guò)dp數(shù)組的定義...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day51 | LeetCode309 最佳買賣股票的時(shí)機(jī)含冷凍期猿挚、LeetCode714 買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi)摘要 有些動(dòng)態(tài)規(guī)劃的題目的難點(diǎn)在于如何劃分狀態(tài)和這些狀態(tài)之間如何進(jìn)行轉(zhuǎn)移咐旧，列出可能的狀態(tài)以及轉(zhuǎn)移到這些狀態(tài)的可能，是定義dp數(shù)組及數(shù)組下標(biāo)绩蜻、推導(dǎo)遞推公式的關(guān)鍵铣墨。 畫出簡(jiǎn)單的狀...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day50 | LeetCode123 買賣股票的最佳時(shí)機(jī)III、LeetCode188 買賣股票的最佳時(shí)機(jī)IV
摘要 只買賣一次股票辜羊，和不限制次數(shù)地買賣股票踏兜，只是在遞推公式上有差別。而且八秃，這兩種情況都不需要記錄完成買賣的次數(shù)碱妆。 指定了至多買k次股票，這就暗含著每天的狀態(tài)信息要有買賣股票...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day49 | LeetCode121 買賣股票的最佳時(shí)機(jī)昔驱、LeetCode122 買賣股票的最佳時(shí)機(jī)II
摘要 貪心算法可以看作是動(dòng)態(tài)規(guī)劃的特例疹尾，可以使用貪心算法解決的問(wèn)題往往都可以使用動(dòng)態(tài)規(guī)劃解決，而動(dòng)態(tài)規(guī)劃往往是解決一類問(wèn)題的通法骤肛。 買賣股票的問(wèn)題纳本，通過(guò)添加一個(gè)維度來(lái)保存更詳...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day48 | LeetCode198 打家劫舍、LeetCode213 打家劫舍II腋颠、LeetCode337 打家劫舍III摘要 如果一步選擇會(huì)受之前的選擇影響繁成，可以考慮是否能使用動(dòng)態(tài)規(guī)劃。 不需要遍歷環(huán)的所有可能序列淑玫，只需要從某個(gè)位置將環(huán)拆開(kāi)巾腕。 樹(shù)形 dp 要結(jié)合二叉樹(shù)遍歷和動(dòng)態(tài)規(guī)劃的思路面睛，先劃...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day46 | LeetCode139 單詞拆分、多重背包問(wèn)題摘要 如何選取物品有時(shí)也會(huì)影響代碼的執(zhí)行效率尊搬，雖然不同的選取物品的方法的時(shí)間復(fù)雜度可能在同一個(gè)數(shù)量級(jí)叁鉴，但有時(shí)候執(zhí)行效率依然有比較明顯的差距。比如判斷一個(gè)字符串的一個(gè)子串是否是...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day45 | LeetCode70 爬樓梯佛寿、LeetCode322 零錢兌換幌墓、LeetCode279 完全平方數(shù)
摘要 用背包問(wèn)題的思路解決具體問(wèn)題時(shí)，要明確什么是物品冀泻，物品的重量是什么常侣，物品的價(jià)值是什么，以及要求的背包的狀態(tài)是什么（裝入的價(jià)值最大腔长、裝滿背包使用的物品數(shù)最少袭祟，裝滿背包有多...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day44 | 完全背包問(wèn)題、LeetCode518 零錢兌換II捞附、LeetCode377 組合總和IV摘要 只需改變遞推公式的一處，就可以將 0-1 背包問(wèn)題變?yōu)橥耆嘲鼏?wèn)題您没。 使用滾動(dòng)數(shù)組時(shí)鸟召，0-1 背包倒序遍歷重量的維度，保證每件物品最多被選取一次氨鹏；而完全背包正序遍歷重量...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day43 | LeetCode1049 最后一塊石頭的重量 II欧募、LeetCode494 目標(biāo)和、LeetCode474 一和零摘要 用動(dòng)態(tài)規(guī)劃解決問(wèn)題時(shí)仆抵，不僅要從簡(jiǎn)單的子問(wèn)題來(lái)考慮遞推公式跟继，也要從問(wèn)題的整體來(lái)考慮，看問(wèn)題的輸入?yún)?shù)本身有什么性質(zhì)和公式镣丑，也有助于得到遞推公式舔糖。 LeetCode1049...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day42 | 0-1 背包問(wèn)題、LeetCode416 分割等和子集摘要 0-1 背包問(wèn)題是動(dòng)態(tài)規(guī)劃的經(jīng)典問(wèn)題莺匠，通過(guò)“縮小”背包來(lái)找到問(wèn)題的簡(jiǎn)單的子結(jié)構(gòu)金吗，再“放大”背包，用子結(jié)構(gòu)來(lái)推導(dǎo)答案趣竣。 推導(dǎo)dp[i][j]所需的狀態(tài)不一定在二維dp數(shù)組...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day41 | LeetCode343 整數(shù)拆分摇庙、LeetCode96 不同的二叉搜索樹(shù)
摘要 整數(shù)拆分和不同的二叉搜索樹(shù)，這兩個(gè)問(wèn)題遥缕，都可以看做是從整體中不斷拆出子結(jié)構(gòu)（整數(shù)的子結(jié)構(gòu)是更小的整數(shù)卫袒，二叉樹(shù)的子結(jié)構(gòu)是子樹(shù)），模擬拆分子結(jié)構(gòu)的過(guò)程单匣，有助于思考遞推公式夕凝。...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day39 | LeetCode62 不同路徑宝穗、LeetCode63 不同路徑II摘要 從到達(dá)當(dāng)前狀態(tài)的有幾種可能來(lái)思考，是一種確定dp數(shù)組及數(shù)組下標(biāo)含義的方式 滾動(dòng)數(shù)組是一種能夠在動(dòng)態(tài)規(guī)劃中降低空間復(fù)雜度的方法迹冤，當(dāng)我們?cè)谑褂眠f推方程計(jì)算下一步狀態(tài)的時(shí)候讽营，...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day38 | LeetCode509 斐波那契數(shù)、LeetCode70 爬樓梯泡徙、LeetCode746 使用最小花費(fèi)爬樓梯
摘要 通過(guò)簡(jiǎn)單的題目來(lái)熟悉方法論橱鹏。 和貪心法只需要每一步保證局部最優(yōu)相比，動(dòng)態(tài)規(guī)劃的下一步的決策需要根據(jù)之前的狀態(tài)推導(dǎo)堪藐。貪心法只需要保存和局部最優(yōu)相關(guān)的信息莉兰，動(dòng)態(tài)規(guī)劃需要保存...
-
代碼隨想錄算法訓(xùn)練營(yíng)打卡Day37 | LeetCode738 單調(diào)遞增的數(shù)字、LeetCode968 監(jiān)控二叉樹(shù)摘要 不同類型的問(wèn)題礁竞，即使都具有貪心選擇性質(zhì)糖荒，解題思路也可能差別很大，需要多看多練模捂。 比較實(shí)用的一個(gè)辦法是捶朵，從簡(jiǎn)單的問(wèn)題開(kāi)始模擬求解的過(guò)程，對(duì)如何形成貪心策略往往很有啟發(fā)狂男。 ...