Leetcode - Word Ladder

 class Solution {  
 public:  
   int ladderLength(string start, string end, unordered_set<string> &dict) {  
     // BFS  
     queue<string> q;  
     q.push(start);  
     dict.erase(start);  
     int length = 1;  
     while(!q.empty()) {  
       queue<string> tempQ;  
       while(!q.empty()) {  
         string str(q.front());  
         q.pop();  
         set<string> ret(getOneEditedWord(str, dict));  
         for(string s : ret) {  
           if(s == end) {  
             return length + 1;  
           }  
           tempQ.push(s);  
         }  
       }  
       length++;  
       swap(q, tempQ);  
     }  
       return 0;  
     }  
   set<string> getOneEditedWord(string str, unordered_set<string> & dict) {  
     set<string> result;  
     for(int i = 0; i < str.length(); ++i) {  
       for(int j = 'a'; j <='z'; ++j) {  
         if(j == str[i]) {  
           continue;  
         }  
         char temp = str[i];  
         str[i] = j;  
         if(dict.count(str) > 0) {  
           result.insert(str);  
           dict.erase(str);  
         }  
         str[i] = temp;  
       }  
     }  
     return result;  
   }  
 };  

Heap and maintain the median

Here the classic approach to handle a heap is insert new element at the root and sift it down.

 #include <iostream>  
 #include <vector>  
 #include <algorithm>  
 #include <stdexcept>  
 #include <stdlib.h>  
 #include <memory>  
 #include <time.h>   
 #include <set>  
 using namespace std;  
 template <typename T>  
 class Heap {  
  vector<T> _heap;  
 public:  
  // never call a virtual function from constructor  
  void build(const vector<T>& nums) {  
   for(int i = 0; i < nums.size(); ++i) {  
    offer(nums[i]);  
   }  
  }  
  T peek() const {  
   if(!_heap.empty()) {  
    return _heap[0];  
   } else {  
    std::cerr << "heap is empty" << std::endl;  
   }  
  }  
  void offer(T val) { //insert  
   _heap.insert(_heap.begin(), val);  
   heapify();  
  }  
  T poll() { // delete  
   int val = _heap[0];  
   swap(0, _heap.size() - 1);  
   _heap.pop_back();  
   heapify();  
   return val;  
  }  
  void print() {  
   for_each(_heap.begin(), _heap.end(), [](T val) {  
     std::cout << val << ", ";  
    });  
   std::cout << std::endl;  
  }  
  int size() const {  
   return _heap.size();  
  }  
  virtual ~ Heap() {}  
 private:  
 
  void heapify() {  
   heapify(0);  
  }  
  void heapify(int i) {  
   //sift down  
   int l = left(i);  
   int r = right(i);  
   int largest = i;  
   if(l < _heap.size() && comp(_heap[l], _heap[largest])) {  
    largest = l;  
   }  
   if(r < _heap.size() && comp(_heap[r], _heap[largest])) {  
    largest = r;  
   }  
   if (largest != i) {    
    swap(largest, i);  
    heapify(largest);  
   }  
  }  
  inline void swap(int i, int j) {  
   if(i >= _heap.size() && j >= _heap.size()) {  
    throw std::runtime_error("Out of bound!");  
   }  
   int temp = _heap[i];  
   _heap[i] = _heap[j];  
   _heap[j] = temp;  
  }  
  inline int parent(int i) {  
   return i / 2;  
  }  
  inline int left(int i) {  
   return 2 * i;  
  }  
  inline int right(int i) {  
   return 2 * i + 1;  
  }  
  virtual bool comp(T val1, T val2) const = 0;  
 };  

 template<typename T>  
 class MaxHeap : public Heap<T> {  
 public:  
  virtual ~MaxHeap() {}  
 private:  
  virtual bool comp(T val1, T val2) const {  
   return val1 > val2;  
  }  
 };  
 template <typename T>  
 class MinHeap : public Heap<T> {  
 public:  
  virtual ~MinHeap() {}  
 private:  
  virtual bool comp(T val1, T val2) const {  
   return val1 < val2;  
  }  
 };  

 class StreamMediam {  
 private:  
  MinHeap<int> _minHeap;  
  MaxHeap<int> _maxHeap;  
  set<int> _record;  
 public:  
  StreamMediam() {  
   srand (time(NULL));    
  }  
  int genRandNum(int maxNum) {  
   return rand() % maxNum;  
  }  
  void accept(int maxNum = 100) {  
   int val = genRandNum(maxNum);  
   _record.insert(val);  
   if(_minHeap.size() == _maxHeap.size()) {  
    if(_minHeap.size() > 0 && val > _minHeap.peek()) {  
     _maxHeap.offer(_minHeap.poll());  
     _minHeap.offer(val);  
    } else {  
     _maxHeap.offer(val);  
    }  
   } else {  
    if(val < _maxHeap.peek()) {  
     _minHeap.offer(_maxHeap.poll());  
     _maxHeap.offer(val);  
    } else {  
     _minHeap.offer(val);  
    }  
   }  
  }  
  int getMedian() const {  
   if(_minHeap.size() == _maxHeap.size()) {  
    return (_minHeap.peek() + _maxHeap.peek() ) / 2;  
   } else {  
    return _maxHeap.peek();  
   }  
  }  
  void print() {  
    for_each(_record.begin(), _record.end(), [](int val) {  
      std::cout << val << ", ";  
     });  
     std::cout << std::endl;  
  }  
 };  

 int main(int argc, char *argv[])  
 {  
  vector<int> nums{4,1,3,2,16,9,10,14,8,7};  
  shared_ptr<Heap<int> > heap1(new MaxHeap<int>());  
  heap1->build(nums);  
  heap1->print();  
  shared_ptr<Heap<int> > heap2(new MinHeap<int>());  
  heap2->build(nums);  
  heap2->print();  
  StreamMediam sm;  
  for(int i = 0; i < 10; ++i) {  
   sm.accept();  
   sm.print();  
   std::cout <<  sm.getMedian() << std::endl;  
  }  
  return 0;  
 }  

