Algorithm Problem: Longest Non-Descending Sub Array or Logest Increasing Subarray, Dynamic programming

The ordinary dynamic programing gives our an algorithm of time complexity O(n2).
However, we could achieve the result by O(n * logn).
Inorder to do this, we need an array named min4length to hold the minimum value in array for the last number of the subarray in each length we could get. For example, given array {1,2,0}, the first run min4len = {1}, second {1,2}, third {0,2}.
At each step i from 0 to array.size() – 1, we find out the position l in min4length that satisfy that min4len[l] > array[i], and all the values before l is small than array[i], if exists. that is min4len[j] < array[i],j < l.
This step we could do in O(log n) time by binary search.
Then if the l is equal to min4len.size(), that indicated that we get to new length record, just push the value array[i] into min4len.
Else, update the min4len[l] = array[i], if min4len[l] > array[i]. And this step will NOT break the non-decreasing attribute of the array min4len, so we could do binary search again.
At last, the min4len.size() is the max length we could achieve.



If we need to output all the values in the final sub-array, it’s much harder, we have to keep track for each length of sub-array. see the code below in function:longestNonDecreasingSubArray()



Problem
Given an array with integers, find the longest non-descending sub-array of the given array.
For example:
Given: {1,2,3,-1,0,1,2,3,4,-1}
Should find out: {-1,0,1,2,3,4} of length 6.



Codes

<

pre>
//
// main.cpp
// LongestIncreasingSubarray
//
// Created by Qiu Xiangyu on 12-12-23.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

include

using namespace std;

void printArray(vector array) {
for (size_t i = 0; i < array.size(); ++i) {
if (i > 0) {
cout<<“,”;
}
cout<<array[i];
}
cout<<endl;
}

int lengthOfLongestNonDecreasingSubArray(vector &array) {
if (array.size() == 0) {
return 0;
}
vector min4Length;
for (int i = 0; i < array.size(); ++i) {
int l = 0,h = (int)min4Length.size() – 1;
while (l <= h) {
int mid = (l + h) / 2;
if (min4Length[mid] <= array[i]) {
l = mid + 1;
} else {
h = mid – 1;
}
}
if (l == min4Length.size()) {
min4Length.push_back(array[i]);
} else {
if (min4Length[l] > array[i]) {
min4Length[l] = array[i];
}
}
printArray(min4Length);
}

return (int)min4Length.size();

}

