7.3 - medium總結(jié)5

77. Combinations: 簡(jiǎn)單的backtracking。
78. Subsets: 又是一道backtracking,backtracking的題目就是要注意進(jìn)入和出來的條件和相應(yīng)變量狀態(tài)的改變。
79. Word Search: 又是一個(gè)backtracking的題目,但是不是簡(jiǎn)單的loop,而是訪問上下左右四種情況,同時(shí)要維護(hù)一個(gè)visited矩陣防止重復(fù)。有一點(diǎn)寫法上的小技巧是:for x, y in [(i-1, j),(i+1, j),(i, j-1), (i, j+1)]:,然后判斷x, y是否在范圍內(nèi),寫成這樣比較方便一些, 否則要寫一堆if語句。
80 . Remove Duplicates from Sorted Array II: 這題還是花了十來分鐘來做的。要點(diǎn)是考慮清楚復(fù)制的時(shí)機(jī),和復(fù)制后的狀態(tài),已經(jīng)是否需要更新index

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) <= 2:
            return len(nums)
        prev = 1
        tail = 2
        while tail < len(nums):
            if nums[prev] == nums[prev-1] == nums[tail]:
                tail += 1
            else:
                nums[prev+1] = nums[tail]
                prev += 1
                tail += 1
        return prev+1

81. Search in Rotated Sorted Array II: 這道題如果有重復(fù)項(xiàng)就無法用二分搜索法了。
82. Remove Duplicates from Sorted List II: 記錄一個(gè)prev節(jié)點(diǎn),和一個(gè)prev value,然后對(duì)于每一個(gè)節(jié)點(diǎn)都先對(duì)比一下next value,如果當(dāng)前節(jié)點(diǎn)和之前的不一樣而且和下一個(gè)也不一樣,那么更新prev,然后對(duì)每一次循環(huán)更新prev value(這題做的時(shí)候有點(diǎn)著急了,所以做錯(cuò)了后就直接看以前的submission,重做一次)
86. Partition List: 這題想法很簡(jiǎn)單,就是用兩個(gè)dummyhead,然后一個(gè)一個(gè)連上去就可以了
89. Gray Code: 對(duì)于一個(gè)valid的code,先把所有的code前面加0,然后把這個(gè)code reverse, 再所有的加1,再拼接就可以了。
90. Subsets II: 在進(jìn)入下一層的時(shí)候,記得檢查一下,if i > pos and nums[i] == nums[i-1]: continue
91. Decode Ways: 動(dòng)態(tài)規(guī)劃來做。初始化的時(shí)候比較麻煩,然后遞推公式情況比較多,不過可以抓住當(dāng)前char是否為0,還有兩位數(shù)和是否在11~26之間來做。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點(diǎn),簡(jiǎn)書系信息發(fā)布平臺(tái),僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容