Letter Combinations of a Phone Number (C++ code)

LeetCode Letter Combinations of a Phone Number, Jan 27 '12

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"].

2->a,3->d 

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

void findpath(string &digits, int level, string &path, vector<string> &res, vector<string> &v){
       if(level == digits.length()) {
          res.push_back(path);
          return;
       }
      if(digits[level] == 1 || digits[level] == 0) findpath(digits,level+1,path,res,v);
      else{
         for(int i = 0; i < v[digits[level]].length(); i++){
          path.push_backdigits[level][i]);
          findpath(digits,level+1,path,res,v);
          path.pop_back();
        }
      }
}

 vector<string> letterCombinations(string digits) {
       vector<string> res;
       string path;
       vector<string> v(10);
       v[1] = "abc";
       v[2] = "def";
       v[3] = "ghi";
       v[4] = "jkl";
       v[5] = "mno";
       v[6] = "pqrs";
       v[7] = "tuv";
       v[8] = "wxyz";
       findpath(digits, 0, path, res, v);
    
       return res;
    }

merge k sorted list of intervals(C++ code)

n个人，每个人有m个时间段，每个时间段代表这个人是忙碌的
例如：
A： （1， 2）， （7， 9）
B： （1， 3）， （4， 5）
C: （12， 15）
D： （16， 20）
每个人的时间段都是排好序的(时间段是inclusive的， 抱歉没说清楚)。
输出：时间段的集合，在这个时间段里，有人是忙碌的。
上面例子中的输出就应该是：{（1， 5）， （7， 9）， （12， 20）}
----------------
思路：用heap存每行的第一个元素，每次取最小值，和相关的interval merge, 产生结果的interval .
假如n行m列，时间复杂度为O((n*m)log n  )(每个元素都会被推进和推出heap)

0. struct Interval{  
1.   
2. int left;  
3.   
4. int right;  
5.   
6. Interval *next;  
7.   
8. }  
9.   
10. vector<Interval> mergeInterval(vector<Interval *> &input ){  
11.   
12.   vector<Interval> res;  
13.   
14.   priority_queue<Interval*, comp> q;  
15.   
16.   for(int i = 0; i < input.size(); i++){  
17.   
18.     q.push(input[i]);  
19.   
20.     input[i] = input[i]->next;  
21.   
22.  }  
23.   
24. }  
25.   
26. while(!q.empty()){  
27.   
28.  Interval* I = q.top();  
29.   
30.  q.pop();  
31.   
32.  if(I->next) q.push(I->next);   
33.   
34.  while(!q.empty){  
35.   
36.    Interval *J = q.top;  
37.   
38.    if(J->left <= I->right ){  
39.   
40.      q.pop(); I->right = max(J->right, I->right);  
41.   
42.      if(J->next) q.push(J->next);   
43.   
44.    }  
45.   
46.    else {  
47.   
48.      res.push_back(*I);   
49.   
50.      break;  
51.   
52.    }  
53.   
54.  }  
55.   
56.   
57.   
58. res.push_back(*I);  
59.   
60.   
61.   
62. return res;   
63.   
64. }  

word ladder(C++ code)

LeetCode Word Ladder, Feb 11
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. 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.

思路：bfs,我用map来记录每个单词的depth的，大集合用了1932ms...其实不需要用map，可以用两个int记录当前层和下一层的节点数，当前层用完后，当前层移到下一层，下一层则重设为0，同时update depth。这样稍微快一点，1.4s左右。。

0. int ladderLength(string start, string end, unordered_set<string> &dict) {    
1.     
2.         if(start == end) return 1;    
3.         //prev counts words of current level, next counts for next level, depth denotes current level.  
4.         //same level means same distance from original word.  
5.         int depth = 1, prev =1, next = 0;     
6.         //queue stores intermediate words  
7.         queue<string> q;    
8.      
9.         q.push(start);    
10.         //set stores visited words to avoid redundant work.  
11.         unordered_set<string> visited;    
12.     
13.         visited.insert(start);    
14.     
15.   while(!q.empty()) {    
16.     
17.     string cur = q.front();    
18.     
19.     q.pop(); prev--;    
20.     //for each letter in the intermediate word, iterate over 26 options and push it into queue if it's a word,   
21.     //don't forget to update level count next.   
22.     for(int i = 0; i < cur.length(); i++){    
23.     
24.        for(int j = 0; j < 26; j++){    
25.     
26.          string mid = cur;    
27.     
28.          mid[i] = 'a' + j;    
29.     
30.          if(dict.find(mid) != dict.end() && visited.find(mid) == visited.end()){    
31.     
32.            visited.insert(mid);    
33.     
34.            q.push(mid);    
35.     
36.            next += 1;    
37.     
38.            if(mid == end) return depth + 1;    
39.          }    
40.        }     
41.    }    
42.     
43.   if(prev == 0) {prev = next; next = 0; depth++;}    
44.    
45.   }    
46.         return 0;    
47. }    