vector longestNonDecreasingSubArray(vector &array) {
vector ret;
if (array.size() == 0) {
return ret;
}
vector min4Length;
vector<vector > pathes;
for (int i = 0; i < array.size(); ++i) {
int l = 0,h = (int)min4Length.size() – 1;
while (l <= h) {
int mid = (l + h) / 2;
if (min4Length[mid] <= array[i]) {
l = mid + 1;
} else {
h = mid – 1;
}
}
cout<<“step “<<i<<“, value “<<array[i]<<“, position “<<l<<“, in min4len: “;
printArray(min4Length);
if (l == min4Length.size()) {
min4Length.push_back(array[i]);
vector path;
if (l > 0) {
vector &prePath = pathes[l – 1];
for (int k = 0; k < prePath.size(); ++k) {
path.push_back(prePath[k]);
}
}
path.push_back(i);
pathes.push_back(path);
cout<<“new length, min4len: “;
printArray(min4Length);
cout<<” path: “;
printArray(path);
} else {
if (min4Length[l] > array[i]) {
min4Length[l] = array[i];
if (l > 0) {
vector &prePath = pathes[l – 1];
for (int k = 0; k < prePath.size(); ++k) {
pathes[l][k] = prePath[k];
}
}
pathes[l].back() = i;
cout<<“path for “<<l<<” is:”;
printArray(pathes[l]);
}
cout<<“old for length: “< &lpath = pathes.back();
for (int i = 0; i < lpath.size(); ++i) {
ret.push_back(array[lpath[i]]);
}
return ret;
}

int main(int argc, const char * argv[])
{
vector arr = {1,2,3,-1,0,1,2,3,4,-1};
// int longest = lengthOfLongestNonDecreasingSubArray(arr);
// cout<<longest<<endl;
vector larr = longestNonDecreasingSubArray(arr);
printArray(larr);
cout<<“length : “<<larr.size()<<endl;
return 0;
}

Algorithm Problem: Coins,Integer Bag Problem using Dynamic Programming

We can calculate the result by dynamic programming.

When there is only one coin valued 1, there is only one way to sum up to the money.
How about the coin valued 2 is available ? We can use the coin2 by count of 0,1,…,Sum/2, and using coin1 for the rest of money which is already calculated by the former step.
Generally, when we already calculated the ways with using the first k types of coins for the money 0,1,…,Sum. When the k+1 types of coin is available, the ways for a certain sum of money tSum is the sum ways of using 0 of new coins, 1 of new coins, 2 of new coins,… and handle the rest of money by first k types of coins, while the rest of money is none-negative.

Then we can get the code below.



Coins or Bags
There are some coins valued 1,2,5,20,50,100. Given a sum of money Sum, how many ways are there by using these coins to sum up to the given money.
The classic integer bag problem is similar to this problem.



Codes:Recur version and Dynamic version

<

pre>

//
// main.cpp
// 背包问题
//
// Created by Qiu Xiangyu on 12-12-15.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

// 类似背包问题
// 有一些面值的硬币,1 2 5 20 50 100,要求给出凑足某个数目的钱,总共多少方法

include

using namespace std;

static const int types = 6;
const int coins[types] = {1,2,5,20,50,100};
int waysRecur(int total, int maxAllowType) {
if (maxAllowType <= 0) {
return 1;
}
int maxCoin = coins[maxAllowType];
int ways = 0;
for (int i = 0; i <= total / maxCoin; ++i) {
ways += waysRecur(total – i * maxCoin, maxAllowType – 1);
}
return ways;
}

int waysDp(int sum) {
if (sum <= 0) {
return 1;
}
//1.build a 2-d array to hold the results
int * ways[types];
for (int it = 0 ; it < types; ++it) {
ways[it] = new int[sum + 1];
}
for (int is = 0; is <= sum; ++is) {
ways[0][is] = 1;
}
//2.dp from types 1 to types – 1 to calculate the ways
for (int it = 1; it < types; ++it) {
int coinValue = coins[it];
for (int is = 0; is <= sum; ++is) {
ways[it][is] = 0;
for (int itime = 0; itime * coinValue <= is; ++itime) {
int remain = is – itime * coinValue;
ways[it][is] += ways[it-1][remain];
}
}
}
//3.return the result
int ret = ways[types – 1][sum];
for (int it = 0 ; it < types; ++it) {
delete ways[it];
}
return ret;
}

int main(int argc, const char * argv[])
{
int total = 111;
int ways = waysRecur(total, types – 1);
int wdp = waysDp(total);
cout<<“ways from recur:”<<ways<<endl;
cout<<“ways from dp:”<<wdp<<endl;
return 0;

/*
 5:{1,1,1,1,1},{1,1,1,2},{1,2,2},{5}
 it=0:{1,1,1,1,1}
 it=1:{1,1,2,2,3}
 it=2:{1,1,2,2,4}
 */

}

LeetCode题目:Best Time to Buy and Sell Stock III,一维动态规划

和前两道题比起来的话,这道题最难了,因为限制了交易次数。
解决问题的途径我想出来的是:既然最多只能完成两笔交易,而且交易之间没有重叠,那么就divide and conquer。
设i从0到n-1,那么针对每一个i,看看在prices的子序列[0,…,i][i,…,n-1]上分别取得的最大利润(第一题)即可。
这样初步一算,时间复杂度是O(n2)。


改进:
改进的方法就是动态规划了,那就是第一步扫描,先计算出子序列[0,…,i]中的最大利润,用一个数组保存下来,那么时间是O(n)。
第二步是逆向扫描,计算子序列[i,…,n-1]上的最大利润,这一步同时就能结合上一步的结果计算最终的最大利润了,这一步也是O(n)。
所以最后算法的复杂度就是O(n)的。



Best Time to Buy and Sell Stock III
Say you have an array for which the ith 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).



代码:12ms过大集合,一次性bug free,很happy

class Solution {
public:
    int maxProfit(vector &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(prices.size() <= 1)
            return 0;
            
        //stores the max profit in [0, ... , i] subarray in prices
        vector maxEndWith;
        {//build the maxEndWith.
            int lowest = prices[0];
            int maxprofit = 0;
            maxEndWith.push_back(0);
            for(int i = 1; i < prices.size(); ++i) {
                int profit = prices[i] - lowest;
                if(profit > maxprofit) {
                    maxprofit = profit;
                }
                maxEndWith.push_back(maxprofit);
                if(prices[i] < lowest) lowest = prices[i];
            }
        }
        
        int ret = maxEndWith[prices.size() - 1];
        {//reverse to see what is the maxprofit of [i, ... , n-1] subarray in prices
        //and meanwhile calculate the final result
            int highest = prices[prices.size() - 1];
            int maxprofit = 0;
            for(int i = prices.size() - 2; i >= 0; --i) {
                int profit = highest - prices[i];
                if(profit > maxprofit)  maxprofit = profit;
                int finalprofit = maxprofit + maxEndWith[i];
                if(finalprofit > ret) ret = finalprofit;
                if(prices[i] > highest) highest = prices[i];
            }
        }

        return ret;
    }
};

LeetCode题目:Unique Paths II,二维动态规划

每个cell,如果自身没有障碍的话,可以从上面一个cell或者左边一个cell到达。所以用动态规划来解决很简单:
开一个数组(和输入矩阵的列数等大),记录到达该cell的可能路径个数。
逐行扫描输入矩阵,根据条件计算到达该cell可能的路径个数(只能从上面或者左边)。
最后输出这个数组的最后一个元素即可。

这样做的话,时间复杂度是O(rows * cols),空间复杂度是O(cols)



Unique Paths II
Follow up for “Unique Paths”:
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3×3 grid as illustrated below.

 [
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
 

The total number of unique paths is 2.
Note: m and n will be at most 100.



代码:24ms过大集合

class Solution {
public:
    int uniquePathsWithObstacles(vector > &obstacleGrid) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rows = obstacleGrid.size();
        if(rows == 0) return 0;
        int cols = obstacleGrid[0].size();
        if(cols == 0) return 0;
        int *preways = new int[cols];
        int *ways = new int[cols];
        
        //first row
        preways[0] = 1 - obstacleGrid[0][0];
        for(int i = 1; i  &rowobs = obstacleGrid[ir];
            for(int ic = 0; ic < cols; ++ic) {
                if(rowobs[ic] == 1) {
                    ways[ic] = 0;
                    continue;
                }
                //from cell above
                ways[ic] = preways[ic];
                //from left
                if(ic > 0) {
                    ways[ic] += ways[ic - 1];
                }
            }
            int *temp = preways;
            preways = ways;
            ways = temp;
        }
        return preways[cols-1];
    }
};

LeetCode题目:Unique Binary Search Trees,一维动态规划

用一维动态规划解。
Sigma(左边的子树可能状态 * 右边子树可能状态) = 当前个数的nodes形成的BST总数。



Unique Binary Search Trees
Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example,
Given n = 3, there are a total of 5 unique BST’s.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3



代码:8ms过大集合

class Solution {
public:
    int numTrees(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(n <= 1) return n;
        //ways[i] rep. the number of ways with i nodes
        int *ways = new int[n + 1];
        ways[0] = 1;
        ways[1] = 1;
        for(int i = 2 ; i <= n; ++i) {
            ways[i] = 0;
            for(int left = 0; left < i; ++ left) {
                //with number of left noeds in the left sub-tree
                int lways = ways[left];
                int rways = ways[i - left - 1];
                ways[i] += lways * rways;
            }
        }
        int ret = ways[n];
        delete [] ways;
        return ret;
    }
};

LeetCode题目:Triangle,动态规划

逐行扫描,计算在每一个位置能取得的最小sum,实际上是该元素上面两个能取得的最小sum中最小的那一个sum加上自己的值。
动态规划,只需要开一个数组重复利用就行了。



Triangle
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.



代码:40ms过大集合

class Solution {
public:
    int minimumTotal(vector > &triangle) {
        int rows = triangle.size();
        if(0 == rows) return 0;
        int *minSums = new int[rows];
        int *temp = new int[rows];
        
        for(int r = 0; r < rows; ++r) {
            vector trow = triangle[r];
            if(trow.size() != r + 1) return 0;//input error occur
            //first should be last 0 add trow[0]
            temp[0] = trow[0] + (r > 0 ? minSums[0] : 0);
            //from 1 to r - 1, the min from above to parants add self
            for(int i = 1; i < r; ++ i) {
                temp[i] = trow[i] + min(minSums[i-1],minSums[i]);
            }
            //last element, just like the first one. only can add self to the last element above.
            if(r > 0)
                temp[r] = trow[r] + minSums[r-1];
            //swap temp with minSums
            int *tswap = temp;
            temp = minSums;
            minSums = tswap;
        }
        
        //scan the minSums, find out the minimum one
        int m = minSums[0];
        for(int i = 1; i < rows; ++i) {
            if(minSums[i] < m)
                m = minSums[i];
        }
        
        delete temp;
        delete minSums;
        return m;
    }
};



Code rewrite at 2012-12-30

class Solution {
public:
    int minimumTotal(vector > &triangle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int levels = triangle.size();
        if(levels<=0) return 0;
        vector *psum = new vector(levels,0);
        vector *psumtemp = new vector(levels,0);
        (*psum)[0] = triangle[0][0];
        for(int ilevel = 1; ilevel < levels; ++ilevel) {
            vector &level = triangle[ilevel];
            const int levelsize = level.size();
            //only one path could arrive to the first and last number in a level
            (*psumtemp)[0] = (*psum)[0] + level[0];
            //if (level.size() > 1)
            (*psumtemp)[levelsize - 1] = (*psum)[levelsize - 2] + level[levelsize - 1];
            //there are 2 pathes for the middle numbers.
            for(int ipos = 1; ipos < levelsize - 1; ++ipos) {
                int tsum = (*psum)[ipos] + level[ipos];
                if(tsum > (*psum)[ipos-1] + level[ipos]) {
                    tsum = (*psum)[ipos-1] + level[ipos];
                }
                (*psumtemp)[ipos] = tsum;
            }
            //swap the psum and psumtemp
            vector *ptemp = psum;
            psum = psumtemp;
            psumtemp = ptemp;
        }
        //scan the psum and output the minnimum sum
        int minsum = (*psum)[0];
        for(int i = 1; i < levels; ++i) {
            if(minsum > (*psum)[i])
                minsum = (*psum)[i];
        }
        //clearup
        delete psum;
        delete psumtemp;
        return minsum;
    }
};



Code rewrite at 2013-1-17

class Solution {
public:
    int minimumTotal(vector > &triangle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rows = triangle.size();
        if(0 == rows) return 0;//error
        int *sumrow = new int[rows];
        int *sumrowtemp = new int [rows];
        sumrow[0] = triangle[0][0];
        for(int ir = 1; ir < rows; ++ir) {
            vector &trirow = triangle[ir];
            sumrowtemp[0] = sumrow[0] + trirow[0];
            for(int ic = 1; ic < trirow.size(); ++ic) {
                int minsum = sumrow[ic-1];
                if(ic < trirow.size()-1 && sumrow[ic] < minsum) {
                    minsum = sumrow[ic];
                }
                sumrowtemp[ic] = minsum + trirow[ic];
            }
            int *temp = sumrow;
            sumrow = sumrowtemp;
            sumrowtemp = temp;
        }
        int ret = sumrow[0];
        for(int ic = 1; ic < rows; ++ic) {
            if(ret > sumrow[ic]) ret = sumrow[ic];
        }
        delete sumrow;
        delete sumrowtemp;
        return ret;
    }
};

LeetCode题目:Scramble String,三维动态规划

一开始拿到这个题的时候没什么想法,浆糊了之后立马百度之,才有了思路。
简单的说,就是s1和s2是scramble的话,那么必然存在一个在s1上的长度l1,将s1分成s11和s12两段,同样有s21和s22。
那么要么s11和s21是scramble的并且s12和s22是scramble的;
要么s11和s22是scramble的并且s12和s21是scramble的。
先用递归写了一个算法,但是大集合不过,然后用三维动态规划才搞定。



题目描述Scramble String
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.



代码:三维动态规划,48ms过大集合

    bool isScrambleDP(string s1, string s2) {
        if(s1.size() != s2.size()) return false;
        if(s1.size() == 0) return true;
        if(s1 == s2) return true;
        bool ***iss = NULL;//iss[len][startIndexAtS1][startIndexAtS2]
        iss = new bool**[s1.size()];
        for(int len = 1;len <= s1.size(); ++len) {
            //size at this level
            int levelSize = s1.size() - len + 1;
            int levelIndex = len - 1;
            iss[levelIndex] = new bool*[levelSize];
            for(int indexS1 = 0;indexS1 < levelSize; ++ indexS1) {
                iss[levelIndex][indexS1] = new bool[levelSize];
                for(int is2 = 0; is2 < levelSize; ++is2) {
                    if(len == 1) {
                        iss[levelIndex][indexS1][is2] = (s1[indexS1] == s2[is2]);
                    } else {
                        iss[levelIndex][indexS1][is2] = false;
                        for(int seglen1 = 1; seglen1 < len; ++seglen1) {
                            int seglen2 = len - seglen1;
                            int sli1 = seglen1 - 1;
                            int sli2 = seglen2 - 1;
                            if(iss[sli1][indexS1][is2] && iss[sli2][indexS1 + seglen1][is2 + seglen1]) {
                                iss[levelIndex][indexS1][is2] = true;
                                break;
                            }
                            if(iss[sli1][indexS1][is2 + seglen2] && iss[sli2][indexS1 + seglen1][is2]) {
                                iss[levelIndex][indexS1][is2] = true;
                                break;
                            }
                        }
                    }
                }
            }
        }
        return iss[s1.size() - 1][0][0];
    }



递归代码,小集合12ms过,大集合过不了,因为时间复杂度是O(3n)

class Solution {
public:
    bool isScramble(string s1, string s2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(s1.size() != s2.size()) return false;
        if(s1 == s2) return true;
        for(int isep = 1; isep < s1.size(); ++ isep) {
            //seporate s1 as [0,isep - 1],[isep, s1.size() - 1]
            string seg11 = s1.substr(0,isep);
            string seg12 = s1.substr(isep);
            {//see if forward order is ok
                string seg21 = s2.substr(0,isep);
                string seg22 = s2.substr(isep);
                if(isScramble(seg11,seg21) && isScramble(seg12,seg22)) return true;
            }
            {//see if reverse order is ok
                string seg21 = s2.substr(s2.size() - isep);
                string seg22 = s2.substr(0,s2.size() - isep);
                if(isScramble(seg11,seg21) && isScramble(seg12,seg22)) return true;
            }
        }
        return false;
    }
};



Recursive code rewrite at 2013-2-5, 48ms pass large set

class Solution {
public:
    bool isScramble(string s1, string s2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(s1.size() != s2.size()) return false;
        if(s1 == s2) return true;
        string ts1 = s1,ts2 = s2;
        sort(ts1.begin(), ts1.end());
        sort(ts2.begin(), ts2.end());
        if(ts1 != ts2) return false;
        for(int isep = 1; isep < s1.size(); ++ isep) {
            //seporate s1 as [0,isep - 1],[isep, s1.size() - 1]
            string seg11 = s1.substr(0,isep);
            string seg12 = s1.substr(isep);
            {//see if forward order is ok
                string seg21 = s2.substr(0,isep);
                string seg22 = s2.substr(isep);
                if(isScramble(seg11,seg21) && isScramble(seg12,seg22)) return true;
            }
            {//see if reverse order is ok
                string seg21 = s2.substr(s2.size() - isep);
                string seg22 = s2.substr(0,s2.size() - isep);
                if(isScramble(seg11,seg21) && isScramble(seg12,seg22)) return true;
            }
        }
        return false;
    }
};

LeetCode题目:Longest Palindromic Substring,二维动态规划

Updated at 2016-04-28

Question

Longest Palindromic Substring
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.

Analyze

The brute force method will take O(n3) time, and apparently, it will exceed the time limit.

To reduce the time, as we noticed there are a lot of duplicated comparisons in the brute force method, the first thought is dynamic programming. But I was too aggressive at the begging, want to solve this with 1-D dynamic programming in O(n) time.

After find out several exceptional cases with either focus on the start of substring or the end of substring, I realized that it can not fit into a 1-D dynamic programming. But 2-D, can easily beat this question.

2-D Dynamic Programming

Let’s focus on the start index si and end index ei of the substring. When we want answer the question: “Is the substring s[si..ei] palindromic?”, we just check if s[si + 1 .. ei – 1] is palindromic and if s[si] == s[ei]. If both conditions are true, then we can get the positive answer. Then if we solve the problem in this order:

for(int ei = 0; ei < s.length(); ei ++)
  for(int si = ei; si >= 0; si --)
  { // implement here }

Then we can make sure when we resolve sub problem on (si, ei), we know the answer of (si+1, ei-1). So, just build a 2-D matrix and we can beat this question in O(n2) time.

Expand from center

That’s the DP solution. And since it’s O(n2), then there is a more straight forward method with the same time level:
Just at each point in the string S, on the positions of it’s characters like 0,1,2,… or between characters like 0.5, 1.5, … . Then from this position, just expand the substring if it is still palindromic. Then there are O(n) centers and at each center, we need expand O(n) times. Thus, this is also a O(n2) time solution. And simpler.

Codes

Ruby version DP

def longest_palindrome(s)
    map = {}
    max_si, max_ei, max_length = nil, nil, 0
    s.length.times do |ei|
        si = ei
        while si >= 0 do
            if si == ei
                map[ei] = { si => true }
            else
                map[ei][si] = s[ei] == s[si] && (si + 1 >= ei || map[ei - 1][si + 1] == true)
            end

            len = (ei - si + 1)
            if map[ei][si] && len > max_length
                max_length = len
                max_si = si
                max_ei = ei
            end

            si -= 1
        end
    end

    s[max_si..max_ei]
end

Ruby version expand from center

def expand(s, center)
  li, ri = center.floor, center.ceil
  if li == ri
      li -= 1
      ri += 1
  end
  left_space = li
  right_space = s.length - ri - 1
  max_space = [left_space, right_space].min
  most_left = li - max_space
  while li >= most_left do
    if s[li] == s[ri]
      li -= 1
      ri += 1
    else
      break
    end
  end
  #p [ri - li - 1, li + 1, ri - 1]
  [ri - li - 1, li + 1, ri - 1]
end

def longest_palindrome(s)
  i = 0
  max_si, max_ei, max_len = nil, nil, 0
  while i <= s.length - 1 do
    len, si, ei = expand(s, i)
    if max_len < len
        max_si, max_ei, max_len = si, ei, len
    end
    i += 0.5
  end
  s[max_si..max_ei]
end

C++ version DP

class Solution {
public:
    inline void setIsPalindrome(bool * dpmap, int si, int ei, int total_length, bool value) {
        *(dpmap + total_length * ei + si) = value;
    }
    inline bool isPalindrome(bool * dpmap, int si, int ei, int total_length) {
        return *(dpmap + total_length * ei + si);
    }
    string longestPalindrome(string s) {
        int total_length = s.length();
        int max_len = 0, max_si, max_ei;
        bool *dpmap = new bool[total_length * total_length];
        for(int ei = 0; ei < total_length; ei++) {
            for(int si = ei; si >= 0; si--) {
                bool positive = 
                    (si == ei) ||
                    ((s[si] == s[ei]) && ((si == ei - 1) || isPalindrome(dpmap, si + 1, ei - 1, total_length)));
                setIsPalindrome(dpmap, si, ei, total_length, positive);
                if(positive){
                    int len = ei - si + 1;
                    if(max_len < len){
                        max_len = len;
                        max_si = si;
                        max_ei = ei;
                    }
                }
            }
        }
        delete dpmap; dpmap = NULL;
        return s.substr(max_si, max_len);
    }
};

旧版,有误,奇怪的是当初竟然通过了测试…

问题要求是寻找一个字符串中的最长可逆子串,可以转化为求它和自身的逆序串的最长公共子串问题。
关键的思路是:
用一个matrix记录最长公共子串的长度,mat[i][j]表示以a串的i-1字符结束且以b串的j-1字符结束的最长子串长度。
当stringa[i-1] == stringb[j-1]时,mat[i][j] == mat[i-1][j-1] + 1

其中遇到了两个问题:
1.在子函数longestCommonSub中,如果先new,在得到最长公共串之后delete申请的空间mat的话,运行到大概第5个test case的时候会报runtime error。
2.在代码段

if(max <= len)

中,如果把小于等于改成小于,在大测试集合中会有一个莫名其妙的test case结果错误。
这两个问题都不知道原因。



代码:1488ms过大集合

class Solution {
public:
    string longestCommonSub(string &sa, string &sb) {
        int rows = sa.size() + 1;
        int cols = sb.size() + 1;
        static int *mat = NULL;
        if(NULL == mat) {
            mat = new int[1001 * 1001];
        }
        for(int ir = 0 ; ir < rows; ++ ir) {
            for(int ic = 0 ; ic < cols; ++ ic) {
                *(mat + ir * cols + ic) = 0;
            }
        }
        int max = 0;
        int maxIr;
        for(int ir = 1 ; ir < rows; ++ ir) {
            char sai = sa[ir - 1];
            for(int ic = 1 ; ic < cols; ++ ic) {
                if(sai == sb[ic - 1]){
                    int len = 1 + *(mat + (ir-1) * cols + ic - 1);
                    *(mat + ir * cols + ic) = len;
                    if(max <= len) {
                        max = len;
                        maxIr = ir;
                    }
                }
            }
        }
        string result;
        if(max > 0) {
            result = sa.substr(maxIr - max, max);
        }
        return result;
    }
    string longestPalindrome(string s) {
        string rs = s;
        for( int i = 0 ; i < s.size(); ++ i) {
            rs[i] = s[s.size() - 1 - i];
        }
        return longestCommonSub(s,rs);
    }
};

LeetCode题目:Jump Game II,一维动态规划,贪心

这个简单,只需要在Jump Game的基础上用一个int来记录最小跳跃次数就行了。

不过,贪心法可以解,O(n)扫一次就可以了,比DP好得多。因为这道题是最远跳到那么远,而不是只能跳到那么远。如果是后者,引入dp值得。



题目描述:Jump Game II
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.)



贪心法,48ms过大集合

class Solution {
public:
    int jump(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int minstep = 0;
        int ldist = 0;
        int hdist = 0;
        if (n == 1) return 0;
        while(ldist <= hdist) {
            ++minstep;
            int lasthdist = hdist;
            for(int i = ldist; i <= lasthdist; ++i) {
                int possibledist = i + A[i];
                if (possibledist >= n-1)
                    return minstep;
                if (possibledist > hdist) {
                    hdist = possibledist;
                }
            }
            ldist = lasthdist + 1;
        }
        return 0;
    }
};



一维动态规划,1936ms过大集合

class Solution {
public:
    int jump(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(n <= 1)
            return 0;
        const int noWay = n + 1;
        int *jumps = new int[n];
        jumps[n-1] = 0;
        for(int i = n - 2; i >= 0; -- i) {
            int lenJump = A[i];
            int minJumps = noWay;
            for(int j = i + 1; j <= i + lenJump && j < n; ++ j) {
                if(jumps[j] + 1 < minJumps)
                    minJumps = jumps[j] + 1;
            }
            jumps[i] = minJumps;
        }
        return jumps[0];
    }
};

LeetCode题目:Jump Game,一维动态规划

最开始用

vector

超时,想了想没法改进算法的阶,就把这个换成bool[],居然就过了。。。哎,该用数组还是用数组啊。



题目描述:Jump Game
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.



大集合不超时了,不过貌似有一个testcase有问题,错误一个:[2,0,1,1,1,1],这应该返回true啊,不过系统给的答案是false

class Solution {
public:
    bool canJump(int A[], int n) {
        //if (n > 100) return false;
        if (n <= 1)
            return true;
        //vector canJump(n, false);
        bool *canJump = new bool[n];
        canJump[n - 1] = true;
        for( int i = n - 2; i >= 0; --i ) {
            int maxJump = A[i];
            for(int j = i + 1; j <= i + maxJump && j < n ; ++j) {
                if (canJump[j]) {
                    canJump[i] = true;
                    break;
                }
            }
        }
        return canJump[0];
    }
};



大集合超时

class Solution {
public:
    bool canJump(int A[], int n) {
        if (n <= 1)
            return true;
        vector canJump(n, false);
        canJump[n - 1] = true;
        for( int i = n - 2; i >= 0; --i ) {
            int maxJump = A[i];
            if (i + maxJump >= n)
                maxJump = n - i;
            for(int j = i + maxJump; j > i; --j) {
                if (canJump[j]) {
                    canJump[i] = true;
                    break;
                }
            }
        }
        return canJump[0];
    }
};

LeetCode题目:Interleaving String,二维动态规划

分析
题目给定3个字符串(s1,s2,s3),看s3是否是有s1和s2通过交织可以得到。


可以这么来看这个问题,每次从s3开头拿出来一个字符,如果s1的开头或者s2的开头有这个字符的话,就消掉相应的字符,把这个操作记为del。
这样看待这个问题的话,好像挺简单的,很直观。
但是当遇到case:s1=aa,s2=ab,s3=abaa,的时候可以看出当s1和s2同时可以进行del操作的时候,选择就成了一个必须考虑的问题。
假如最开始那个a,消掉了s1中的第一个a,那么就进行不下去了。
<br>
所以最后这个问题其实并不那么简单,假如函数

bool isInterleaving(string &s1, int len1, string &s2, int len2, string &s3, int len3);

表示子问题:si取前leni个字符的话,那么实际上可以得到这样的一个公式:

isInterleaving(s1,len1,s2,len2,s3,len3) 
    =   (s3.lastChar == s1.lastChar) && isInterleaving(s1,len1 - 1,s2,len2,s3,len3 - 1)
      ||(s3.lastChar == s2.lastChar) && isInterleaving(s1,len1,s2,len2 - 1,s3,len3 - 1)

由于len3 === len1 + len2,所以这个问题里面实际上存在着两个变量,是一个二维动态规划题目。
从矩阵的角度来看的话,每一个元素的值,依赖于它的上边和左边两个值。
最后写出程序,用24ms过大测试集合。



题目描述:Interleaving String
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.



正解就是二维动态规划

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s3.size() != s1.size() + s2.size())
            return false;
        //create indicator
        vector > match(s1.size() + 1, vector(s2.size() + 1, false));
        //initialization the first row and the first column
        match[0][0] = true;
        for( int l1 = 1; l1 <= s1.size(); ++ l1 ) {
            char c1 = s1[l1 - 1];
            char c3 = s3[l1 - 1];
            if (c1 == c3) {
                match[l1][0] = true;
            } else 
                break;
        }
        for( int l2 = 1; l2 <= s2.size(); ++ l2 ) {
            char c2 = s2[l2 - 1];
            char c3 = s3[l2 - 1];
            if (c2 == c3) {
                match[0][l2] = true;
            } else 
                break;
        }
        //work through the rest of matrix using the formula
        for( int l1 = 1; l1 <= s1.size(); ++ l1 ) {
            char c1 = s1[l1 - 1];
            for( int l2 = 1 ; l2 <= s2.size() ; ++ l2 ) {
                char c2 = s2[l2 - 1];
                int l3 = l1 + l2;
                char c3 = s3[l3 - 1];
                if (c1 == c3) {
                    match[l1][l2] = match[l1 - 1][l2] || match[l1][l2];
                }
                if (c2 == c3) {
                    match[l1][l2] = match[l1][l2 - 1] || match[l1][l2];
                }
            }
        }
        //the last element is the result
        return match[s1.size()][s2.size()];
    }
};



