# 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) ### 教學網站 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](/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) + 其他 + [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,來得到答案。 + [解題技巧](/4qhm9YxKSZSs76s9qi0Low) + [小技巧/code snippet](/3I17t2spT6GDLFRftfEOZA) + [關鍵字/keyword](/jrO24dggStyloQy6nO3OZw) + [C++API/STL整理](/_LIBYTzATYWdOTpEu3dV0Q) + [C++ Operator Precedence]([/gxs9HkI_QmyHpl9mq8bbJA](https://en.cppreference.com/w/cpp/language/operator_precedence)) + [Learn C++](https://www.learncpp.com/) + [名詞解釋](/WXlO8tuoS1yyD_RGmyPGyQ) + [Time/Space Complexity](/nPCWaocaSEedyO0-07plZg) ###### tags: `leetcode` `刷題`