Triangle (C++ code)

Leetcode Triangle Oct 30 '123620 / 9772
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.


好久没写code了，先练个暴力的：

void helper(vector<vector<int> > &triangle, int &res, int sum, int level, int pos){
  if(level == triangle.size()) {
        if(sum < res) res = sum;
        return;
  }
  helper(triangle, res, sum + triangle[level][pos], level + 1, pos);
  helper(triangle, res, sum + triangle[level][pos+1], level + 1, pos + 1);

}

int minimumTotal(vector<vector<int> > &triangle) {
        int  n = triangle.size();
        if(n == 0) return 0;
        int sum = triangle[0][0], res = INT_MAX;
        helper(triangle,res, sum, 1,0);

        return res;
    }

果然大集合没过，想了下，如果记录到达每个node的最短距离，可以省去很多重复计算，于是写了下面这个：
 int minimumTotal(vector<vector<int> > &triangle) {
       int  n = triangle.size();
       map<pair<int,int>, int> record;
       int res = INT_MAX;
       record[make_pair(0,0)] = triangle[0][0];
       for(int i = 1; i < n; i ++){
            record[make_pair(i,0)] = record[make_pair(i-1,0)] + triangle[i][0];
            record[make_pair(i,i)] = record[make_pair(i-1,i-1)] + triangle[i][i];
            for(int j = 1;  j < i; j++){
                 record[make_pair(i,j)] = min(record[make_pair(i-1,j)], record[make_pair(i-1, j-1)]) +  
                 triangle[i][j];
            }
      }     
      for(int i = 0; i < n; i++){
        if(record[make_pair(n-1,i)] < res) res = record[make_pair(n-1,i)];
      }
        return res;
    }

然后又follow了一下题目的hint, 只用一个长度为n的array来记录结果。注意每次新的一行更新要倒着来。
 int minimumTotal(vector<vector<int> > &triangle) {
       int  n = triangle.size();
      vector<int> record(n, INT_MIN);
       int res = INT_MAX;
       record[0] = triangle[0][0];
       for(int i = 1; i < n; i ++){
            record[i] = record[i-1] + triangle[i][i];
            for(int j = i-1;  j > 0; j--){
                 record[j] = min(record[j], record[j-1]) +  triangle[i][j];           
            }
            record[0] += triangle[i][0];
      }     
      for(int i = 0; i < n; i++){
        if(record[i] < res) res = record[i];
      }
        return res;
    }

Scramble string (C++ code)

Leetcode Scramble String, Apr 30 '121887 / 5901
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
 思路： 直接递归做超时了，因此改用DP，恩，其实是个很典型的DP题了。

0. bool isScramble(string s1, string s2) {  
1.   int n = s1.size();  
2.   if(s2.size() != n) return false;  
3.   if(n == 0) return true;  
4.   bool A[n][n][n+1];  
5.   for(int i = 0; i < n; i++){  
6.    for(int j = 0; j < n; j++){  
7.       A[i][j][1] =(s1[i] == s2[j])? true : false;  
8.    }  
9.  }  
10. for(int k = 2; k < n+1; k++){  
11.   for(int i = 0; i <= n - k; i++){  
12.     for(int j = 0; j <= n - k; j++){  
13.       A[i][j][k] = false;  
14.       for(int m = 1; m < k; m++){  
15.        if(A[i][j][m] && A[i+m][j+m][k-m]) A[i][j][k] = true;       
16.        if(A[i][j+k-m][m] && A[i+m][j][k-m]) A[i][j][k] = true;  
17.       }    
18.     }   
19.   }  
20. }  
21.   
22. return A[0][0][n];  
23.   
24. }   

暴力解法：
bool isScramble(string s1, string s2) {
        if(s1.size() != s2.size()) return false;
        if(s1 == s2) return true;
        int n = s1.length();
        if(n == 0) return true;
        if(n == 1) return s1 == s2;

       for(int i = 1; i < n; i++){

         string s1left = s1.substr(0,i), s1right = s1.substr(i, n-i);
         string s2left = s2.substr(0, i), s2right = s2.substr(i, n-i);
         string s2left2 = s2.substr(0, n-i), s2right2 = s2.substr(n-i, i);

        if(isScramble(s1left, s2left) && isScramble(s1right, s2right)) return true;
        if(isScramble(s1left, s2right) && isScramble(s1right, s2left)) return true;
        if(isScramble(s1left, s2left2) && isScramble(s1right, s2right2)) return true;
        if(isScramble(s1left, s2right2) && isScramble(s1right, s2left2)) return true;

        }
        return false;                   
    }

Maximum subsequence sum C++

