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;

            
 }

Gray code (c++ code)

LeetCode Gray Code, May 20 '12
 难度4，出现频率2
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

     vector<int> grayCode(int n) {
        vector<int> res;
        if(n == 0){ res.push_back(0); return res;}
        vector<int> last = grayCode(n-1);
        res.insert(res.end(), last.begin(), last.end());
        vector<int> :: iterator it = last.end() - 1;
        while( it != last.begin() - 1 ){
            res.push_back((1<<(n-1)) + *it);
            it--;
        }       
     
      return res;             

    }

注：如果不用recursive function call,直接写是这个样子：
(copy from UniEagle)

  vector<int> grayCode(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> ret;
        ret.push_back(0);
        if (n <= 0) return ret;
        int mostbit = 1;
        for(int i = 1; i <= n; ++i) {
            for(int k = ret.size() - 1; k >= 0; --k) {
                int v = ret[k];
                ret.push_back(v | mostbit);
            }
            mostbit = mostbit << 1;
        }
        return ret;
    }

generate parentheses (C++ code)

LeetCode Generate Parentheses, Feb 13 '12
 难度3， 出现频率4


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:
"((()))", "(()())", "(())()", "()(())", "()()()"

思路：写了个简单的递归算法。

void generate(int n, vector<string> &res, string path, int left, int right){
   if(left == n && right == n){
     res.push_back(path);
     return;
   }
   if(left == right) {
     path.push_back('('); 
     generate(n,res,path,left+1,right);
   }
   else if(left == n) {
           path.push_back(')');
           generate(n,res,path,left,right+1);
        }
   else{
     path.push_back('(');
     generate(n,res,path,left+1, right);
     path.back() = ')';
     generate(n,res,path,left,right+1);
    
   }

}

 vector<string> generateParenthesis(int n) {
       vector<string> res;
       string path;
       generate(n,res,path,0,0);

       return res;
    }

Flatten binary tree to linked list

LeetCode Flatten Binary Tree to Linked List, Oct 14 '12
难度3，出现频率3
Given a binary tree, flatten it to a linked list in-place.
For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

思路： 用递归挺简单的--第一个一次通过bug free的代码，oh yeah! 

void flatten(TreeNode *root) {
      if(root == NULL) return;  

      flatten(root->left);

      flatten(root->right);

      TreeNode *temp = root->right; 

      root->right = root->left;

      root->left = NULL;
      TreeNode *cur = root;

      while(cur->right != NULL){

        cur = cur->right;

      } 

      cur->right = temp;
    } 

Binary Tree Maximum Path Sum (C++ code)

LeetCode Binary Tree Maximum Path Sum, Nov 8 '12
难度4，出现频率2
  Given a binary tree, find the maximum path sum.The path may start and end at any node in the tree.
For example: Given the below binary tree,

       1
      / \
     2   3

Return 6.
思路： recursion,在当前node, 设定函数返回包含当前node最长单向path，最大和可能是：
1，当前node + 左边最长单向(if >0) +右边最长单向(if >0)
2, 从左边node开始的最大和
3，从右边node开始的最大和
所以函数要返回的是包括当前node的最长单向和，同时在主体里更新最大和。

int maxDirected(TreeNode *root, int &maxSofar){
   if(!root) return 0;   
   int leftmax = maxDirected(root->left, maxSofar);
   int rightmax = maxDirected(root->right, maxSofar);
   int temp = root->val;
   temp = temp + max(leftmax,0) + max(rightmax,0); //temp is the max sum containing root;
   maxSofar = max(maxSofar, temp);

   int directedSum =  max(leftmax, rightmax );
  directedSum = root->val +max(directedSum,0);

   return directedSum ;
}

int maxPathSum(TreeNode *root){
   if(!root) return INT_MIN;
   int maxSofar = root->val ;
  
  maxDirected(root, maxSofar);

  return maxSofar;
}