Dynamic Programming

448. Find All Numbers Disappeared in an Array

448. Find All Numbers Disappeared in an Array 這個題目的簡單做法是排序後再找,但是這樣的做法通常都是會被問到提供更好的解法。 關於解法其實也不難,那就是使用 Set 記錄起來有出現過的元素,之後從小走到大,再把沒有出現在 Set 裡面的數字記錄起來,那就可以找到解答了。 class Solution: def findDisappearedNumbers(self, nums: List[int]) -> List[int]: m = len(nums) S = set(nums) ans = [] for i in range(1, m + 1): if i not in S: ans.
Gary Lai

651. 4 Keys Keyboard

651. 4 Keys Keyboard 這個題目滿有趣的,為了幫助大家對這個題目有更深的印象,我分享一個小故事,我在剛開始學寫程式的時候,是從 HTML 和 CSS 開始學起,當時看到迴圈就頭痛,以為只要學好 HTML 加上 CSS 就能當前端工程師,那時候響應式設計剛興起,Twitter Bootstrap 才剛出了第一版,我為了要測試當網站的內容很多的時候,看看網站變得很長會怎麼樣,也就很土法煉鋼的複製一段文字,接著一直貼上,貼了幾段後發現,我應該要全選所有的文字,再重新複製一次,在繼續一直貼上,這樣子一次會產生更多的內容會更快,一直貼上到一定的程度後,就要重新再全選一次、複製、再繼續動作...不斷重複。 這一個題目設計的情況就是這樣,有一個鍵盤,只有四個按鈕:A,全選,複製,貼上。我們可以隨便按任何鍵,可是總共按的次數只有 n 次。試問我們要怎麼樣建立出最長的一個字串? 以前我在複製的時候很隨性,
Gary Lai

10. Regular Expression Matching

10. Regular Expression Matching 這一題是正規表達式的題目,主要有兩個符號要考慮:「.」和「*」,點號和星號,點號比較好處理,因為只要是點好,就代表可以跳過該字元,最難處理的是星號;因為星號可以代表的是該字元可以出現零到無限次。其中又以.* 代表的是可以符合任何字元無限次。 下面是如果只以 . 當作匹配的字串時所做的考量。 class Solution: def isMatch(self, s: str, p: str) -> bool: i = 0 j = 0 while i < len(s) and j < len(p): if s[i] == p[j] or p[j] == '.':
Gary Lai

416. Partition Equal Subset Sum

416. Partition Equal Subset Sum 首先我們要確立目標,目標是給定一個陣列能不能分成兩個子集合,讓這兩個子集合的總和相等。 第一個要去想的地方比較簡單,既然兩個子集合要相等,那一個子集合一定是原陣列總和的一半,我們的目標就是要找到一個一個子集合,其總和是原陣列總和的一半。 另外,有可能原陣列的元素總和是奇數:例如:[1, 2, 1, 1] 這樣的陣列總和是 5 ,一定不會有辦法分成兩個集合,所以可以先用這樣的方式去剪枝(把所有總和為奇數的直接排除掉)。 接著是要怎麼選擇,每一個元素我們都可以有「選」或是「不選」這兩種方式,如果選的話,我們的目標就會減少當下的數值,如果不選的話,目標並不會改變,一直到如果我們選了最後一個數字,如果最後目標剛好等於 0 ,那就是我們透過選擇,找到了目標。 這樣的關係可以用一個遞迴的方式來呈現。 遞迴 class Solution: def canPartition(self, nums: List[int]
Gary Lai