# Leetcode刷題學習筆記--心得統整

## Useful references
### 面試準備
1. [軟體工程師求職 (1)履歷撰寫](https://www.ptt.cc/bbs/Tech_Job/M.1485621882.A.714.html)
2. [軟體工程師求職 (2)公告於市](https://www.ptt.cc/bbs/Tech_Job/M.1485622180.A.C4B.html)
3. [軟體工程師求職 (3)面試準備](https://www.ptt.cc/bbs/Tech_Job/M.1485622697.A.337.html)
4. [軟體工程師求職 (4)面試工具篇](https://www.ptt.cc/bbs/Tech_Job/M.1506226845.A.685.html)
5. [分享技術部落格: 酷殼](https://www.ptt.cc/bbs/Tech_Job/M.1485709329.A.A46.html)
6. [中年找工作心得](https://www.ptt.cc/bbs/Tech_Job/M.1524879194.A.7AA.html)
7. [軟體職缺準備心得](https://www.ptt.cc/bbs/Soft_Job/M.1657873542.A.6AB.html)

### 刷code心得
1. [LeetCode高效刷題心得分享](https://www.ptt.cc/bbs/Soft_Job/M.1602732913.A.BD9.html)
2. [COVID期間拿到Google FB 微軟 Offer Part3](https://www.ptt.cc/bbs/Soft_Job/M.1605589986.A.CBA.html)
3. [面試分享 Google/MS/Amazon/Roku](https://www.ptt.cc/bbs/Soft_Job/M.1628870944.A.C3B.html)
4. [Google TW SWE 面試心得（上）](https://www.ptt.cc/bbs/Soft_Job/M.1625756279.A.914.html)
5. [Google TW SWE 面試心得（下）](https://www.ptt.cc/bbs/Soft_Job/M.1625903945.A.52F.html)
6. [0到100的軟體工程師面試之路](https://ithelp.ithome.com.tw/users/20152262/ironman/5615)

### 薪資比較
1. [薪資透明化](https://www.ptt.cc/bbs/Soft_Job/M.1628006709.A.6E5.html)
2. [levels.fyi](https://www.levels.fyi/Salaries/Software-Engineer/Taiwan/)

### 推薦題庫
1. [Blind Curated 75](https://leetcode.com/list/xoqag3yj/), [(我的整理)](/B5OJc3twTAOJg6yEysmOoA)
2. [Leetcode 题解](http://www.cyc2018.xyz/%E7%AE%97%E6%B3%95/Leetcode%20%E9%A2%98%E8%A7%A3/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E7%9B%AE%E5%BD%95.html#%E5%89%8D%E8%A8%80)
3. [花花酱 LeetCode Problem List 题目列表](https://zxi.mytechroad.com/blog/leetcode-problem-categories/)
4. [Leetcode 101](https://github.com/changgyhub/leetcode_101/)
5. [NeetCode 150](https://neetcode.io/)
6. [Grind 75 questions](https://www.techinterviewhandbook.org/grind75)
### 解題網站
1. [Grandyang](https://www.cnblogs.com/grandyang/)
2. [花花酱](https://zxi.mytechroad.com/blog/)
3. [wisdompeak](https://github.com/wisdompeak/LeetCode)
4. [Leetcode Solutions in Java Python C++ Php Go Typescript](https://leetcode.ca/)
### 教學網站
1. [LABULADONG 的算法网站](https://labuladong.github.io/algo/)
2. [LEARN C++](https://www.learncpp.com/)

### 面試時的反問
1. [面試時的反問](https://github.com/NeroCube/reverse-interview-zh-tw)

### 資訊科技產業專案設計(2021年秋季)
1. [課程進度表和公告](https://hackmd.io/@sysprog/info2021/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FSJ3QpJJNY)
2. [作業1](https://hackmd.io/@sysprog/info2021-homework1)
3. REACTO
+ Repeat: 重複提問，確認自己理解原本的要求
+ Examples: 針對題目條件，舉出符合的案例，不限於特例
+ Approach: 說明自己打算採用的方案
+ Code: 撰寫程式
+ Test: 若不能實際測試，那說明驗證程式的方案

### [Google Tech Dev Guide](https://techdevguide.withgoogle.com/)

### 超牢記憶法Make It Stick
1. 努力回想才是記憶的關鍵（retrieve檢索）
+ 奮力回想(從題目到解答自己做一次)
+ 不要重複翻閱(不要只看code不動手做，試著回想解答的流程)
2. 穿插式練習(同時練習好幾種類型的題目)
+ 將練習當成比賽，才能把比賽當成是練習。
3. 每天回想學習過的東西，不能拿出筆記來參考
5. 費曼學習法(把學過的東西給12歲小孩聽得懂，看見事物的原始結構)
6. 找一個好的教練（簡答題考試）
+ 當一個在某個領域越不擅長時，就越容易高估自己的能力。
+ 花幾分鐘為幾天後自己出一張考卷(周末把一個禮拜的每日精選做一次)
+ 考試的時機點，在大腦開始遺忘，但還沒完全遺忘之前。(隔天)(每天選一題隔天再做一次)

{%youtube k-MOeKIkvfs %}

---

+ 演算法
+ [Recursive](/231S57V1QcmoVFfMr2c5_A)
把問題切成相同的小題目。
+ [Tree Traversal](/k_fIImRKQlSvwXp-OUMS9A)
分為pre-order, in-order，post-order和level-order，可以使用DFS或BFS.
+ [Depth-First-Search/Breadth-First-Search](/Rs3M7lf1TzOR0Lx_RhgpNg)
依深度或是廣度瀏覽所有的資料
+ [Dynamic Programming](/474VEENxSVSGMRRRtfvetQ)
通常是求maximal或是minimal或是幾種方法的時候會用到。
+ [Divide and Conquer](/KRNZe1ZKRIu79PJDR1KPLg)
將題目分成一樣的小題目，最後將結果合併起來。
+ [Binary Search](/u7dufNJ-SAq7z0WmS-Semw)
在排序過的資料中，尋找目標值。用二分法找效率為O(logN)。
+ [Two-pointers Binary Search](/qocJcScbSySS7xWbLbhaLg)
在排序過的1D或是2D vector中尋找想要的值。
+ [Two Pointers](/gg-708HfRomJ66P7XX_QKQ)
通常為array中，使用前後兩個pointer來比較資料。
+ [Fast Slow Pointers](/jO2mrGfpSiyZ_WlZIG7Aeg)
在linked-list中使用快慢pointer來解決問題。
+ [Combination](/BRtCz4qGR-y4XevyNbchzg)
在所有的組合中，找出最佳的答案。
+ [Sliding Window](/6lto0AbFTjCDxw7ohUkd3Q)
需要找出連續資料的關聯性。ex. substring, subarray.
+ [Backtracking](/h4ghhABcT9yyDC0JcSPRPw)
+ Sort algorithm
+ [Selection/Bubble/Insertion/Heap sort](/qxzTY7A4Sha_jFHpGJx5Wg)
+ [Bucket Sort](/K5s3M6TkS0q2HrRpCBpnnQ)
把數字分成一個一個的區段，ex: [0] : 0~9, [1] : 10~19, [2] : 20~29
+ [Counting/Radix Sort](/I-kxuqAqSsiB6wlIddQpGA)
+ [Greedy + heap](/dqDTmv4jQMeuOOQYdzEG_Q)
如果問題是詢問max或是min，最直覺的解法就是依序把最大或是最小的數值相加，但是有時候必須刪減就是用heap提供的數值。
+ [Greedy](/p9hSX0fpSQGwCUL3QF7cLA)
每次都把目前的狀態update到最有利的狀態。
+ 資料結構
+ [Set](/zoTq--X9Ri6RruOyCRcP1A)
只能儲存value，必把value當成key。
+ [Map](/XfUiK191STCsppXWkgjbXQ)
把資料做成key-value的對應，可以快速找到key對應的value。</br>或是使用==客製的key==來對資料做統計。
+ [stack](/7JBTdRgkQnmDaTlUacYuTA) [後進先出]
利用後進先出的特性，可以解決pair的問題或是反轉的效果。兩個stack也可以組成不同的特性。
+ [Queue](/TNlZeQk_T-qqsLS7caigZQ)
先進先出，可以用在BFS。使用BFS通常可以解決最小數量的問題。
+ [monotonic stack](/zEgS9fqBSzScisni9JNm_A)
一樣是stack，但是stack的內容有照一定的順序排列。遞增或遞減。找出前後比自己大或小的element。或是往左看往右看的最大值。
+ [Binary Search Tree(BST)](/neNmzsZsRrmYQ-RtPWbYxA)
他是一個binary tree，但是準守著左邊的node小於root, 右邊的node大於root。
+ [Graph](/dIurYyg1T5ue-KlCoj9reA)
有向圖和無向圖。
+ [Disjoint set/Union Find](/wU2PrLOpSZmcgiu64UYnRQ)
使用root array來紀錄每個vertex的root或是parent node
+ Minimal spinning tree
最小weight和，可以把全部的node連起來的tree，通常使用greedy演算法，==每次都從最小的weight開始選，如果沒在graph裡面就加進來。==
+ Single Source Shortest Path Algorithm
+ [Dijkstra](/3IcoorPnRX66_oBNZd6Inw)
類似BFS，但是使用priority_queue來取最小weight路徑。
+ [Shortest Path Faster Algorithm(SPFA)](/Uy6iSrZSTHa32c_tO6Zx_w)
使用vector和queue來記錄從source到每個node的最短路徑。可用在negative weight。
+ [Topological sorting](/OeOB6NHGSvGkkhJIZd5Jog)
走訪有相依性的圖。
+ [Trie](/QDEA_oTZTwOqDc35dWwOHw)
統計字串或是數字的bit
+ [Priority_queue](/m_6sQq4DS9u3TXsGYEcUTw)
統計最大最小值的出現。
+ [Binary Index Tree(BIT)](/ogxY5ToqTT-RAZUqRhxbgw)
計算range sum可以達到 update是O(logN)，getSum也是O(logN)
使用prefix sum只能達到 update是O(N), getSum是O(1)
使用array sum 只能達到 update是O(1), getSum是O(N)
+ [Segment Tree](/ctPbr-0MS72wc4rerLwD5Q)
和Binary Index Tree一樣，可以用來計算range sum。除此之外還可以計算range maximum/minimum，或是有效率的update一個區間的elements。
+ 其他
+ [Brute Force暴力破解](/eCH42Zj-RJ-9xo3rbFOCBg)
走訪所有的可能性，來找出最佳解。通常是面試時提出的第一個解法。從這邊也許可以延伸出sub-optimal或是optimal的解法。
+ [Math數學解法](/ncPyegzYSdGq1G6xCP4gPQ)
有些時候分析完題目，發現用數學解反而更精簡。
+ [Randomized](/zOR7woWNRwyVGtir5Lj_4A)
選取element並且每個的機率都一樣。
+ [Bit Manipulation](/3VK0v_k7TpiJwtArT1otxg)
對bit做處理。
+ [加法器設計](/fxpMUrR7Sd6bt_mrzUMkYg)
+ [prefix sum](/Io-i2knhQvaqqXSOKn2BcA)
prefix_sum[i] = sum(nums[0:i - 1]); 前i個的和，適合用來解區段sum的題目。
+ [subset sum](/FbvqYdi1SsCc-R96j0jVAA)
把一個數列分成若2個subset，求出兩個subset的特殊 關係。例如sum(s1) = sum(s2) 或是 sum(s1) - sum(s2) = target等等。
+ [Interval](/fiSdDPowTOywK9g9Rl_jLg)
使用[start, end)來表示一個區間。
+ [Line Sweep](/kAUQzqmBQKSfB8Kw7QSk1Q)
依序掃描x或是y，來得到答案。
+ [Binary Lifting]()
尋找第k個parent的技巧。
+ [two pass](/7HFHM30fTLq3SfBeW99DyQ)
題目的解答和前後都有關係。
+ [解題技巧](/4qhm9YxKSZSs76s9qi0Low)
+ [小技巧/code snippet](/3I17t2spT6GDLFRftfEOZA)
+ [關鍵字/keyword](/jrO24dggStyloQy6nO3OZw)
+ [C++API/STL整理](/_LIBYTzATYWdOTpEu3dV0Q)
+ [C++ Operator Precedence](https://en.cppreference.com/w/cpp/language/operator_precedence)
+ [Learn C++](https://www.learncpp.com/)
+ [名詞解釋](/WXlO8tuoS1yyD_RGmyPGyQ)
+ [Time/Space Complexity](/nPCWaocaSEedyO0-07plZg)
###### tags: `leetcode` `刷題`