All about life: 10月 2018

2018年10月31日星期三

[LeetCode] 54. Spiral Matrix

Problem: Spiral Matrix, 用 vector 給定一個二維陣列, 順時針螺旋的方式, 將所有元素 traverse 一次
Concept: 注意邊界的處理, 轉彎的動作包含了

超過邊界: 判斷是否超過 minX, maxX 及 Y 方向的邊界
返回界內
轉彎: 可以用 enum 來寫 direction
更新邊界: e.g. 往下走, 則上界 minY += 1

Implementation:

class Solution {
public:
    enum E_DIRECTION {
        E_DIR_RIGHT = 0,
        E_DIR_DOWN,
        E_DIR_LEFT,
        E_DIR_UP,
        E_DIR_ALL
    };
    
    enum E_TOWARD {
        E_FORWARD = 0,
        E_BACKWARD,
        E_TOWARDS
    };
    
    void step (E_DIRECTION dir, E_TOWARD to, int &x, int &y) {
        int step = (E_FORWARD == to) ? 1 : -1;
        switch (dir) {
            case E_DIR_RIGHT:
                x += step;
                break;
            case E_DIR_DOWN:
                y += step;
                break;
            case E_DIR_LEFT:
                x -= step;
                break;
            case E_DIR_UP:
                y -= step;
                break;
        }
    }
    
    void turn (E_DIRECTION &dir, int &minX, int &maxX, int &minY, int &maxY) {
        int nextDir = (1 + dir) % E_DIR_ALL;
        dir = (E_DIRECTION) nextDir;
        switch (dir) {
            case E_DIR_DOWN:
                minY += 1;
                break;
            case E_DIR_LEFT:
                maxX -= 1;
                break;
            case E_DIR_UP:
                maxY -= 1;
                break;
            case E_DIR_RIGHT:
                minX += 1;
                break;
        }
    }
    
    vector spiralOrder(vector>& matrix) {
        vector result;
        if (matrix.empty()) return result;
        
        int height = matrix.size();
        int width = matrix[0].size();  // check matrix.empty before
        int x = 0, y = 0;   // current traverse coordinate
        int minX = 0, maxX = width - 1, minY = 0, maxY = height - 1;
        E_DIRECTION eDir = E_DIR_RIGHT;     
        
        // termination condition
        while (minX <= maxX && minY <= maxY) {
            // change direction condition
            if (x < minX || x > maxX || y < minY || y > maxY) {
                step (eDir, E_BACKWARD, x, y);
                turn (eDir, minX, maxX, minY, maxY);
                step (eDir, E_FORWARD, x, y);
            } else {
                // index starts from 1
                result.push_back(matrix[y][x]);
                step (eDir, E_FORWARD, x, y);
            }
        }
        return result;
    }
};

[LeetCode] 42. Trapping Rain Water

Problem: Trapping Rain Water, 利用 histogram 的圖形, 統計可以接的雨水量
Concept:

第 i 個 bin 能接的水量, 被左右高度所決定 (取其小的)
而左右的高度, 相當於持續統計的結果

leftMaxHeight (i) = max { leftMaxHeight[i-1], height [i-1] }

同理, rightMaxHeight 也是, 只是要由右往左統計

Implementation:

class Solution {
public:
    int trap(vector& height) {
        int result = 0;
        if (height.size() < 2) return result;
        vector leftMaxHeight;
        vector rightMaxHeight(height.size(), 0);
        
        leftMaxHeight.push_back(0);
        for (int i = 1; i < height.size(); i++) {                
            leftMaxHeight.push_back(max(leftMaxHeight[i-1], height[i-1]));
        }
        
        for (int i = height.size() - 2; i >= 0; i--) {
            rightMaxHeight[i] = max(rightMaxHeight[i+1], height[i+1]);
        }
        
        for (int i = 0; i < height.size(); i++) {
            int h = min (leftMaxHeight[i], rightMaxHeight[i]) - height[i];
            if (h > 0) result += h;
        }
        return result;
    }
};

[LeetCode] 66. Plus One

Problem: use vector to express digits, plus one to calculate result
Concept: 算是簡單考 carry 的概念, mod 等基本運算
Implementation:

