211 Add and Search Word - Data structure design

Smart Pointer C++

来源：Bloomberg Phone Interview

原帖：http://www.hawstein.com/posts/13.9.html

题目：
Write a smart pointer (smart_ptr) class.

代码：

 #include <iostream>  
 #include <cstdlib>  
 using namespace std;  
   
 template <typename T>  
 class SmartPointer{  
 public:  
   SmartPointer(T* ptr){  
     ref = ptr;  
     ref_count = (unsigned*)malloc(sizeof(unsigned));  
     *ref_count = 1;  
   }  
     
   SmartPointer(SmartPointer<T> &sptr){  
     ref = sptr.ref;  
     ref_count = sptr.ref_count;  
     ++*ref_count;  
   }  
     
   SmartPointer<T>& operator=(SmartPointer<T> &sptr){  
     if (this != &sptr) {  
       if (--*ref_count == 0){  
         clear();  
         cout<<"operator= clear"<<endl;  
       }  
         
       ref = sptr.ref;  
       ref_count = sptr.ref_count;  
       ++*ref_count;  
     }  
     return *this;  
   }  
     
   ~SmartPointer(){  
     if (--*ref_count == 0){  
       clear();  
       cout<<"destructor clear"<<endl;  
     }  
   }  
     
   T getValue() { return *ref; }  
     
 private:  
   void clear(){  
     delete ref;  
     free(ref_count);  
     ref = NULL; // 避免它成为迷途指针  
     ref_count = NULL;  
   }  
     
 protected:    
   T *ref;  
   unsigned *ref_count;  
 };  
   
 int main(){  
   int *ip1 = new int();  
   *ip1 = 11111;  
   int *ip2 = new int();  
   *ip2 = 22222;  
   SmartPointer<int> sp1(ip1), sp2(ip2);  
   SmartPointer<int> spa = sp1;  
   sp2 = spa; // 注释掉它将得到不同输出  
   return 0;  
 }  

217 Contains Duplicate

来源：Leetcode

原帖：https://leetcode.com/problems/contains-duplicate/

题目：
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

代码：

 class Solution {  
 public:  
   bool containsDuplicate(vector<int>& nums) {  
     unordered_set<int> _set;  
     for (auto i : nums) {  
       if (_set.count(i)) return true;  
       _set.insert(i);  
     }  
     return false;  
   }  
 };  

约瑟夫环问题

来源：Bloomberg Onsite

原帖：http://blog.csdn.net/wuzhekai1985/article/details/6628491

题目：
最近看bloomberg的面经看到出现过几次约瑟夫环问题。这道题的模拟解法非常直观，更好的解法是观察索引的映射关系采用recursion来解。以前没有仔细思考过这个问题。博客链接给了很好的解释。

约瑟夫环问题的原来描述为，设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。  稍微简化一下。

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

代码：
1] Brute force solution

 int JosephusProblem(int n, int m) {   
   if (n < 1 || m < 1)   
     return -1;   
    
   list<int> listInt;   
   unsigned i;   
   //初始化链表   
   for (i = 0; i < n; i++)   
     listInt.push_back(i);    
   list<int>::iterator iterCurrent = listInt.begin();   
   while (listInt.size() > 1) {   
     //前进m - 1步   
     for(i = 0; i < m-1; i++) {   
       if(++iterCurrent == listInt.end())   
         iterCurrent = listInt.begin();   
     }   
     //临时保存删除的结点   
     list<int>::iterator iterDel = iterCurrent;   
     if(++iterCurrent == listInt.end())   
       iterCurrent = listInt.begin();   
     //删除结点   
     listInt.erase(iterDel);   
   }  
   return *iterCurrent;   
 }  

2] dp solution

 int JosephusProblem(int n, int m) {   
   if(n < 1 || m < 1)   
     return -1;   
   vector<int> f(n+1,0);   
   for(unsigned i = 2; i <= n; i++)   
     f[i] = (f[i-1] + m) % i;    
   return f[n];   
 }  

160 Intersection of Two Linked Lists

来源：Leetcode

原帖：https://leetcode.com/problems/intersection-of-two-linked-lists/

题目：
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
 A:          a1 → a2
                    ↘
                      c1 → c2 → c3
                    ↗          
 B:     b1 → b2 → b3
begin to intersect at node c1.

Notes:
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

代码：

 class Solution {  
 public:  
   ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {  
     ListNode *p1 = headA, *p2 = headB;  
     if (!p1 || !p2) return NULL;  
     while (p1 && p2 && p1 != p2) {  
       p1 = p1->next;  
       p2 = p2->next;  
       if (p1 == p2) return p1;  
       if (!p1) p1 = headB;  
       if (!p2) p2 = headA;  
     }  
     return p1;  
   }  
 };  

Ugly Numbers

来源：cc150, fgdsb

原帖：http://www.hawstein.com/posts/ctci-ch10-math.html
            http://www.fgdsb.com/2015/01/03/ugly-numbers/

题目：
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
shows the first 11 ugly numbers. By convention, 1 is included.

Write a program to find and print the 150’th ugly number.

cc150上也有相类似的题目，不过prime factors是3,5,7。

代码：

 int uglyNumber(int n) {  
   vector<int> num(n+1);  
   num[0] = 1;  
   int i3 = 0, i5 = 0, i7 = 0;  
   for (int i = 1; i <= n; ++i) {  
     int next = min({num[i3]*3, num[i5]*5, num[i7]*7});  
     num[i] = next;  
     if (next == num[i3]*3) i3++;  
     else if (next == num[i5]*5) i5++;  
     else i7++;  
   }  
   return num[n];  
 }  
   
 int main() {  
   vector<int> ugly = {1,3,5,7,9,15,21,25,27,35,45,49,63};  
   int k = 5;  
   cout << uglyNumber(k) << endl;  
   return 0;  
 }  

Singleton

来源：Lintcode

原帖：http://www.lintcode.com/en/problem/singleton/

题目：
Singleton is a most widely used design pattern. If a class has and only has one instance at every moment, we call this design as singleton. For example, for class Mouse (not a animal mouse), we should design it in singleton.
You job is to implement a getInstance method for given class, return the same instance of this class every time you call this method.

Have you met this question in a real interview? Yes
Example
In Java:
A a = A.getInstance();
A b = A.getInstance();
a should equal to b.

Challenge
If we call getInstance concurrently, can you make sure your code could run correctly?

代码：

 class Solution {  
 public:  
   /**  
    * @return: The same instance of this class every time  
    */  
   static Solution* getInstance() {  
     // write your code here  
     if (obj == NULL) {  
       obj = new Solution();  
     }  
     return obj;  
   }  
 private:  
   Solution() {}  
   static Solution* obj;  
 };  
 Solution* Solution::obj = NULL;  

Stock Real-time Update

来源：Google 

原帖：http://www.meetqun.com/thread-2227-1-1.html

题目：

假设有一个显示一个公司实时估价的网站，不断的会有最新价格进来（每个价格都会贴上一个timestamp，用于标识），要求提供几个方法查询highest price,和latest price。问如何实现。。。同时该系统支持add(timestamp, price)，和update(timestamp, price)。add()即添加新价格，update即根据timestamp来跟新以前的数据。
- 系统不用提供删除操作
- 假设add()进来的price的timestamp都是递增的，即timestamp没有重复。
- follow up，如果add()需求很大，update只是偶尔的操作，该怎么解决。

解答
我用的是max heap+hash来解决highest pric，用一个变量来解决latest price(因为不要求删除)。
follow up
之前的add()和update()操作都是O(logN)，follow up之后，不再维护heap，将add()降低为O(1)的操作，update()变为O(N)的操作。
这道题的关系在于及时更新heap和hash。