Leetcode -- Merge Two Sorted Array

class Solution {  
 public:  
   void merge(int A[], int m, int B[], int n) {  
     while(m >= 1 && n >= 1) {  
       if(A[m - 1] > B[n - 1]) {  
         A[m + n - 1] = A[m - 1];  
         m--;  
       } else {  
         A[m + n - 1] = B[n - 1];  
         n--;  
       }  
     }  
     while(n>=1) {  
       A[n - 1] = B[n - 1];  
       n--;  
     }  
   }  
 };  

Leetcode -- LRU Cache

class LRUCache{  
 public:  
   list<vector<int> > _list;  
   unordered_map<int, list<vector<int> >::iterator> _hash;  
   int _capacity;  
   LRUCache(int capacity): _capacity(capacity) {  
   }  
   int get(int key) {  
    if(_hash.count(key) > 0) {  
      auto it = _hash[key];  
      vector<int> temp(*it);  
      _list.erase(it);  
      _list.push_front(temp);  
      _hash[key] = _list.begin();  
      return temp[1];  
    } else {  
      return -1;  
    }  
   }  
   void set(int key, int value) {  
     if(_hash.count(key) > 0) {  
       auto it = _hash[key];  
       _list.erase(it);  
       _list.push_front(vector<int>{key, value});  
       _hash[key] = _list.begin();  
     } else {  
       if(_hash.size() >= _capacity) {  
         vector<int> temp(_list.back());  
         _list.pop_back();  
         _hash.erase(temp[0]);  
       }  
       vector<int> newElement{key, value};  
       _list.push_front(newElement);  
       _hash.emplace(key, _list.begin());  
     }  
   }  
 };  

