[LeetCode] 50 power (x, n)

• Problem: power (x, n), x為正整數
• Solution:
• 一種是 iteratively 的用 while loop, count down n 的值, 每次乘上 x
• 另一種直覺的是用 recursive, 但注意指數可以用平方來加速, 即 x^2 = x * x
• Note: 注意各 boundary, e.g. n < 0, n = MIN_INT 及 unsigned/signed 切換等 case

class Solution {
public:
    double myPow(double x, int n) {
        if (0 == n) return 1;
        if (1 == n) return x;

        double sq = myPow(x, n/2);
        if (INT_MIN == n)
            return sq * sq;
        if (0 > n) return 1.0 / myPow(x, abs((unsigned int)-n));

        if (0 == n % 2)
            return sq * sq;
        else
            return x * sq * sq;
    }
};

[LeetCode] 23. merge k sorted lists

• Problems: merge k 個 sorted 的 lists
• Solution:
• 延續 21 merge two lists, iteratively 將 k 個中的 lists 兩兩 merge 即可

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeLists(ListNode *l1, ListNode *l2)
    {
        // ref to problem 22, merge two sorted list
        if (NULL == l1) return l2;
        if (NULL == l2) return l1;
        
        if (l1->val < l2->val) {
            l1->next = mergeLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeLists(l1, l2->next);
            return l2;
        }
    }

    ListNode* mergeKLists(vector& lists) {
        // merge 2 by 2 lists
        size_t iters = lists.size() / 2;
        while (iters > 0) {
            iters = lists.size() / 2;
            for (size_t i = 0; i < iters; i++){
                lists[i] = mergeLists(lists[i], lists[lists.size() - 1 - i]);
            }

            lists.erase(lists.begin() + iters + (1 == lists.size() % 2), lists.end());
        }
        return (lists.size() > 0) ? lists[0] : NULL;
    }
};

[LeetCode] 21 Merge Two Sorted Lists

• Problem: merge 兩個已排序的 lists
• Solution: 
• 可以直接 iteratively 比較兩個 list 元素, 一個一個 push
• recursive
• 終止條件: list0 或 list1已到結尾, 則 return 另一個 list
• 當前判斷:
• 將最小元素的 next 指向 recursive return 回來的 list
• Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (NULL == l1) return l2;
        if (NULL == l2) return l1;
        
        if (l1->val < l2->val) 
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
            
    }
};

[LeetCode] 22. generate parentheses

• Problem: 給定括號個數, 產生合法的括號排列組合
• Solution:
• 以 recursive 方式來解決
• 當下考慮的是, 還要加入幾個左括號及幾個右括號
• 終止條件: 左右括號都加完了
• 當前條件: 左括號沒有限制, 右括號則需有對應的左括號先加入了才行
• Note: 注意邊際條件 leftCount > 0
• Code

class Solution {
public:
    // recursive solve this problem
    static void genParenthesis(vector &result, string s, int leftCount, int rightCount) {
        // when append done, add string to vector
        if (0 == leftCount && 0 == rightCount)
            result.push_back(s);

        // no matter where position, if leftCount > 0, you can add it
        if (leftCount > 0) 
            genParenthesis(result, s + "(", leftCount - 1, rightCount); 

        // you can append right parenthesis only when rightCount > leftCount
        if (leftCount < rightCount)
            genParenthesis(result, s + ")", leftCount, rightCount - 1);
    }
    
    vector generateParenthesis(int n) {
        vector result;
        genParenthesis(result, "", n, n);
        return result;
    }
};

[LeetCode] 20. Valid Parentheses

• 題目: Valid Parentheses 判斷字串是否為合理的左右括號
• 作法: 實作 First in last out 的 stack, 遇到左括號做 push, 右括號 pop, 若不是對應的括號或是沒有 pop 完, 則不是 valid 

class Solution {
public:
    bool isValid(string s) {
        vector bracketVec;
        for (size_t i = 0; i < s.length(); i++){
            if (s[i] == ')' || s[i] == ']' || s[i] == '}' )
            {
                if (bracketVec.empty())
                    return false;
                else if ( (s[i] == ')' && bracketVec.back() == '(')
                        || (s[i] == ']' && bracketVec.back() == '[')
                        || (s[i] == '}' && bracketVec.back() == '{'))
                    bracketVec.pop_back();
                else
                    return false;
            }
            else if (s[i] == '(' || s[i] == '[' || s[i] == '{')
            {
                bracketVec.push_back(s[i]);
            }
        }

        return bracketVec.empty();
    }
};