代码：


 #include <iostream>  
 #include <string>  
 #include <vector>  
 #include <algorithm>  
 #include <unordered_map>  
 using namespace std;  
 typedef pair<int,int> Pair;//<timestamp, price>  
 class Price {  
 public:  
   Price() { }  
   void Add(int timestamp, int price);  
   void Update(int timestamp, int price);  
   int GetHighest() const { return _data.front().second; };  
   int GetLatest() const { return _latest; };  
 private:  
   unordered_map<int, int> _hash; //key:timestamp, value:index in container.  
   vector<Pair> _data;  
   int _latest;  
 };  
 void Price::Add(int timestamp, int price) {  
   _data.push_back({timestamp, price});  
   int idx = _data.size()-1;  
   int parent = (idx-1)/2;  
   while (parent >= 0 && idx > 0){  
     if (price > _data[parent].second){  
       _hash[_data[parent].first] = idx;  
       swap(_data[parent], _data[idx]);  
       idx = parent;  
       parent = (idx-1)/2;  
     } else {  
       break;  
     }  
   }  
   _hash[timestamp] = idx;  
   _latest = price;  
   // for (auto i : _data) {  
   //   cout << i.first << " " << i.second << " " << _hash[i.first] << endl;  
   // }  
   // cout << endl;  
 }  
 void Price::Update(int timestamp, int price){  
   int idx = _hash[timestamp];  
   int old_price = _data[idx].second;    
   if (price > old_price) {  
     // move up  
     int parent = (idx-1)/2;  
     while (parent >= 0 && idx > 0) {  
       if (price > _data[parent].second) {  
         _hash[_data[parent].first] = idx;  
         swap(_data[idx], _data[parent]);  
         idx = parent;  
         parent = (idx-1)/2;  
       } else {  
         break;  
       }  
     }  
   } else {  
     // move down  
     int j = 2 * idx + 1;  
     if (j < _data.size()-1 && _data[j].second < _data[j+1].second) {  
       ++j;  
     }  
     while (j < _data.size()) {  
       if (price < _data[j].second) {  
         _hash[_data[j].first] = idx;  
         swap(_data[idx], _data[j]);  
         idx = j;  
         j = 2*idx + 1;  
         if (j < _data.size()-1 && _data[j].second < _data[j+1].second) {  
           ++j;  
         }  
       }  
     }  
   }  
   _hash[timestamp] = idx;  
 }  
 int main(){  
   Price P;  
   P.Add(10, 100);  
   P.Add(20, 200);  
   P.Add(30, 300);  
   P.Update(30, 50);  
   cout << P.GetHighest() << endl;  
   cout << P.GetLatest() << endl;  
   return 1;  
 }  

Implement Heap

来源：Bloomberg onsite

原帖：

题目：
Implement a heap structure.

代码：

 #include <vector>  
 #include <iostream>  
 using namespace std;  

 typedef int heap_element;
 /* 堆，默认为最小堆 */  
 int cmp_int(const heap_element& x, const heap_element& y) {  
      heap_element dif = x - y;  
      if (dif > 0) {  
           return 1;  
      } else if (dif < 0) {  
           return -1;  
      } else {  
           return 0;  
      }  
 }  
 typedef int (*compare)(const heap_element& x, const heap_element& y);  
 class heap {  
 public:  
      heap(compare _cmp) {  
           cmp = _cmp;  
      }  
      bool empty() const {  
           return element.size() == 0;   
      }  
      int size() const {  
           return element.size();  
      }  
      void push(const heap_element x) {  
           element.push_back(x);  
           heap_sift_up(element.size() - 1);  
      }  
      void pop() {  
           if (element.size() <= 0) {  
                cerr << "heap is out of space" << endl;  
           }  
           swap(element[0], element[element.size() - 1]);  
           element.pop_back();  
           if (element.size() == 0) {  
                return;  
           }  
           heap_sift_down(0);  
      }  
      heap_element top() const {  
           return element[0];  
      }  
 private:  
      void heap_sift_down(int start) {  
           int i = start, j = 2 * i + 1;  
           while (j < element.size()) {  
                if (j < element.size() - 1 && cmp(element[j], element[j+1]) > 0) {  
                     j++;  
                }  
                if (cmp(element[i], element[j]) < 0) {  
                     break;                      
                } else {  
                     swap(element[i], element[j]);  
                }  
                i = j;  
                j = 2 * i + 1;  
           }  
      }  
      void heap_sift_up(int start) {  
           int j = start, i = (j - 1) / 2;  
           while (j >= 0) {  
                if (cmp(element[i], element[j]) <= 0) {  
                     break;  
                } else {  
                     swap(element[i], element[j]);  
                }  
                j = i;  
                i = (j - 1) / 2;  
           }  
      }  
      vector<heap_element> element;  
      compare cmp;  
 };  
 int main() {  
      int myints[] = {10,20,30,5,15};  
       vector<int> v(myints,myints+sizeof(myints)/sizeof(int));  
       heap minheap(cmp_int);  
       for(int i = 0; i < v.size(); ++i) {  
            minheap.push(v[i]);  
       }  
       cout << minheap.top() << endl;  
       // const vector<int>& elements = minheap.getElements();   
       // for (auto& i : elements) {  
       //      cout << i << " ";  
       // }  
       // cout << endl;  
 }  

Median In Stream

来源：CC150

原帖：http://www.fgdsb.com/2015/01/03/median-in-stream/#more
            http://www.hawstein.com/posts/20.9.html

题目：
Create the data structure for a component that will receive a series of numbers over the time and, when asked, returns the median of all received elements.

代码：

 class Online {  
 public:  
     void add_number(int n) {  
         if (max_heap.empty() || max_heap.top() > n) {  
             max_heap.push(n);  
             if (max_heap.size() - min_heap.size() > 1) {  
                 int m = max_heap.top();   
                 max_heap.pop();  
                 min_heap.push(m);  
             }  
         } else {  
             min_heap.push(n);  
             if (min_heap.size() > max_heap.size()) {  
                 int m = min_heap.top();  
                 min_heap.pop();  
                 max_heap.push(m);  
             }  
         }  
     }  
   
     int get_median() const {  
         int total = max_heap.size() + min_heap.size();  
         if (total % 2 == 0) {  
             return (max_heap.top() + min_heap.top()) / 2;  
         } else {  
             return max_heap.top();  
         }  
     }  
   
 private:  
     priority_queue<int,vector<int>,less<int>> max_heap;  
     priority_queue<int,vector<int>,great<int>> min_heap;      
 };  

Wildcard Matching

来源：Leetcode

原帖：https://oj.leetcode.com/problems/wildcard-matching/

题目：
 Implement wildcard pattern matching with support for '?' and '*'.
 '?' Matches any single character.
 '*' Matches any sequence of characters (including the empty sequence).
 The matching should cover the entire input string (not partial).
 The function prototype should be:
 bool isMatch(const char *s, const char *p)
 Some examples:
 isMatch("aa","a") ? false
 isMatch("aa","aa") ? true
 isMatch("aaa","aa") ? false
 isMatch("aa", "*") ? true
 isMatch("aa", "a*") ? true
 isMatch("ab", "?*") ? true
 isMatch("aab", "c*a*b") ? false

代码：

 class Solution {  
 public:  
   // s does NOT include '?' and '*'. p has '?' and '*'  
   //Version 1: iteration  
   bool isMatch(const char *s, const char *p) {  
     const char *start_s = NULL, *start_p = NULL;  
     while (*s != '\0') {  
       if (*p == '?' || *s == *p) {  
         s++;  
         p++;  
       } else if (*p == '*') {  
         while (*p == '*') p++;  
         if (*p == '\0') return true;  
         start_s = s;  
         start_p = p;  
       } else {  
         if (!start_s) return false;  
         s = ++start_s;  
         p = start_p;  
       }  
     }  
     while (*p == '*') p++;  
     return *s == '\0' && *p == '\0';  
   }  
 };  
   
 class Solution {  
 public:  
   //Version 2: recursion:   
   // time limit exceed  
   bool isMatch(const char* s, const char* p) {  
     if (*s == '\0') {  
       while(*p && *p == '*') p++;  
       return *p == '\0';  
     }  
     if (*s == *p || *p == '?') {  
       return isMatch(s+1, p+1);  
     } else if (*p == '*') {  
       while (*p == '*') p++;  
       if (*p == '\0') return true;  
       while (*s != '\0') {  
         if (isMatch(s, p)) return true;  
         s++;  
       }  
     }  
     return false;  
   }  
 };  

Regular Expression Matching

来源：Leetcode

原帖：http://oj.leetcode.com/problems/regular-expression-matching/

题目：
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a*") ? true
isMatch("aa", ".*") ? true
isMatch("ab", ".*") ? true
isMatch("aab", "c*a*b") ? true  zero or more

思路：
http://www.cnblogs.com/zuoyuan/p/3781773.html
解题思路：正则表达式匹配的判断。网上很多的解法是用递归做的，用java和c++都可以过，但同样用python就TLE，说明这道题其实考察的不是递归。而是动态规划，使用动态规划就可以AC了。这里的'*'号表示重复前面的字符，注意是可以重复0次的。
先来看递归的解法：
如果P[j+1]!='*'，S[i] == P[j]=>匹配下一位(i+1, j+1)，S[i]!=P[j]=>匹配失败；
如果P[j+1]=='*'，S[i]==P[j]=>匹配下一位(i+1, j)或者(i, j+2)，S[i]!=P[j]=>匹配下一位(i,j+2)。
匹配成功的条件为S[i]=='\0' && P[j]=='\0'。