-------------用map的---------------

int ladderLength(string start, string end, unordered_set<string> &dict) {

        if(start == end) return 1;
        map<string,int> visited;

        queue<string> q;

        q.push(start);

        visited[start] = 1;

      

while(!q.empty()) {

    string cur = q.front();

    q.pop();

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

       for(int j = 0; j < 26; j++){

         string mid = cur;

         mid[i] = 'a' + j;

         if(mid == end) return visited[cur] + 1;

         if(dict.find(mid) != dict.end() && visited.find(mid) == visited.end()){

           visited[mid] = visited[cur] + 1;

           q.push(mid);

     

         }

       }

   }
}

        return 0;
    }

Sum Root to Leaf NumbersFeb 191675 / 4693
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

-----------乌龙的分割线oops..--------------正解随后---------------
我这什么记性啊，看完题目去睡觉，然后睡前想了下，自以为想出来了，今天早上唰唰写好 code, 放到OJ一测试，没过，仔细一看，原来我答非所问，完全做的另外一道题！！为了不浪费劳动成果，还是贴在这把，我做的题是：对每条root-to-leaf path求和，最后得出总和，比如
  1
2  3
得到的就是(1+2)+(1+3) = 7.

void postorder(TreeNode *root, int &sum, unordered_map<TreeNode *, int> &count){
   if(!root) return;
   if(!root->left && !root->right) {
     count[root] = 1;
     sum += root->val;
     return;
  }
   postorder(root->left, sum, count);
   postorder(root->right,sum,count);
   count[root] = 0;
   if(root->left) count[root] +=  count[root->left];
   if(root->right) count[root] += count[root->right];
   sum += root->val * count[root];
  
}

int sumNumbers(TreeNode *root) {
       int sum = 0;
unordered_map<TreeNode *, int> count;
       postorder(root, sum,count);
       
      return sum;
    }

------------------正解my solution-------------------后面有更优解-------------
还好思路也差不多，还更简单，建个map对每个node重新赋值就好了
void preorder(TreeNode *root, int &sum, unordered_map<TreeNode *, int> &num){
   if(!root->left && !root->right) {
     sum += num[root];
     return;
  }

  if(root->left) {
     num[root->left] = num[root] *10 + root->left->val;
     preorder(root->left, sum, num);
  }                  
  if(root->right) {
     num[root->right] = num[root] *10 + root->right->val;
     preorder(root->right, sum, num);
  }
}

int sumNumbers(TreeNode *root) {
      if(!root) return 0;
      int sum = 0;
unordered_map<TreeNode *, int> num;
      num[root] = root->val;
       preorder(root, sum, num);
       
      return sum;
    }
-------------最优解best solution-----------------
写完上面的解后，觉得这个map挺多余的，应该能去掉，但是懒得弄了，于是找了个别人的code(lu-an gong at Leetcode)，就是用一个动态number代替map,每次做到leaf node这个number就回去一个，如果做完右子树再回去一个。

0. int sumNumbers(TreeNode *root) {  
1.     int num = 0, sum = 0;  
2.     sumNumbersImpl(root, num, sum);  
3.     return sum;  
4. }  
5.   
6. void sumNumbersImpl(TreeNode *root, int& num, int& sum) {   
7.     if (root == nullptr) return;   
8.     num = num * 10 + root->val;   
9.     if (root->left == nullptr && root->right == nullptr) {   
10.        sum += num;   
11.     }   
12.     else {   
13.        sumNumbersImpl(root->left, num, sum);   
14.        sumNumbersImpl(root->right, num, sum);   
15.     }   
16.     num /= 10;   
17. }  

palindrome partitioning I,II(C++ code)

LeetCode Palindrome Partitioning, Feb 28,13

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

void partition(string s, int level, vector<string> &path, vector<vector<string>> &res, bool **A){

   if(level == s.length()) {

       res.push_back(path); return;

   }

   for(int i = level; i < s.length(); i++){

       if(A[level][i]){

          path.push_back(s.substr(level, i-level+1));

          partition(s,i+1,path,res,A);

          path.pop_back(); 

       }

   } 

} 