几个失败的想法

一开始的想法,错在当s1,s2同时匹配的时候,这里存在一个策略问题,比如测试用例:aa,ab,abaa,就过不了。

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s3.size() != s1.size() + s2.size())
            return false;
        int i1 = 0;
        int i2 = 0;
        for(int i3 = 0 ; i3 < s3.size(); ++i3) {
            if(i1 < s1.size() && s1[i1] == s3[i3]) {
                ++i1;
            } else if (i2 < s2.size() && s2[i2] == s3[i3]) {
                ++i2;
            } else
                return false;
        }
        return true;
    }
};



第二个错误想法,先从s3中标记掉s1中出现的内容,然后在看剩下的部分是不是s2,也不对,一样的存在“标记掉s1"的策略问题

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s3.size() != s1.size() + s2.size())
            return false;
        vector visited(s3.size(),false);
        int i3 = 0;
        for( int i1 = 0; i1 < s1.size() ; ++i1 ) {
            bool match = false;
            while(i3 < s3.size()) {
                if(s3[i3] == s1[i1]) {
                    visited[i3 ++] = true;
                    match = true;
                    break;
                }
                ++i3;
            }
            if(!match)
                return false;
        }
        i3 = 0;
        for( int i2 = 0; i2 < s2.size() ; ++i2 ) {
            bool match = false;
            while(i3 < s3.size()) {
                if (visited[i3]) {
                    ++i3;
                    continue;
                }
                if(s3[i3 ++] == s2[i2]) {
                    match = true;
                    break;
                }
            }
            if(!match)
                return false;
        }
        return true;
    }
};



