二分查找前提是數(shù)組為有序數(shù)組注意開閉區(qū)間int search(vector & nums, int target) {int left = 0;int right = num...
發(fā)簡信
IP屬地：上海
-
代碼隨想錄算法訓(xùn)練營第一天|704. 二分查找、27. 移除元素
-
代碼隨想錄算法訓(xùn)練營第六十三四| 訓(xùn)練營總結(jié)
兩個(gè)月的算法訓(xùn)練營，主要學(xué)習(xí)了 數(shù)組、鏈表、哈希表、字符串、棧與隊(duì)列、二叉樹、回溯、貪心、動態(tài)規(guī)劃及單調(diào)棧。 題目雖然不多，但也是卡哥精心挑選，對于我們這種工作中很少使用到算...
-
代碼隨想錄算法訓(xùn)練營第六十三天|84.柱狀圖中最大的矩形
84.柱狀圖中最大的矩形 找每個(gè)柱子左右兩邊第一個(gè)小于該柱子的柱子 從棧頭（元素從棧頭彈出）到棧底的順序從大到小 三種情況： 情況一：當(dāng)前遍歷的元素heights[i]大于棧...
-
代碼隨想錄算法訓(xùn)練營第六十二天|503.下一個(gè)更大元素II、42. 接雨水
503.下一個(gè)更大元素II 兩個(gè)nums數(shù)組拼接在一起，使用單調(diào)棧計(jì)算出每一個(gè)元素的下一個(gè)最大值，最后再把結(jié)果集即result數(shù)組resize到原數(shù)組大小就可以 vector...
-
代碼隨想錄算法訓(xùn)練營第六十天|739. 每日溫度、496.下一個(gè)更大元素 I
739.每日溫度 首先想到暴力求解 遍歷的過程中需要用一個(gè)棧來記錄右邊第一個(gè)比當(dāng)前元素高的元素，優(yōu)點(diǎn)是整個(gè)數(shù)組只需要遍歷一次 單調(diào)棧里存放元素的下標(biāo)i 情況一：當(dāng)前遍歷的元素...
-
代碼隨想錄算法訓(xùn)練營第五十九天|647. 回文子串、516.最長回文子序列647.回文子串 動規(guī)五部曲 確定dp數(shù)組（dp table）以及下標(biāo)的含義 dp[i][j]：表示區(qū)間范圍[i,j] （注意是左閉右閉）的子串是否是回文子串，如果是dp[i...
-
代碼隨想錄算法訓(xùn)練營第五十八天|583. 兩個(gè)字符串的刪除操作、72. 編輯距離583.兩個(gè)字符串的刪除操作 動規(guī)五部曲 確定dp數(shù)組（dp table）以及下標(biāo)的含義 dp[i][j]：以i-1為結(jié)尾的字符串word1，和以j-1位結(jié)尾的字符串word...
-
代碼隨想錄算法訓(xùn)練營第五十七天|392.判斷子序列、115.不同的子序列392.判斷子序列 動態(tài)規(guī)劃五部曲 確定dp數(shù)組（dp table）以及下標(biāo)的含義 dp[i][j] 表示以下標(biāo)i-1為結(jié)尾的字符串s，和以下標(biāo)j-1為結(jié)尾的字符串t，相同子...
-
代碼隨想錄算法訓(xùn)練營第五十六天|1143.最長公共子序列、1035.不相交的線、53. 最大子序和 動態(tài)規(guī)劃1143.最長公共子序列 動規(guī)五部曲 確定dp數(shù)組（dp table）以及下標(biāo)的含義 dp[i][j]：長度為[0, i - 1]的字符串text1與長度為[0, j - 1...
-
代碼隨想錄算法訓(xùn)練營第五十五天|300.最長遞增子序列、674. 最長連續(xù)遞增序列、18. 最長重復(fù)子數(shù)組300.最長遞增子序列 動規(guī)五部曲 dp[i]的定義 dp[i]表示i之前包括i的以nums[i]結(jié)尾的最長遞增子序列的長度 狀態(tài)轉(zhuǎn)移方程 位置i的最長升序子序列等于j從0到...
-
代碼隨想錄算法訓(xùn)練營第五十一天|309.最佳買賣股票時(shí)機(jī)含冷凍期、714.買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi)309.最佳買賣股票時(shí)機(jī)含冷凍期 動規(guī)五部曲 確定dp數(shù)組以及下標(biāo)的含義 dp[i][j]，第i天狀態(tài)為j，所剩的最多現(xiàn)金為dp[i][j] 狀態(tài)一：持有股票狀態(tài) 狀態(tài)二：保...
-
代碼隨想錄算法訓(xùn)練營第五十天|123.買賣股票的最佳時(shí)機(jī)III、188.買賣股票的最佳時(shí)機(jī)IV123.買賣股票的最佳時(shí)機(jī)III 動態(tài)規(guī)劃五部曲 確定dp數(shù)組以及下標(biāo)的含義 一天一共就有五個(gè)狀態(tài)， 沒有操作 （其實(shí)我們也可以不設(shè)置這個(gè)狀態(tài)） 第一次持有股票 第一次不持有...
-
代碼隨想錄算法訓(xùn)練營第四十九天|121. 買賣股票的最佳時(shí)機(jī)、122.買賣股票的最佳時(shí)機(jī)II121.買賣股票的最佳時(shí)機(jī) 動規(guī)五部曲 確定dp數(shù)組（dp table）以及下標(biāo)的含義 dp[i][0] 表示第i天持有股票所得最多現(xiàn)金 dp[i][1] 表示第i天不持有股...
-
代碼隨想錄算法訓(xùn)練營第四十八天|198.打家劫舍、213.打家劫舍II 、337.打家劫舍III198.打家劫舍 當(dāng)前房屋偷與不偷取決于 前一個(gè)房屋和前兩個(gè)房屋是否被偷了 動規(guī)五部曲 確定dp數(shù)組（dp table）以及下標(biāo)的含義 dp[i]：考慮下標(biāo)i（包括i）以內(nèi)的...
-
代碼隨想錄算法訓(xùn)練營第四十五天|139.單詞拆分139.單詞拆分 轉(zhuǎn)化為背包問題： 單詞就是物品，字符串s就是背包 動規(guī)五部曲 確定dp數(shù)組以及下標(biāo)的含義 dp[i] : 字符串長度為i的話，dp[i]為true，表示可以...
-
代碼隨想錄算法訓(xùn)練營第四十四天|完全背包、518. 零錢兌換 II、377. 組合總和 Ⅳ完全背包 與01背包差別是物品可以重復(fù)用，那么在遍歷容量就要從小到大遍歷 // 先遍歷物品，再遍歷背包for(inti=0;i<weight.size();i++){// 遍...
-
代碼隨想錄算法訓(xùn)練營第四十三天|1049. 最后一塊石頭的重量 II、494. 目標(biāo)和 、474.一和零1049.最后一塊石頭的重量II 關(guān)鍵將一堆石頭分成兩份，近可能接近平均值 動規(guī)五步曲： 確定dp數(shù)組以及下標(biāo)的含義 dp[j]表示容量（這里說容量更形象，其實(shí)就是重量）為j...
-
代碼隨想錄算法訓(xùn)練營第四十二天|01背包問題、416. 分割等和子集
01背包問題 分為二維數(shù)組和一維數(shù)組，一維有點(diǎn)繞 416.分割等和子集 動規(guī)五部曲： 確定dp數(shù)組以及下標(biāo)的含義 01背包中，dp[j] 表示： 容量為j的背包，所背的物品價(jià)...
-
代碼隨想錄算法訓(xùn)練營第四十一天|343. 整數(shù)拆分、96.不同的二叉搜索樹
343.整數(shù)拆分 動規(guī)五部曲： 確定dp數(shù)組（dp table）以及下標(biāo)的含義 dp[i]：分拆數(shù)字i，可以得到的最大乘積為dp[i] 確定遞推公式 dp[i] = max(...
-
代碼隨想錄算法訓(xùn)練營第三十九天|62.不同路徑、63. 不同路徑 II
62.不同路徑 動規(guī)五部曲： 確定dp數(shù)組（dp table）以及下標(biāo)的含義 dp[i][j] ：表示從（0 ，0）出發(fā)，到(i, j) 有dp[i][j]條不同的路徑。 確...