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...

要顯示 java  Integer type 的 minimum and maximum 的方式 Integer.MAX_VALUE (2147483647)  及 Integer.MIN_VALUE (-2147483648) 若不用內建涵式, 直覺會用： 1<<31 -1<<31 可結果卻都是 -2147483648 這是由於 1<<31 已發生 overflowed, 在java中下一個位數則是 -1<<31 要得到正確的 MAX_VALUE 可用 (1<<31)-1 其實這是我在作 leetcode (Reverse Integer) 的考題遇到的問題. 該題目回傳值跟輸入值是 int, 但側資的輸出有可能是 overflowed 的情形! 真是太狡猾了。 http://goo.gl/7el8Kf