所以,绕不开策略问题,就得在做出决策的时候让程序分支。下面是一个正确但大集合会超时的递归算法:

class Solution {
public:
    bool isInterleave(string &s1,int i1, string &s2, int i2, string &s3, int i3) {
        if(i1 == s1.size() && i2 == s2.size() && i3 == s3.size())
            return true;
        bool match = false;
        if(i1 < s1.size() && s1[i1] == s3[i3]) {
            match = isInterleave(s1, i1 + 1, s2, i2, s3, i3 + 1);
        }
        if (!match && i2 < s2.size() && s2[i2] == s3[i3]) {
            match = isInterleave(s1, i1, s2, i2 + 1, s3, i3 + 1);
        }
        return match;
    }
    bool isInterleave(string s1, string s2, string s3) {
        if(s3.size() != s1.size() + s2.size())
            return false;
        return isInterleave(s1,0,s2,0,s3,0);
    }
};

LeetCode题目:Edit Distance,字符串之间的编辑距离,动态规划

这个题目花了我太长的时间,方向是对的,不过一直没有找到关键的递推。

题目描述
Edit Distance
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

简单的说,就是将一个字符串变成另外一个字符串所用的最少操作数,每次只能增加、删除或者替换一个字符。


做这个题过程挺曲折

      一开始考虑的是,只要找到能重用的最大子串不就行了么,比如将字符:
      abc变成xxxxxaxxxxxbxxxxxcxxxxx,只要abc都可以重用,就只需要20步。
      但是写完了这个方法之后(见下面失败方法1),被一个简单的case击败了:
      将ykyyyab变成abxxxxx,
      这种情况下,如果利用了最长子串ab的话,编辑距离实际上是10,但是不用的话只需要7。也就是说,最长子串不一定能降低编辑距离。


      然后就又想,上面这种失败case的原因在于为了利用最长子串,导致的头尾一删一添,两次操作,还不如只需一次的替换操作。
      于是就限制了一下匹配的区间,比如abxxxxx中的b在匹配的时候,只在kyyya这个范围内才有实际作用,超过这个区间再匹配就会造成得不偿失的一删一添两次操作,得不偿失。
      于是写完代码,悲剧的是,又发现问题:
      sea变成eat,
      按这个算法,编辑距离是3,但实际上是2(删s添t)。


      最后花了太长时间忍不了了,百度之,发现正确的解出来方法是用二维的dp。
      假如我们要将字符串str1变成str2
      sstr1(i)是str1的子串,范围[0到i),sstr1(0)是空串
      sstr2(j)是str2的子串,同上
      d(i,j)表示将sstr1(i)变成sstr2(j)的编辑距离

      首先d(0,t),0<=t<=str1.size()和d(k,0)是很显然的。 当我们要计算d(i,j)时,即计算sstr1(i)到sstr2(j)之间的编辑距离, 此时,设sstr1(i)形式是somestr1c;sstr2(i)形如somestr2d的话, 将somestr1变成somestr2的编辑距离已知是d(i-1,j-1) 将somestr1c变成somestr2的编辑距离已知是d(i,j-1) 将somestr1变成somestr2d的编辑距离已知是d(i-1,j) 那么利用这三个变量,就可以递推出d(i,j)了: 如果c==d,显然编辑距离和d(i-1,j-1)是一样的 如果c!=d,情况稍微复杂一点,

      1. 如果将c替换成d,编辑距离是somestr1变成somestr2的编辑距离 + 1,也就是d(i-1,j-1) + 1
      2. 如果在c后面添加一个字d,编辑距离就应该是somestr1c变成somestr2的编辑距离 + 1,也就是d(i,j-1) + 1
      3. 如果将c删除了,那就是要将somestr1编辑成somestr2d,距离就是d(i-1,j) + 1
      4. 那最后只需要看着三种谁最小,就采用对应的编辑方案了。

      递推公式出来了,程序也就出来了。