Unique Path

 class Solution {  
 public:  
   int uniquePaths(int m, int n) {  
     int dp[1000] = {-1};  
     dp[0] = 1;  
     for(int i = 0; i < m; ++i) {  
       for(int j = 1; j < n; ++j) {  
         dp[j] = dp[j] + dp[j - 1];  
       }  
     }   
     return dp[n - 1];  
   }  
 };  

Leetcode -- Minimum Window Substring

 #include <iostream>  
 #include <unordered_map>  
 #include <climits>  
 using namespace std;  
 class Solution {  
 public:  
  string minWindow(string S, string T) {  
   if(S.empty()) {  
    return "";  
   }  
   unordered_map<char, int> expectedToFind;  
   unordered_map<char, int> hasFound;  
   for(int i = 0; i < T.length(); ++i) {  
    expectedToFind[T[i]]++;  
   }  
   int minLength = INT_MAX;  
   int minStart = 0;  
   int minEnd = 0;  
   int count = 0;  
   for(int start = 0, end = 0; end < S.length(); end++) {  
    if(expectedToFind[S[end]] > 0) {  
     hasFound[S[end]]++;  
    }  
    if(expectedToFind[S[end]] > 0 && hasFound[S[end]] <= expectedToFind[S[end]]) {  
     count++;  
    }  
    if(count == T.length()) {  
     while(expectedToFind[S[start]] == 0 || hasFound[S[start]] > expectedToFind[S[start]]) {  
      if(hasFound[S[start]] > expectedToFind[S[start]] ) {  
       hasFound[S[start]]--;  
      }  
      start++;  
     }  
     int wLen = end - start + 1;  
     if(wLen < minLength) {  
      minLength = wLen;  
      minStart = start;  
      minEnd = end;  
     }  
    }  
   }  
   return count == T.length() ? S.substr(minStart, minEnd - minStart + 1): "";  
  }  
 };  
 int main(int argc, char *argv[])  
 {  
  Solution s;  
  std::cout << s.minWindow("a", "a") << std::endl;  
  return 0;  
 }  

Leetcode -- Word Break II

TLE because I didn't use dynamic programming

 class Solution {  
 public:  
   vector<string> wordBreak(string s, unordered_set<string> &dict) {  
    vector<string> breaks;  
     string output;  
     wordBreakHelper(s, 0, dict, output, breaks);  
     return breaks;  
   }  
   void wordBreakHelper(string s, int start, unordered_set<string>& dict, string& output, vector<string>& breaks) {  
     if(start >= s.length()) {  
       breaks.emplace_back(output.substr(1));  
       return;  
     }  
     for(int i = start; i < s.length(); ++i) {  
       string sub(s.substr(start, i - start + 1));  
       if(dict.count(sub) > 0) {  
         output +=" " + sub;  
         wordBreakHelper(s, i + 1, dict, output, breaks);  
         output = output.substr(0, output.length() - 1-sub.length());  
       }  
     }  
   }  
 };  

Cut some branches

 class Solution {  
 public:  
   vector<string> wordBreak(string s, unordered_set<string> &dict) {  
    vector<string> breaks;  
     string output;  
     vector<bool> possible(s.length() + 1, true);  
     wordBreakHelper(s, 0, dict, output, breaks, possible);  
     return breaks;  
   }  
   void wordBreakHelper(string s, int start, unordered_set<string>& dict, string& output, vector<string>& breaks, vector<bool>& possible) {  
     if(start >= s.length()) {  
       breaks.emplace_back(output.substr(1));  
       return;  
     }  
     for(int i = start; i < s.length(); ++i) {  
       string sub(s.substr(start, i - start + 1));  
       if(dict.count(sub) > 0 && possible[i + 1]) {  
         output +=" " + sub;  
         int beforeTheChange = breaks.size();  
         wordBreakHelper(s, i + 1, dict, output, breaks, possible);  
         if(beforeTheChange == breaks.size()) {  
           possible[i + 1] = false;  
         }  
         output = output.substr(0, output.length() - 1-sub.length());  
       }  
     }  
   }  
 };