Find the maximum subsequence sum of an array of integers which contains both positive and negative numbers and return the starting and ending indices within the array.

For example:

int array[] = {1, -2, -3, 4, 5, 7, -6}

The max subsquence sum is 4+5+7= 16 and start index is at 3 and end index is at 5.

思路：DP，用一个int maxsofar记录当前最大和，对每个元素记录包含此元素的最大和cursum，同时更新maxsofar,这样做一遍就行了。

0. //assume n>0  
1.   
2. int maxsubsum(int A[], int n){  
3.   
4.   int maxsofar = A[0], cursum = A[0];  
5.   
6.   for(int i = 1; i < n; i++){  
7.   
8.     cursum = A[i] + max(cursum, 0);  
9.   
10.     maxsofar = max(maxsofar, cursum);  
11.   
12.  }  
13.   
14.  return maxsofar;  
15.   
16. }  

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

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

Edit Distance (C++ code)

LeetCode Edit Distance, Apr 4 '12
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
 思路：经典DP题，设定数组A[i][j]表示配对word1前i位和word2前j位所需的次数。

int minDistance(string word1, string word2) {
        int m = word1.length(), n = word2.length();
        vector<vector<int> > A(m+1,vector<int>(n+1));
        int i,j;

        for( i = 0; i <= m; i++) A[i][0] = i; 

        for(i = 1; i <= n; i++) A[0][i] = i;

       for( i = 1; i <= m; i++){
           for( j = 1; j <= n; j++ ){               
          //replace
          if(word1[i-1] == word2[j-1]) A[i][j]  = A[i-1][j-1];
          else A[i][j] = A[i-1][j-1] + 1;
         //insert or delete
         A[i][j] = min( A[i][j], min(A[i-1][j], A[i][j-1]) + 1 );
          }
     }

          return A[m][n];
    }

Distinct Subsequences (C++ code)

LeetCode Distinct Subsequences, Oct 19 '12

 难度4，出现频率2

Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.

思路：first, so each letter in T, set up a list with position information. Second, set up an array A of size(T). Now iterate through S from end to start, for each element s, update A[i] where i is the position of s in T.
A[i] gives the number of subsequences containing the part starting from ith position of T.
（还是用英文好写，汗。）
例子： S = bababa     T = baa
step 1: pos[b] = {0}, pos[a] ={1,2} .
step 2:  array A[4], A[i] =0 for i<3, A[3]=1.
step3: for S[5] = a, A[1] += A[2] = 0; A[2] +=A[3] = 1;
          for S[4] = b, A[0] += A[1] = 0;
         for S[3] = a, A[1] += A[2] = 1, A[2] +=A[3] =2;
         for S[4] = b, A[0] = 1
        for S[5] = a, A[1] = 3, A[2] = 3
So the result is A[0 ]= 1.
 时间复杂度O(n), worst case O(mn), m=size(T), 代码如下：
----------------------------

 int numDistinct(string S, string T) {
      map<char, vector<int>> pos;
      vector<int> list;
      int i;
      for(i = 0; i < T.length(); i++){
         pos[T[i]].push_back(i);
      }
     int *A= new int[T.length()+1];
     memset(A,0,T.length()*sizeof(int));
     A[T.length()] = 1;
      for(i = S.length() - 1; i >= 0; i--){
          list = pos[S[i]];          
          for(int j = 0; j < list.size(); j++){
             A[list[j]] += A[list[j]+1];
          }
         
      } 
     i = A[0];
     delete [] A;

     return i;
    }

Decode ways (C++ code)

LeetCode Decode Ways, Jun 25 '12
 难度3，出现频率4
A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
 思路：从末位倒着算，简单DP, 结果存在数组里。这道题没什么难点，但是要仔细，还要注意character和int的区别。


   int numDecodings(string s) {
       if(s.empty()) return 0;
       int n = s.length();
       int A[n];
       if(s[n-1] == '0') A[n-1] = 0; 
       else A[n-1] = 1;
    

      for(int i = n-2; i >= 0 ; i--){
        if(s[i] == '0') A[i] = 0;
        else if(s[i] == '1' || (s[i] == '2' && s[i+1] <= '6')) {
            if(i == n - 2);
               A[i] = A[i+1] + 1;
           else A[i] = A[i+1] + A[i+2];          
        }
        else   A[i] = A[i+1];

      }

      return A[0];

    }

Climbing Stairs (C++ code)

LeetCode Climbing StairsApr 3 '12
难度2，出现频率5
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

思路：简单的递归，Fibonacci数列。
Tips: 用数组挨个存结果，省去了重复计算，比直接recersive function call速度要快。


 int climbStairs(int n){
  if(n == 0) return 0;
  int A[n];
  A[0] = 1; A[1] = 2;
  
  for(int i = 2; i < n; i++ ){
    A[i] = A[i-1] + A[i-2];
  }
 
  return A[n-1];
}