vector<vector<string>> partition(string s) {
        vector<vector<string>> res;

        vector<string> path;

        bool **A = new bool*[s.length()];

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

           A[i] = new bool[s.length()]; 

           A[i][i] = true; 

           if(i > 0) A[i-1][i] = (s[i] == s[i-1])? true :false;

           for(int j = 0; j < i-1; j++){

             if(!A[j+1][i-1]|| s[i] != s[j]) A[j][i] = false;

             else A[j][i] = true;

           }

        }

        partition(s, 0,path, res,A);

for(int i = 0; i < s.length(); ++i) {
    delete [] A[i];
}
delete [] A; 

      return res;

        
    } 

Palindrome Partitioning II， Mar 12

Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.


暴力解法超时了。。
void countcut(string s, bool **A, int level, int &minsofar, int count){
  if(level == s.length()) {
   minsofar = min(minsofar, count-1);
   return;
 }
 for(int i = level; i < s.length(); i++){
  if(A[level][i]) {
      countcut(s,A,i+1,minsofar,count+1);
  }
 }

}
 int minCut(string s) {
       int minsofar = s.length() - 1;
   

        bool **A = new bool*[s.length()];

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

           A[i] = new bool[s.length()]; 

           A[i][i] = true; 

           if(i > 0) A[i-1][i] = (s[i] == s[i-1])? true :false;

           for(int j = 0; j < i-1; j++){

             if(!A[j+1][i-1]|| s[i] != s[j]) A[j][i] = false;

             else A[j][i] = true;

           }

        }

       countcut(s,A,0,minsofar, 0);

for(int i = 0; i < s.length(); ++i) {
    delete [] A[i];
}
delete [] A; 

return minsofar; 

       
    }

换个想法，按切的刀数从小到大考虑，对平均情况会快些， 但考虑到最坏情况跟暴力解法一样，大集合还是超时了。。

---------------

bool countcut(string s, bool **A, int count, int start){

 if(count == 0) return A[start][s.length()-1];

 for(int i = start; i < s.length(); i++){

   if(A[start][i]) {

        if(countcut(s,A,count-1,i+1)) return true;

   }

 } 

 return false;

}

int minCut(string s) {
       int minsofar = s.length() - 1;

   
bool **A = new bool*[s.length()];  
for(int i = 0; i < s.length(); i++){ 
 A[i] = new bool[s.length()]; A[i][i] = true;  
 if(i > 0) A[i-1][i] = (s[i] == s[i-1])? true :false;  
 for(int j = 0; j < i-1; j++){  
   if(!A[j+1][i-1]|| s[i] != s[j]) A[j][i] = false; 
   else A[j][i] = true; } 
 }

int count;
for( count = 0; count < s.length(); count++){
 if(countcut(s,A,count,0)) break;
}

for(int i = 0; i < s.length(); ++i) { 
 delete [] A[i]; }  
delete [] A;   

return count;
       
    }

----------
正解原来是DP，能用DP一定不要用recursion啊，下面这个来自leetcode ID wangya,自己懒得写了。。

int minCut(string str){

        int leng = str.size();

        int dp[leng+1];
        bool palin[leng][leng];

      for(int i = 0; i <= leng; i++)
        dp[i] = leng-i;
        for(int i = 0; i < leng; i++)
            for(int j = 0; j < leng; j++)
                palin[i][j] = false;

      for(int i = leng-1; i >= 0; i--){
        for(int j = i; j < leng; j++){
          if(str[i] == str[j] && (j-i<2 || palin[i+1][j-1])){
            palin[i][j] = true;
            dp[i] = min(dp[i],dp[j+1]+1);
          }
        }
      }
      return dp[0]-1;
    }

Find nearest m nodes for a key in BST(C++ code)

面试题。
先写个O(n)的，用in order traversal, 用queue存m个，每次尾巴新进来一个，跟头做比较，因为queue里面的元素是in order的， 如果新尾巴比头更接近key，就把头挤掉。如果不比头更接近，说明已经完成，就return queue。

queue<node *> findmclosest(node * root, int key,  int m){
      queue<node *> q;
     findhelper(root, key, q, m);
     return q;
}

void findhelper(node *root, int key, queue<node *> q, int m){
     if(root == NULL) return;
     findhelper(root->left, key, q, m);
     if(q.size() < m) q.push(root->val);
     else{
         int diff = abs(root->val - key);
         if(diff >= abs(q.front() - key) ) return;
         else{
            q.pop();
            q.push(root);
        }
     }
     findhelper(root->right, key, q, m);
}


接下来是复杂一点的O(m*log n)，思路是先找到key，一边找一边用两个m sized queue存经过的节点，
pre: 存放比key小的节点
next:存放比key大的节点
pre:每次pop元素后，要考虑该元素的左子树， next:每次pop后，要考虑该元素的右子树
用logn的时间找到节点后，注意到pre和next都是尾巴上的点跟key值最接近，就直接从尾巴一个一个取就好了。
 //push next(min element of right subtree) and push pre(max element of left subtree)
