摘要 通過取模運(yùn)算來模擬在數(shù)組中循環(huán)搜索元素，這比在數(shù)組后拼接一個(gè)相同數(shù)組更方便，空間復(fù)雜度更低。 “接雨水”和“柱狀圖中的最大矩形”，都可以看成是對(duì)每個(gè)柱子，找一組 3 個(gè)...
發(fā)簡信
IP屬地：江蘇
-
代碼隨想錄算法訓(xùn)練營打卡Day59&60 | LeetCode503 下一個(gè)更大元素II、LeetCode42 接雨水、LeetCode84 柱狀圖中最大的矩形 -
代碼隨想錄算法訓(xùn)練營打卡Day58 | LeetCode739 每日溫度、LeetCode496 下一個(gè)更大元素I摘要 單調(diào)棧方法的時(shí)間復(fù)雜度是O(n)，只需要一層循環(huán)遍歷一次輸入數(shù)組，代碼更簡潔，邏輯更巧妙。 棧內(nèi)元素從棧頂?shù)綏５走f增（或非遞減），找的是任意一個(gè)元素的右邊第一個(gè)比該元素...
-
代碼隨想錄算法訓(xùn)練營打卡Day57 | LeetCode647 回文子串、LeetCode516 最長回文子序列
摘要 今天的兩道題目是區(qū)間 dp 的入門題目，以每一個(gè)區(qū)間作為一個(gè)狀態(tài)來定義 dp 數(shù)組和遞推公式。 子串（子字符串）要求元素在原序列（原字符串）中連續(xù)，子序列不要求元素在原...
-
代碼隨想錄算法訓(xùn)練營打卡Day56 | LeetCode583 兩個(gè)字符串的刪除操作、LeetCode72 編輯距離
摘要 編輯距離問題中，插入一個(gè)字符和刪除一個(gè)字符，對(duì)于使得兩個(gè)字符串相等的作用是一樣的，都是使得兩個(gè)字符串更加接近，所以可以統(tǒng)一只使用“插入”或者只使用“刪除” 可以進(jìn)行”修...
-
代碼隨想錄算法訓(xùn)練營打卡Day55 | LeetCode392 判斷子序列、LeetCode115 不同的子序列摘要 套用“最長公共子序列”的思路，LeetCode392 判斷子序列可以轉(zhuǎn)化為：求s和t的最長公共子序列的長度，并判斷這個(gè)最長公共子序列的長度是否和s的長度相等。 Leet...
-
代碼隨想錄算法訓(xùn)練營打卡Day53 | LeetCode1143 最長公共子序列、LeetCode1035 不相交的線、LeetCode53 最大子數(shù)組和摘要 如果不要求子序列中的元素在原序列中連續(xù)，相比于要求“連續(xù)”，dp數(shù)組的定義和遞推公式是不一樣的。 如果要求“連續(xù)”，那dp數(shù)組定義為以具體的元素結(jié)尾；如果不要求連續(xù)，那...
-
代碼隨想錄算法訓(xùn)練營打卡Day52 | LeetCode300 最長遞增子序列、LeetCode674 最長連續(xù)遞增子序列、LeetCode718 最長重復(fù)子數(shù)組摘要 如果答案在dp數(shù)組中的位置不是固定的，可以在dp數(shù)組的更新過程中記錄可能的答案，簡化代碼，例如今天的三道題，都可以在每次更新dp數(shù)組后來記錄最大值。 通過dp數(shù)組的定義...
-
代碼隨想錄算法訓(xùn)練營打卡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)鍵。 畫出簡單的狀...
-
代碼隨想錄算法訓(xùn)練營打卡Day50 | LeetCode123 買賣股票的最佳時(shí)機(jī)III、LeetCode188 買賣股票的最佳時(shí)機(jī)IV
摘要 只買賣一次股票，和不限制次數(shù)地買賣股票，只是在遞推公式上有差別。而且，這兩種情況都不需要記錄完成買賣的次數(shù)。 指定了至多買k次股票，這就暗含著每天的狀態(tài)信息要有買賣股票...
-
代碼隨想錄算法訓(xùn)練營打卡Day49 | LeetCode121 買賣股票的最佳時(shí)機(jī)、LeetCode122 買賣股票的最佳時(shí)機(jī)II
摘要 貪心算法可以看作是動(dòng)態(tài)規(guī)劃的特例，可以使用貪心算法解決的問題往往都可以使用動(dòng)態(tài)規(guī)劃解決，而動(dòng)態(tài)規(guī)劃往往是解決一類問題的通法。 買賣股票的問題，通過添加一個(gè)維度來保存更詳...
-
代碼隨想錄算法訓(xùn)練營打卡Day48 | LeetCode198 打家劫舍、LeetCode213 打家劫舍II、LeetCode337 打家劫舍III摘要 如果一步選擇會(huì)受之前的選擇影響，可以考慮是否能使用動(dòng)態(tài)規(guī)劃。 不需要遍歷環(huán)的所有可能序列，只需要從某個(gè)位置將環(huán)拆開。 樹形 dp 要結(jié)合二叉樹遍歷和動(dòng)態(tài)規(guī)劃的思路，先劃...
-
代碼隨想錄算法訓(xùn)練營打卡Day46 | LeetCode139 單詞拆分、多重背包問題摘要 如何選取物品有時(shí)也會(huì)影響代碼的執(zhí)行效率，雖然不同的選取物品的方法的時(shí)間復(fù)雜度可能在同一個(gè)數(shù)量級(jí)，但有時(shí)候執(zhí)行效率依然有比較明顯的差距。比如判斷一個(gè)字符串的一個(gè)子串是否是...
-
代碼隨想錄算法訓(xùn)練營打卡Day45 | LeetCode70 爬樓梯、LeetCode322 零錢兌換、LeetCode279 完全平方數(shù)
摘要 用背包問題的思路解決具體問題時(shí)，要明確什么是物品，物品的重量是什么，物品的價(jià)值是什么，以及要求的背包的狀態(tài)是什么（裝入的價(jià)值最大、裝滿背包使用的物品數(shù)最少，裝滿背包有多...
-
代碼隨想錄算法訓(xùn)練營打卡Day44 | 完全背包問題、LeetCode518 零錢兌換II、LeetCode377 組合總和IV摘要 只需改變遞推公式的一處，就可以將 0-1 背包問題變?yōu)橥耆嘲鼏栴}。 使用滾動(dòng)數(shù)組時(shí)，0-1 背包倒序遍歷重量的維度，保證每件物品最多被選取一次；而完全背包正序遍歷重量...
-
代碼隨想錄算法訓(xùn)練營打卡Day43 | LeetCode1049 最后一塊石頭的重量 II、LeetCode494 目標(biāo)和、LeetCode474 一和零摘要 用動(dòng)態(tài)規(guī)劃解決問題時(shí)，不僅要從簡單的子問題來考慮遞推公式，也要從問題的整體來考慮，看問題的輸入?yún)?shù)本身有什么性質(zhì)和公式，也有助于得到遞推公式。 LeetCode1049...
-
代碼隨想錄算法訓(xùn)練營打卡Day42 | 0-1 背包問題、LeetCode416 分割等和子集摘要 0-1 背包問題是動(dòng)態(tài)規(guī)劃的經(jīng)典問題，通過“縮小”背包來找到問題的簡單的子結(jié)構(gòu)，再“放大”背包，用子結(jié)構(gòu)來推導(dǎo)答案。 推導(dǎo)dp[i][j]所需的狀態(tài)不一定在二維dp數(shù)組...
-
代碼隨想錄算法訓(xùn)練營打卡Day41 | LeetCode343 整數(shù)拆分、LeetCode96 不同的二叉搜索樹
摘要 整數(shù)拆分和不同的二叉搜索樹，這兩個(gè)問題，都可以看做是從整體中不斷拆出子結(jié)構(gòu)（整數(shù)的子結(jié)構(gòu)是更小的整數(shù)，二叉樹的子結(jié)構(gòu)是子樹），模擬拆分子結(jié)構(gòu)的過程，有助于思考遞推公式。...
-
代碼隨想錄算法訓(xùn)練營打卡Day39 | LeetCode62 不同路徑、LeetCode63 不同路徑II摘要 從到達(dá)當(dāng)前狀態(tà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)練營打卡Day38 | LeetCode509 斐波那契數(shù)、LeetCode70 爬樓梯、LeetCode746 使用最小花費(fèi)爬樓梯
摘要 通過簡單的題目來熟悉方法論。 和貪心法只需要每一步保證局部最優(yōu)相比，動(dòng)態(tài)規(guī)劃的下一步的決策需要根據(jù)之前的狀態(tài)推導(dǎo)。貪心法只需要保存和局部最優(yōu)相關(guān)的信息，動(dòng)態(tài)規(guī)劃需要保存...
-
代碼隨想錄算法訓(xùn)練營打卡Day37 | LeetCode738 單調(diào)遞增的數(shù)字、LeetCode968 監(jiān)控二叉樹摘要 不同類型的問題，即使都具有貪心選擇性質(zhì)，解題思路也可能差別很大，需要多看多練。 比較實(shí)用的一個(gè)辦法是，從簡單的問題開始模擬求解的過程，對(duì)如何形成貪心策略往往很有啟發(fā)。 ...