代码：

 class Solution {  
 public:  
   bool isMatch(const char *s, const char *p) {  
     if (*p == '\0') return *s == '\0';  
     if (*(p+1) == '*') {  
       if (isMatch(s, p+2)) return true; // match 0  
       while (*s && (*s == *p || *p == '.')) { // match 1,2,...  
         if (isMatch(s+1, p+2)) return true;  
         s++;  
       }  
     } else if (*s && (*p == *s || *p == '.') && isMatch(s+1, p+1)) // always check *s  
         return true;  
     return false;  
   }  
 };  
   
 // dp solution  
 class Solution {  
 public:  
   bool isMatch(const char* s, const char* p) {  
     if (*p == '\0') return *s == '\0';  
     int M = strlen(s), N = strlen(p);  
     vector<vector<bool> > dp(M+1, vector<bool>(N+1, false)); // 前i个字符in s和前j个字符in p的匹配  
     dp[0][0] = true;  
     for (int j = 0; j < N; ++j)  
       dp[0][j+1] = p[j] == '*' ? (j >= 1 && dp[0][j-1]) : false;   
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         if (s[i] == p[j] || p[j] == '.') {  
           dp[i+1][j+1] = dp[i][j];  
         } else if (p[j] == '*') {  
           dp[i+1][j+1] = dp[i+1][j-1] || ((s[i] == p[j-1] || p[j-1] == '.') && dp[i][j+1]);  
         }  
       }  
     }  
     return dp[M][N];  
   }  
 };  

186 Reverse Words In a String II

来源：Leetcode

原帖：https://leetcode.com/problems/reverse-words-in-a-string-ii/

题目：
Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters. The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example,
Given s = "the sky is blue", return "blue is sky the".
Could you do it in-place without allocating extra space?

代码：

 class Solution {  
 public:  
   // in-place reverse  
   void reverseWords(string &s) {  
     reverse(s.begin(), s.end());  
     int end = 0;  
     for (int i = 0; i < s.size(); ++i) {  
       if (s[i] == ' ') continue;  
       if (end != 0) s[end++] = ' ';  
       int l = i, h = i;  
       while (i != s.size() && s[i] != ' ') {  
         h++; i++;  
       }  
       reverse(s.begin() + l, s.begin() + h);  
       for (int j = l; j < h; ++j) {  
         s[end++] = s[j];  
       }  
     }  
     s.resize(end);    
   }  
 };  

Peek Iterator

来源：一亩三分地

原帖：http://www.fgdsb.com/2015/01/25/peek-iterator/

题目：
写一个PeekIterator，包装一个普通的Iterator，要实现peek()方法，返回当前iterator指向的元素，但是不能移动它。除此之外也要实现has_next()和next()方法。
PeekIterator可以用普通iterator的get_next()来获得，但是要记录下来，下一次调用get_next的时候直接返回上一次peek的即可。

代码：

 class Iterator {  
 public:  
     Iterator(vector<int>& num) : data(move(num)), size(0) {}  
     bool has_next() {return size < data.size();}  
     int get_next() {  
         return data[size++];  
     }  
 private:  
     vector<int> data;  
     int size;  
 };  
   
 class PeekIterator {  
 public:  
     PeekIterator(vector<int>& num) : iter(num) {}  
     bool has_next() {  
         iter.has_next() || !peek.empty();  
     }  
   
     int get_next() {  
         if (!peek.empty()) {  
             int ret = peek.back();  
             peek.pop_back();  
             return ret;  
         }  
         return iter.get_next();  
     }  
   
     int get_peek() {  
         if (!peek.empty()) {  
             return peek.back();  
         }  
         int ret = iter.get_next();  
         peek.push_back(ret);  
         return ret;  
     }  
   
 private:  
     vector<int> peek;  
     Iterator iter;  
 };  

157 Read N Characters Given Read4

来源：Leetcode

原帖：https://leetcode.com/problems/read-n-characters-given-read4/

题目：
The API: int read4(char *buf) reads 4 characters at a time from a file. The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file. By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.
Note:
The read function will only be called once for each test case.
// Forward declaration of the read4 API.
int read4(char *buf);

代码：

 class Solution {  
 public:  
   /**  
    * @param buf Destination buffer  
    * @param n  Maximum number of characters to read  
    * @return  The number of characters read  
    */  
   int read(char *buf, int n) {  
     char buffer[4];  
     int cnt = 0;  
     while (cnt < n) {  
       int sz = read4(buffer);  
       if (cnt + sz >= n) {  
         memcpy(buf+cnt, buffer, n-cnt);  
         cnt = n;  
       } else {  
         memcpy(buf+cnt, buffer, sz);  
         cnt += sz;  
       }  
       //sz = min(sz, n-cnt);  
       //memcpy(buf + cnt, buffer, sz);  
       //cnt += sz;  
       if (sz < 4) break;  
     }  
     return cnt;  
   }  
 };  

Implement Hash

来源：Bloomberg面试题

原帖：http://www.cnblogs.com/xiekeli/archive/2012/01/13/2321207.html
            http://www.cnblogs.com/xiekeli/archive/2012/01/16/2323391.html

题目：
Hash表的简单实现可以作为一个好的练习和理解hash结构。使用拉链法实现hash。

代码：

 struct Node {  
   string key;  
   string val;  
   Node* next;  
   Node() {};  
   Node(string k, string v) : key(k), val(v) {}  
 };  
   
 const int HASHSIZE = 10001; // Hashsize; bucket size  
 const int CAPACITY = 1205; // 哈希能够装载最大的容量，一定大于最大元素个数, capacity; < hashsize;  
   
 class Hash {  
 public:  
   Hash() : node(CAPACITY), table(HASHSIZE,NULL), size(0) {}  
   
   bool insert(string k, string v) {  
     int code = hashcode(k);  
     Node* cur = table[code];  
     while (cur) {  
       if (cur->key == k) return false;  
       cur = cur->next;  
     }  
     node[size] = Node(k,v);  
     node[size].next = table[code];  
     table[code] = &node[size++];  
     return true;  
   }  
   
   bool find(string k) {  
     int code = hashcode(k);  
     Node* cur = table[code];  
     while (cur) {  
       if (cur->key == k) return true;  
       cur = cur->next;  
     }  
     return false;  
   }  
   
   const string& operator[](string k) const {  
     int code = hashcode(k);  
     Node* cur = table[code];  
     while (cur) {  
       if (cur->key == k) {  
         return cur->val;  
       }  
       cur = cur->next;  
     }  
   }  
   
   string& operator[](string k) {  
     int code = hashcode(k);  
     Node* cur = table[code];  
     while (cur) {  
       if (cur->key == k) {  
         return cur->val;  
       }  
       cur = cur->next;  
     }  
   }  
   
 private:  
   int hashcode(const string& s) const {  
     unsigned int hash = 0;  
     for (auto i : s) {  
       hash = hash * + i;  
     }  
     return (hash & 0x7FFFFFFF) % HASHSIZE;  
   }  
   
   static const int seed = 131;   
   int size;  
   vector<Node> node;  
   vector<Node*> table;  
 };  
   
   
 int main() {  
   Hash hash;  
   hash.insert("tiger", "1");  
   hash.insert("monkey", "2");  
   hash.insert("cat", "3");  
   
   if (hash.find("tiger")) {  
     cout << "find the animal" << endl;  
   } else {  
     cout << "not find the animal" << endl;  
   }  
     
   cout << hash["tiger"] << endl;  
   return 0;  
 }  

151 Reverse Words In a String I

来源：Leetcode

原帖：https://oj.leetcode.com/problems/reverse-words-in-a-string/

题目：
Given an input string, reverse the string word by word. For example,
Given s = "the sky is blue", return "blue is sky the".
click to show clarification. Clarification:
What constitutes a word?
A sequence of non-space characters constitutes a word. Could the input string contain leading or trailing spaces? Yes. However, your reversed string should not contain leading or trailing spaces. How about multiple spaces between two words? Reduce them to a single space in the reversed string.

