刷題第十七天
134. 加油站:
這題很有意思,再做一遍還是做不出來(lái)。這題的思路是畫(huà)出折線圖,找出最低點(diǎn)。首先的關(guān)鍵點(diǎn)在于能否到達(dá),因此0點(diǎn)的油量是0,到達(dá)下一個(gè)點(diǎn)的油量是gas[0]-cost[0]。其次是最后結(jié)果要多+1,這里的理解可以是最低點(diǎn)是耗油量最高的,那我勢(shì)必從最低點(diǎn)的下一點(diǎn)出發(fā),這樣可以積攢更多的油量應(yīng)對(duì)這一次的消耗。

135. 分發(fā)糖果:
這題要考慮左邊的也要考慮右邊的,可以先遍歷一遍,先考慮左邊的,如果比自己左邊的大,糖果數(shù)就比左邊多加1。之后再考慮右邊,從末尾開(kāi)始遍歷,如果比自己右邊大,就取右邊+1和自身糖果數(shù)的較大值。

860. 檸檬水找零:
這題把當(dāng)前收到的5塊十塊記錄下來(lái),如果收到了十塊,當(dāng)前有五塊,就將十塊加一,五塊減一,如果找不開(kāi),就返回false,如果收到了二十,先找一張十塊和一張五塊的,如果沒(méi)有十塊,就找三張五塊的,還是沒(méi)有就返回false。

406. 根據(jù)身高重建隊(duì)列:
遇到這種有兩個(gè)參數(shù)的題目,往往只需要讓兩個(gè)參數(shù)按照相反的方式排列。這題采用的是身高由高到低,身高一致則屬性低的在前。再遍歷一次,依次插入在屬性值的位置即可。

452. 用最少數(shù)量的箭引爆氣球:
這題的直觀思路就是從頭到尾打重疊的部分。先對(duì)數(shù)組從小到大排序,cnt初始值設(shè)為1,開(kāi)始遍歷,如果當(dāng)前的左邊界比前一個(gè)的右邊界大,說(shuō)明不重合,cnt++。否則更新當(dāng)前的右邊界為當(dāng)前和前一個(gè)中較小的右邊界。

435. 無(wú)重疊區(qū)間:
這題和452其實(shí)是一樣的思路,452也是算重疊區(qū)間。

763. 劃分字母區(qū)間:
首先遍歷一遍,用一個(gè)map記錄字符出現(xiàn)過(guò)的最后的位置下標(biāo)。然后再?gòu)?開(kāi)始遍歷,記錄下0位置字符的最后出現(xiàn)下標(biāo)為e,再內(nèi)循環(huán)從i到e,在這個(gè)范圍內(nèi)的字符的最后下標(biāo)如果超過(guò)e,那就更新e,最后跳出循環(huán),此時(shí)的i到e就是符合題目要求的子串了。

56. 合并區(qū)間:
這題其實(shí)剖開(kāi)外表,核心思想和763是一樣的。先將數(shù)組排序,使用一個(gè)s和e記錄起始和結(jié)束位置,如果當(dāng)前節(jié)點(diǎn)的起始位置大于開(kāi)始位置,那就將s和e記錄下來(lái),否則更新e。

738. 單調(diào)遞增的數(shù)字:
這題就是找到開(kāi)始單調(diào)遞減的點(diǎn)f,從后向前遍歷。如果找到i-1大于i,就讓i-1的值減一,因?yàn)閒要設(shè)為9,這樣前一個(gè)點(diǎn)是要減少一的。