[LeetCode] String to Integer (atoi)

思路: 先處理 prefix, 分別判斷合法字元 +, -, 後面再處理數字部分, 以 double 暫存判斷是否會 overflow or underflow

class Solution {

public:

    int isValidChar(char c) {

        if (c >= '0' && c <= '9')

            return 1;

        else

            return 0;

    }

    

    int myAtoi(string str) {

        double testVal = 0.0;

        int absVal = 0;

        int sign = 1;

        

        int i = 0;

        // prefix

        for (i = 0; i < str.length(); i++) {

            // whitespace

            if (str[i] == ' ')

                continue;

            else if (str[i] == '+' || str[i] == '-') {

                if (str[i] == '-') sign = -1;

                i++;

                break;

            } else if (isValidChar(str[i])) {

                break;

            } else {    // illegal prefix

                return 0;

            }

        }

        for (; i< str.length(); i++) {

            if (isValidChar(str[i])) {

                testVal = 10.0 * absVal + (str[i] - '0');

                if (sign * testVal >= INT_MAX) {

                    return INT_MAX;

                } else if (sign * testVal <= INT_MIN) {

                    return INT_MIN;

                } else {

                    absVal = (int) testVal;

                }

            } else {

                break;

            }

        }

        return sign * absVal;

    }

};

[LeetCode] 118. Pascal's Triangle

• Problem: 118 Pascals's Triangle, 主要為該層元素為上一層的左邊加上一層右邊而得
• Concept:
• 算是滿基本的題目, 稍微將 index 列出來, 可以發現

• A[i][j] = A[i-1][j-1] + A[i-1][j]

• 但還是需要注意 index 從 0開始, 必須習慣一下
• Implementation

• class Solution {
  public:
      vector> generate(int numRows) {
          vector> result;
  
          for (int i = 0; i < numRows; i++) {
              vector row;
              
              row.push_back(1);
              for (int j = 1; j < i; j++) {
                  int val = result[i - 1] [j - 1] + result[i - 1][j];
                  row.push_back(val);
              }
              // no need to add right 1 at first row
              if (i > 0) row.push_back(1);
              
              result.push_back(row);
          }
          return result;
      }
  };
  

[LeetCode] 139. Word Break

• Problem: Word Break
• Concept:
• 可以 recursive 的將一個 word 拆成左半跟右半
• 利用 memorize 的 hash table 來記錄
• 注意終止條件:
• cache 已存在
• 目前的 dictionary 包含完整的 string
• Implementation

• class Solution {
  public:
      bool wordBreak(string s, vector& wordDict) 
      {
          unordered_set quickHash(wordDict.begin(), wordDict.end());
          return wordBreak(s, quickHash);
      }
      
      bool wordBreak(string s, unordered_set quickHash) 
      {
          if (m_mem.count(s)) return m_mem[s];
          if (quickHash.count(s) > 0) {
              m_mem[s] = true;
              return m_mem[s];
          }
  
          for (int i = 1; i < s.length(); i++) {
              if (quickHash.count(s.substr(0, i)) && wordBreak(s.substr(i), quickHash)) {
                  m_mem[s] = true;
                  return m_mem[s];
              }
          }
  
          m_mem[s] = false;
          return m_mem[s];
      }
  
  private:
      unordered_map m_mem;
  };
  

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

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

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

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