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

[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: 
• Should I include xxxx.h or cxxxx in C++ programs?
• Math interface vs cmath in C++

[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 区别与用法比较 

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