故障鍵盤

【雙端隊(duì)列】遇到'i'時(shí)看作是把字符添加到開(kāi)頭，沒(méi)有遇到則添加到末尾，最后判斷是否需要反轉(zhuǎn)后輸出答案，時(shí)空復(fù)雜度均為O(n)。

判斷是否能拆分?jǐn)?shù)組

【枚舉】當(dāng)n≤2時(shí)必然滿足，當(dāng)n≥3時(shí)，只要nums中存在和≥m的長(zhǎng)為2的子數(shù)組，那么除了這個(gè)子數(shù)組之外的元素可以被一個(gè)一個(gè)地去掉，最后剩下這個(gè)子數(shù)組再拆掉。所以問(wèn)題轉(zhuǎn)化為數(shù)組中是否有兩個(gè)相鄰元素之和≥m。

找出最安全路徑

【多源BFS + 并查集】從所有1出發(fā)寫一個(gè)多源BFS，計(jì)算每個(gè)格子(i,j)到最近的1的曼哈頓距離dis[i] [j]，由于答案不會(huì)超過(guò)dis[i] [j]的最大值所以可以倒序枚舉答案。設(shè)答案為ans，把所有dis[i] [j] = ans的格子和他四周>=ans的格子用并查集連起來(lái)，答案為ans的情況下，這些格子間可以互相到達(dá)，用并查集判斷(0,0)和(n-1,n-1)是否聯(lián)通，只要聯(lián)通就立刻返回ans。

子序列最大優(yōu)雅度

【貪心】按照利潤(rùn)從大到小排序。先把前k個(gè)項(xiàng)目選上?？紤]選第k+1個(gè)項(xiàng)目，為了選它，我們必須從前k個(gè)項(xiàng)目中移除一個(gè)項(xiàng)目。由于已經(jīng)按照利潤(rùn)從大到小排序，選這個(gè)項(xiàng)目不會(huì)讓totalprofit變大，所以我們重點(diǎn)考慮能否讓distinct.categories變大。分類討論：如果第k+1個(gè)項(xiàng)目和前面某個(gè)已選項(xiàng)目的類別相同，那么無(wú)論怎么移除都不會(huì)讓distinct_categories變大，所以無(wú)需選擇這個(gè)項(xiàng)目；如果第k+1個(gè)項(xiàng)目和前面任何已選項(xiàng)目的類別都不一樣，考慮移除前面已選項(xiàng)目中的哪一個(gè)：如果移除的項(xiàng)目的類別只出現(xiàn)一次，那么選第k+1個(gè)項(xiàng)目后，distinct_categories一減一增，保持不變，所以不考慮這種情況。如果移除的項(xiàng)目的類別重復(fù)出現(xiàn)多次，那么選第k+1個(gè)項(xiàng)目后，distinct_categories會(huì)增加一，此時(shí)有可能會(huì)讓優(yōu)雅度變大，可以選擇這個(gè)項(xiàng)目。按照這個(gè)過(guò)程，繼續(xù)考慮選擇后面的項(xiàng)目。計(jì)算優(yōu)雅度，取最大值，即為答案。