代码：

 class Solution {  
   void reverseWords(string &s) {  
     stringstream ss(s);  
     vector<string> vs;  
     string word;  
     while (ss >> word) {  
       vs.push_back(word);  
     }  
     reverse(vs.begin(), vs.end());  
     for (size_t i = 0; i < vs.size(); ++i {  
       if (i ! = 0) ss << ' ';  
         ss << vs[i];  
     }  
     s = ss.str();  
   }  
 };  
   
 class Solution {  
 public:  
   void reverseWords(string &s) {  
     string result;  
     int pos = 0;  
     for (int i = 0; i < s.size(); i ++){  
       if (s[i] == ' '){  
         if (i > pos )  
           result = s.substr(pos,i-pos)+ " " + result ;  
         pos = i + 1;  
       }  
       else if (i == s.size()-1)  
         result = s.substr(pos,s.size()-pos)+" "+result;  
     }  
     s = result.substr(0,result.size()-1) ;  
   }  
 };  
   

Max Points on a Line

来源：Leetcode

原帖：https://oj.leetcode.com/problems/max-points-on-a-line/

题目：
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

代码：

 /**  
  * Definition for a point.  
  * struct Point {  
  *   int x;  
  *   int y;  
  *   Point() : x(0), y(0) {}  
  *   Point(int a, int b) : x(a), y(b) {}  
  * };  
  */  
   
 class Solution {  
 public:  
   // int GCD(int a, int b){  
   //   if(a == 0)   
   //     return b;  
   //   else   
   //     return GCD(a, b%a);  
   // }  
     
   struct hashfunc {   
     size_t operator() (const pair<int,int>& l) const {   
       return l.first ^ l.second;   
     }  
   };    
     
   int maxPoints(vector<Point> &points) {  
     int res = 0;  
     for (int i = 0; i < points.size(); i++) {  
       unordered_map<pair<int,int>,int,hashfunc> lines;  
       int localmax = 0, vertical = 0, overlap = 0;  
       for (int j = i + 1; j < points.size(); j++){  
         if (points[j].x == points[i].x && points[j].y == points[i].y){  
           overlap++;  
           continue;  
         } else if (points[j].x == points[i].x) {  
           vertical++;  
         } else {  
           int yd = points[j].y - points[i].y, xd = points[j].x - points[i].x;  
           int gcd = __gcd(yd, xd);  
           yd /= gcd;  
           xd /= gcd;  
           lines[{xd, yd}]++;  
           localmax = max(lines[{xd, yd}], localmax);  
         }  
         localmax = max(vertical, localmax);  
       }  
       res = max(res, localmax+overlap+1);  
     }    
     return res;  
   }  
 };  
   

Word Ladder II

来源：Leetcode

原帖：https://oj.leetcode.com/problems/word-ladder-ii/

题目：
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that: Only one letter can be changed at a time. Each intermediate word must exist in the dictionary. For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
 [
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
 ]
Note:
All words have the same length.
All words contain only lowercase alphabetic characters.
Solution: Idea is from blog: http://blog.csdn.net/niaokedaoren/article/details/8884938

代码：

 class Solution {  
 public:  
     vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {  
     // If A->C and B->C, then traces[C] contains A and B. This is used for recovering the paths.  
     unordered_map<string, vector<string>> traces;   
     queue<string> q;  
     q.push(start);  
     bool found = false;  
     while (!q.empty()) {  
       int size = q.size();  
       unordered_set<string> level;  
       for (int i = 0; i < size; ++i) {  
         string word = q.front(); q.pop();  
         string nextWord = word;  
         for (size_t j = 0; j < nextWord.size(); ++j) {  
           char before = nextWord[j];  
           for (char c = 'a'; c <= 'z'; c++) {  
             if (c == before) continue;  
             nextWord[j] = c;  
             if (nextWord == end)  
               found = true;  
             if (nextWord == end || dict.find(nextWord) != dict.end()) {  
               traces[nextWord].push_back(word);  
               level.emplace(nextWord);  
             }  
           }  
           nextWord[j] = before;  
         }     
       }  
       if (found) break;  
       for (auto it = level.begin(); it != level.end(); it++) {  
         q.push(*it);  
         dict.erase(*it);  
       }  
     }  
     vector<vector<string> > result;  
     vector<string> onePath;  
     if (!traces.empty()) {  
       buildResult(traces, result, onePath, end, start);        
     }  
     return result;  
   }  
   
   // backtracking to target (start word), then reverse the root->leaf order  
   // DFS  
   void buildResult(unordered_map<string, vector<string> > &traces, vector<vector<string>> &result,   
            vector<string> &onePath, string word, const string &target) {  
     if (word == target) { // word = start word   
       vector<string> copy(onePath);  
       copy.push_back(word);  
       reverse(copy.begin(), copy.end());  
       result.push_back(copy);  
       return;  
     }  
     vector<string> &s = traces[word];  
     onePath.push_back(word);  
     for (int i = 0; i < s.size(); ++i) {  
       buildResult(traces, result, onePath, s[i], target);  
     }  
     onePath.pop_back();  
   }    
 };  
   

Word Ladder I

来源：Leetcode

原帖：https://oj.leetcode.com/problems/word-ladder/

题目：
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that: Only one letter can be changed at a time. Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

代码：

 class Solution {  
 public:  
   int ladderLength(string start, string end, unordered_set<string> &dict) {  
     queue<pair<string, int> > q; // (word, transformation steps)  
     q.push({start, 1});  
     while (!q.empty()) {  
       pair<string, int> front = q.front(); q.pop();  
       string word = front.first;  
       for (size_t i = 0; i < word.size(); i++) {  
         char before = word[i];      
         for (char c = 'a'; c <= 'z'; c++) {  
           if (c == before) continue;  
           word[i] = c;  
           if (word == end) {  
             return front.second + 1; // return shortest length              
           }  
           if (dict.find(word) != dict.end()) {  
             q.push({word, front.second + 1});  
             dict.erase(word);  
           }  
         }  
         word[i] = before;  
       }  
     }  
     return 0;  
   }  
 };  

212 Word Search II

来源：Leetcode

原帖：https://leetcode.com/problems/word-search-ii/

题目：
Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
For example,
Given words = ["oath","pea","eat","rain"] and board =
 [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
 ]
Return ["eat","oath"].

代码：

 struct TrieNode {  
   bool isWord;  
   string word;  
   unordered_map<char, TrieNode*> next;  
   TrieNode(bool w = false) : isWord(w) {}  
 };  
   
 class Solution {  
 public:  
   void insert(TrieNode*& root, string s) {  
     if (!root) root = new TrieNode();  
     TrieNode* cur = root;  
     for (int i = 0; i < s.size(); ++i) {  
       if (!cur->next.count(s[i])) {  
         cur->next[s[i]] = new TrieNode();  
       }  
       cur = cur->next[s[i]];  
     }  
     cur->isWord = true;  
     cur->word = s;  
   }  
     
   vector<pair<int,int>> offset = {{0,-1},{-1,0},{0,1},{1,0}};  
   void dfs(vector<vector<char>>& board, vector<vector<bool>>& visited, int i, int j,   
       TrieNode* root, vector<string>& res) {  
     int M = board.size(), N = board[0].size();  
     char c = board[i][j];  
     if (!root->next.count(c)) return;  
     if (root->next[c]->isWord) {  
       res.push_back(root->next[c]->word);  
       root->next[c]->isWord = false;  
     }  
     visited[i][j] = true;  
     for (auto o : offset) {  
       int ii = i + o.first, jj = j + o.second;  
       if (ii >= 0 && ii < M && jj >= 0 && jj < N && !visited[ii][jj]) {  
         dfs(board, visited, ii, jj, root->next[board[i][j]], res);  
       }  
     }  
     visited[i][j] = false;  
   }  
     
   vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {  
     if (words.empty()) return {};  
     TrieNode* root = NULL;  
     for (auto s : words) {  
       insert(root, s);  
     }  
     vector<string> res;  
     int M = board.size(), N = board[0].size();  
     vector<vector<bool>> visited(M, vector<bool>(N,false));  
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         dfs(board, visited,i,j,root,res);  
       }  
     }  
     return res;  
   }  
 };  

Word Search I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/word-search/

题目：
Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
 [
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
 ]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

代码：

 class Solution {  
 public:  
   vector<pair<int,int> > offset = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  
   bool exist(vector<vector<char> > &board, string word) {  
     int M = board.size(), N = board[0].size();  
     vector<vector<bool> > visited(M, vector<bool>(N, false)); // visiting status   
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         if (existHelper(board, word, 0, i, j, visited)) {  
           return true;  
         }  
       }      
     }  
     return false;  
   }  
   
   bool existHelper(const vector<vector<char> > &board, const string &word, int deep, int i, int j,   
     vector<vector<bool> > &visited) {  
     int M = board.size(), N = board[0].size();    
     if (deep == word.size()) return true;  
     if (i < 0 || i >= M || j < 0 || j >= N) return false;  
     if (board[i][j] != word[deep] || visited[i][j] == true) return false;  
     visited[i][j] = true;  
     for (auto o : offset) {  
       if (existHelper(board, word, deep + 1, i+o.first, j+o.second, visited)) {  
         return true;  
       }  
     }  
     visited[i][j] = false;  
     return false;  
   }  
 };  

Task Schedule

来源：itint5

原帖：http://www.itint5.com/oj/#10

