No. | 完成日期 | 難易度 | Leetcode Link | 網路講解視頻 | Memo |
1 | 2020/09/27 | Easy | 28. Implement strStr() | Leetcode : 28 Implement strStr 讲解 [LeetCode] 28. Implement strStr() 实现strStr()函数 | 找出A是否為B的子字串,若是回傳A在B的起始位置 直接用兩個PTR遍歷,注意一些邊界條件。 1. needle.size() == 0 2. haystack.size()<needle.size() |
2 | | Easy | 14. Longest Common Prefix | Leetcode: 14 Longest Common Prefix 讲解 [LeetCode] 14. Longest Common Prefix 最长共同前缀 | 找出給定字串的共同最長前綴子字串 1、先將LCP指定為第一個字串,接著開始遍歷裡面的字元是否存在其他的每個字串中。 2、另一個方式是排序,這樣最長子字串一定是頭尾兩個的共同子字串。 |
3 | | Easy | 58. Length of Last Word | [LeetCode] 58. Length of Last Word 求末尾单词的长度 | 找出最後面一個單字的長度 從後往前找,找到 ‘ ’ 就回傳長度,要注意的是要前處理把最後面的空格先去掉。 |
4. | | Easy | 387. First Unique Character in a String | [LeetCode] First Unique Character in a String 字符串第一个不同字符 | 找到第一個只出現一次的字元 先掃一遍建Map,再掃一遍看個數是不是只有一個。 |
5 | | Easy | 383. Ransom Note | | 給定一勒索信字串,判斷是否可用雜誌字串組出來 建兩個 map,若勒索字元數>雜誌字元數就不行 |
6 | | Easy | 344. Reverse String | | 將一個字串反過來 寫一個 for 迴圈第一個跟最後一個交換,直到遍歷到中間就都換完了。 |
7 | 2020/09/28 | Medium | 151. Reverse Words in a String | 贾考博 LeetCode 151. Reverse Words in a String | 將一個字串中的單字反過來排,必須忽略空白 先用 while 把最前面和最後面的空白去掉,接著再用PTR從後面往前找空白,找到後塞到 ans 中。 |
8 | | Easy | 345. Reverse Vowels of a String | [LeetCode] Reverse Vowels of a String 翻转字符串中的元音字母 | 翻轉字串中的母音 用 2ptr 從前往後掃,掃到兩個母音就交換。 注意母音大小寫都算,可以 1、寫一個 func 來判斷是否母音 2、用 find_first_of(“aeiouAEIOU”, left)/find_last_of(“aeiouAEIOU”, right) 3、string t = “aeiouAEIOU”; t.find(…) |
9 | | Easy | 205. Isomorphic Strings | 贾考博 LeetCode 205. Isomorphic Strings 想起化学课 [LeetCode] 205. Isomorphic Strings 同构字符串 | 給定兩字串,確認是否裡面的字元都是一對一對應 宣告兩個長度 256 的陣列,遍歷兩字串並查找對應的數字是否相同,若不同就結束,相同就更新成i+1。 |
10 | | Easy | 290. Word Pattern | [LeetCode] 290. Word Pattern 词语模式 | 判斷單字與 pattern 是否一對一對應 建一個 map 儲存 pattern,若 key 存在,確認 value 是否相同;若 key 不存在,確認是否已存在相同的 value;如果沒有新建對應關係。 最後需確認單字與 pattern 個數是否相同。 istringstream in(str); string t ; in >> t; |
11 | | Easy | 242. Valid Anagram | | 判斷兩單字是否為字謎(重組後相同) 排序,判斷是否相同。 開兩個 256 的陣列計算每個字元的個數,最後比較是否相同。 |
12 | 2020/09/29 | Medium | 49. Group Anagrams | Leetcode 49 Group Anagrams 讲解 [LeetCode] 49. Group Anagrams 群组错位词 | 分類字謎,把重組後相同的排在一起 把每個字串的字元數量當作 Key 分類存到 map 中。 |
13 | | Medium | 179. Largest Number | 贾考博 LeetCode 179. Largest Number 何必呢? | 將給定的字串排成最大的數字 需要客製化比較函數,比較兩個拼起來之後誰大。 sort(nums.begin(), nums.end(), comp); |
14 | | Medium | 6. ZigZag Conversion | [LeetCode]6. ZigZag Conversion 中文 [LeetCode] 6. ZigZag Conversion 之字型转换字符串 | 把給定字串轉成之字形排序 可以觀察到骨幹部分是以 2*numRows-2 的方式遞增 中間之字形就是 j+2*numRows-2-2*i 的方式遞增 |
15 | 2020/10/03 | Easy | 38. Count and Say | 贾考博 LeetCode 38. Count and Say [LeetCode] 38. Count and Say 计数和读法 | 計數和讀法 1 : 1 ; 2: 11 ; 3 : 21 計算前面有幾個一樣的元素,把個數和元素存到下一個字串中 |
16 | | Hard | 316. Remove Duplicate Letters | 小旭讲解 LeetCode 316 Remove Duplicate Letters – EP28 [LeetCode] Remove Duplicate Letters 移除重复字母 | 刪除重複字母,並且在不打亂原先順序前提下照字母順序排列 使用 stack &兩個 HashMap 紀錄出現個數與是否已經放在 stack 中。如果遍歷過就繼續,如果沒遍歷過,判斷 stack 上的是不是比自己大,如果比較大,後面又會出現就 pop 掉。 |
17 | | Easy | 168. Excel Sheet Column Title | [LeetCode] Excel Sheet Column Title 求Excel表列名称 | 給一個數字求 Excel 表列名稱 從後面往前算,先%26再/26,最後輸出答案時反轉即可。 |
18 | | Easy | 171. Excel Sheet Column Number | [LeetCode] Excel Sheet Column Number 求Excel表列序号 | 給一個 Excel 表列名稱求數字 遍歷字串,相當於26進位轉10進位。 |
19 | | Easy | 13. Roman to Integer | 花花酱 LeetCode 13. Roman to Integer – 刷题找工作 EP299 [LeetCode]13. Roman to Integer 中文 [LeetCode] 13. Roman to Integer 罗马数字转化成整数 | 將羅馬數字轉成整數 可以用一個 Map 先把羅馬字母/數字對應存起來 依序遍歷,若後面大於前面,就把前面的兩倍減掉。 |
20 | 2020/10/04 | Medium | 12. Integer to Roman | [LeetCode]12. Integer to Roman 中文 | 將整數轉成羅馬數字 先用陣列將所有數字與對應字母存起來,從大往下掃 while(num>=val[i]) { num-=val[i]; ans.append(sym[i]); } |
21 | | Hard | 273. Integer to English Words | [LeetCode] Integer to English Words 整数转为英文单词 | 將整數轉為英文表達 三個三個一組,分別處理 |
22 | | Hard | 68. Text Justification | LeetCode 68. Text Justification 中文解释 Chinese Version [LeetCode] Text Justification 文本左右对齐 | 文字左右對齊 首先先判斷一行有幾個單字,接著如果該行是最後一行或是只有一個單字,則只要補到最大行寬。如果不是,那就要計算有幾個空格,然後平均分配。 |
23 | 2020/10/05 | Hard | 65. Valid Number | [Leetcode 65] Valid Number [LeetCode] Valid Number 验证数字 | 判斷是否為有效數字 先把前後的空格去掉,如果只剩一個確認是否為數字 依序處理第一個/中間/最後一個,判斷是否有效 |
24 | 2020/10/07 | Hard | 76. Minimum Window Substring | [LeetCode]76. Minimum Window Substring 中文 | 最小窗口子字串 使用 sliding window 先找出涵蓋此字串的子字串,再動態調整找出最小範圍。 |
25 | | Hard | 30. Substring with Concatenation of All Words | Leetcode : 30. Substring with Concatenation of All Words 讲解 [LeetCode] 30. Substring with Concatenation of All Words 串联所有单词的子串 | 找出串連所有單詞的子字串 先用一個 map 把所有要找的字串記下來。 接著從頭開始掃,概念有點類似變形的 sliding window。 |
26 | | Medium | 3. Longest Substring Without Repeating Characters | Leetcode : 3 Longest Substring Without Repeating Characters 讲解 [LeetCode] 3. Longest Substring Without Repeating Characters 最长无重复字符的子串 | 找出最長無重複的字串 用一個 map 紀錄每個字元上次出現的位置,如果沒有出現過,或是不在 window 中繼續往右擴張,但如果發現字元已經在目前涵蓋區間中,則將 window 最左邊更新到該字元的下一個位置。每次更新 window 時都紀錄最大值。 |
27 | | Medium | 395. Longest Substring with At Least K Repeating Characters | 【工傅坊:小FU讲解】Leetcode 395. Longest Substring With At Least K Repeating Characters [LeetCode] 395. Longest Substring with At Least K Repeating Characters 至少有K个重复字符的最长子字符串 | 找出至少重複K次的子字串 暴力解把全部子字串切出來,判斷是否字元超過K次,但超時。 用 Divide And Conquer,先用一個陣列把字元出現數存起來,用小於K次的地方當切點分兩半,再分別計算回傳左右半邊的最大值。找到切點之後記得再往後找到大於K次的才是右半邊起始點。 |
28 | | Easy | 125. Valid Palindrome | [LeetCode] Valid Palindrome 验证回文字符串 | 驗證字串是否回文(需跳過非數字與字母) isalnum() 可判斷是否為數字&字母 tolower() 可將字母轉成小寫 使用兩個指針,一直移動到數字&字母,轉成小寫比較 |
29 | 2020/10/08 | Medium | 5. Longest Palindromic Substring | [LeetCode]5. Longest Palindromic Substring 中文 [LeetCode] 5. Longest Palindromic Substring 最长回文子串 | 最長回文子字串 用 dp[i][j] 紀錄i~j是否回文,則可寫出DP方程 i = j : true j = i + 1:if 兩字元相同則回文 j = i + n:if 兩字元相同且 dp[i+1][j-1] 是回文 最後紀錄最長回文字串起始與長度
另一個是馬拉車算法,待研究。 |
30 | | Easy | 9. Palindrome Number | [LeetCode] 9. Palindrome Number 验证回文数字 | 驗證數字是否回文 只要是負數就一定不是,把 int 轉成 string,判斷是否回文。 Follow up 不能用字串,可以直接把數字倒過來,相等就是回文。 |
31 | 2020/10/11 | Hard | 214. Shortest Palindrome | 花花酱 LeetCode 214. Shortest Palindrome [LeetCode] 214. Shortest Palindrome 最短回文串 | 最短回文字串 在給定字串前加上字符讓他成為最短回文字串。 將給定的字串S反轉得到T,一個從頭一個從尾取N−1~1個,當相等時表示找到最長回文字串,只要再加上前面沒有重複的即可。
另一個是KMP算法,待研究。 |
32 | | Hard | 336. Palindrome Pairs | [LeetCode] Palindrome Pairs 回文对 | 給定一字串陣列,找出組起來是回文的組合 先用一 Map 存字串與 Index 的對應,遍歷每個字串先找到是否有反轉後相等且不是同樣位置的字串;接著在找是否存在反轉子字串且剩餘部分回文。 |
33 | | Medium | 131. Palindrome Partitioning | 贾考博 LeetCode 131. Palindrome Partitioning [LeetCode] Palindrome Partitioning 拆分回文串 | 給定一字串,找出切開之後是回文的地方 這題可以用 Backtracking 的方式枚舉所有可能性,當遇到回文的時候繼續往下遍歷。 |
34 | | Hard | 132. Palindrome Partitioning II | 花花酱 LeetCode 132. Palindrome Partitioning II – 刷题找工作 EP281 [LeetCode] Palindrome Partitioning II 拆分回文串之二 | 給定一字串,求出切開之後是回文的最少刀數 這題需要兩個DP陣列,一個紀錄j-i是否是回文,一個紀錄前i個的最小刀數是多少。當j-i是回文時,取前j−1的最小刀數+1和目前紀錄的最小值。當J=0表是從頭開始到目前都是回文,刀數=0。 |
35 | | Easy | 20. Valid Parentheses | [LeetCode] 20. Valid Parentheses 验证括号 | 驗證括號是否有效 ([{}])需成對出現,右括號也必須在左括號後面。 這題直接用 Stack來解,遇到左邊的就放進去,遇到右邊的就看S是否為空或是最上面那個是否跟他成對。 |
36 | 2020/10/12 | Medium | 22. Generate Parentheses | Leetcode : 22 Generate Parentheses 讲解 贾考博 LeetCode 22. Generate Parentheses | 生成所有有效的括號組 這題也是用 Backtracking 來枚舉,當左右都=0則到達最後邊界可以直接加入答案,需要注意的是左括號數量<右括號不合法。 |
37 | | Hard | 32. Longest Valid Parentheses | Leetcode : 32. Longest Valid Parentheses 讲解 [LeetCode] 32. Longest Valid Parentheses 最长有效括号 | 最長有效括號組 用 Stack 來解,並宣告一個變數存起始位置。當遇到左括號就壓入棧中,若在 Stack 為空情況下遇到右括號,更新起始位置。不然就把棧內的 pop 出來,紀錄最長有效括號長度。 |
38 | 2020/10/13 | Medium | 241. Different Ways to Add Parentheses | 花花酱 LeetCode 241. Different Ways to Add Parentheses – 刷题找工作 EP32 [LeetCode] 241. Different Ways to Add Parentheses 添加括号的不同方式 | 添加括號的不同方式:給定一字串之後算出不同括號排列下的值 這題可以在運算符的地方用遞迴切開左右半邊遍歷求解,當最後只有數字就把字串轉述自存進去,然後再把左右半邊的和根據運算符計算出來,過程中可以把求過的紀錄在 Map 裡節省重複運算的時間。 |
39 | | Hard | 301. Remove Invalid Parentheses | 花花酱 LeetCode 301. Remove Invalid Parentheses – 刷题找工作 EP139 [LeetCode] 301. Remove Invalid Parentheses 移除非法括号 | 移除非法括號 先掃一遍計算不合法的左括號&右括號個數 接著遞歸先把右括號刪掉,再刪左括號,當左右括號都刪光光時判斷是否為合法解。 |
40 | | Easy | 392. Is Subsequence | [LeetCode] Is Subsequence 是子序列 | 判斷一字串是否是另一個字串的子序列 使用兩個PTR指向S/T,如果兩個字元相等就都加一,不然只有T的往前移動,最後判斷S指針是否已經找到終點。 另一個方式是先將T中所有字元的位置存到 HashMap 中,在搜尋時用 pre 把S在T中的位置記錄下來,後面必須大於前面才是合法。 |
41 | | Hard | 115. Distinct Subsequences | 花花酱 LeetCode 115. Distinct Subsequences – 刷题找工作 EP208 [LeetCode] 115. Distinct Subsequences 不同的子序列 | 不同的子序列,給定S找出可以從中找出幾組子序列T 給定兩個XXX,求XXX,通常用DP解 找到動態轉移方程:如果字元相同則 dp[i][j] = dp[i-1][j-1] + dp[i-1][j],不然直接等於 dp[i-1][j] |
42 | 2010/10/18 | Medium | 187. Repeated DNA Sequences | 贾考博 LeetCode 187. Repeated DNA Sequences 有这样的DNA应该是活不了太久了 [LeetCode] 187. Repeated DNA Sequences 求重复的DNA序列 | 重複的DNA序列 求重複的DNA子序列,用 Map 來紀錄出現次數,如果超過兩次就放入解答中。利用ATGC最後三 bit 值會不同的特性,可以用一個整數來存10個字元,如此一來即可節省使用空間。 |