C***U
发帖数: 2406 | 1 用了DP 但是过不了judge large
应该哪里再改进改进啊？
谢谢大牛指教
int numDistinct(string S, string T) {
unordered_map > indexMap;
vector indices;
vector tempResult, result;
result.push_back(-1);
for(int i = 0; i < T.size(); i++) {
if(indexMap.find(T[i]) == indexMap.end()) {
indexMap[T[i]] = indices;
}
}
for(int i = 0; i < S.size(); i++) {
if(indexMap.find(S[i]) != indexMap.end()) {
indexMap[S[i]].push_back(i);
}
}
int tempLast;
for(int i = 0; i < T.size(); i++) {
for(int j = 0; j < result.size(); j++) {
tempLast = result[j];
for(int k = 0; k < indexMap[T[i]].size(); k++) {
int tempNew = indexMap[T[i]][k];
if(tempLast < tempNew) {
tempResult.push_back(tempNew);
}
}
}
result = tempResult;
tempResult.clear();
}
return result.size();
}
}; | i**********e
发帖数: 1145 | 2 DP O(M*N) 复杂度吧。
你这算法好像是 O(M*N^2) 了。
【在 C***U 的大作中提到】
: 用了DP 但是过不了judge large
: 应该哪里再改进改进啊？
: 谢谢大牛指教
: int numDistinct(string S, string T) {
: unordered_map > indexMap;
: vector indices;
: vector tempResult, result;
: result.push_back(-1);
:
: for(int i = 0; i < T.size(); i++) {
| q****m
发帖数: 177 | 3 dp的话你得用一个二维的矩阵来存储过程吧？
【在 C***U 的大作中提到】
: 用了DP 但是过不了judge large
: 应该哪里再改进改进啊？
: 谢谢大牛指教
: int numDistinct(string S, string T) {
: unordered_map > indexMap;
: vector indices;
: vector tempResult, result;
: result.push_back(-1);
:
: for(int i = 0; i < T.size(); i++) {
| C***U
发帖数: 2406 | 4 大牛
我用一个数组存放每一种组合的当前最后一个位置的index。然后滚动数组走。该在哪
里改进啊?
【在 i**********e 的大作中提到】
: DP O(M*N) 复杂度吧。
: 你这算法好像是 O(M*N^2) 了。
| C***U
发帖数: 2406 | 5 恩。我搞复杂了。没必要构造解。
【在 i**********e 的大作中提到】
: DP O(M*N) 复杂度吧。
: 你这算法好像是 O(M*N^2) 了。
| w***o
发帖数: 109 | 6 大牛们很忙，让我来给你解释解释。我两水平差不多，我的思路对你可能容易理解一点
。这题主要是要逼你写DP，而且是Buttomup的。我没有二爷那么牛，可以直接写
buttomup的DP，我是一步一步来的。不好意思C＋＋早忘了，java的，你凑合看吧。
先来recursive without DP。
public int numDistinct(String S, String T) {
if(T.length() == 0)
return 1;
if(S.length() < T.length())
return 0;
int ret = 0;
if(S.charAt(0) == T.charAt(0))
ret += numDistinct(S.substring(1), T.substring(1));
ret += numDistinct(S.substring(1), T);
return ret;
}
这个很简单，谁都会写，但问题是效率太低，能过small，肯定过不了large。因为，有
太多重复计算，所以要用DP来记住中间结果。然后我就写了下面这个recursive ＋ dp
的。主要加了个二维数组dp，其中元素dp[i][j]表示S的长度为i的后缀和T的长度为j的
后缀相比较的结果，代码如下：
public int numDistinct(String S, String T) {
if(T.length() == 0)
return 1;
if(S.length() < T.length())
return 0;
int[][] dp = new int[S.length() + 1][T.length() + 1];
return internal(S, T, dp);
}
private int internal(String s, String t, int[][] dp) {
int n = s.length();
int m = t.length();
if(dp[n][m] > 0)
return dp[n][m] - 1;
if(m == 0) {
dp[n][m] = 2;
return 1;
}
if(n == 0 || n < m) {
dp[n][m] = 1;
return 0;
}
int ret = 0;
if(s.charAt(0) == t.charAt(0))
ret += internal(s.substring(1), t.substring(1), dp);
ret += internal(s.substring(1), t, dp);
dp[n][m] = ret + 1;
return ret;
}
看上去很好，减少了不必要重复计算，但仍然过不来large。原因可能是太多function
call。那就只能把recursive去掉，换句话说就是要用bottomup的方法（上面这个是
topdown）的。仔细想想，实际上整个过程就是要计算这个二维数组。对任何一个dp[i]
[j]，它的值要么是dp[i - 1][j] + dp[i - 1][j - 1]（如果S的后缀第一个字符与T的
后缀第一个字符相等）, 要么是dp[i - 1][j]（如果不等）。这从第一个recursive的
代码就可以看出来。
基于这个思考，写代码如下：
public int numDistinct(String S, String T) {
if(T.length() == 0)
return 1;
if(S.length() < T.length())
return 0;
int n = S.length();
int m = T.length();
int[][] dp = new int[n + 1][m + 1];
for(int j = 0; j <= m; j++)
for(int i = j; i <= n; i++) {
if(j == 0) {
dp[i][j] = 1;
continue;
}
if(S.charAt(n - i) == T.charAt(m - j))
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
else
dp[i][j] = dp[i - 1][j];
}
return dp[n][m];
}
这个就能过large了。其实，在空间方面还可以再提高一点，你看两个计算dp[i][j]的
statement，他们最多只用到前一行的两个元素，我们可以用两个一维数组来交换使用
就可以了，代码要麻烦一点。
我用同样的步骤和方法解决String Interleave的和其它的与string比较有关的几个问
题。你可以试试。 | C***U
发帖数: 2406 | 7 非常感谢你得详细解答
我后来发现我搞错思路了
我去够高出所有得解
没必要
确实和你说得那个一样 可以用string interleave得方法来做
但是内循环要从后往前走
【在 w***o 的大作中提到】
: 大牛们很忙，让我来给你解释解释。我两水平差不多，我的思路对你可能容易理解一点
: 。这题主要是要逼你写DP，而且是Buttomup的。我没有二爷那么牛，可以直接写
: buttomup的DP，我是一步一步来的。不好意思C＋＋早忘了，java的，你凑合看吧。
: 先来recursive without DP。
: public int numDistinct(String S, String T) {
: if(T.length() == 0)
: return 1;
:
: if(S.length() < T.length())
: return 0;
| h****n
发帖数: 1093 | 8 举一反三，将来必定又是一个大牛啊
贴贴我的代码：
class Solution {
public:
int numDistinct(string S, string T) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
//return recursive(S,T);
return DP(S,T);
}
int DP(string S, string T)
{
int m = T.size();
int n = S.size();
vector >matrix(m+1, vector(n+1,0));
int i,j;
for(i=0;i<=n;i++)
matrix[0][i] = 1;
for(i=1;i<=m;i++)
matrix[i][0] = 0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(S[j-1]==T[i-1])
matrix[i][j] = matrix[i-1][j-1] + matrix[i][j-1];
else matrix[i][j] = matrix[i][j-1];
}
return matrix[m][n];
}
int recursive(string S, string T)
{
int sizeS = S.size();
int sizeT = T.size();
if(sizeT == 0) return 1;
if(sizeS == 0) return 0;
if(S[0]==T[0])
return numDistinct(S.substr(1),T.substr(1))+numDistinct(S.substr
(1),T);
else return numDistinct(S.substr(1),T);
}
};
【在 w***o 的大作中提到】
: 大牛们很忙，让我来给你解释解释。我两水平差不多，我的思路对你可能容易理解一点
: 。这题主要是要逼你写DP，而且是Buttomup的。我没有二爷那么牛，可以直接写
: buttomup的DP，我是一步一步来的。不好意思C＋＋早忘了，java的，你凑合看吧。
: 先来recursive without DP。
: public int numDistinct(String S, String T) {
: if(T.length() == 0)
: return 1;
:
: if(S.length() < T.length())
: return 0;
| w***o
发帖数: 109 | 9 建议把
for(j=1;j<=n;j++)
改成
for(j=i;j<=n;j++)
因为j必须>= i
【在 h****n 的大作中提到】
: 举一反三，将来必定又是一个大牛啊
: 贴贴我的代码：
: class Solution {
: public:
: int numDistinct(string S, string T) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: //return recursive(S,T);
: return DP(S,T);
: }
|
|