题目：
有n个任务需要完成（编号1到n），任务之间有一些依赖关系，如果任务a依赖于任务b和c，那么只有当任务b和任务c完成之后才能完成任务a。给定所有的依赖关系，判断这些任务是否能够完成。如果能够完成，请给出一个合法的任务完成序列。
样例：
n=5
1->2,3
3->4
上述样例中任务1依赖于任务2和任务3，任务3依赖于任务4，那么存在合法的任务完成序列4,3,2,1,5
Solution: topological sorting
Refer to http://www.geeksforgeeks.org/topological-sorting/

代码：

 /*  
  * deps[id]表示任务id所依赖的任务  
  * 如果存在合法的任务完成序列，返回true，否则返回false  
  * 合法的任务序列请存放在参数result中（已经分配空间，不需要push_back）  
    2->1; 3->1  
    4->3  
    拓扑排序方法如下:  
    (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.  
    (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.  
    (3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.  
  */  
   
 typedef int JobID;  
 // BFS  
 // deps: <key, node(-->key) INDEGREE>  
 // rmap: <key, node(<--key) OUTDEGREE>  
 bool jobSchedule(const map<JobID, vector<JobID> > &deps, int n, vector<JobID> &result) {  
   vector<JobID> indegree(n+1, 0); // 计算图形入度  
   map<JobID, vector<JobID>> rmap; //   
   for (auto it = deps.begin(); it != deps.end(); it++) {  
     indegree[it->first] = it->second.size();  
     for (int i = 0; i < it->second.size(); i++) {  
       rmap[it->second[i]].push_back(it->first);  
     }  
   }  
   stack<JobID> s;  
   for (int i = 1; i <= n; i++) {  
     if(indegree[i] == 0) {  
       s.push(i);  
     }  
   }  
   for (int i = 0; i < n; i++) {  
     if (s.empty()) return false;  
     JobID id = s.top(); s.pop();  
     result[i] = id;  
     for (int j = 0; j < rmap[id].size(); j++) {  
       indegree[rmap[id][j]]--;  
       if(indegree[rmap[id][j]] == 0) {  
         s.push(rmap[id][j]);  
       }  
     }  
   }  
   return true;  
 }  

Surrounded Regions

来源：

原帖：https://oj.leetcode.com/problems/surrounded-regions/

题目：
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region .
For example,
 X X X X
 X O O X
 X X O X
 X O X X
After running your function, the board should be:
 X X X X
 X X X X
 X X X X
 X O X X
Solution: Traverse from the boarder to the inside and mark all the 'O's that are not surrounded by 'X' as 'V' (visited).

代码：

 // rumtime error  
 class Solution {  
 public:  
   typedef vector<vector<char> > BOARDTYPE;    
   vector<pair<int,int> > offset = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};  
   void solve(BOARDTYPE &board) {  
     if (board.empty() || board[0].empty()) return;  
     int M = board.size(), N = board[0].size();  
     for (int j = 0; j < board[0].size(); ++j) {  
      if (board[0][j] == 'O') dfs(board, 0, j);  
      if (board[board.size()-1][j] == 'O') dfs(board, board.size()-1, j);  
     }  
     for (int i = 0; i < board.size(); ++i) {  
      if (board[i][0] == 'O') dfs(board, i, 0);  
      if (board[i][board[0].size()-1] == 'O') dfs(board, i, board[0].size()-1);  
     }  
     // flip remaining 'O' to 'X' and revert 'V' to 'O'  
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         board[i][j] = (board[i][j] == 'V') ? 'O' : 'X';                
       }  
     }  
   }  
     
   void dfs(BOARDTYPE &board, int row, int col) {  
     int M = board.size(), N = board[0].size();  
     board[row][col] = 'V';  
     for (auto o : offset) {  
       int i = row + o.first, j = col + o.second;  
       if (i >= 0 && i < M && j >= 0 && j < N && board[i][j] == 'O') {  
         dfs(board, i, j);  
       }  
     }  
   }  
 };  
   
 class Solution {  
 public:  
   typedef vector<vector<char> > BOARDTYPE;    
   vector<pair<int,int> > offset = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};  
   
   void bfs(BOARDTYPE &board, int row, int col) {  
     if (board[row][col] != 'O') return;  
     int M = board.size(), N = board[0].size();  
     queue<pair<int, int> > q;  
     board[row][col] = 'V';  
     q.push({row, col}); // q.push({i, j}); pair对也可以使用{i, j} instead of make_pair(i,j)  
     while (!q.empty()) {  
       int i = q.front().first, j = q.front().second;  
       q.pop();  
       for (auto o : offset) {  
         int ii = o.first + i, jj = o.second + j;  
         if (ii >= 0 && ii < M && jj >= 0 && jj < N && board[ii][jj] == 'O') {  
           board[ii][jj] = 'V'; // update !!!   
           q.push({ii, jj});  
         }  
       }  
     }  
   }  
   
   void solve(BOARDTYPE &board) {  
     if (board.empty() || board[0].empty()) return;  
     int M = board.size(), N = board[0].size();  
     for (int j = 0; j < board[0].size(); ++j) {  
      if (board[0][j] == 'O') bfs(board, 0, j);  
      if (board[board.size()-1][j] == 'O') bfs(board, board.size()-1, j);  
     }  
     for (int i = 0; i < board.size(); ++i) {  
      if (board[i][0] == 'O') bfs(board, i, 0);  
      if (board[i][board[0].size()-1] == 'O') bfs(board, i, board[0].size()-1);  
     }  
     // flip remaining 'O' to 'X' and revert 'V' to 'O'  
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         board[i][j] = (board[i][j] == 'V') ? 'O' : 'X';                
       }  
     }  
   }  
 };  
   

Sudoku Solver

来源：Leetcode

原帖：http://oj.leetcode.com/problems/sudoku-solver/

题目：
Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character '.'. You may assume that there will be only one unique solution.
Solution: back-tracking... Recursion.
Note: Backtracking...
http://blog.csdn.net/linhuanmars/article/details/20748761
这道题的方法就是用在N-Queens中介绍的常见套路。简单地说思路就是循环处理子问题，对于每个格子，带入不同的9个数，然后判合法，如果成立就递归继续，结束后把数字设回空

代码：

 class Solution {  
 public:  
   typedef vector<vector<char>> BOARDTYPE;  
   const int N = 9;  
   
   void getNextEmpty(BOARDTYPE &board, int &row, int &col) {  
     do {  
       if (board[row][col] == '.') return;  
       row = (col == N - 1) ? row + 1 : row;  
       col = (col + 1) % N;  
     } while (row < N);  
   }  
     
   void getAvailable(BOARDTYPE &board, vector<bool> &avail, int row, int col) {  
     for (int i = 0; i < 9; ++i) {  
       if (board[row][i] != '.') {  
         avail[board[row][i] - '1'] = false;  
       }  
       if (board[i][col] != '.') {  
         avail[board[i][col] - '1'] = false;  
       }  
       int box_i = row/3*3 + i/3;  
       int box_j = col/3*3 + i%3;  
       if (board[box_i][box_j] != '.') {  
         avail[board[box_i][box_j] - '1'] = false;  
       }  
     }  
   }  
   
   bool solveSudokuHelper(BOARDTYPE &board, int row, int col) {  
     getNextEmpty(board, row, col); // get next empty position [row, col]  
     if (row == 9) return true;  
     vector<bool> avail(9, true);  
     getAvailable(board, avail, row, col); // available value at(row, col) in row/col/box check   
     for (int i = 0; i < 9; ++i) {  
       if (!avail[i]) continue;  
       board[row][col] = i + '1';  
       if (solveSudokuHelper(board, row, col)) return true;  
       board[row][col] = '.';  
     }  
     return false;  
   }  
     
   void solveSudoku(BOARDTYPE &board) {  
     solveSudokuHelper(board, 0, 0);  
   }  
 };  
   

Valid Sudoku

来源：Leetcode

原帖：http://oj.leetcode.com/problems/valid-sudoku/