终于过了,72ms过大集合

class Solution {
public:
    int minDistance(string word1, string word2) {
        int rows = word1.size() + 1;
        int cols = word2.size() + 1;
        int ** d = (int**)malloc(rows * sizeof(int*));
        for(int i = 0; i < rows; ++i){
            d[i] = (int*)malloc(cols * sizeof(int));
            d[i][0] = i;//sub string in word1 range [0,i) edit to ""
        }
        for(int j = 0; j < cols; ++j)
            d[0][j] = j;//sub string in word2 range [0,j) edit to ""
        for(int i = 1; i < rows; ++i) {
            char ci = word1[i-1];
            for(int j = 1; j < cols; ++j) {
                char cj = word2[j-1];
                //we will edit str1:word1[0,i) to str2:word2[0,j)
                if (ci == cj) {
                    //if ci equal to cj, then the edit ditance of word1[0,i) to word2[0,j)
                    // is the same as word1[0,i-1) to word2[0,j-1)
                    d[i][j] = d[i-1][j-1];
                } else {
                    //if we modify letter ci to cj, there will be 1 operation
                    int dEdit = d[i-1][j-1] + 1;
                    //if we add cj to the end of word1[0,i), then from the edit distance of 
                    // word1[0,i) to word2[0, j -1), we can conclude follow dist
                    int dAdd = d[i][j-1] + 1;
                    //if we delete ci from word1[0,i), and we know the dist
                    // from word1[0,i-1) to word2[0,j), the things done:
                    int dDel = d[i-1][j] + 1;
                    //the minimum one will be the final distance for str1 to str2
                    int min = dEdit < dAdd ? dEdit : dAdd;
                    min = min < dDel ? min : dDel;
                    d[i][j] = min;
                }
            }
        }
        int result = d[rows - 1][cols - 1];
        //delete dist;
        return result;
    }
};



