經過上次的 leetcode 30days project 不知不覺又過了四個月
其實這段時間 Leetcode 有一直在持續每個月的挑戰計畫,但在忙碌的上班生活中,實在是一不小心就會鬆懈了。
上次每天寫系統分配的一題,雖然有考量到 Easy / Medium / Hard 循序漸進,不過每天題目的類型非常多變,也不容易有系統性地整理和思考。
這次想參考網路上已經有整理的 Leetcode 分类顺序表,依照不同主題來刷,看看兩個月後到底會進步多少。
在這過程當中也發現許多講解的頻道或部落格,提供給大家參考:
YT:花花醬 / Cspiration 官方频道 / Jacob Huang /basketwangCoding/今天比昨天厲害/来Offer – LaiOffer/小Q刷Leetcode
Blog:Grandyang/
這篇基本上就是總覽,把解題過程的思路和參考的講解視頻以及其他參考資料都整理在下面。
[2020/09/23] 終於把第一個分類Array 寫完一遍,總計67題:20E、28M、19H,這樣寫了一輪下來的心得是:果然當初一天想寫十題太過樂觀。但目前這樣刷下來也發現自己的不足之處,還了不少的債。一開始訂個高一點的目標,就算最後沒有達成,也會發現已經爬得比預想的還高了。保持這股氣勢繼續前進吧。
No. | 完成日期 | 難易度 | Leetcode Link | 網路講解視頻 | 文章 | Memo |
---|---|---|---|---|---|---|
1 | 2020/09/05 | Easy | 27. Remove Element | Leetcode :27 Remove Element 讲解 | [Leetcode] 27. Remove Element | 刪除重複的元素。 透過兩個一快一慢的 ptr 判斷是否重複,如果相同,快的繼續往前;如果不同將值寫到慢的。 |
2 | Easy | 26. Remove Duplicates from Sorted Array | leetcode: 26 Remove Duplicates from Sorted Array 贾考博 LeetCode 26. Remove Duplicates from Sorted Array | 與上一題相同。 | ||
3 | Medium | 80. Remove Duplicates from Sorted Array II | 贾考博 LeetCode 80. Remove Duplicates from Sorted Array II | 上面兩題的變形,至少可以重複兩個。 一樣透過兩個一快一慢的 ptr,但判斷改成是否與前兩個位置相同,如果相同表示前面已經有重複兩個一樣的。Ex(1,1,1) | ||
4 | Easy | 189. Rotate Array | 贾考博 LeetCode 189. Rotate Array | [1,2,3,4,5,6,7] rotate k 1. 先 revert 成 [7,6,5,4,3,2,1] 2. 再分別 revert 前 k 個(以 3 為例) 先 revert 前三個 [5,6,7,4,3,2,1] 再 revert 後四個 [5,6,7,1,2,3,4] | ||
5 | Hard | 41. First Missing Positive | Leetcode : 41 First Missing Positive 讲解 | [Leetcode] 41. First Missing Positive | 找到第一個不存在的最小正整數 當 array 有 n 個,裡面的數字就該是 1~n 如果發現 nums[i] 介於 1~n,且nums[nums[i]-1] != nums[i] 那就把他們交換讓 nums[i] 物歸原位 最後再掃一遍如果有人不等於那就找到答案拉。 | |
6 | Easy | 299. Bulls and Cows | 小Q刷Leetcode第22期 299 | 經典的幾A幾B 先判斷是否為 A,不然宣告 cnt[] 來存對應數字的個數,假設 secret++ 還是負,表示先前已經有 guess;或是反過來假設 guess– 還是正,表示先前已經有 secret,兩者都需要B++。 | ||
7 | Medium | 134. Gas Station | 贾考博 LeetCode 134. Gas Station 加不起油怎么算? | 油夠不夠 若 Total gas > Total cost,那一定可以繞完 若 中途 gas < cost,則開始點一定在後面 | ||
8 | 2020/09/06 | Easy | 118. Pascal’s Triangle | 贾考博 LeetCode 118. Pascal’s Triangle 【LeetCode】 118. Pascal’s Triangle | [Leetcode] 118/119. Pascal’s Triangle | 帕斯卡三角形 Input: 5 Output: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] For 每一列i< input For 每一行 j <= i 若 j==0 || j==i –> 1 否則 –> 上一行的 [j-1] + [j] |
9 | Easy | 119. Pascal’s Triangle II | 贾考博 LeetCode 119. Pascal’s Triangle II 【LeetCode】 119. Pascal’s Triangle II [LeetCode] 119. Pascal’s Triangle II 杨辉三角之二 | 與上一題相同,只要回傳最後一列即可。 | ||
10 | Easy | 169. Majority Element | 花花酱 LeetCode 169. Majority Element – 刷题找工作 EP101 贾考博 LeetCode 169. Majority Element [Day 23] 從LeetCode學演算法 – 0169. Majority Element (Easy) | 找出佔大多數的數字: Boyer–Moore majority vote algorithm(摩爾投票算法) 這個算法的核心在於, 刪去一個數列中的兩個不同的數字,不會影響該數列的majority element。 假設有一群人投票,候選人A/B/C,已知A過半。 如果任意取消兩個人的投票資格,則會出現以下狀況: 1取消B/C->A依然當選且比例更高 2取消A/B或A/C->對A不造成影響 另外假設題目沒有保證一定會有一個數字超過 2/n,則也可以用相同方式找到一個值,再去遍歷一遍看是否超過 2/n 這題解法其實很多種,ex:Hashmap、 Sorting(Majority 一定在中間),花花影片整理的很齊全,有興趣可以參考。 | ||
11 | Medium | 229. Majority Element II | [LeetCode] 229. Majority Element II 求大多数之二 | 這題是上一題的變形,找出所有出現次數超過 n/3 的數字。 時間限定 O(N)、空間O(1),那就只能用摩爾了。 因為超過 n/3 的最多只有兩個,所以可以先用摩爾找一遍把最多的兩個找出來。接著再跑一遍看這兩個有沒有超過 n/3 即可。 | ||
12 | Medium | 274. H-Index | 小Q刷Leetcode第21期 274 | 求H-Index,也就是N篇中H篇的引用次數>H 可以直接排序求解,從後面開始掃描,如果該篇引用次數大於目前H值,則H可以加加繼續往前掃。 | ||
13 | Medium | 275. H-Index II | 這題和上一題一樣,差在給的是已經排好的陣列。 *提示是否可以用 log(N),這個等到 BST 的時候再來研究。 | |||
14 | Easy | 217. Contains Duplicate | 贾考博 LeetCode 217. Contains Duplicate | 找出是否有重複數字 暴力解會超時,可以透過 sorting 排序後確認是否有人跟下一個一樣;或是透過 Map/HashSet 等都可以用來確認是否有重複。 | ||
15 | Easy | 219. Contains Duplicate II | 贾考博 LeetCode 219. Contains Duplicate II | 找出重複數字的 index 差是否 <= K 宣告一個 Map 存 <val / index>,如果有相同 val 存在比較是否 <= K 無論是沒找到還是 >K 都要更新,直到遍歷完確定沒有。 *ps:map 88ms vs unordered_map 48ms | ||
16 | Medium | 220. Contains Duplicate III | 贾考博 LeetCode 220. Contains Duplicate III 220 – Contains Duplicate III【FLAG高频精选面试题讲解】 leetcode Contains Duplicate 整理 | 找出是否有兩數字差值介於T且距離介於K 用SET來實作 sliding window,只存K個值。在這K個中找高於 nums[i] – t 的最小值,如果這兩個差 <t,則表示滿足條件。 | ||
17 | Medium | 55. Jump Game | 贾考博 LeetCode 55. Jump Game 花花酱 LeetCode 55. Jump Game | 是否能跳到最後一格 找出目前可以跳得最遠格數,如果超過最後一格表示可以到達。 若中間最遠小於當下的位置,表示一定跳不到後面。 | ||
18 | 2020/09/07 | Hard | 45. Jump Game II | Leetcode :45 Jump Game II 讲解 LeetCode 笔记系列13 Jump Game II [去掉不必要的计算] | 假設一定可以跳到最後一格,求最小步數 核心概念是記錄我可以到的最遠距離,該跳再跳。 | |
19 | 2020/09/08 | Easy | 121. Best Time to Buy and Sell Stock | 花花酱 LeetCode 121. Best Time to Buy and Sell Stock – 刷题找工作 EP140 贾考博 LeetCode 121. Best Time to Buy and Sell Stock 别做梦了,让你知道涨落你都赚不到钱 | 如果只能買賣一次,求最大獲利 逐一掃描找目前最低,以及減最低看是否最高。 這題可以轉成給定每日獲利,求最大總和。 | |
20 | Easy | 122. Best Time to Buy and Sell Stock II | 贾考博 LeetCode 122. Best Time to Buy and Sell Stock II | 如果只能買賣多次,求最大獲利 相鄰兩天如果後面漲前一天就買,全部加起來就是最大獲利。 | ||
21 | Hard | 123. Best Time to Buy and Sell Stock III | [LeetCode] Best Time to Buy and Sell Stock III 买股票的最佳时间之三 [Leetcode 123] Best Time to Buy and Sell Stock III LeetCode 123. Best Time to Buy and Sell Stock III – Python思路總結 | 如果只能買賣兩次,求最大獲利 看到三種方式,一個是DP,可以求買賣K次 另外一個是把陣列切成兩個,從前往後掃和從後往前掃,分別求兩個陣列的最大獲利。 第三個是分別紀錄第一次和第二次的最大獲利/最低成本。 不得不說看完算法真的很厲害。 | ||
22 | Hard | 188. Best Time to Buy and Sell Stock IV | [Leetcode 188] Best Time to Buy and Sell Stock IV | 如果能買賣K次,求最大獲利 影片講得非常清楚,照著方程式自己跑一次範例就可以弄懂了。 這題的DP方程式&我的白話翻譯 dp[k][d] = max(dp[k][d-1], maxR + prices[d]) 今天的獲利 =max(昨天的獲利(不交易),目前的最大利潤+今天的賣價(交易)) maxR = max(maxR, dp[k-1][d] – prices[d]) 目前的最大利潤=max(目前的最大利潤,前一筆交易的最大獲利-今天的買價) 最後答案為 dp[k][d] | ||
23 | 2020/09/09 | Medium | 309. Best Time to Buy and Sell Stock with Cooldown | 309 – Best Time to Buy and Sell Stock with Cooldown【FLAG高频精选面试题讲解】 | 如果能買賣K次,但賣完股票隔天要休息一天,求最大獲利 這題一樣用DP來解 每天會有兩種持有股票的狀態:持有/非持有,以下分別代表第i天持有或非持有的最大獲利 hold[i] = max(hold[i-1], unhold[i-2]-prices[i]) 持有股票的最大獲利=max(前一天持有股票的最大獲利,前兩天非持有股票的最大獲利−今天的股價) unhold[i] = max(unhold[i-1], hold[i-1]+prices[i]) 非持有股票的最大獲利=max(前一天非持有股票的最大獲利,前一天持有股票的最大獲利+今天的股價) 最後答案為 unhold[i-1] | |
24 | Medium | 11. Container With Most Water | Leetcode : 11 Container With Most Water | 給一個數組求最多可以裝多少水![]() 這題其實蠻簡單的,可能是因為不能暴力解會超時所以Medium(? 宣告兩個 PTR 分別從前往後/從後往前掃(低的往高的移動),紀錄過程中遇到的最大面積。 | ||
25 | Hard | 42. Trapping Rain Water | Leetcode : 42. Trapping Rain Water 讲解 | 給一個數組求最多可以裝多少水 跟上一題不同的是只要左右擋板比較小就裝不住了 ![]() 一樣用左右兩個 PTR 的概念,更新左右擋板,只要目前比左右的都小,可以困住的水就是當前的值和左右最小值的差。 | ||
26 | Medium | 334. Increasing Triplet Subsequence | [LeetCode] Increasing Triplet Subsequence 递增的三元子序列 | 找出是否存在長度三的遞增子數列(不一定要連續) 很Greedy 的方式, 是否小於第一個最小值,如果是,更新第一小 是否小於第二個最小值,如果是,更新第二小 or 找到第三個大的數,回傳T | ||
27 | Hard | 128. Longest Consecutive Sequence | 花花酱 LeetCode 128. Longest Consecutive Sequence – 刷题找工作 EP80 | 求最長連續子序列,題目未排序且需要O(N) 暴力解需要O(N三方),不過查找的部分可以透過 unordered_set 直接N解決,果然這就是善用SLT的好處阿。 | ||
28 | 2020/09/10 | Hard | 164. Maximum Gap | [Leetcode 164] Maximum Gap | 求兩個排序後相鄰整數的最大 Gap 1、排序,然後掃一遍找 max nums[i+1] – nums[i],O(NlogN) 2、桶排序,O(N),影片講得很清楚,大推。 先找出輸入的最大值/最小值 桶子個數=arr.size()-1 桶子容量=(max-min)/桶子個數 arr[i] 要放在第幾個桶子=min(桶子個數-1,(arr[i] – min)/桶子容量)//避免最後一個超界 紀錄每個桶子的最大最小 要求的最大 Gap=現在桶子裡的最小−前一個桶子的最大 | |
29 | Medium | 287. Find the Duplicate Number | 287 Find the Duplicate Number | 找出重複數字,上面14題的加強版 用排序/Set 都可以找到,但題目希望是時間小於O(N平方)空間O(1),且不改到原始的陣列。 這題可以轉換成 Link-list 找環的題目,如此一來就可以2個快慢的PTR來找。當快慢兩指針相遇時,相遇點到環起始點=起點到環的起始點長度會相同。用這個特性就可以把重複點找出來了。 | ||
30 | Hard | 135. Candy | 【每日一题:小Fu讲解】LeetCode 135. Candy | 根據小孩的排序發糖果 每個人至少一個 &大的要比小得多 宣告一個陣列,至少為一 從前往後掃,如果後面比前面大,則等於前面加一 從後往前掃,如果前面比後面大,則取後面加一和當下值的最大 | ||
31 | Hard | 330. Patching Array | [LeetCode] Patching Array 补丁数组 | 給定一數列N,決定要打幾次補丁才能表示1~N的數字 核心概念為如果可以表達[1~X),加上Y之後可以多表達[Y~Y+X),所以可表達範圍就變成[1~Y+X),如果你現在的陣列沒有X,那一定要加X這個補丁。 | ||
32 | 2020/09/13 | Hard | 4. Median of Two Sorted Arrays | Leetcode : 4. Median of Two Sorted Arrays [LeetCode]4. Median of Two Sorted Arrays 中文 | 給定兩排序陣列,找出這兩個陣列的中位數 宣告一個(M+N)array,可以用 2ptr 比較陣列大小塞到新的陣列中,接著再根據偶數還是奇數個回傳中位數即可。 另一個方式是 Binary Search,將陣列切成前I個加前J個=後M−I+N−J。只要滿足L1<R2&&L2<R1即表示找到切點。 | |
33 | 2020/09/14 | Hard | 321. Create Maximum Number | 花花酱 LeetCode 321. Create Maximum Number – 刷题找工作 EP107 [LeetCode] 321. Create Maximum Number 创建最大数 | 給定兩陣列,找出相對順序不變可以表達的最大K位數 這題可以分成兩小題,先從兩個陣列中取出i&k−i個最大值,接著再把這兩個合成一個最大數列。 | |
34 | Easy | 303. Range Sum Query – Immutable | 花花酱 LeetCode 303. Range Sum Query – Immutable – 刷题找工作 EP10 | 給定一陣列,求出區間 [i,j] 的和 每次都 for 迴圈算太慢,可以先把前N個都加起來,每次回傳第j+1個~i的差即可。 | ||
35 | 2020/09/15 | Medium | 304. Range Sum Query 2D – Immutable | 花花酱 LeetCode 304. Range Sum Query 2D – Immutable – 刷题找工作 EP63 [LeetCode] Range Sum Query 2D – Immutable 二维区域和检索 – 不可变 | 給定一二維陣列,求出區間 [i,j] 的和 先用一個二維陣列預存結果,最後再輸出 sum[row2+1][col2+1] – sum[row1][col2+1] – sum[row2+1][col1] + sum[row1][col1] | |
36 | Medium | 307. Range Sum Query – Mutable | [LeetCode] 307. Range Sum Query – Mutable 区域和检索 – 可变 [LeetCode]307. Range Sum Query – Mutable 中文 | 給定一可變陣列,,求出區間 [i,j] 的和 因為值會改變,這樣就無法先預處理了,直接每次都暴力解也可以過,不過時間很久。 參考解法是先將陣列轉成線段樹,如此一來計算區間和就可以縮短到O(logN)了 | ||
37 | 2020/09/16 | Hard | 327. Count of Range Sum | *** | ||
38 | Medium | 289. Game of Life | 花花酱 LeetCode 289. Game of Life – 刷题找工作 EP199 | 給定一陣列要求模擬下一次的生死(Conway’s Game of Life) 題目本身解法不難想,比較驚豔的是邊界檢查以及用倒數第二個 bit 表示下一次生死來達成 in-place 計算。 for(int x=max(0, i-1); x<min(row, i+2); x++) for(int y=max(0, j-1); y<min(col, j+2); y++) | ||
39 | 2020/09/17 | Medium | 56. Merge Intervals | 花花酱 LeetCode 56. Merge Intervals – 刷题找工作 EP85 | 給定一陣列,合併重複區間 先排序,如果後面的 start < 前面的 end,表示兩區間有重疊。 | |
40 | Hard | 57. Insert Interval | 花花酱 LeetCode 57. Insert Interval – 刷题找工作 EP86 | 給定一排序陣列,合併加入數組後的重複區間 先判斷新數組的位置,再同上一題合併 | ||
41 | 2020/09/18 | Hard | 352. Data Stream as Disjoint Intervals | [LeetCode] 352. Data Stream as Disjoint Intervals 分离区间的数据流 | 給定數據流,依序生成不重複的對應區間 同上一題思路,每次有新數字進來就計算重複範圍 newInterval[0] > interval[1] + 1(目前數組比新的小,直接放進去)it++ newInterval[1] < interval[0] – 1(目前數組比新的大,也直接放進去) 其他的就更新 newInterval,最後插入到 it 指的地方 | |
42 | Hard | 239. Sliding Window Maximum | 花花酱 LeetCode 239. Sliding Window Maximum – 刷题找工作 EP159 | 給定一個 sliding window,求出範圍內最大的數 使用 multiset 來記錄 window,特別的是下方寫法只會刪掉一個,不然相同數字的都會被刪掉。 m.erase(m.equal_range(nums[i-k]).first); 如果要求 set 最大值,可使用 *m.rbegin() | ||
43 | Hard | 295. Find Median from Data Stream | 花花酱 LeetCode 295. Find Median from Data Stream – 刷题找工作 EP51 | 給定一數字流,求出中位數 這題有很多解法: 1. 暴力解會超時。 2. Insertion sort:v.insert(lower_bound(v.begin(), v.end(), num), num); 找出小於 Num 的最大值,時間O(logN) 3. Two heap:左邊=右邊 or 右邊加一 priority_queue, greater> r; 存右半邊,top() 就是最小值 priority_queue, less> l; 存左半邊,top() 就是最大值 若左右個數相同 Medium 取兩個 top 平均,or 左邊的最大 | ||
44 | Easy | 53. Maximum Subarray | 花花酱 LeetCode 53. Maximum Subarray – 刷题找工作 EP25 贾考博 LeetCode 53. Maximum Subarray | 求總和最大的連續子數組 宣告DP陣列,目前比較大還是加上前面的比較大。 | ||
45 | 2020/09/20 | Medium | 209. Minimum Size Subarray Sum | 贾考博 LeetCode 209. Minimum Size Subarray Sum | 求等於給定值的最短子數組之和 先從頭開始找到大於等於的,接著在從頭開始減,直到找到大於等於的最小區間,判斷是否最短距離&更新。 | |
46 | Medium | 238. Product of Array Except Self | [LeetCode]238. Product of Array Except Self 中文 | 求除了自己之外的乘積 先從左往右掃,再從右往左掃,乘上除了自己的值。 | ||
47 | Medium | 152. Maximum Product Subarray | 贾考博 LeetCode 152. Maximum Product Subarray | 求乘積最大的子數組 和 53 求總和最大的子數組類似,不過乘積會受正負影響,所以必須多計算最小值,有可能最小×當前數字反而變最大。 | ||
48 | Medium | 228. Summary Ranges | [LeetCode] Summary Ranges 总结区间 | 給一數組求總結連續區間 求出從i開始連續j個相連位置,若j=1那就只要輸出 nums[i],否則輸出 nums[i] -> nums[i+j-1] | ||
49 | Easy | 88. Merge Sorted Array | 贾考博 LeetCode 88. Merge Sorted Array | 合併兩排序陣列 因為要合到 nums1,從後面大的往小的排才不會有 overlap | ||
50 | Medium | 75. Sort Colors | [LeetCode]75. Sort Colors 中文 | 給定三顏色分別以012表示,依照這個順序排序顏色 直接用 sort 竟然過了。 另一個方式是先掃過一次算出每個顏色分別有幾格再回填。 另一個方式是使用兩個 ptr 指向0&2,依序遍歷&交換。 | ||
51 | 2020/09/21 | Easy | 283. Move Zeroes | [LeetCode]283. Move Zeroes 中文 | 給定一個陣列,把0都搬到最後面 宣告 ptr ,如果目前第i個不是零就更新原陣列[ptr++] 接著再把地 ptr ~ n 個都改寫成0 | |
52 | Medium | 324. Wiggle Sort II | [LeetCode] Wiggle Sort II 摆动排序之二 | 擺動(差值正負交替)排序 先排序,接著交替從後半/前半往前取值 | ||
53 | Medium | 376. Wiggle Subsequence | [LeetCode] Wiggle Subsequence 摆动子序列 | 求最長擺動(差值正負交替)子序列長度 設PQ兩變數,遍利陣列,如果後者大於前者 Q=P+1;如果小於 P=Q+1。最後取大值 | ||
54 | Easy | 278. First Bad Version | 找出第一個BAD Binary Search,O(logN) | |||
55 | Easy | 35. Search Insert Position | Leetcode : 35 Search Insert Position 讲解 | 找出給定數字的 index,如果沒有就回傳要插入的位置 Binary Search,O(logN) | ||
56 | Easy | 374. Guess Number Higher or Lower | [LeetCode] 374. Guess Number Higher or Lower 猜数字大小 | 猜大小,給定一數字N,猜出是0~N的哪個數 Binary Search,O(logN) | ||
57 | 2020/09/22 | Medium | 33. Search in Rotated Sorted Array | Leetcode : 33 Search in Rotated Sorted Array 讲解 [Leetcode 33]Search In Rotated Sorted Array | 在一個旋轉過的遞增數組找到 Target Binary Search,O(logN) 透過 nums[mid] > nums[start] or nums[mid] < nums[start] 判斷是否包含旋轉點。 | |
58 | Medium | 81. Search in Rotated Sorted Array II | [Leetcode 81] Search in Rotated Sorted Array II | 在一個旋轉過的遞增(可重複)數組找到 Target Binary Search,O(logN) 同上題,但需加入判斷若非上述情況,則可能是平行,直接 start++ | ||
59 | Medium | 153. Find Minimum in Rotated Sorted Array | 贾考博 LeetCode 153. Find Minimum in Rotated Sorted Array LeetCode 153. Find Minimum in Rotated Sorted Array – 花花酱 刷题找工作 EP38 [LeetCode] 153. Find Minimum in Rotated Sorted Array 寻找旋转有序数组的最小值 | 在一個旋轉過的遞增數組找到最小值 Binary Search,O(logN) 如果 nums[mid] > nums[end],表示最小值在右邊,start = mid,反之 end = mid,最後比較 start & end 哪個值比較小即為答案。 | ||
60 | Hard | 154. Find Minimum in Rotated Sorted Array II | LeetCode 154. Find Minimum in Rotated Sorted Array II – 花花酱 刷题找工作 EP39 [LeetCode] 154. Find Minimum in Rotated Sorted Array II 寻找旋转有序数组的最小值之二 | 在一個旋轉過的遞增(可重複)數組找到最小值 Binary Search,O(logN) 同上題,但需加入判斷若非上述情況,則可能是平行,直接 start++ | ||
61 | Medium | 162. Find Peak Element | 贾考博 LeetCode 162. Find Peak Element | 給定一個陣列,找出波峰 Binary Search,O(logN) 如果 nums[mid] < nums[mid+1] 表示波峰在右邊,start = mid 反之波峰在左邊,end = mid,最後比較 start & start+1 誰比較大就是答案。 | ||
62 | Medium | 34. Find First and Last Position of Element in Sorted Array | Leetcode : 34 Find First and Last Position of Element in Sorted Array 贾考博 LeetCode 34. Find First and Last Position of Element in Sorted Array | 給定一個陣列,求某數的範圍 兩次BS,第一次盡可能往左找,第二次盡可能往右找。 | ||
63 | Easy | 349. Intersection of Two Arrays | [LeetCode] Intersection of Two Arrays 两个数组相交 | 求兩給定數組的交集(數字不重複) 用兩個 Set 存數組,在 s2 中遍歷 s1 | ||
64 | Easy | 350. Intersection of Two Arrays II | [LeetCode] 350. Intersection of Two Arrays II 两个数组相交之二 | 求兩給定數組的交集(數字可重複) 1、兩陣列先排序,接著分別用兩指針掃,比較小的加加。 2、使用 unordered_map,num1++,若 nums2– 還大於零表示兩個陣列都有。 | ||
65 | 2020/09/23 | Hard | 315. Count of Smaller Numbers After Self | 花花酱 LeetCode 315. Count of Smaller Numbers After Self – 刷题找工作 EP149 花花酱 Fenwick Tree / Binary Indexed Tree – 刷题找工作 SP3 | 回傳每個元素右邊有幾個比自己小 先把陣列反向排序,接著用 Fenwick Tree 儲存&查找。 | |
66 | Medium | 300. Longest Increasing Subsequence | 花花酱 LeetCode 300. Longest Increasing Subsequence (Dynamic Programming O(n^2)) – 刷题找工作 EP48 [LeetCode] 300. Longest Increasing Subsequence 最长递增子序列 | 找出最長遞增子序列長度 用DP紀錄前I個裡面有幾個最長遞增子序列 | ||
67 | Hard | 354. Russian Doll Envelopes | [LeetCode] Russian Doll Envelopes 俄罗斯娃娃信封 | 俄羅斯娃娃信封,給定長寬判斷可以裝的最大容量 前一題的變形,先排序,然後一樣用DP陣列來掃 |
LinkList 是個面試一定要會的 Session,整理如下
No. | 完成日期 | 難易度 | Leetcode Link | 網路講解視頻 | 文章 | Memo |
2020/09/13 | Easy | 1290. Convert Binary Number in a Linked List to Integer | 找出 Linklist 代表的數字 當ptr!=空,ans = ans << 1 | ptr->val ptr=ptr->next |