void nextpush(node *tmp, deque<node *> &next)
while(tmp){
     if(next.size() >= m) next.pop_front();
     next.push(tmp);
     tmp = tmp->left;
   }
}

void prepush(node *tmp, deque<node *> &pre)
while(tmp){
     if(pre.size() >= m) pre.pop_front();
     pre.push(tmp);
     tmp = tmp->right;
   }
}

//find key node
void findkey(node *root, int key, deque<node *> &pre, deque<node *> &next, int m){
  if(!root) return;
  if(root->val <= key){
    if(pre.size() >= m) pre.pop();
    pre.push(root); 
    findkey(root->right, key, pre, next, m);
  }
 if(root->val >= key){
   if(next.size() >= m) next.pop();
    next.push(root); 
    findkey(root->left, key, pre, next, m); }
}


vector<int> findmclosest(node *root, int key, int m){
  int i = 0;
  vector<int> res;
  deque<node *> pre;
  deque<node *>next;
  node *tmp;
  findkey(root, key, pre,next, m);
//deal with key found in tree
 if(!pre.empty() && !next.empty &&pre.back() == next.back()){
   res[i++] = key;
   tmp = pre.back()->left;
   pre.pop_back();
   prepush(tmp,pre);
   tmp = next.back()->right;
   next.pop_back();
   nextpush(tmp,next);
 }

//start comparing and setting up result nodes.
while(!pre.empty() && !next.empty()){
  int prenode = pre.back();
  int nextnode = next.back();
  if(key - prenode->val > nextnode->val - key ) {
      res[i++] = nextnode->val;
      if(i == m) return res;
      next.pop_back();
      nextpush(nextnode->right, next);
  }
 else{
     res[i++] = prenode->val;
      if(i == m) return res;
      pre.pop_back();      prepush(prenode->left, pre);
  }
}

//when pre/next used up before getting m nodes

while(!pre.empty()){
   res[i++] = prenode->val;
      if(i == m) return res;
      pre.pop_back();   
   prepush(prenode->left, pre);
}

while(!next.empty()){
   res[i++] = nextnode->val;
      if(i == m) return res;
      next.pop_back();   
   nextpush(nextnode->right, next);
}

 return res;

}

KMP algorithm C++ code

写个代码在这里吧,based on wiki。
从字符串S中找字符串W。
主要思路是：S开始match的位置sb和已经match的位数w，如果匹配就w++,如果不匹配，sb移动到next(sb) = sb + w - T[w], 此时前T[w]位已经匹配了，因此从w = T[w]位开始考察匹配。

//set up help array to find next j, assume that W.length() >=2. T[i] = the max length of equal pre-/suf- substring from W[0]->W[i-1](the first i digits).

void prefun(string W, int &T[]){
  T[0] = -1; T[1] = 0;
  int ind = 0, i = 2;
  while( i < W.length()){
     if(W[i-1] == W[ind]) {
           T[i] = ind + 1; ind++; i++;
     }
    else if(ind > 0) ind  = T[ind];
    else {T[i] = 0; i++;}
  }
  
}

//KMP search algorithm, I will write only the case W.length()>1.

int kmp_search(string S, string W) {
 int[] T = new int[W.length()];
 int sb = 0, w = 0;  //sb is the begining of match in S, w is the cur matching pos of w.
while(sb + w < S.length() ){
  if(S[sb+w] == W[w])  {
      if(w == W.length() - 1) return sb;
      else w++;
  }
 else {
   sb = sb + w  - T[w];
   if(T[w] == -1) w = 0;
   else w = T[w];
  }
}
}
 return S.length();
}

hash table implementation

这个链接很不错：
http://www.algolist.net/Data_structures/Hash_table/Chaining

graph split （C++）

2维0，1矩阵。判断有多少个封闭的全是0的area。DFS，BFS的方法都要写。

void dfs(const vector<vector<int>> &G, int i, int j){
  if(i<0 || i >= rown || j<0 || j >= coln) return;
  if(G[i][j] == 1 || visited[i][j] == 1) return;
  visited[i][j] = 1;
  dfs(G, i - 1, j);
  dfs(G, i + 1, j);
  dfs(G, i, j+1);
  dfs(G, i, j-1);
}

