CS:APP 電腦系統:程式設計師的角度 第一章筆記
這是來自卡內基梅隆大學的優質課程，對底層系統的理解越深，對程式設計師來說只有百利而無一害。雖然一時半刻看不到有什麼成效，但未來的某些日子一定會覺得當初學了這些真是太好了 電腦名詞譯名 首先從hello world開始以C語言來說，讓寫好的以下程式碼執行，需要經過如下步驟 #include <stdio.h> int main() { printf("hello, worl
130. Surrounded Regions - Medium
前往題目 想法 用DFS看每個島嶼在哪，然後翻轉，但是要注意外圈的O會使得比鄰的O不能被反轉，這部分不知道怎麼做，得另外再搜尋哪些有比鄰 思路 用BFS從border開始更好理解 從外圈開始遇到O就BFS搜尋比鄰它的O，感染的概念，一個接著一個感染，並先標記為# 最後搜尋完了之後再疊代整個board，遇到O就是沒有比鄰的，直接翻轉為X，遇到#就是比鄰的O，翻轉回O Code文字解析 cl
695. Max Area of Island - Medium
前往題目 想法 和之前寫過的島嶼類似，但忘了怎麼開頭，只知道DFS會輕鬆一些 思路 利用DFS 從第一個cell開始，遇到水就跳過，遇到走過的cell也跳過，出界的也跳過 把每個區域的1都走過然後加起來，因為dfs遇到出界或是海水就會回傳，所以最終每個區域的面積都可以被單獨算出來，因為演算法不會越過水到另一片陸地。 Code class Solution { privat
131. Palindrome Partitioning - Medium
前往題目 想法 backtracking把所有組合都看過，每次要判斷是否是palindrome然後才加入 思路 平常的backtrack 要紀錄起始點，然後每個循環都要判斷是否為palindrome Codeclass Solution { List<List<String>> res = new LinkedList<>(); LinkedLis
40. Combination Sum II - Medium
前往題目 想法 和今天稍早寫的另一題(90)一樣的套路 思路 先sort，這樣才好跳過取過的數字 正常backtrack 唯一需要注意的是追蹤index，如果循環中的index已經比傳入的index還大的時候就要判斷是否和前一個數字一樣，要跳過，代表前一個已經被取過了 這題很妙的是和第90一樣的做法，但90是不能取同一個subset即便順序不同，這個是不能取到取過的數字 總之這個技巧的核心就
90. Subsets II - Medium
前往題目 想法 以為是簡單的backtrack，但是需要考慮如何防止加入重複的subset 思路 先sort，這樣才好判斷相同的數字 正常backtrack 唯一需要注意的是追蹤index，如果循環中的index已經比傳入的index還大的時候就要判斷是否和前一個數字一樣，要跳過 判斷的邏輯很妙，尤其是i > idx，後來想了想應該是i == idx的時候不用判斷，因為還沒加入，加入後
46. Permutations - Medium
前往題目 想法 之前做過的簡單backtracking 思路 backtracking check是否數字已存在，以免重複加入 暫存的list可能可以用其他實作方式，可以removeLast in O(1)，不然arraylist要移除最後一項需要N次操作 Codeclass Solution { List<List<Integer>> res; pub
33. Search in Rotated Sorted Array - Medium
前往題目 想法 之前寫過，條件實在不好想 思路 Binary search整個nums 如果mid不是答案，看左指針的值是否小於等於mid的值，代表順序正常，再接著判斷，是否左邊的portion被rotate到右邊了 如果都不是那判斷右邊portion是否被rotate到左邊去了，並移動指針 這次第二次做，覺得可以思考的方向是: mid和l指針的值正常的情況(l <= mid)如何判斷