这是两次错误的尝试

  1. 通过寻找最长公共子序列(可间断序列)来解决
    class Solution {
    public:
        class datum{
            public: 
                int lastIndex;
                int len;
                datum(){
                    lastIndex = -1;
                    len = 0;
                }
        };
        inline int locationOfCharInStr(char c, string &str, int startIndex) {
            for( int i = startIndex; i < str.size() ; ++ i ) {
                if (c == str[i])
                    return i;
            }
            return -1;
        }
        int longestCommonArray(string &str1, string &str2) {
            if(str1.size() == 0 || 0 == str2.size())
                return 0;
            vector maxLen(str1.size());
            for( int i = 0; i <  str1.size(); ++i ) {
                char ci = str1[i];
                datum &di = maxLen[i];
                for (int pre = 0 ; pre < i; ++pre ) {
                    datum dpre = maxLen[pre];
                    if (dpre.len == 0 ) continue;
                    int cie = locationOfCharInStr(ci,str2,dpre.lastIndex + 1);
                    if( cie != -1 && di.len < dpre.len + 1 ) {
                        di.len = dpre.len + 1;
                        di.lastIndex = cie;
                    }
                }
                if(di.len == 0) {
                    int cie = locationOfCharInStr(ci,str2,0);
                    if( cie != -1 ) {
                        di.len = 1;
                        di.lastIndex = cie;
                    }
                }
            }
            int maxlen = 0;
            for(int i = 0 ; i < maxLen.size(); ++i) {
                if (maxlen < maxLen[i].len)
                    maxlen = maxLen[i].len;
            }
            return maxlen;
        }
        int minDistance(string word1, string word2) {
            int lcsl = longestCommonArray(word1,word2);
            int maxlen = word1.size();
            if(maxlen < word2.size())
                maxlen = word2.size();
            return maxlen - lcsl;
        }
    };
    
  2. 通过限制查找范围来解决
    class Solution {
    public:
        class datum{
            public: 
                int loc;
                int len;
                datum(){
                    loc = -1;
                    len = 0;
                }
        };
        inline int locationOfCharInStr(char c, string &str, int startIndex, int endIndex) {
            if(endIndex > str.size() - 1)
                endIndex = str.size() - 1;
            for( int i = startIndex; i <= endIndex ; ++ i ) {
                if (c == str[i])
                    return i;
            }
            return -1;
        }
        int minDist(string &str1, string &str2) {
            vector minLen(str2.size());
            for( int i = 0; i <  str2.size(); ++i ) {
                char ci = str2[i];
                datum &di = minLen[i];
                di.len = str1.size();
                di.loc = i;
                int endIndex = str1.size() - str2.size() + i;
                for (int pre = 0 ; pre < i; ++pre ) {
                    datum dpre = minLen[pre];
                    int startIndex = dpre.loc + i - pre;
                    int cie = locationOfCharInStr(ci,str1,startIndex,endIndex);
                    if( cie != -1 && (di.len >= dpre.len ||
                                      di.loc > cie)) {
                        di.len = dpre.len - 1;
                        di.loc = cie;
                    }
                }
                if(di.len == str1.size()) {
                    int cie = locationOfCharInStr(ci,str1,i,endIndex);
                    if( cie != -1 ) {
                        di.len = str1.size() - 1;
                        di.loc = cie;
                    }
                }
            }
            int result = str1.size();
            for(int i = 0 ; i < minLen.size(); ++i) {
                if (result > minLen[i].len)
                    result = minLen[i].len;
            }
            return result;
        }
        int minDistance(string word1, string word2) {
            // Start typing your C/C++ solution below
            // DO NOT write int main() function
            string *pSLen, *pSShort;
            if(word1.size() >= word2.size()){
                pSLen = &word1;
                pSShort = &word2;
            } else {
                pSLen = &word2;
                pSShort = &word1;
            }
            if (pSShort->size() <= 0)
                return pSLen->size();
            int result = minDist(*pSLen,*pSShort);
            return result;
        }
    };
    