题目：
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules (http://sudoku.com.au/TheRules.aspx). The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

代码：

 class Solution {  
 public:  
   bool isValidSudoku(vector<vector<char>> &board) {  
     const int N = 9;  
     vector<int> col(N, 0), box(N, 0);  
     for (int i = 0; i < N; ++i) { // row traverse   
       int row = 0; // update row bit  
       for (int j = 0; j < N; ++j) { // col traverse  
         if (board[i][j] == '.') continue;  
         int bit = 1 << (board[i][j] - '1');  
         int box_index = i/3*3 + j/3;  
         if ((row & bit) || (col[j] & bit) || (box[box_index] & bit)) {  
           return false;            
         }          
         row |= bit;  
         col[j] |= bit;  
         box[box_index] |= bit;  
       }  
     }  
     return true;  
   }  
 };  

Restore IP Addresses

来源：Leetcode

原帖：http://oj.leetcode.com/problems/restore-ip-addresses/

题目：
Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

代码：

 class Solution {  
 public:  
   vector<string> restoreIpAddresses(string s) {  
     vector<string> result;  
     string ip;  
     restoreIpAddressHelper(s, result, ip, 0, 0);  
     return result;  
   }  
     
   void restoreIpAddressHelper(const string &s, vector<string> &result, string ip, int deep, int start) {  
     // pruning  
     if (s.size() - start > (4 - deep) * 3) return;  
     if (s.size() - start < 4 - deep) return;  
     if (deep == 4 && start == s.size()) {  
       ip.resize(ip.size() - 1);  
       result.push_back(ip);  
       return;  
     }  
     int num = 0;  
     for (int i = start; i < start + 3; ++i) {  
       num = num * 10 + s[i] - '0';  
       if (num > 255) break;  
       ip.push_back(s[i]);  
       restoreIpAddressHelper(s, result, ip + ".", deep + 1, i + 1);  
       if (num == 0) break; // case 0.0.0.0 or case 255.128.0.23  
     }  
   }  
 };  

Clone Graph

来源：Leetcode

原帖：http://oj.leetcode.com/problems/clone-graph/

题目：
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:
Nodes are labeled from 0 to N - 1, where N is the total nodes in the graph.
We use # as a separator for each node, and , as a separator for each neighbor of the node.
As an example, consider the serialized graph {1,2#2#2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
Connect node 0 to both nodes 1 and 2.
Connect node 1 to node 2.
Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

 Solution: 1. DFS. 2. BFS.

代码：

 /**  
  * Definition for undirected graph.  
  * struct UndirectedGraphNode {  
  *   int label;  
  *   vector<UndirectedGraphNode *> neighbors;  
  *   UndirectedGraphNode(int x) : label(x) {};  
  * };  
  */  
 class Solution {  
 public:  
   typedef UndirectedGraphNode GraphNode;  
   typedef unordered_map<GraphNode*, GraphNode*> MAP;  
   //Version 1: DFS, hash-map  
   GraphNode* cloneGraph(GraphNode *node) {  
     MAP map;  
     return cloneGraphHelper(node, map);  
   }  
     
   GraphNode* cloneGraphHelper(GraphNode *node, MAP &map) {  
     if (!node) return NULL;  
     if (map.count(node)) return map[node];        
     GraphNode* newNode = new GraphNode(node->label);  
     map[node] = newNode;  
     for (int i = 0; i < node->neighbors.size(); ++i) {  
       newNode->neighbors.push_back(cloneGraphHelper(node->neighbors[i], map));  
     }  
     return newNode;  
   }  
 };  
   
 class Solution {  
 public:  
   typedef UndirectedGraphNode GraphNode;  
   typedef unordered_map<GraphNode*, GraphNode*> MAP;  
     
   //Version 2: BFS, HashMap  
   GraphNode *cloneGraph(GraphNode *node) {  
     if (!node) return NULL;  
     queue<GraphNode*> q;  
     q.push(node);  
     MAP map;  
     map[node] = new GraphNode(node->label);  
     while (!q.empty()) {  
       GraphNode *oriNode = q.front();   
       q.pop();  
       GraphNode *newNode = map[oriNode];  
       for (int i = 0; i < oriNode->neighbors.size(); ++i) {  
         GraphNode *oriNeighbor = oriNode->neighbors[i];  
         if (map.find(oriNeighbor) != map.end()) {  
           newNode->neighbors.push_back(map[oriNeighbor]); // already visited!不再加入队列中  
           continue;  
         }  
         GraphNode *newNeighbor = new GraphNode(oriNeighbor->label);  
         newNode->neighbors.push_back(newNeighbor);  
         map[oriNeighbor] = newNeighbor; // set up hash-map  
         q.push(oriNeighbor); // push for next visit  
       }  
     }  
     return map[node];  
   }  
 };  

Subsets II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/subsets-ii/

题目：
Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets.
For example,
If S = [1,2,2], a solution is:
 [
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
 ]

代码：

 class Solution {  
 public:  
   //Version 1: 从树状结构考虑递归方法  
   vector<vector<int> > subsetsWithDup(vector<int> &S) {  
     vector<vector<int> > result;  
     if (S.empty()) return result;  
     sort(S.begin(), S.end());  
     vector<int> oneset;  
     subsetsWithDupHelper(S, 0, oneset, result);  
     return result;  
   }  
   
   void subsetsWithDupHelper(vector<int> &S, int start, vector<int> &oneset, vector<vector<int> > &result) {  
     result.push_back(oneset);  
     for (int i = start; i < S.size(); ++i) {  
       if (i != start && S[i] == S[i - 1]) {  
         continue;  
       }    
       oneset.push_back(S[i]);  
       subsetsWithDupHelper(S, i + 1, oneset, result);  
       oneset.pop_back();  
     }  
   }   
 };  
   
 // {}  
 // 1  
 // 2  
 // 1,2  
 // 2,2  
 // 1,2,2  
 class Solution {  
 public:  
   vector<vector<int> > subsetsWithDup(vector<int> &S) {  
     sort(S.begin(), S.end());  
     vector<vector<int>> ret = {{}};  
     int size = 0, startIndex = 0;  
     for (int i = 0; i < S.size(); i++) {  
       startIndex = i >= 1 && S[i] == S[i - 1] ? size : 0;  
       size = ret.size();  
       for (int j = startIndex; j < size; j++) {  
         vector<int> temp = ret[j];  
         temp.push_back(S[i]);  
         ret.push_back(temp);  
       }  
     }  
     return ret;  
   }  
 };  

Subsets I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/subsets/

题目：
Given a set of distinct integers, S, return all possible subsets.
Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:
 [
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
 ]

代码：

 class Solution {  
 public:  
   void subsetHelper(const vector<int> &S, int start, vector<int> &oneset, vector<vector<int> > &result) {  
     result.push_back(oneset);  
     for (int i = start; i < S.size(); ++i) {  
       oneset.push_back(S[i]);  
       subsetHelper(S, i + 1, oneset, result);  
       oneset.pop_back();  
     }  
   }  
   
   //Version 1: 从树状结构考虑递归方法  
   vector<vector<int> > subsets(vector<int> &S) {  
     vector<vector<int> > result;  
     if (S.empty()) return result;  
     sort(S.begin(), S.end());  
     vector<int> oneset;  
     subsetHelper(S, 0, oneset, result);  
     return result;  
   }  
 };  
   
 // Bitwise solution. each bit has two state, present or not.  
 class Solution {  
 public:  
   vector<vector<int> > subsets(vector<int> &S) {  
     sort (S.begin(), S.end());  
     int elem_num = S.size();  
     int subset_num = pow (2, elem_num);  
     vector<vector<int> > subset_set (subset_num, vector<int>());  
     for (int i = 0; i < elem_num; i++)  
       for (int j = 0; j < subset_num; j++)  
         if ((j >> i) & 1)  
           subset_set[j].push_back (S[i]);  
     return subset_set;  
   }  
 };  
   
 // iteration  
 class Solution {  
 public:  
   vector<vector<int> > subsets(vector<int> &S) {  
     vector<vector<int> > R;  
     R.push_back(vector<int>());  
     sort(S.begin(), S.end());  
     for (int i = 0; i<S.size(); i++) {  
       int Rsize = R.size();  
       for (int j = 0; j<Rsize; j++) {  
         vector<int> sub(R[j]);  
         sub.push_back(S[i]);  
         R.push_back(sub);  
       }  
     }  
     return R;  
   }  
 };  

Permutations II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/permutations-ii/

题目：
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
 For example,
 [1,1,2] have the following unique permutations:
 [1,1,2], [1,2,1], and [2,1,1].

代码：

 class Solution {  
 public:  
   vector<vector<int>> permuteUnique(vector<int> &num) {  
     vector<vector<int>> result;  
     if (num.empty()) return result;  
     sort(num.begin(), num.end());  
     vector<bool> avail(num.size(),true);  
     vector<int> onepum;  
     permuteHelper(num, onepum, avail, result);  
     return result;  
   }  
   
   void permuteHelper(const vector<int> &num, vector<int> &onepum, vector<bool> &avail, vector<vector<int> > &result) {  
     if (onepum.size() == num.size()) {  
       result.push_back(onepum);  
       return;  
     }  
     int last_index = -1;  
     for (int i = 0; i < num.size(); ++i) {  
       if (!avail[i]) continue;  
       // 1233 -> 1323  
       if (last_index != -1 && num[i] == num[last_index]) {  
         continue; // last_index stores the position been visited          
       }  
       avail[i] = false;  
       onepum.push_back(num[i]);  
       permuteHelper(num, onepum, avail, result);  
       onepum.pop_back();  
       avail[i] = true;  
       last_index = i;  
     }  
   }  
 };  
   

Permutations I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/permutations/

题目：
Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

代码：

 class Solution {  
 public:  
   vector<vector<int>> permute(vector<int> &num) {  
     if (num.empty()) {}  
     vector<vector<int> > result;  
     vector<bool> avail(num.size(), true);  
     vector<int> onepum;  
     permuteHelper(num, avail, onepum, result);  
     return result;  
   }  
   
   void permuteHelper(const vector<int> &num, vector<bool> &avail, vector<int> &onepum, vector<vector<int>> &result) {  
     if (onepum.size() == num.size()) {  
       result.push_back(onepum);  
       return;  
     }      
     for (int i = 0; i < num.size(); ++i) {  
       if (avail[i]) {  
         avail[i] = false;  
         onepum.push_back(num[i]);  
         permuteHelper(num, avail, onepum, result);  
         onepum.pop_back();  
         avail[i] = true;  
       }  
     }  
   }  
 };  

Permutation Sequence

来源：Leetcode

原帖：http://oj.leetcode.com/problems/permutation-sequence/

题目：
The set [1,2,3,...,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):
 "123"
 "132"
 "213"
 "231"
 "312"
 "321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
Solution: k = 3 return "231"

代码：

 class Solution {  
 public:  
   // permuation problem, not graph problem  
   string getPermutation(int n, int k) {  
     // index k starting from 0.  
     string num, res;  
     int total = 1;  
     for (int i = 1; i <= n; ++i) { // push back "123"  
       num.push_back(i + '0');  
       total *= i;  
     }  
   
     k--; // index starting from 0  
     while (n) {  
       total /= n;  
       int i = k / total; // i-th group (start from 0)  
       k %= total; // (start from 0) k-th element i-th group  
       res.push_back(num[i]);  
       num.erase(i, 1);  
       n--;  
     }  
     return res;  
   }  
 };  

Next Permutation

来源：Leetcode

原帖：http://oj.leetcode.com/problems/next-permutation/

题目：
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory. Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
 1,2,3 -> 1,3,2
 3,2,1 -> 1,2,3
 1,1,5 -> 1,5,1
Solution: O(n)
Processes: Take A = {1,3,2} as an example:
1. Traverse from back to forth, find the turning point, that is A[i] = 3.
2. Sort from the turning point to the end (A[i] to A[end]), so {3,2} becomes {2,3}.
            3. If i equals to 0, finish! Else, goto 4.
            4. Let j = i, search from A[j] to A[end] to find the first elem which is larger than A[i-1], '2' here.
            5. Swap the elem A[j] with A[i-1].
            Finally, the next permutation is {2,1,3}.

代码：

 class Solution {  
 public:  
   void nextPermutation(vector<int> &num) {  
     int i = num.size() - 1;  
     while (i > 0 && num[i] <= num[i - 1]) i--;        
     sort(num.begin() + i, num.end());  
     if (i == 0) return;        
     int j = i;  
     while (j < num.size() && num[j] <= num[i - 1]) j++;        
     swap(num[j], num[i - 1]);  
   }  
 };  

N-Queens II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/n-queens-ii/

题目：
The n-queens puzzle is the problem of placing n queens on an n*n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
 [
 [".Q..",  // Solution 1
 "...Q",
 "Q...",
 "..Q."],

 ["..Q.",  // Solution 2
 "Q...",
 "...Q",
 ".Q.."]
 ]

代码：

 class Solution {  
 public:  
   //Version 1: recursion  
   int totalNQueens(int n) {  
     vector<int> board(n, -1); // store board (col) configuration from row 0...n-1.  
     int res = 0;  
     totalNQueensHelper(n, 0, board, res);  
     return res;  
   }  
     
   void totalNQueensHelper(int n, int row, vector<int>& board, int &res) {  
     if(row == n) {  
       res++;  
       return;  
     }  
     for(int i = 0; i < n; ++i) {  
       if(isValid(board, row, i)) {  
         board[row] = i;  
         totalNQueensHelper(n, row + 1, board, res);  
         board[row] = -1;  
       }  
     }  
   }  
     
   bool isValid(vector<int>& board, int row, int col) {  
     for (int i = 0; i < row; ++i) {  
       if (board[i] == col || row - i == abs(col - board[i])) {  
         return false;                
       }  
     }  
     return true;  
   }  
 };  
   
 class Solution {  
 public:   
   //Version 2: Bit version  
   int totalNQueens(int n) {  
     int result = 0;  
     totalNQueensHelp(n, 0, 0, 0, result);  
     return result;  
   }  
   
   void totalNQueensHelp(int n, int col, int ld, int rd, int &result) {  
     if (col == (1 << n) - 1) {  
       result++;  
       return;  
     }  
     int avail = ~(col | ld | rd);  
     for (int i = n - 1; i >= 0; --i) {  
       int pos = 1 << i;  
       if (avail & pos) {  
         totalNQueensHelp(n, col | pos, (ld | pos) << 1, (rd | pos) >> 1, result);          
       }  
     }  
   }  
 };  
   

N-Queens I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/n-queens/

题目：
The n-queens puzzle is the problem of placing n queens on an n*n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
 [
 [".Q..",  // Solution 1
 "...Q",
 "Q...",
 "..Q."],

 ["..Q.",  // Solution 2
 "Q...",
 "...Q",
 ".Q.."]
 ]
 Solution: Recursion (DFS). Use bit-manipulation solution (See N-QueensII for more details).

代码：

 class Solution {  
 public:  
   vector<vector<string> > solveNQueens(int n) {  
     vector<vector<string> > result;  
     vector<string> onePath;  
     solveNQueensHelper(n, 0, 0, 0, onePath, result);  
     return result;  
   }  
     
   // col: 第几列被占据; ld: 左45度对角线被占据; rd: 右45度对角线被占据  
   void solveNQueensHelper(int n, int col, int ld, int rd, vector<string> &onePath,   
     vector<vector<string> > &result) {  
     if (col == (1 << n) - 1) { // all cols are full 1111  
       result.push_back(onePath);  
       return;  
     }  
     int avail = ~(col | ld | rd); // find all available positions  
     for (int i = n - 1; i >= 0; --i) { // n =4, start 'Q...'   
       int pos = 1 << i;  
       if (avail & pos) {  
         string s(n, '.');  
         s[i] = 'Q';  
         onePath.push_back(s);  
         solveNQueensHelper(n, col | pos, (ld | pos) << 1, (rd | pos) >> 1, onePath, result);   
         onePath.pop_back();  
       }  
     }  
   }  
 };  

Longest Common Subsequence

来源：nineChapter

原帖：nineChapter; dp

题目：
state: f[i][j]表示前i个字符配上前j个字符的LCS的长度
function: f[i][j] = f[i-1][j-1] + 1 // a[i] == b[j]
                 = MAX(f[i-1][j], f[i][j-1]) // a[i] != b[j]
intialize: f[i][0] = 0
               f[0][j] = 0
answer: f[a.length()][b.length()]

代码：

 int longestCommonSubsequence(string s1, string s2) {  
   int M = s1.size(), N = s2.size();  
   int dp[M + 1][N + 1] = {0};  
   //memset(dp, 0, sizeof(dp));  
   for (int i = 0; i <= M; ++i) {  
     dp[i][0] = 0;  
   }  
     
   for (int j = 0; j <= N; ++j) {  
     dp[0][j] = 0;  
   }  
   for (int i = 1; i <= M; ++i) {  
     for (int j = 1; j <= N; ++j) {  
       if (s1[i - 1] == s2[j - 1]) {  
         dp[i][j] = dp[i - 1][j - 1] + 1;  
       } else {  
         dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);  
       }  
     }  
   }  
   return dp[M][N];  
 }  

Combinations

来源：Leetcode

原帖：http://oj.leetcode.com/problems/combinations/

题目：
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
 [
    [2,4],
    [3,4],
    [2,3],
    [1,2],
    [1,3],
    [1,4],
 ]

代码：

 class Solution {  
 public:  
   vector<vector<int> > combine(int n, int k) {  
     vector<vector<int> > res;  
     vector<int> onecom;  
     combineHelper(n, k, 1, onecom, res);  
     return res;  
   }  
     
   void combineHelper(int n, int k, int start, vector<int> &onecom, vector<vector<int> > &res) {  
     int m = onecom.size();  
     if (m == k) {  
       res.push_back(onecom);  
       return;  
     }  
     for (int i = start; i <= n - (k - m) + 1; ++i) { // index = n-(k-m);  
       onecom.push_back(i);  
       combineHelper(n, k, i + 1, onecom, res);  
       onecom.pop_back();  
     }  
   }  
 };  

Combination Sum II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/combination-sum-ii/

题目：
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations
in C where the candidate numbers sums to T. Each number in C may only be used once in the combination. Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2, .. , ak) must be in non-descending order. (ie, a1 <= a2 <= ... <= ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

代码：

 class Solution {  
 public:  
   vector<vector<int>> combinationSum2(vector<int> &num, int target) {  
     vector<vector<int> > res;  
     sort(num.begin(), num.end());  
     vector<int> com;  
     combinationSum2Helper(num, target, 0, com, res);  
     return res;  
   }  
   
   void combinationSum2Helper(const vector<int> &num, int target, int start, vector<int> &com, vector<vector<int>> &res) {  
     if (target == 0) {  
       res.push_back(com);  
       return;  
     }  
     for (int i = start; i < num.size() && num[i] <= target; ++i) {  
       if (i > start && num[i] == num[i - 1]) {  
         continue; // avoid duplicates  
       }  
       com.push_back(num[i]);  
       combinationSum2Helper(num, target - num[i], i + 1, com, res);  
       com.pop_back();  
     }  
   }  
 };  

Combination Sum I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/combination-sum/

题目：
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers. Elements in a combination (a1, a2, .. , ak) must be in non-descending order. (ie, a1 <= a2 <= ... <= ak). The solution set must not contain duplicate combinations. For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]
Solution: Sort & Recursion.