[LeetCode] 57. Insert Interval

• Problem:
• 將一個新的 interval 插入到已排序且不 overlapped 的 interval list 中, 必要時進行 merge
• Solution: 
• 先將 newInterval 依據 start 放到 interval list中
• 檢查 interval 是否需要 merge

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */

static bool isIntersec(const Interval &a, const Interval &b)
{
    return max(a.start, b.start) <= min(a.end, b.end);
}

static Interval mergeInterval(const Interval &a, const Interval &b)
{
    return (isIntersec(a, b))? Interval(min(a.start, b.start), max(a.end, b.end)) : Interval(0, 0);
}

class Solution {
public:
    vector insert(vector& intervals, Interval newInterval) {
        vector result;
        // step 1. directly add newInterval into intervals first
        vector::iterator it;
        for (it = intervals.begin(); it < intervals.end(); it++)
        {
            if (newInterval.start < it->start)
            {
                break;
            }
        }
        intervals.insert(it, newInterval);

        // step 2. merge nearby intervals if necessary
        for (size_t i = 0; i < intervals.size(); i++){
            Interval merged(intervals[i].start, intervals[i].end);
            while (i+1 < intervals.size() && isIntersec(merged, intervals[i+1]))
            {
                merged.end = max(merged.end, intervals[i+1].end);
                i++;
            }
            result.push_back(merged);
        }
        
        return result;
    }
};

[Mac] 硬體重設與診斷

• 重開機後, 純白開機畫面按

• D: 硬體診斷 => 個人是在 Macbook上聞到燒焦味時做的

• command + option + P + R => 我是在重裝 SSD 後需要hardware重新偵測

• Reference
• 如何使用 Mac 上的 Apple Hardware Test
• 重置電腦的 NVRAM or PRAM

[Python] setup Python environment in Mac OSX

• Environment setup
• install Python (via MacPorts)

sudo port install python

• version selection (e.g version: 3.6 or 2.7)
• check installed version by

port installed | grep python

sudo port select --set python python36 (or python27)

Success message: "Selecting 'python36' for 'python' succeeded. 'python36' is now active."

• install pip & select version (python package manager)

sudo port install py36-pip (or py27-pip)
port select --set pip pip36

• Reference
• installing and setting PIP with MacPorts
• macports installation

[Programming] Recursive

• Programming problems 中重要的一個分類就是 recursive
• e.g. 著名的 n 階算法
int factorial(int n) { if (1 == n) return 1; if (0 == n) return 1; return n * factorial(n-1); }
• 但更重要的是應該要考慮 recursive 的限制
• stack overflow
• 解法: 
• tail recursive
• 連結內的解釋相當清楚, 主要是透過寫法不同, 讓 compiler 在 O2, O3的 optimization時, 不用 call function, 而是 jne (jump not equal)

• int factorial_acc(int n, int acc = 1) 
  {    
      if (n == 1) 
          return acc;
      else
          return factorial_acc(n - 1, n * acc);
  }
  

• iterative

• int factorial_iterative(int n)
  {
      int acc = 1;
      if (n <= 1) return acc;
      while (n > 1)
      {
          acc *= n;
          n--;
      }
      return sum;
  }

• 延伸閱讀
• Iterative vs. Recursive
• Stack size
• stack vs heap

[Child] 相片書比較

• 從網路上的資訊, 大概先整理如下表格, 等實際印了, 再來分享

• 品牌	價格	相片用紙	相片印刷	裝訂	軟體操作/樣板
  健豪	便宜			蝴蝶本
  點點印	貴		較亮/色彩較鮮艷
  Li Book	貴

Referece:

• [開箱] 線上相片書評比：健豪蝴蝶本、點點印膠裝寫真本、印簿玩雜誌本
• [攝影] Libook(啦book) + 點點印 + 健豪Photo book 送印心得