Code rewrite at 2012-12-29


// // main.cpp // EditDistance // // Created by Qiu Xiangyu on 12-12-29. // Copyright (c) 2012年 Qiu Xiangyu. All rights reserved. // #include <iostream> #include <string> #include <vector> using namespace std; int editDist(string &str0, string &str1) { if (str0.size() == 0) { return (int)str1.size(); } else if (str1.size() == 0) { return (int)str0.size(); } vector<vector<int> > dists(str0.size() + 1, vector<int>(str1.size() + 1,0)); for(int i0 = 0; i0 <= str0.size(); ++ i0) { dists[i0][0] = i0; } for (int i1 = 0; i1 <= str1.size(); ++i1) { dists[0][i1] = i1; } for (int l0 = 1; l0 <= str0.size(); ++l0) { for (int l1 = 1; l1 <= str1.size(); ++l1) { if (str0[l0 - 1] == str1[l1-1]) { //the same ending of this length pair for strings dists[l0][l1] = dists[l0-1][l1-1]; } else { //for replace int replaceDist = dists[l0-1][l1-1] + 1; int mindist = replaceDist; //insert the last char into substr1 int insertDist = dists[l0][l1-1] + 1; if (mindist > insertDist) { mindist = insertDist; } //delete the last char from substr1 int deleteDist = dists[l0-1][l1] + 1; if (mindist > deleteDist) { mindist = deleteDist; } dists[l0][l1] = mindist; } } } return dists[str0.size()][str1.size()]; } int main(int argc, const char * argv[]) { string str0 = "abc"; string str1 = "bcd"; int editdist = editDist(str0, str1); cout<<"edit distance is : "<<editdist<<endl; return 0; }



Code rewrite 2012-12-30

class Solution {
public:
    int minDistance(string word1, string word2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector > dists(word1.size() + 1, vector(word2.size() + 1, 0));
        for(int l1 = 1; l1 <= word1.size(); ++l1) {
            //by adding chars in sub-word1 to sub-word2 with zero length
            dists[l1][0] = l1;
        }
        for(int l2 = 1; l2 <= word2.size(); ++l2) {
            dists[0][l2] = l2;
        }
        for(int l1 = 1; l1 <= word1.size(); ++l1) {
            for(int l2 = 1; l2 <= word2.size(); ++l2) {
                if(word1[l1-1] == word2[l2-1]) {
                    dists[l1][l2] = dists[l1-1][l2-1];
                } else {
                    //if we can form sub-word1 with length l1-1 to sub-word2 with length l2-1, 
                    //with steps of dists[l1-1][l2-1]
                    //then we can replace the char sub-word2[l2] to sub-word1[l1], 
                    //then we can edit sub-word2 with length l2 to sub-word1 with length l1 
                    //with steps of dists[l1-1][l2-1] + 1
                    int replacedist = dists[l1-1][l2-1] + 1;
                    //if we can form sub-word1 with length l1-1 to sub-word2 with length l2, 
                    //with steps of dists[l1-1][l2]
                    //then we can add the char sub-word1[l1] after sub-word2[l2],
                    //or se can delete the char sub-word1[l1]
                    //then we can edit sub-word2 with length l2 to sub-word1 with length l1 
                    //with steps of dists[l1-1][l2] + 1
                    int adddist = dists[l1-1][l2] + 1;
                    //or if we can form sub-word1 with length l1 to sub-word2 with length l2-1,
                    //with steps of dists[l1][l2-1]
                    //then we can add the char sub-word2[l2] after sub-word1[l1],
                    //or we can delete the char sub-word2[l2]
                    //then we can edit sub-word2 with length l2 to sub-word1 with length l1
                    //with steps of dists[l1][l2-1] + 1
                    int deldist = dists[l1][l2-1] + 1;
                    
                    int mindist = replacedist;
                    if(mindist>adddist) mindist = adddist;
                    if(mindist>deldist) mindist = deldist;
                    dists[l1][l2] = mindist;
                }
            }
        }
        return dists[word1.size()][word2.size()];
    }
};