代码：

 class Solution {  
 public:  
   vector<vector<int>> combinationSum(vector<int> &candidates, int target) {  
     vector<vector<int> > res;  
     sort(candidates.begin(), candidates.end()); // 如果没有要求结果是非下降序列，则sort是非必要的  
     vector<int> com;  
     combinationSumHelper(candidates, target, 0, com, res);  
     return res;  
   }  
   
   void combinationSumHelper(const vector<int> &num, int target, int start, vector<int> &com, vector<vector<int>> &res) {  
     if (target == 0) {  
       res.push_back(com);  
       return;  
     }  
     for (int i = start; i < num.size() && target >= num[i]; ++i) {  
       com.push_back(num[i]);  
       combinationSumHelper(num, target - num[i], i, com, res);  
       com.pop_back();  
     }  
   }  
 };  

Coin Change

来源：g4g, Facebook Onsite

原帖：http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

题目：

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter. For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

代码：

 #include <iostream>  
 #include <string>  
 #include <vector>  
 using namespace std;  
   
 int changeCoins(int m, vector<int>& amount, int idx) {  
   if (idx == 0) return m % amount[idx] == 0 ? 1 : 0;  
   int count = 0;  
   for (int i = 0; i * amount[idx] <= m; ++i) {  
     count += changeCoins(m - i * amount[idx], amount, idx - 1);  
   }  
   return count;  
 }  
   
 vector<int> amount = {2, 3, 5};  
 int main() {  
   int m = 7;  
   int idx = amount.size();  
   cout << changeCoins(m, amount, idx-1);  
   return 0;  
 }  