int count(vector<vector<int>>G){
  if(G.empty()) return 0;
  int count;
 int rown = G.size(), coln = G[0].size;
 vector<vector<int>> visited(rown, vector<int>(coln,0));
  for(i = 0; i < rown; i++) {
    for(j = 0; j < coln; j++){
      if(visited[i][j] == 0&& G[i][j] == 0) {  
            count++;
          dfs(G,i, j, rown, coln);
        }
      }
    }

return count;

}

-------------------
void bfs(const vector<vector<int>> &G, int i, int j){
  queqe<pair<int,int>> q;
  q.push(make_pair(i,j));
  while(!q.empty()){
     i = queue.front().first; j = queue.front().second;
     queue.pop();
     visited[i][j] = 1;
     if(i > 0 && visited[i-1][j] == 0 && G[i-1][j] == 0) queue.push(make_pair(i-1,j));
     if(j> 0 && visited[i][j-1] == 0 && G[i][j-1] == 0) queue.push(make_pair(i,j-1));
     if(i < rown - 1 && visited[i+1][j] == 0 && G[i+1][j] == 0) queue.push(make_pair(i+1,j));
     if(j < coln - 1 && visited[i][j+1] == 0&& G[i][j+1] == 0) queue.push(make_pair(i,j+1));
  }
 

}


int count(vector<vector<int>>G){
  if(G.empty()) return 0;
  int count;
 int rown = G.size(), coln = G[0].size;
 vector<vector<int>> visited(rown, vector<int>(coln,0));
  for(i = 0; i < rown; i++) {
    for(j = 0; j < coln; j++){
      if(visited[i][j] == 0&& G[i][j] == 0) {  
            count++;
          bfs(G,i, j, rown, coln);
        }
      }
    }

return count;

}

Text Justification(C++ code)

LeetCode Text Justification, Apr 3 '12
Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.
Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.


    

0. //fill each line  
1.   
2. void fill(vector<string> &words, int start, int end, int num, vector<string> &res){  
3.   
4.   string line;  
5.   
6.   if(end == words.size() -1 || start == end){  
7.   
8.     while(start < end){line.append(words[start++]); line.push_back(' ');}  
9.   
10.     line.append(words[end]);  
11.   
12.     while(num-- > 0) line.push_back(' ');  
13.   
14.     res.push_back(line); return;  
15.   }  
16.   
17.  int spacen = num/(end - start) + 1, extra = num%(end - start);  
18.   
19.  while(start < end){  
20.   
21.    int pad = spacen;  
22.   
23.    if(extra-- > 0) pad += 1;  
24.   
25.    line.append(words[start]);  
26.   
27.    while(pad-- > 0) line.push_back(' ');  
28.   
29.    start++;  
30.   
31.   }  
32.   
33.   line.append(words[end]);  
34.   
35.   res.push_back(line);  
36.   
37. }  
38.   
39. //separate each line  
40.   
41. void fullJustify(vector<string> &words, int start, int L, vector<string> &res){  
42.   
43.    if(start >= words.size()) return;  
44.   
45.    int len = 0, cur = start, end;  
46.   
47.    while(cur < words.size()){  
48.   
49.       if(len + words[cur].length() == L) {len = L;  end = cur; cur++; break;}  
50.   
51.       if(len + words[cur].length() < L){  
52.   
53.              if(cur == words.size() - 1){end = words.size() - 1;len += words[cur].length();}  
54.   
55.              else len += words[cur].length() + 1;  
56.   
57.              cur++;  
58.   
59.              }  
60.   
61.       else {end = cur - 1; len -= 1; break;}  
62.   
63.     }  
64.   
65.    fill(words,start, end, L - len, res);  
66.   
67.    fullJustify(words, cur, L, res);  
68.   
69. }  
70.   
71. //main function  
72.   
73. vector<string> fullJustify(vector<string> &words, int L) {  
74.   
75.         vector<string> res;  
76.   
77.         if(words.empty()) {  
78.   
79.           string str(L,' ');  
80.   
81.           res.push_back(str);  
82.   
83.         }  
84.   
85.         fullJustify(words, 0, L, res);  
86.   
87. return res;  
88.   
89. }   

serialization/deserialization of a binary tree(C++ code)

Leetcode Serialization/Deserialization of a Binary Tree

Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called ‘serialization’ and reading back from the file to reconstruct the exact same binary tree is ‘deserialization’.

Assume we have a binary tree below:

    _30_ 
   /    \    
  10    20
 /     /  \ 
50    45  35

Using pre-order traversal, the algorithm should write the following to a file:

30 10 50 # # # 20 45 # # 35 # #

这个OJ没有，当面试题准备做做。