class Solution {
public:
    vector plusOne(vector& digits) {
        vector result(digits);
        if (digits.size() == 0) return result;

        int carry = 1;  // init as plus one
        for (vector::iterator iter = digits.end() - 1; iter >= digits.begin(); iter--)        
        {
            int prevCarry = carry;
            carry = (*iter + carry) / 10; 
            *iter = (*iter + prevCarry) % 10; 
            if (0 == carry)
                break;
        }   
        if (1 == carry) digits.insert(digits.begin(), 1); 
        return digits;
    }
};

2018年10月25日星期四

[LeetCode] 681. Next Closet Time

Problem: 681. Next Closet Time 下個最接近的時間
Limitation: 只能用原本時間的 digits, 可以重複
Concept:

string/char/time 操作
可以直接暴力的使用累加來比對是否符合條件, 因為最大值僅 60 * 24 (=1440)
Note: includes 的 parameter 僅能用以排序的 container, e.g. set

class Solution {
public:
    string nextClosestTime(string time) {
        string nextTime = time;
        
        // brute force to incremental check
        set setTimeChar(time.begin(), time.end());

        int hours = stoi(time.substr(0, 2));
        int mins = stoi(time.substr(3, 2));

        const int MAX_NEXT_TIME = 60 * 24;
        
        for (int i = 0; i < MAX_NEXT_TIME; i++) {
            if(++mins >= 60) {
                mins -= 60;
                ++hours;
                if (hours >= 24)
                    hours -= 24;
            };
            
            const int TIME_LEN = 5;
            char buf[TIME_LEN];
            sprintf(buf, "%02d:%02d", hours, mins);
            set setNextTimeChar(buf, buf + TIME_LEN);
            if (includes(setTimeChar.begin(), setTimeChar.end(), setNextTimeChar.begin(), setNextTimeChar.end()))
                return string(buf);
        }
        return time;
    }
};

[LeetCode] 200. Number of Islands

Problem: Number of Islands, 僅上下左右 (不包含對角線) 相鄰的 components (islands) 個數
Limitation:
Note:

注意 data type, namely, char 的 '0', hex 為 30, 不要拿來與 0 做比較
注意邊界條件, width, height 判斷依據為 >=, 若判斷條件有誤會跑不完

Concept:

nIslands 計數後, 運用 DFS將相鄰的全設為 '0'

Implementation:

class Solution {
public:
    void dfs(int i, int j, size_t width, size_t height, vector> &grid) {
        if (i < 0 || j < 0 || i >= width || j >= height || grid[i][j] == '0')
            return;

        grid[i][j] = '0';

        dfs(i    , j - 1, width, height, grid);
        dfs(i    , j + 1, width, height, grid);
        dfs(i - 1, j    , width, height, grid);
        dfs(i + 1, j    , width, height, grid);
    }
    
    int numIslands(vector>& grid) {
        int nIslands = 0;
        if(grid.empty()) return 0;

        const size_t width = grid.size();
        const size_t height = grid[0].size();
        
        for (size_t i = 0; i < width; i++) {
            assert (height == grid[i].size());
            for (size_t j = 0; j < height; j++) {
                if (grid[i][j] - '0') {
                    nIslands++;
                    dfs(i, j, width, height, grid);
                }
            }
        }
        
        return nIslands;
    }
};

[LeetCode] 146. LRU Cache

Problem: 實作 LRU Cache data structure and get/put operations
Limitation: O(1) time complexity
Note:

get 與 put 都包含了 find 的 operation, 若需要 O(1), 則需要 hash table (unordered_map)
insert 與 pop: 若 insert (push), pop 都是 push / pop back的話, linked list 或是 vector container 都可以達到 O(1) 的 complexity
move: 但 LRU 包含了將最近使用的 entry 移動到 begin, 這只有 linked list 能達成
要明確了解 get/put 的動作, e.g. put 若是 put 同樣 key, 不同 value, 則 value 應更新

Concept:

較無演算發的要求, 畢竟 LRU 本身就是演算法的概念
相當於在考 data structure design, 可知要實作 hash table 找 entry (key 做 hash, value 為 pointer to cache entry), 並用 linked list 來maintain cache entries (key, value) 的 pair

Implementation:

class LRUCache {
public:
    LRUCache(int capacity) {
        m_capacity = capacity;
    }   
    
    int get(int key) {
        unordered_map >::iterator>::iterator it = m_hash.find(key);
        if (it != m_hash.cend())
        {   
            // move cache
            m_cache.splice(m_cache.begin(), m_cache, it->second);
            it->second = m_cache.begin();
            return it->second->second;
        }   
        else
            return -1; 
    }   
    