二维dp

 int count( int S[], int m, int n )  
 {  
   int i, j, x, y;  
    
   // We need n+1 rows as the table is consturcted in bottom up manner using   
   // the base case 0 value case (n = 0)  
   int table[n+1][m];  
     
   // Fill the enteries for 0 value case (n = 0)  
   for (i=0; i<m; i++)  
     table[0][i] = 1;  
    
   // Fill rest of the table enteries in bottom up manner   
   for (i = 1; i < n+1; i++)  
   {  
     for (j = 0; j < m; j++)  
     {  
       // Count of solutions including S[j]  
       x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;  
    
       // Count of solutions excluding S[j]  
       y = (j >= 1)? table[i][j-1]: 0;  
    
       // total count  
       table[i][j] = x + y;  
     }  
   }  
   return table[n][m-1];  
 }  
    

Generate Parentheses

来源：Leetcode

原帖：http://oj.leetcode.com/problems/generate-parentheses/

题目：
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

代码：

 class Solution {  
 public:  
   vector<string> generateParenthesis(int n) {  
     vector<string> result;  
     generateParenthesisHelper(n, n, "", result);  
     return result;  
   }  
   
   void generateParenthesisHelper(int left, int right, string s, vector<string> &result) {  
     if (left == 0 && right == 0) {  
       result.push_back(s);        
     }  
     if (left > 0) {  
       generateParenthesisHelper(left - 1, right, s + "(", result);        
     }  
     if (right > left) {  
       generateParenthesisHelper(left, right - 1, s + ")", result);        
     }  
   }  
 };  

Letter Combinations of a Phone Number

来源：Leetcode

原帖：http://oj.leetcode.com/problems/letter-combinations-of-a-phone-number/

题目：
Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

代码：

 class Solution {  
 public:  
   vector<string> letterCombinations(string digits) {  
     if (digits.empty()) return {};  
     vector<string> mapping = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  
     string s;  
     vector<string> result;  
     letterCombinationsHelper(digits, mapping, s, result);  
     return result;  
   }  
     
   void letterCombinationsHelper(const string& digits, vector<string>& mapping, string& s, vector<string> &result) {  
     if (s.size() == digits.size()) {  
       result.push_back(s);  
       return;  
     }  
     string &letters = mapping[digits[s.size()] - '2'];   
     for (int i = 0; i < letters.size(); ++i) {  
       s.push_back(letters[i]);  
       letterCombinationsHelper(digits, mapping, s, result);  
       s.pop_back();  
     }  
   }  
 };  
   
 class Solution {  
 public:  
   vector<string> letterCombinations(string digits) {  
     string mapping[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  
     vector<string> res;  
     if (digits.empty()) return {};  
     for (int i = 0; i < digits.size(); ++i) {  
       vector<string> tmp;  
       auto& letters = mapping[digits[i] - '2'];  
       for (int j = 0; j < letters.size(); ++j) {  
         if (res.empty()) {  
           string s(1, letters[j]);  
           tmp.push_back(s);   
           continue;  
         }  
         for (int k = 0; k < res.size(); ++k) {  
           tmp.push_back(res[k] + letters[j]);  
         }  
       }  
       res = move(tmp);  
     }  
     return res;  
   }  
 };  

Longest Common Substring

来源：nineChapter

原帖：nineChapter; dp

题目：
state: f[i][j]表示前i个字符配上前j个字符的LCS‘的长度 (一定以第i个和第j个结尾的LCS’)
function: f[i][j]  = f[i-1][j-1] + 1 // a[i] == b[j]
                  = 0 // a[i] != b[j]
intialize: f[i][0] = 0
            f[0][j] = 0
answer: MAX(f[0..a.length()][0..b.length()]

代码：

 int longestCommonSubstring(string s1, string s2) {  
   int M = s1.size(), N = s2.size();   
   vector<vector<int> > dp(M, vector<int>(N,0));  
   for (int i = 0; i <= M; ++i)  
     dp[i][0] = 0;  
   for (int j = 0; j <= N; ++j)  
     dp[0][j] = 0;  
   int maximum = 0;  
   for (int i = 1; i <= M; ++i) {  
     for (int j = 1; j <= N; ++j) {  
       if (s1[i - 1] == s2[j - 1]) {  
         dp[i][j] = dp[i - 1][j - 1] + 1;  
       } else {  
         dp[i][j] = 0;  
       }  
       maximum = max(maximum, dp[i][j]);  
     }  
   }  
   return maximum;  
 }  

Longest Increasing Subsequence

来源：nineChapter

原帖：nineChapter; dp

题目：
Longest Increasing Subsequence
1 1000 2 3 4
10 11 12 1 2 3 4 13

代码：

 int longestIncreasingSubsequence(const vector<int> &nums) {  
   vector<int> dp(nums.size(), 0);  
   dp[0] = 1;  
   unordered_map<int, vector<int> > map;  
   map[0] = {nums[0]};  
   for (int i = 1; i < nums.size(); ++i) {  
     for (int j = 0; j < i; ++j) {  
       if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {  
         map[i] = move(map[j]);  
         map[i].push_back(nums[i]);  
         dp[i] = max(dp[i], dp[j] + 1);  
       }  
     }  
   }  
   for (auto i : map[nums.size()-1]) cout << i << " ";  
   cout << endl;   
   return dp[nums.size() - 1];  
 }  
   
 int main() {  
   vector<int> nums = {1,2,4,3,2,7,8,9};  
   longestIncreasingSubsequence(nums);  
   return 0;  
 }