Best Time to Buy and Sell Stock I, II, III(C++ code)

LeetCode Best Time to Buy and Sell StockOct 30 '12

 难度2， 出现频率1

Say you have an array for which the i^th element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

0. int maxProfit(vector<int> &prices){  
1.   
2.    if(prices.empty()) return 0;  
3.   
4.    int profit = 0, minp = prices[0];  
5.   
6.    for(int i = 0; i < prices.size(); i++){  
7.   
8.       minp = min(minp, prices[i]);  
9.   
10.       profit = max(profit, prices[i] - minp);  
11.   
12.     }  
13.   
14.    return profit;  
15. }  

  
LeetCode Best Time to Buy and Sell Stock II,Oct 31
难度3 出现频率1 
Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

0. int maxProfit(vector<int> &prices){  
1.   
2.    if(prices.empty()) return 0;  
3.   
4.    int profit = 0, start = 0, end = 0;  
5.   
6.    for(int i = 1; i < prices.size(); i++){  
7.   
8.       if(prices[i] >= prices[i-1]) end++;  
9.   
10.       else{  
11.   
12.         if(start < end) profit += prices[end] - prices[start];   
13.   
14.         start = end = i;  
15.       }      
16.     }  
17.   
18.    if(start < end) profit += prices[end] - prices[start];  
19.   
20.    return profit;  
21. }  

Best Time to Buy and Sell Stock III, Nov 7 '12
难度4，出现频率1
Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

思路一(后面有最优解)： 对每一个点，计算左边一次交易右边一次交易得到的最大可能profit，每次新的计算update profit. 计算左边交易最大profit需要记录每个点的left minimum number，计算右边交易需要倒着记录每个点的right maximum number，并把右边profit结果存在一个数组里，以供循环从左到右使用。
时间复杂度O(n)，空间复杂度O(n).

int maxProfit(vector<int> &prices){
   if(prices.size() < 2) return 0;
   int n = prices.size();
   int proend = 0, profit;
   int rm = prices[n-1];
   int lm = prices[0];
   int prostart[n];
   prostart[n-1] = 0;
   for(int i = n-2; i >= 0 ; i--){
      rm = max(rm, prices[i]);     
      prostart[i] = max(prostart[i+1], rm - prices[i]);        
    }

   profit = prostart[0];

   for(int i = 1; i < n-1; i++){    
      lm = min(lm, prices[i]);
      proend = max(proend, prices[i] - lm);
      profit = max(profit, proend + prostart[i+1]);      
   }   
   
   return profit;
      
}

思路二： 来源： http://www.mitbbs.com/article/JobHunting/32289973_0.html
这是最优解，时间O(n),空间O（1）
其实我开始也想用DP做，想了下以为不行，结果还是我思考的不够仔细，恩，虽然解法原帖已经贴了，我还是自己练一个。
主要思路分下如下：
要找当前点i进行两个交易的最大收益，两种可能：
1，不包括当前点i：结果是在前一点i-1进行两个交易的最大收益，这是第一层DP
2， 包括当前点i： 起始点可能是任何j<i, 结果是在j-1点进行一次交易+buy j sell i交易的最大可能收益。这里比较tricky,实际上我们可以通过定义另外一个DP来省去重复计算，关键的观察是：
prices[i]- prices[j] = prices[i] - prices[i-1] + prices[i-1] - prices[j] 
所以这里我们可以设定第二层DP

结论： g(m)-> 到当前点为止最多进行m次交易最大可能收益
           f(m)-> 到当前点为止最多m次交易，并包括当前点的最大可能收益，注意最后一次交易可能只包括i-1,i这两点，这种情况下f_i(m) = price[i] - price[i-1] + g_i-1(m-1).

所以在点i:
         f_i(m) =   price[i] - prices[i-1] + max(f_i-1(m), g_i-1(m-1))
         g_i(m) = max(f_i(m),g_i-1(m))

代码如下（比原帖优化了一点）：

0. int maxProfit(vector<int> &prices){  
1.   
2.   if(prices.size() < 2) return 0;  
3.   
4.   int f[3] = {0};  
5.   
6.   int g[3] = {0};  
7.   
8.   for(int i = 1; i < prices.size(); i++){  
9.   
10.     for(int m = 2; m > 0; m--){  
11.   
12.       f[m] = prices[i] - prices[i-1] + max(f[m],g[m-1]);  
13.   
14.       g[m] = max(f[m],g[m]);  
15.     }     
16.  }  
17.   
18.  return g[2];  
19. }