LeetCode题目:Decode Ways,一维动态规划

从后往前动态规划,要注意临界状态,可以用占位符来避免程序内的越界判断。


Decode Ways
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.


暴力递归,大集合超时

class Solution {
public:
    int numDecodings(string s) {
        if(s.size() == 0)
            return 0;
        if(s.size() == 1 && s[0] != '0')
            return 1;
        if(s[0] == '0')
            return 0;
        int fix = s.size() == 2 ? 1: 0;
        if(s[0] == '1' || (s[0] == '2' && s[1] <= '6'))
            return numDecodings(s.substr(1)) + numDecodings(s.substr(2)) + fix;
        return numDecodings(s.substr(1));
    }
};



动态规划,16ms过大集合

class Solution {
public:
    int numDecodings(string s) {
        if(s.size() == 0)
            return 0;
        vector ways(s.size() + 2,1);//多出来的两个作为占位符,避免程序内判断是否超过size
        for(int i = s.size() - 1; i >= 0; --i)
        {
            //self
            if(s[i] == '0')
                ways[i] = 0;
            else
                ways[i] = ways[i+1];
            
            //self and next
            if( i + 1 < s.size() && ((s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6')))) {
                ways[i] += ways[i + 2];
            }
        }
        return ways[0];
    }
};



Code rewrite at 2013-1-4, not very nice

class Solution {
public:
    int numDecodings(string s) {
        if (s.size() == 0) return 0;
        if (s[0] == '0') return 0;
        int *ways = new int[s.size()];
        ways[0] = 1;
        for(int ei = 1; ei < s.size(); ++ei) {
            char last = s[ei - 1];
            char cur = s[ei];
            if(cur == '0') {
                if(last == '1' || last == '2')
                    ways[ei] = ei > 1 ? ways[ei-2] : 1;
                else {
                    delete ways;
                    return 0;
                }
            } else if(last == '1' || (last == '2' && cur <= '6')) {
                ways[ei] = ways[ei-1];
                ways[ei] += ei > 1 ? ways[ei-2] : 1;
            } else {
                ways[ei] = ways[ei-1];
            }
        }
        int ret = ways[s.size() - 1];
        delete ways;
        return ret;
    }
};

LeetCode题目:Combination Sum II

题目和Combination Sum差不多,加了限制,候选参数中的数字只能使用一次。
还是动态规划,利用两个数组来回倒腾。
其中还是发现了不少问题:

  1. unique和erase的用法
    result.erase(unique(result.begin(),result.end()),result.end());
  2. 细心检查语法



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]


代码
1432ms过大测试集合

class Solution {
public:
    vector > combinationSum2(vector &num, int target) {
        if(num.size() == 0)
            return vector >();
        sort(num.begin(),num.end());
        vector > > *pR = new vector > >(target + 1);
        vector > > *pT = new vector > >(target + 1);
        //initialize
        {
            int c0 = num[0];
            if(c0 > 0 && c0 <= target)
            {
                vector titem = vector(1,c0);
                (*pR)[c0].push_back(titem);
            }
        }
        
        for(int k = 1; k < num.size(); ++k)
        {
            int ck = num[k];
            for(int t = 1; t <= target; ++t)
            {
                (*pT)[t].clear();
                vector > &excludePre = (*pR)[t];
                for( int i = 0 ; i < excludePre.size(); ++i)
                {
                    (*pT)[t].push_back(excludePre[i]);
                }
                if(t - ck > 0)
                {
                    vector > &includePre = (*pR)[t - ck];
                    for( int i = 0 ; i < includePre.size(); ++i)
                    {
                        vector tResult = includePre[i];
                        tResult.push_back(ck);
                        (*pT)[t].push_back(tResult);
                    }
                } else if (t == ck)
                {
                    (*pT)[t].push_back(vector(1,ck));
                }
            }
            vector > > *temp = pR;
            pR = pT;
            pT = temp;
        }
        vector > &result = (*pR)[target];
        sort(result.begin(),result.end());
        result.erase(unique(result.begin(),result.end()),result.end());
        return result;
    }
};

LeetCode题目:Combination Sum,动态规划

这道题是动态规划,先写一个伪代码是挺好的方法。可以先笼统的写出来算法,算法ok了再注意语法之类的细节。


题目描述如下:
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]



小集合12ms,大集合1416ms过

class Solution {
public:
    vector > combinationSum(vector &candidates, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (candidates.size() == 0)
            return vector >();
        sort(candidates.begin(),candidates.end());
        vector > > *pR = new vector > >(target + 1);
        vector > > *pT = new vector > >(target + 1);
        for (int t = 1; t <= target; ++ t)
        {
            int c = candidates[0];
            if (t % c == 0)
            {
                (*pR)[t].push_back(vector(t/c,c));
            }
        }
        for (int k = 1; k < candidates.size(); ++k)
        {
            int ck = candidates[k];
            for (int t = 1 ; t <= target; ++t)
            {
                (*pT)[t].clear();
                for (int p = 0; p * ck <= t; ++p)
                {
                    int remain = t - ck * p;
                    if (remain == 0)
                    {
                        (*pT)[t].push_back(vector(p,ck));
                    }
                    else
                    {
                        vector > &rRemain = (*pR)[remain];
                        for (int irr = 0; irr < rRemain.size() ;++ irr)
                        {
                            vector newSum(rRemain[irr]);
                            for(int ip = 0; ip < p; ++ip)
                                newSum.push_back(ck);
                            (*pT)[t].push_back(newSum);
                        }
                    }
                }
            }
            vector > > *pTemp = pR;
            pR = pT;
            pT = pTemp;
        }
        return (*pR)[target];
    }
};