0. void writeBinaryTree(TreeNode *p, ostream &out) {  
1.   
2.   if(!p) {out<<"# "; return;}  
3.   
4.   out<<p->val<<" ";  
5.   
6.   writeBinaryTree(p->left, out);  
7.   
8.   writeBinaryTree(p->right, out);  
9.   
10. }   

 

0. void readBinaryTree(TreeNode *&p, ifstream &fin){  
1.   
2.   if(fin.eof()) return;  
3.   
4.   string value;  
5.   
6.   value<<fin;  
7.   
8.   int number ;  
9.   
10.   if( istringstream(value)>>number){  
11.   
12.   p = new TreeNode(number);  
13.   
14.   readBinaryTree(p->left, fin);  
15.   
16.   readBinaryTree(p->right,fin);  
17.   
18.   }  
19.   
20. }   

Longest Palindromic Substring(C++ code)

LeetCode Longest Palindromic Substring, Nov 11 '11

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

思路：回文的递归在于：去掉两头还是回文。基于这个思路，对每个点i, 计算以i为中心(奇数回文)或者以i为中心偏右(偶数回文)能扩展的最长长度，一旦出现不是回文，break就行了。最坏情况下还是要O(n^2),但是比我一开始用数组存结果快，能过大集合了。

0. string longestPalindrome(string s) {  
1.   
2.     string res;  
3.   
4.     if(s.empty()) return res;  
5.   
6.     int start = 0, n = s.length();  
7.   
8.     int longest = 1;  
9.   
10.     for(int i = 1; i < n; i++){  
11.   
12.        //j in center  
13.        for(int j = 1; j <= min(i, n-i-1); j++){  
14.   
15.           if(s[i+j] != s[i-j]){  
16.   
17.              if( longest < 2*j - 1){  
18.   
19.                start = i - j + 1;  longest = 2*j - 1;  
20.              }  
21.              break;  
22.          }  
23.   
24.          if(j == min(i,n-i-1) && s[i+j] == s[i-j]){  
25.   
26.              if(longest < 2*j + 1 ){  
27.   
28.                start = i - j ;  longest = 2*j + 1;  
29.              }  
30.          }  
31.      }  
32.   
33.       //i in right center  
34.       for(int j = 0; j < min(i,n-i); j++ ){  
35.   
36.          if(s[i+j]!= s[i-1-j]){  
37.   
38.              if(longest < 2*j ){  
39.   
40.                start = i - j ;  longest = 2*j ;  
41.              }  
42.   
43.              break;  
44.          }  
45.   
46.          if(j == min(i,n-i) - 1 && s[i+j] == s[i-1-j]){  
47.   
48.              if(longest < 2*(j+1) ){  
49.   
50.                start = i - 1 - j ;  longest = 2*(j+1) ;  
51.              }  
52.          }  
53.       }  
54.   }  
55.   
56.  res = s.substr(start, longest);  
57.   
58.  return res;  

这是一开始写的用数组存结果的，这个方法的缺点是有些不必要的计算，比如abca知道b!=c之后，还是要再设定abca的值为false，而用上面改进方法，知道b!=c后，就不用再考虑abca了。

   string longestPalindrome(string s) {
     string res;
     int start = 0, end = 0, longest = 1;
     if(s.empty()) return res;
     vector<vector<bool> > A(s.length(),vector<bool>(false));

     for(int j = 0; j < s.length(); j++){

          A[j][j] = true;

        for(int i = j - 1; i >= 0; i--){

          if(i == j - 1 && s[i] == s[j])  {

             A[i][j] = true;

             if(longest < (j - i + 1)) {

                start = i; end = j; longest = j - i + 1;

             }

          }

          else if(i == j - 1 && s[i] != s[j]) A[i][j] = false;

          else if(A[i+1][j-1] == true && s[i] == s[j]) {

             A[i][j] = true;

             if(longest < (j - i + 1)) {

                start = i; end = j; longest = j - i + 1;

             }

          }

          else A[i][j] = false;

        }

     }

res = s.substr(start, longest);



return res;

            
 }

longest common prefix (C++ code)

Leetcode Longest Common Prefix, Jan 17 '12

Write a function to find the longest common prefix string amongst an array of strings.

Tips: 空字符串不能用NULL返回，新建了一个string才返回成功的。

0. //find common prefix of two strings  
1.   
2. string  findcommon(string first,  string second){  
3.   
4.    string res;  
5.   
6.    for(int i = 0; i < first.length(); i++){  
7.   
8.       if(i >= second.length()) break;  
9.   
10.       if(first[i] != second[i]) break;  
11.   
12.       else res.push_back(first[i]);  
13.   
14.   }  
15.   
16.    return res;  
17.   
18. }  
19.   
20. //main function  
21.   
22.  string longestCommonPrefix(vector<string> &strs) {  
23.   
24.         string res;  
25.   
26.         if(strs.empty()) return res;  
27.   
28.        res = strs[0];  
29.   
30.         for(int i = 1; i < strs.size(); i++){  
31.   
32.            string temp = strs[i];  
33.   
34.             res = findcommon(res, temp);  
35.   
36.         }  
37.   
38.                    
39.   
40.       return res;  
41.   
42.     }  

Length of Last Word(C++ code)

LeetCode Length of Last Word, Mar 27 '12
Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
For example,
Given s = "  Hello  World  ",
return 5.

 思路：细节啊细节，俺细节一向很差。。

  int lengthOfLastWord(const char *s) {

   if(!s) return 0;
    int start = 0, cur = 0, length = 0;

   while(s[cur] != '\0'){

       if(s[cur] == ' ') {length = cur - start;

          while(s[cur] == ' ')cur++;
           if(s[cur] == '\0') return length;
          start = cur; continue;}   

           cur++;

   }

  return cur - start;
    
    }

trie C++ implementation

下面这个帖子很赞：
http://login2win.blogspot.com/2011/06/c-tries.html

Convert Sorted Array to Binary Search Tree (C++ code)

LeetCode Convert Sorted Array to Binary Search Tree, Oct 2 '12
 G家面试题，写一个吧。
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

TreeNode *sortedArrayToBST(vector<int> &num, int start, int end){
    if(start > end) return NULL;
    int mid = (start + end)/2;
    TreeNode *root = new TreeNode(num[mid]);
    root->left = sortedArrayToBST(num, start, mid - 1);
    root->right = sortedArrayToBST(num, mid+1, end);

   return root;
}


TreeNode *sortedArrayToBST(vector<int> &num) {
       if(num.size() == 0) return NULL; 

       return sortedArrayToBST(num, 0, num.size() - 1); 
       
    }

Largest rectangle in Histogram (C++ code)

LeetCode Largest Rectangle in Histogram, Apr 23 '12
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

思路：这题太tricky了，看了别人的code还不懂，跑了几个test cases才明白的:(

 from luckynoob: http://www.mitbbs.com/article/JobHunting/32272665_0.html

int largestRectArea(vector<int> &h) {
        stack<int> p;
        int i = 0, m = 0;
        h.push_back(0);
        while(i < h.size()) {
            if(p.empty() || h[p.top()] <= h[i])
                p.push(i++);
            else {
                int t = p.top();
                p.pop();
                m = max(m, h[t] * (p.empty() ? i : i - p.top() - 1 ));
            }
        }
        return m;
    }

clone graph(c++ code)

LeetCode clone graph

Clone a graph. Input is a Node pointer. Return the Node pointer of the cloned graph.

A graph is defined below:
struct Node {
vector<Node *> neighbors;
}

 思路1：BFS，注意这种方法需要graph是connected的。

Node *clonegraph(Node *graph){
  if(graph == NULL) return NULL;
  map<Node *, Node *> visited;
  queue<Node *> q;
  q.push(graph);
  Node *clonegraph = new Node();
  visited[graph] = clonegraph;
  while(!q.empty()){
    Node *cur = q.front();
    vector<Node *> curadj = cur->neighbors;
    q.pop();
    for(int i = 0; i < curadj.size(); i++){
        if(visited.find(curadj[i]) == visited.end()){
            Node *adj = new Node();
           q.push(curadj[i]);
            visited[cur]->neighbors.push_back(adj);
            visited[curadj[i]] = adj;            
        }
       else visited[cur]->neighbors.push_back(visited[curadj[i]]);
    }

 }
  return clonegraph;
}

思路2： DFS，同上，需要所有nodes reachable from given node.
Node *dfs(Node *graph, map<Node *, Node *>  &visited){
  if(visited.find(graph) != visited.end()) return visited[graph];
  Node *clonegraph = new Node();
  visited[graph] = clonegraph;
  for(int i = 0; i < graph->neighbors.size(); i++){
    Node *neighbor = graph->neighbors[i];
    clonegraph->neighbors.push_back(dfs(neighbor, visited));
 }

 return clonegraph;
}

Node *clonegraph(Node *graph){
  if(!graph) return NULL;
  map<Node *,Node *>visited;
  return dfs(graph, visited);
}

Jump game I, II (C++ code)

LeetCode Jump Game, Mar 25 '12
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
 思路：简单递归。偶第二个一次写完bug free的代码，泪~~~

 bool canJump(int A[], int n) {
        if(n <= 1) return true;
        int dist = 0;
        for(int i = n-2; i >= 0; i--){
           dist++;
           if(A[i] >= dist) {dist = 0;}
        }
       if(dist > 0) return false;
      return true;
       
    }

Jump Game II, Mar 17 '12

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

思路：每次在可跳的位置中选maximum span，并把对应的结束位置记为下一次跳的newend range.
又一次bug free, 泪~~看来我对int还是很熟的, :P

int jump(int A[], int n) {
    if(n <= 1) return 0;
    int start = 0, end = 0, count = 0;   
    
   while(end < n-1){
      int oldend = end;
      while(start <= oldend) {
        end = max(end, start + A[start]);
        start++;
      }
     count++;
   }

return count;
}

Interleaving String (C++ code)

LeetCode Interleaving String, Aug 31 '12
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
思路：用递归超时了，只好用DP，整了个矩阵存结果。
bool isInterleave(string s1, string s2, string s3) {
     if(s1.length() + s2.length() != s3.length()) return false;
     int i, j;
     vector<vector<int> > A(s1.length()+1,vector<int>(s2.length()+1));
     A[0][0] = 1;
     for(i = 1; i < s1.length() + 1; i++){
         if(s1[i-1] == s3[i-1]) A[i][0] = A[i-1][0];
     }
  
    for(j = 1; j < s2.length() + 1; j++){
         if(s2[j-1] == s3[j-1]) A[0][j] = A[0][j-1];
     }

     for(i =1; i < s1.length() + 1; i++ ){
      for(j =1; j < s2.length() + 1; j++){
        if((s1[i-1] == s3[i+j-1] && A[i-1][j] == 1) || (s2[j-1] == s3[i+j-1] && A[i][j-1] == 1) )
           A[i][j] = 1;
        }
    }

   if(A[s1.length()][s2.length()] == 1) return true;
   else return false;
}

Insert Interval (C++ code)

LeetCode Insert Interval, Mar 27 '12
 难度4，出现频率5
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
 思路： 我写的这个好复杂呀。。(后面有简单的)
* struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
       int from =0, to =0,i,left,right;

 if(intervals.empty() || newInterval.end < intervals[0].start){

      intervals.insert(intervals.begin(), newInterval);

      return intervals;

}

if(newInterval.start > intervals.back().end){

  intervals.push_back(newInterval);

  return intervals;

}

      for(i = 0; i < intervals.size(); i++){

         if(newInterval.start < intervals[i].start){

             if(i > 0 && newInterval.start <= intervals[i-1].end) {

                from = i-1;

                left = intervals[i-1].start;

             }

             else{

               from = i;

               left = newInterval.start;

            }

             break;

        }
        from = i;
        left = intervals[i].start;

    }

     for(i = from; i < intervals.size(); i++){

         if(newInterval.end < intervals[i].end){

            if(i > 0 && newInterval.end < intervals[i].start) {

              to = i - 1;

              right =newInterval.end;

            }

          else{

             to = i;

             right = intervals[i].end;

          }
          break;

        }
        to = i;
        right = newInterval.end;

    }

Interval *toadd = new Interval(left,right);  

intervals.erase(intervals.begin() + from, intervals.begin() + to + 1);

intervals.insert(intervals.begin() + from, *toadd);

return intervals;
    }


简单版： 为毛别人能写的如此简单呢，学习~~下面这个是从luckynoob那里看来的（稍作修改）。

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { 

   vector<Interval> res; 
   int i=0;
   int n = intervals.size(); 
 
   while(i < n && newInterval.start > intervals[i].end)
      res.push_back(intervals[i++]);
 
   if(i < n) newInterval.start = min(newInterval.start, intervals[i].start);
 
   while( i < n && newInterval.end >= intervals[i].start ) 
        i++;
 
   if(i > 0) newInterval.end =  max(newInterval.end, intervals[i-1].end);
 
   res.push_back(newInterval); 
 
   while(i < intervals.size())
 
      res.push_back(intervals[i++]);
 
 return res;
 
} 

然后我又写了个修改输入array不需要额外空间的： 

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {    
   int i=0, from, to;
   int n = intervals.size(); 
 
   while(i < n && newInterval.start > intervals[i].end)
      i++;
   from = i; 
   if(i < n) newInterval.start = min(newInterval.start, intervals[i].start);
 
   while( i < n && newInterval.end >= intervals[i].start ) 
        i++;
   to = i - 1;
   if(i > 0) newInterval.end =  max(newInterval.end, intervals[i-1].end); 
 
   if(from <= to) intervals.erase(intervals.begin()+ from, intervals.begin()+ to + 1);

   intervals.insert(intervals.begin()+from, newInterval); 

  
 return intervals;
 
}