JOGG's

這題是給一個 stock price array,  要求一買一賣（＊僅能先買後賣）後的最大獲益。 這題很類似 longest subsequence of Integer array, 不過僅只要記錄兩個elements 差的最大值。    profit = maximum(-BuyPrice + SellPrice ) step 1.  profit =  [ prices[i] - minimum( prices[:i-1]) if prices[i] - minimum( prices[:i-1]) > profit ][0] step 2. minimum( prices[:i-1] 可拆解為 minPrice = price[0]; ...  minPrice = min(minPrice, price[i]); 1: public int maxProfit(int[] prices) { 2: if (prices.length <= 1) { 3: return 0; 4: } 5: int profit = 0; 6: int minPrice = prices[0]; 7: for (int i=1;i<prices.length;i++) { 8: if (prices[i] - minPrice > profit) { 9: profit = prices[i] - minPrice; 10: } 11: if (minPrice > prices[i]) { 12: minPrice = prices[i]; 13: } 14: } 15: return profit; 16: }

#120 Triangle 這題是給一個 triangle 結構的 list, 每個list長度對應他的depth, ex. list[i].size() = i-th depth+1, 求從root(1st list)走到 leaf (last list) 時的最小花費. 以下給兩種解法。值得注意的是用bottom-up 的解法很漂亮, 但是(1)邊界的node處理要小心；(2)作空間最佳化的思路也不是容易懂。 1: public int minimumTotal(List<List<Integer>> a) { 2: if (a.size() == 0) { 3: return 0; 4: } 5: int c0 = 0, c1 = 0; 6: List<Integer> row = null; 7: for (int i=0; i<a.size(); i++) { 8: row = a.get(i); 9: for (int j=0; j< row.size(); j++) { 10: if (j==0) { 11: c0 = 0; 12: } else { 13: c0 = c1; 14: } 15: if (j<i) { 16: } 17: } 18: } 19: } 20: public void traverse(List<List<Integer>> a, int depth, int i, int sum, Integer ret) { 21: List<Integer> row = a.get(depth); 22: s...

這題很簡單, 題目要求給n個階梯, 若每次僅走一步或兩步, 則走到第n階的路徑有多少種。 (思路) 1. 第 i-th 階 step[i] 儘可能從 step[i-1] 或 step[i-2] 出發. 2. 要留意 1st 跟 2rd 階的算法 1: public class Solution { 2: public int climbStairs(int n) { 3: if (n<=0) 4: return 0; 5: int[] steps = new int[n+1]; 6: steps[0] = 1; 7: steps[1] = 1; 8: for (int i=2;i<=n;i++) { 9: steps[i] = steps[i-1] + steps[i-2]; 10: } 11: return steps[n]; 12: } 13: }

個人覺得到目前這兩個網站的分類跟解題說明做得不錯，參考一下。 http://siddontang.gitbooks.io/leetcode-solution/content/array/find_minimum_in_rotated_sorted_array.html http://www.programcreek.com/2012/11/top-10-algorithms-for-coding-interview/

下面的方法都太爛了，目標只有一個：如何 worst case = O(n)下實作 selection sort 。 其實就是透過 medians and order statistics 的概念。 Order Statistics 就是假設在一個 unsorted array 下要找到 i-th order 的值。要找到 maximum or minimum 一般可在 O(n) 下找到，即使是 i-th 也可以先作 O(nlogn) 的排序後找到。但是否有比 O(nlogn)更快的方法？ => how can we modify quicksort to obtain expected-case $\theta(n)$  (hint)   pivot, partition, but recur only on one set of data. no join 複習一下 divide and conquer (這裡叫做 randomized_select) 1: def RANDOMIZED_SELECT(A, p, r, i): 2: if p == r: 3: return p 4: q = PARTITION(A, p, r) 5: k = q-p+1 6: if k == i: 7: return A[:i+1] 8: elif k < i: 9: return RANDOMIZED_SELECT(A, q+1, r, i-k) 10: else: 11: return RANDOMIZED_SELECT(A, p, q-1, i) 12: def PARTITION(A, p, r): 13: pivot = A[r] 14: i = p - 1 15: for j in range(p, r): 16: if A[j] <= pivot: 17: j+=1 18: swap(A, i,j) 19: swap(i+1, r) 20: return i+1  randomized_select 即便在一般時間是 O(n...

Title - #55 Jump Game Level - Medium Description - 題目主要是給一個字串 S = [1,2,3]，每個數字代表可行的距離，求能否到達最後一個字原。 (補充) Greedy 很明顯，也沒有什麼難度... 大概就是給個超級長的字串，但是若得到足夠的數字就可以直接結束程式，屬於O(n)。 作法 iteration (略) Title - #120 Triangle Level - Medium Description - 題目主要是給一個nested List = [[1],[2,3],[4,5,6]]，呈現triangle狀，每個數字代表cost。題目要求traverse從第一個List走到最後一個List，只能走adjacent elements，相是   1  2 3 4 5 6 只能走1-2-5 而非 1-2-6。 (補充) DP問題，主要是記住上次的COST，而且每次的選擇C(i)僅會參照先前min(prevC(i), prevC(i-1))加上C(i)得到total cost at i-th node。不過題目希望僅用一個O(N)的空間複雜度完成，所以多了兩個變數使用，加上須小心處理每個List的1st & last node即可。 作法 iteration 1: for (int i=0;i<S.size();i++) { 2: row <- S[i]; 3: for (int j=0;j<row.size();j++) { 4: if (j=0) c0=0; 5: else c0=c1; 6: if (j<i) c1 = last[j]; 7: if (j=0) min = c1; 8: else min = minimum(c0,c1); 9: last[j] = min + row[j]; 10: } 11: } Java 問題： 1. 在 java 除local variable似乎不需要初始化，所有物件的宣告的元素初始值為0。 From s...

Title - #34 Search for a range Level - Medium Description - 題目主要是給一個字串 S = [1,2,3]，一個目標數字，列出該數字所在的位置。 (補充) 解法很簡單，雖然要求O(logN)但其實用二分法就可以解決，然後記得一開始找數字時同時更新 left_search跟right_search的boundary。不過我在邊界值處理上花了不少時間... Orz 作法 iteration 1: //empty list 2: if (S.length = 0) 3: return new int[]{-1,-1}; 4: lbp = bp = 0, rep = ep = S.length; // bp = begin point, ep=end point 5: min = 0; 6: while (1){ 7: mid = (bp+ep)/2; 8: if (bp==mid) break; 9: if (S[mid] == target) 10: break; 11: else if (S[mid] < target) 12: lbp = bp = mid; 13: else 14: rep = ep = mid; 15: } 16: // target number is not existed. 17: if (S[mid] != target) 18: return new int[]{-1,-1}; 19: // update search boundary 20: rbp = lep = mid; 21: // left search 22: while (1){ 23: tmid = (lbp+lep)/2; 24: if (lbp==tmid) break; 25: if (S[tmid] < target) 26: lbp = tmid; 27: else 28: lep = tmid; 29...

Title - #39 Combination Sum Level - Medium Description - 題目主要是給一個字串 S = [1,2,3]，一個數字target，要列出所有字串相加等於target的子集合，字串可重複出現，集合為嚴格遞增。 (補充) 這裡又發生兩次WA。一次是若找不到時回傳[]而非[[]]；原先算法找無 [1,2], Target =4中 [2,2]的組合，原因是在backtracking時，s i < max(subset) 時我直接break 導致 '=’ 的條件無法觸發。但是為啥 [1,1,2] OK [2,2]卻不行？不是不行而是當 (si=1)<(max=2)時就直接中斷了。 另外，若S裡頭發生重複的字串的情況下可能需要移除，只是拿到RA就不打算處理了。 這題跟昨天subset 的做法很像。 作法 (iteration) 1: Heapify(S, i, len) { 2: left = i*2, right = left+1; 3: max = i; 4: if (leftlen and S[max] < S[left]) max=left; 5: if (rightlen and S[max] < S[right]) max=right; 6: if (i<max) { 7: Swap(A, i, max); 8: Heapify(A, max, len); 9: } 10: } 11: HeapSort(S) { 12: for (int i=S.length/2;i>=0; i--) { 13: Heapify(S, i, S.length); 14: } 15: for (int i=S.length;i>=1;i--) { 16: Swap(S, 0, i-1); 17: Heapify(S, 0, i-1); 18: } 19: } 20: //step-1, O(n) 21: isAscending = True; 22: for (int i =1...

Title - #78 SubSets Level - Medium Description - 題目主要是給一個字串 S = [1,2,3]，列出所有非遞減的子集合。 (補充) 這裡犯了兩個錯誤：它指的 non-decreasing 是嚴格遞增的意思。例如 [1,3,2,4] 不是嚴格遞增。 第二，若要列出僅"非遞減"的所有數列不太可能，因為所有組合是2 N 個。 作法(一) 遞迴 1: Play(nil, S, ret); 2: Play(set, subset, ret) { 3: if (subset == nil) { 4: ret.add([]); 5: return; 6: } 7: for ( s in subset ){ 8: if (set==nil || s>max(set)) { 9: ret.add({set+s}); 10: Play({set + s}, {subset-s}, ret); 11: } 12: } 作法(二) iteration 1: subset<-nil; 2: for (s in S) { 3: s.add({s}); 4: } 5: while (1) { 6: if (subset == nil) { 7: ret.add([]); 8: break; 9: } 10: ss <- subset.pop(0); 11: ret.add(ss); 12: for (s in {S-ss}) { 13: if (s > max(ss)) 14: subset.add({ss, s}); 15: } 16: } time complexity: O(n 2 ) 另外，由於我是使用 java, 遇到了兩個問題 網，路上暫時沒有較generic的作法。 (1) int[] 轉 List 的問題。 tmp = new A...