    void put(int key, int value) {
        // 1. find if it alread exists, if yes, move to begin, else insert it
        unordered_map >::iterator>::iterator it = m_hash.find(key);
        if (it != m_hash.cend()) {
            // move cache
            m_cache.splice(m_cache.begin(), m_cache, it->second);
            it->second = m_cache.begin();
            // Note: this value may differ from original one, we need to update value
            it->second->second = value;
        } else {
            // check if size reaches capacity
            if (m_cache.size() >= m_capacity) {
                // a. remove cache entry
                it = m_hash.find(m_cache.back().first);
                //cout << "m_cache.back().first: " << m_cache.back().first << endl;
                m_hash.erase(it);
                // b. remove LRU
                m_cache.pop_back();
            }
            m_cache.emplace(m_cache.begin(), make_pair(key, value));
            m_hash.insert(make_pair(key, m_cache.begin()));
        }
    }

private:
    // O(1) to move, insert, delete nodes, we need list data structure
    // for the given data, we need a pair to store both key & value
    list< pair > m_cache;

    // max cache size
    int m_capacity;

    // for O(1) to find, we need a hash table which we use map here
    unordered_map >::iterator> m_hash;
};

2018年10月19日星期五

[C++] header.h 與 cheader 的差異

簡單解釋

header.h 是 C++ 為了相容 C 保留的 header files
header.h 與 cheader 是 C 與 C++ 的對應, 但實際介面與實作上有些微差異

如 cmath 中, abs 是以 overload 方式實作與提供介面, 但 math.h 則是 implement 多種 type 的 functions, e.g. fabs

差異的地方是 cheader 將各 function 定義在 std的 namespace 下, 所以使用時要加 std:: 或是呼叫 using namespace std;

實際使用

建議以 C++ 的方式思考
```
include <cxxxx>
```
```
using namespace std::functionYouUsed
```

Reference:

2018年10月18日星期四

[C++] STL 中 list, vector 的差異

C++ library 中, 著名的幾個 container 包含了 list, vector, map, set (hash map/set supported in C++11 or C++03/TR1)

vector 是連續空間, 可以用 [] 作為 index來存取, 隨機存取速度快, 但插入 head 的速度慢, 若有 insert element 到 head, 且要求 complexity 要 O(1) 的話, 不能使用 vector
list 非連續, 即 linked list 的封裝, 對於隨機存取速度慢, 但插入動作相當快速

Ref: c++ list, vector, map, set 区别与用法比较

2018年10月17日星期三

[LeetCode] 830. position of large groups

Problem: position of large groups, 計算連續字母的開始與結束位置
Solution:

直接 iterate 整個字串
第一個字母直接紀錄, 最後一組 group 要特別處理

class Solution {
public:
    vector> collectLargeGroups(const char *str, int len) {
        char currCh;
        int length = 0, start = 0, end = 0;
        vector> result;
        const int LARGE_SIZE = 3;
        
        if (NULL == str) return result;
        currCh = str[0];
        length = 1;
        
        for(size_t i = 1; i < len; ++i)
        {
            if (currCh != str[i])
            {
                end = i - 1;
                length = end - start + 1;

                if (length >= LARGE_SIZE)
                {
                    vector group{start, end};
                    result.push_back(group);
                }
                start = i;
                currCh = str[i];
            }
        }
        
        // add last group
        end = len - 1;
        length = end - start + 1;
        if (length >= LARGE_SIZE)
        {
            vector group{start, end};
            result.push_back(group);
        }
        
        return result;
    }
    
    vector> largeGroupPositions(string S) {
        return collectLargeGroups(S.c_str(), S.length());
    }
};

[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;
    }
};

2018年10月15日星期一

[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();
    }
};

2018年10月13日星期六

[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;
    }
};

2018年10月3日星期三

[Mac] 硬體重設與診斷

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

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

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

Reference

訂閱：文章 (Atom)

網頁

2018年10月31日 星期三

2018年10月25日 星期四

2018年10月19日 星期五

2018年10月18日 星期四

2018年10月17日 星期三

2018年10月15日 星期一

2018年10月13日 星期六

2018年10月3日 星期三

2018年10月31日星期三

2018年10月25日星期四

2018年10月19日星期五

2018年10月18日星期四

2018年10月17日星期三

2018年10月15日星期一

2018年10月13日星期六

2018年10月3日星期三