d******a
发帖数: 238 | 1 是个老印，扯了会工作经验和多线程，然后两道题，感觉老印不太友好。。
1. shifted sorted array找最大元素.
23451 return 5
12345 return 5
2. 3个string a, b, c.判断c是否是a和b的interleave，也就是c中应该有a,b中所有字
符，并且c中字符顺序和a,b中一样。
a = "ef" b = "gh" c = "egfh" return true
a = "ef" b = "gh" c = "ehgf" return false |
l*****a
发帖数: 14598 | 2 常见题
电话中写成bug free也不那么容易
【在 d******a 的大作中提到】
: 是个老印，扯了会工作经验和多线程，然后两道题，感觉老印不太友好。。
: 1. shifted sorted array找最大元素.
: 23451 return 5
: 12345 return 5
: 2. 3个string a, b, c.判断c是否是a和b的interleave，也就是c中应该有a,b中所有字
: 符，并且c中字符顺序和a,b中一样。
: a = "ef" b = "gh" c = "egfh" return true
: a = "ef" b = "gh" c = "ehgf" return false
|
w****x
发帖数: 2483 | 3 abc算不算ab和bc的inter leave ??
abcde算不算ac和bd的inter leave? |
d******a
发帖数: 238 | 4 不算。a中字符数和b中字符数加起来应该与c中字符数相等。
我知道是常见题，但欢迎贴代码。。 |
h*****n
发帖数: 188 | 5 similar as merging in merge sort.
【在 d******a 的大作中提到】
: 不算。a中字符数和b中字符数加起来应该与c中字符数相等。
: 我知道是常见题，但欢迎贴代码。。
|
w****x
发帖数: 2483 | 6 不简单啊,抛个砖:
ab ac => acab
递归:
ab ac acab -> b ac cab c != a && c != b return false
ab ac acab -> ab c cab -> ab "" ab -> b "" b -> "" "" "" return true; |
w****x
发帖数: 2483 | 7
问题是相等的时候不知道移哪个
【在 h*****n 的大作中提到】
: similar as merging in merge sort.
|
p*****2
发帖数: 21240 | |
p*****2
发帖数: 21240 | 9
相等时候就变O(n)了。
【在 w****x 的大作中提到】
:
: 问题是相等的时候不知道移哪个
|
f*****e
发帖数: 2992 | 10 1. if(a[n/2]
if(a[n/2]>a[n])find right half;
if(a[1]
2. 从后面开始找。f("eh","gh","egfh")=f("e","gh","egf") || f("eh","g","egf")
【在 d******a 的大作中提到】
: 是个老印，扯了会工作经验和多线程，然后两道题，感觉老印不太友好。。
: 1. shifted sorted array找最大元素.
: 23451 return 5
: 12345 return 5
: 2. 3个string a, b, c.判断c是否是a和b的interleave，也就是c中应该有a,b中所有字
: 符，并且c中字符顺序和a,b中一样。
: a = "ef" b = "gh" c = "egfh" return true
: a = "ef" b = "gh" c = "ehgf" return false
|
|
|
c*****n
发帖数: 96 | 11 bool isInterleave(String a, String b, String c){
return isInterleave(a, b, c, "");
}
bool isInterleav(String a, String b, String c, String interleave){
if (String.IsNullOrEmpty(a) && String.IsNullOrEmpty(b)){
return c.equals(interleave);
}
if (String.IsNullOrEmpty(a))
return c.equals(interleave + b);
if (String.IsNullOrEmpty(b))
return c.equals(interleave + a);
return isInterleave(a.SubString(1), b, c, interleave + a.SubString(0,1))
|| isInterleave(a, b.SubString(1), c, interleave + b.SubString(0,1));
} |
l*****a
发帖数: 14598 | 12 不明白hashset有什么用
【在 p*****2 的大作中提到】
:
: 相等时候就变O(n)了。
|
w****x
发帖数: 2483 | 13
我靠, 二爷标准的dfs + cache
【在 p*****2 的大作中提到】
:
: 相等时候就变O(n)了。
|
d******a
发帖数: 238 | 14 ab ac => acab 这种情况应该返回true. 我面完后想了用递归写了个简单的，不知道可
能会有啥bug..
bool interleave(const char *a, const char *b, const char *c)
{
assert(a != NULL && b != NULL && c!= NULL);
if (*a == '\0' && *b == '\0' && *c == '\0')
return true;
if (*a == *c && *c != '\0' && interleave(a + 1, b, c + 1) )
return true;
if (*b == *c && *c != '\0' && interleave(a, b + 1, c + 1) )
return true;
return false;
} |
l*****a
发帖数: 14598 | 15 直接拿c的subString去比较不可以吗？
为什么非要再弄一个？
【在 c*****n 的大作中提到】
: bool isInterleave(String a, String b, String c){
: return isInterleave(a, b, c, "");
: }
: bool isInterleav(String a, String b, String c, String interleave){
: if (String.IsNullOrEmpty(a) && String.IsNullOrEmpty(b)){
: return c.equals(interleave);
: }
:
: if (String.IsNullOrEmpty(a))
: return c.equals(interleave + b);
|
l*****a
发帖数: 14598 | 16 *a==*b==*c的时候要单独处理
【在 d******a 的大作中提到】
: ab ac => acab 这种情况应该返回true. 我面完后想了用递归写了个简单的，不知道可
: 能会有啥bug..
: bool interleave(const char *a, const char *b, const char *c)
: {
: assert(a != NULL && b != NULL && c!= NULL);
:
: if (*a == '\0' && *b == '\0' && *c == '\0')
: return true;
:
: if (*a == *c && *c != '\0' && interleave(a + 1, b, c + 1) )
|
g**e
发帖数: 6127 | 17 标记c里面已经被a match的位置
【在 l*****a 的大作中提到】
: 不明白hashset有什么用
|
l*****a
发帖数: 14598 | 18 我的意思说，感觉是多余的
可以不用
【在 g**e 的大作中提到】
: 标记c里面已经被a match的位置
|
p*****2
发帖数: 21240 | 19
的确。
boolean dfs(String a, String b, String c, int i, int j)
{
if(i+j==c.length())
return true;
if(i
{
if(dfs(a,b,c,i+1,j))
return true;
}
if(j
{
if(dfs(a,b,c,i,j+1))
return true;
}
return false;
}
boolean isInterleave(String a, String b, String c)
{
if(a==null || b==null || c==null || a.length()+b.length()!=c.length(
))
return false;
return dfs(a,b,c,0,0);
}
【在 l*****a 的大作中提到】
: 我的意思说，感觉是多余的
: 可以不用
|
d******a
发帖数: 238 | 20 我觉得我代码里单独处理了啊。你能给个反例吗？
【在 l*****a 的大作中提到】
: *a==*b==*c的时候要单独处理
|
|
|
l*****a
发帖数: 14598 | 21 又多用了一个参数
我认为 i+j ==k
不是吗？
【在 p*****2 的大作中提到】
:
: 的确。
: boolean dfs(String a, String b, String c, int i, int j)
: {
: if(i+j==c.length())
: return true;
:
: if(i: {
: if(dfs(a,b,c,i+1,j))
|
p*****2
发帖数: 21240 | 22
确实是。改正了。多谢指导。
【在 l*****a 的大作中提到】
: 又多用了一个参数
: 我认为 i+j ==k
: 不是吗？
|
i***e
发帖数: 452 | 23 大牛， 你这个是你最后的version吗？ 好像不对啊。 没考虑相等情况啊
【在 p*****2 的大作中提到】
:
: 确实是。改正了。多谢指导。
|
p*****2
发帖数: 21240 | 24
相等是什么情况呀？举个例子好吗？
【在 i***e 的大作中提到】
: 大牛， 你这个是你最后的version吗？ 好像不对啊。 没考虑相等情况啊
|
i***e
发帖数: 452 | 25 再看了一下大牛的程序。 你的是对的！
【在 p*****2 的大作中提到】
:
: 相等是什么情况呀？举个例子好吗？
|
i***e
发帖数: 452 | 26 感觉大牛程序越写月精妙了， 一点都不累赘啊！佩服啊！！这是一次到位的吗？
【在 p*****2 的大作中提到】
:
: 相等是什么情况呀？举个例子好吗？
|
p*****2
发帖数: 21240 | 27
不是。lolhaha指点了两次。第一次没好好想写了一个累赘的。第二次多用了一个变量
，第三次写成这样子的。还是得多练呀。
【在 i***e 的大作中提到】
: 感觉大牛程序越写月精妙了， 一点都不累赘啊！佩服啊！！这是一次到位的吗？
|
i**********e
发帖数: 1145 | 28 刚加了这题，题目为 "Interleaving String"。可以网上测试程序。 |
i**********e
发帖数: 1145 | 29 这题可以优化用dp，通常看到递归用 i+1,j，要不然递归 i,j+1，这就是很明显的可以
转换非递归dp。
dp[i,j] = whether s3[i+j] can be formed as interleaving of substrings s1(0,i
) and s2(0,j).
eg, s1 = "hello", s1(0,1) = "h".
Then,
dp[i,j] = dp[i-1,j] && s1[i-1] == s3[i+j-1]
|| dp[i, j-1] && s2[j-1] == s3[i+j-1]
总复杂度 O(m*n). |
p*****2
发帖数: 21240 | 30 写了一个dp的。
public boolean isInterleave(String s1, String s2, String s3)
{
if(s1==null || s2==null || s3==null)
return false;
int l1=s1.length();
int l2=s2.length();
int l3=s3.length();
if(l1+l2!=l3)
return false;
boolean[][] dp=new boolean[l1+1][l2+1];
dp[l1][l2]=true;
for(int i=l1;i>=0;i--)
for(int j=l2;j>=0;j--)
{
if(i
dp[i][j]=true;
if(j
dp[i][j]=true;
}
return dp[0][0];
} |
|
|
p*****2
发帖数: 21240 | 31 感觉两个月没怎么做题，脑子不怎么转了呀。做题感觉可很是退步不少。 |
p*****2
发帖数: 21240 | 32 这题挺有意思。貌似topdown DP 快于 bottomup DP。典型的topdown可以避免一些无用
的计算。 |
w****x
发帖数: 2483 | 33
你给改成O(n)空间的吧, O(n^2)没必要
【在 p*****2 的大作中提到】
: 写了一个dp的。
: public boolean isInterleave(String s1, String s2, String s3)
: {
: if(s1==null || s2==null || s3==null)
: return false;
:
: int l1=s1.length();
: int l2=s2.length();
: int l3=s3.length();
: if(l1+l2!=l3)
|
l*****a
发帖数: 14598 | 34 你拍的真不错
【在 i***e 的大作中提到】
: 感觉大牛程序越写月精妙了， 一点都不累赘啊！佩服啊！！这是一次到位的吗？
|
p*****2
发帖数: 21240 | 35
代码要麻烦一些。
public boolean isInterleave(String s1, String s2, String s3)
{
if(s1==null || s2==null || s3==null)
return false;
int l1=s1.length();
int l2=s2.length();
int l3=s3.length();
if(l1+l2!=l3)
return false;
boolean[][] dp=new boolean[2][l2+1];
for(int i=l1;i>=0;i--)
{
int id=i%2;
Arrays.fill(dp[id],false);
for(int j=l2;j>=0;j--)
{
if(i==l1 && j==l2)
{
dp[id][j]=true;
continue;
}
if(i
{
dp[id][j]=true;
continue;
}
if(j
dp[id][j]=true;
}
}
return dp[0][0];
}
【在 w****x 的大作中提到】
:
: 你给改成O(n)空间的吧, O(n^2)没必要
|
p*****2
发帖数: 21240 | 36
貌似隐形拍你。
【在 l*****a 的大作中提到】
: 你拍的真不错
|
l*****a
发帖数: 14598 | 37 it will be better to use >>1 to replace %2
【在 p*****2 的大作中提到】
:
: 貌似隐形拍你。
|
p*****2
发帖数: 21240 | 38
>>1 是 ／2吧？
【在 l*****a 的大作中提到】
: it will be better to use >>1 to replace %2
|
l*****a
发帖数: 14598 | 39 oh
then &0x1
【在 p*****2 的大作中提到】
:
: >>1 是 ／2吧？
|
l****c
发帖数: 782 | 40 第二题，小测试过了，大测试Time Limit Exceeded怎么回事呢
class Solution {
public:
bool isInterleave(string s, string s1, string s2, int s_index, int s1_index,
int s2_index)
{
if (s_index == s.size()) {
if((s1_index == s1.size())&&(s2_index == s2.size()))
return true;
else
return false;
}
else {
if (s1_index==s1.size()&&s2_index==s2.size())
return false;
else if (s1_index==s1.size()) {
if (s[s_index]==s2[s2_index]&&(isInterleave(s,s1,s2,s_index+1,
s1_index, s2_index+1)))
return true;
else
return false;
}
else if (s2_index==s2.size()) {
if (s[s_index]==s1[s1_index]&&(isInterleave(s,s1,s2,s_index+1,
s1_index+1, s2_index)))
return true;
else
return false;
}
else if (s[s_index]==s1[s1_index]&&(isInterleave(s,s1,s2,s_index+1,
s1_index+1, s2_index)))
return true;
else if (s[s_index]==s2[s2_index]&&(isInterleave(s,s1,s2,s_index+1,
s1_index, s2_index+1)))
return true;
else
return false;
}
}
bool isInterleave(string s1, string s2, string s3) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
return isInterleave(s3, s1, s2, 0,0,0);
}
}; |
|
|
p*****2
发帖数: 21240 | 41
index,
你这个不是DP。
【在 l****c 的大作中提到】
: 第二题，小测试过了，大测试Time Limit Exceeded怎么回事呢
: class Solution {
: public:
: bool isInterleave(string s, string s1, string s2, int s_index, int s1_index,
: int s2_index)
: {
: if (s_index == s.size()) {
: if((s1_index == s1.size())&&(s2_index == s2.size()))
: return true;
: else
|
l****c
发帖数: 782 | 42 嗯，明白了，只允许n^2的大O啊。。。
recursion都不允许啊。。。。
学习了，大牛。
是不是这种找组合的都最好用DP啊？
【在 p*****2 的大作中提到】
:
: index,
: 你这个不是DP。
|
p*****2
发帖数: 21240 | 43
不对。这题我感觉recursion更快一些。过大数据比较容易。但是你要加DP才行。
DP分两种，recursion也可以DP。今天有人发了相关的帖子，你看看就明白了。
【在 l****c 的大作中提到】
: 嗯，明白了，只允许n^2的大O啊。。。
: recursion都不允许啊。。。。
: 学习了，大牛。
: 是不是这种找组合的都最好用DP啊？
|
l****c
发帖数: 782 | 44 加DP的recursion是指 dp_table[m][n] = foo(...m-1,n|| ...m,n-1)吗？
我用的是不好的recursion。。。。
【在 p*****2 的大作中提到】
:
: 不对。这题我感觉recursion更快一些。过大数据比较容易。但是你要加DP才行。
: DP分两种，recursion也可以DP。今天有人发了相关的帖子，你看看就明白了。
|
p*****2
发帖数: 21240 | 45
看我的例子。
int[][] dp=null;
boolean dfs(String a, String b, String c, int i, int j)
{
if(dp[i][j]!=-1)
return dp[i][j]==1;
dp[i][j]=0;
if(i+j==c.length())
{
dp[i][j]=1;
}
else
{
if(i
dp[i][j]=1;
if(dp[i][j]==0 && j
,b,c,i,j+1))
dp[i][j]=1;
}
return dp[i][j]==1;
}
public boolean isInterleave(String s1, String s2, String s3)
{
if(s1.length()+s2.length()!=s3.length())
return false;
dp=new int[s1.length()+1][s2.length()+1];
for(int i=0;i<=s1.length();i++)
Arrays.fill(dp[i],-1);
return dfs(s1,s2,s3,0,0);
}
【在 l****c 的大作中提到】
: 加DP的recursion是指 dp_table[m][n] = foo(...m-1,n|| ...m,n-1)吗？
: 我用的是不好的recursion。。。。
|
l****c
发帖数: 782 | 46 换了DP,觉得和你第二页做的很像，应该是n^2了。
可过了小测试，过不了大测试啊。
您的那个代码也是只能过小测试。。。。。。
boolean isInterleave(string s, string s1, string s2)
{
if (s.length()!=(s1.length()+s2.length())) return false;
int l1 = s1.length()+1;
int l2 = s2.length()+1;
bool **dpt = (bool**)malloc(sizeof(bool*)*l1);
for (int i = 0; i < l1; i++)
dpt[i] = (bool*)malloc(sizeof(bool)*l1);
for (int i = 0; i < l1; i++) {
for (int j = 0; j < l2; j++) {
if (i==0&&j==0)
dpt[i][j] = true;
else {
if (j>0&&s2[j-1]==s[i+j-1]&&dpt[i][j-1])
dpt[i][j] = true;
else if (i>0&&s1[i-1]==s[i+j-1]&&dpt[i-1][j])
dpt[i][j] = true;
else
dpt[i][j] = false;
}
}
}
return dpt[l1-1][l2-1];
}
【在 p*****2 的大作中提到】
:
: 看我的例子。
: int[][] dp=null;
:
: boolean dfs(String a, String b, String c, int i, int j)
: {
: if(dp[i][j]!=-1)
: return dp[i][j]==1;
:
: dp[i][j]=0;
|
i**********e
发帖数: 1145 | 47 哎呀，吓我一跳，还以为系统出了问题。
没关系，只是你程序出了个小bug。
dpt[i] = (bool*)malloc(sizeof(bool)*l1);
应该是 * l2 才对阿 :)
【在 l****c 的大作中提到】
: 换了DP,觉得和你第二页做的很像，应该是n^2了。
: 可过了小测试，过不了大测试啊。
: 您的那个代码也是只能过小测试。。。。。。
: boolean isInterleave(string s, string s1, string s2)
: {
: if (s.length()!=(s1.length()+s2.length())) return false;
: int l1 = s1.length()+1;
: int l2 = s2.length()+1;
: bool **dpt = (bool**)malloc(sizeof(bool*)*l1);
: for (int i = 0; i < l1; i++)
|
i**********e
发帖数: 1145 | 48
>>: 您的那个代码也是只能过小测试。。。。。。
我现在改了一下large input，现在二爷的程序能过large 了。你现在可以试试。
主要是之前的large input 需要太多内存了，我机器可没有那么多内存，而导致运行速
度巨慢。之前二爷能过large 很有可能是当时机器内存比较足够。jvm 确实是麻烦，用
太多内存了。
【在 l****c 的大作中提到】
: 换了DP,觉得和你第二页做的很像，应该是n^2了。
: 可过了小测试，过不了大测试啊。
: 您的那个代码也是只能过小测试。。。。。。
: boolean isInterleave(string s, string s1, string s2)
: {
: if (s.length()!=(s1.length()+s2.length())) return false;
: int l1 = s1.length()+1;
: int l2 = s2.length()+1;
: bool **dpt = (bool**)malloc(sizeof(bool*)*l1);
: for (int i = 0; i < l1; i++)
|
l****c
发帖数: 782 | 49 感谢大牛啊～～昨晚挑灯熬夜的，糊涂了。
谢谢谢谢:)
【在 i**********e 的大作中提到】
:
: >>: 您的那个代码也是只能过小测试。。。。。。
: 我现在改了一下large input，现在二爷的程序能过large 了。你现在可以试试。
: 主要是之前的large input 需要太多内存了，我机器可没有那么多内存，而导致运行速
: 度巨慢。之前二爷能过large 很有可能是当时机器内存比较足够。jvm 确实是麻烦，用
: 太多内存了。
|
p*****2
发帖数: 21240 | 50
这题我测试的时候DFS非常容易过大数据。
【在 i**********e 的大作中提到】
: 哎呀，吓我一跳，还以为系统出了问题。
: 没关系，只是你程序出了个小bug。
: dpt[i] = (bool*)malloc(sizeof(bool)*l1);
: 应该是 * l2 才对阿 :)
|
|
|
d******a
发帖数: 238 | 51 第二题老印说递归就行了，他都没想到过dp.其实大家也可以贴下第一题的代码,交流下
代码有助于提高。 |
p*****2
发帖数: 21240 | 52
第一题careercup上有现成的。如果没练过的话其实不好写。
这两道题都属于中等偏上难度的题。电面搞两道真是不容易了。
【在 d******a 的大作中提到】
: 第二题老印说递归就行了，他都没想到过dp.其实大家也可以贴下第一题的代码,交流下
: 代码有助于提高。
|
d******a
发帖数: 238 | 53 careercup上是找一个元素的索引吧，和这个还是有些不同的，您可以贴下代码试试。
【在 p*****2 的大作中提到】
:
: 第一题careercup上有现成的。如果没练过的话其实不好写。
: 这两道题都属于中等偏上难度的题。电面搞两道真是不容易了。
|
p*****2
发帖数: 21240 | 54
我刚才也重新看了一下题。不一样。这题感觉更容易呀。等一下。
【在 d******a 的大作中提到】
: careercup上是找一个元素的索引吧，和这个还是有些不同的，您可以贴下代码试试。
|
d******a
发帖数: 238 | |
p*****2
发帖数: 21240 | 56
OK.刚写了一个没有重复的。
【在 d******a 的大作中提到】
: 注意数组元素可能有重复的。
|
p*****2
发帖数: 21240 | 57 写了一个这样子的，有点累赘
int max(int[] A)
{
if(A==null || A.length==0)
return -1;
int n=A.length;
int i=0;
int j=n-1;
while(i
{
if(A[j]>A[i])
return A[j];
else
{
int m=i+(j-i)/2;
if(A[m]>A[i])
i=m;
else if(A[m]
j=m-1;
else
{
if(A[m+1]
return A[m];
else
i=m+1;
}
}
}
return A[i];
} |
d******a
发帖数: 238 | 58 你这个程序写得很好的，我当时写的应该有bug.
while(i < j) 和 while (i <= j)有些不同啊。 |
p*****2
发帖数: 21240 | 59
我感觉只剩一个元素的时候就不用比了，就是它了。
【在 d******a 的大作中提到】
: 你这个程序写得很好的，我当时写的应该有bug.
: while(i < j) 和 while (i <= j)有些不同啊。
|
i**********e
发帖数: 1145 | 60 DFS 暴力解过不了大数据吧？
【在 p*****2 的大作中提到】
:
: 我感觉只剩一个元素的时候就不用比了，就是它了。
|
|
|
p*****2
发帖数: 21240 | 61
DFS＋cache更容易。应该是skip掉了不需要的计算。
【在 i**********e 的大作中提到】
: DFS 暴力解过不了大数据吧？
|
l*****a
发帖数: 14598 | 62 能山掉中间冗余的行吗？
【在 p*****2 的大作中提到】
: 写了一个这样子的，有点累赘
: int max(int[] A)
: {
: if(A==null || A.length==0)
: return -1;
:
: int n=A.length;
: int i=0;
: int j=n-1;
:
|
p*****2
发帖数: 21240 | 63
大牛帮我把逻辑简化一下吧。
【在 l*****a 的大作中提到】
: 能山掉中间冗余的行吗？
|
j********2
发帖数: 82 | 64 大牛稍微解释一下O(N) space 的吧
【在 p*****2 的大作中提到】
:
: 大牛帮我把逻辑简化一下吧。
|
l*****a
发帖数: 14598 | 65 先吧这桑行变成两行
其他的等你找人把我的简历递到卖力公司HM手里之后再谈
int n=A.length;
: int i=0;
: int j=n-1;
【在 p*****2 的大作中提到】
:
: 大牛帮我把逻辑简化一下吧。
|
j*****7
发帖数: 10575 | 66 感觉大家是不是太过复杂了，还是我看漏边界条件了。最简单的办法是从后往前找。例如
a="ab";
b="ac"
c="abac"
boolean[] visited = new boolean[c.length()]; // 用于标记当前index被用过没有
用a来从c的结尾开始找，都找到了
visited = {true, true, false, false}
然后用b来找那些标记为false的，也是从后向前找，都找到了
最后visited都是true,就成功了，否则return false
时间上是 2N |
H****r
发帖数: 2801 | 67 这题不需要m*n内存，用2*（min(m,n))就可以了，update时循环使用buffer即可
【在 i**********e 的大作中提到】
: DFS 暴力解过不了大数据吧？
|
H****r
发帖数: 2801 | 68 循环使用buffer空间复杂度是 O(min(m,n))
,i
【在 i**********e 的大作中提到】
: 这题可以优化用dp，通常看到递归用 i+1,j，要不然递归 i,j+1，这就是很明显的可以
: 转换非递归dp。
: dp[i,j] = whether s3[i+j] can be formed as interleaving of substrings s1(0,i
: ) and s2(0,j).
: eg, s1 = "hello", s1(0,1) = "h".
: Then,
: dp[i,j] = dp[i-1,j] && s1[i-1] == s3[i+j-1]
: || dp[i, j-1] && s2[j-1] == s3[i+j-1]
: 总复杂度 O(m*n).
|
H****r
发帖数: 2801 | 69 建议加大large input, 此题空间复杂度是O(min(m,n))不应该内存不够的
【在 i**********e 的大作中提到】
: DFS 暴力解过不了大数据吧？
|
t****a
发帖数: 1212 | 70 a lisp solution, O(n) complexity
;; O(n) solution
(defn interleave? [a b c]
(cond (and (= (count a) 0) (= (count b) 0) (= (count c) 0)) true
(not= (+ (count a) (count b)) (count c)) false
(= (last a) (last c)) (interleave? (butlast a) b (butlast c))
(= (last b) (last c)) (interleave? a (butlast b) (butlast c))
:else false))
(interleave? "ef" "gh" "egfh") ; returned true
(interleave? "ef" "gh" "ehgf") ; returned false
(interleave? "abcc" "ac" "aabccc") ; returned true |
|
|
w****x
发帖数: 2483 | 71
我靠， 这个程序太牛B了！！
我用rec[l1][l2]复杂的死翘翘了.....
【在 p*****2 的大作中提到】
: 写了一个dp的。
: public boolean isInterleave(String s1, String s2, String s3)
: {
: if(s1==null || s2==null || s3==null)
: return false;
:
: int l1=s1.length();
: int l2=s2.length();
: int l3=s3.length();
: if(l1+l2!=l3)
|
H****r
发帖数: 2801 | 72 北2爷这个程序很有意思啊！难道是dfs+dp? 为啥这样会更加efficient? 有一段没来，
北2爷貌似全语言制霸了啊。
【在 p*****2 的大作中提到】
:
: 大牛帮我把逻辑简化一下吧。
|
w***o
发帖数: 109 | 73 反例：
a = "deab"
b = "feac"
c = "defeacab"
不管从头还是从尾扫都是false,但实际应该是true;
例如
【在 j*****7 的大作中提到】
: 感觉大家是不是太过复杂了，还是我看漏边界条件了。最简单的办法是从后往前找。例如
: a="ab";
: b="ac"
: c="abac"
: boolean[] visited = new boolean[c.length()]; // 用于标记当前index被用过没有
: 用a来从c的结尾开始找，都找到了
: visited = {true, true, false, false}
: 然后用b来找那些标记为false的，也是从后向前找，都找到了
: 最后visited都是true,就成功了，否则return false
: 时间上是 2N
|
H****r
发帖数: 2801 | 74 这个过OJ了？
【在 w***o 的大作中提到】
: 反例：
: a = "deab"
: b = "feac"
: c = "defeacab"
: 不管从头还是从尾扫都是false,但实际应该是true;
:
: 例如
|
w***o
发帖数: 109 | 75 好像有问题。再考虑
【在 H****r 的大作中提到】
: 这个过OJ了？
|
w****x
发帖数: 2483 | 76 上个O(n)空间的
bool isInterleave(string s1, string s2, string s3) {
const char* p1 = s1.c_str();
const char* p2 = s2.c_str();
const char* p3 = s3.c_str();
int nLen1 = strlen(p1);
int nLen2 = strlen(p2);
int nLen3 = strlen(p3);
if (nLen3 != nLen1 + nLen2)
return false;
if (nLen3 == 0) return true;
bool* rec = new bool[nLen2+1];
for (int i = nLen1; i >= 0; i--)
{
for (int j = nLen2; j >= 0; j--)
{
if (i == nLen1 && j == nLen2)
rec[j] = true;
else
{
bool bFlg = false;
if (p1[i] == p3[i+j] && i != nLen1 && rec[j])
bFlg = true;
if (p2[j] == p3[i+j] && j != nLen2 && rec[j+1])
bFlg = true;
rec[j] = bFlg;
}
}
}
bool bRet = rec[0];
delete []rec;
return bRet;
} |
H****r
发帖数: 2801 | 77 这一步是我一直没搞透的一个地方，能展开讲讲吗？
【在 p*****2 的大作中提到】
: 这题挺有意思。貌似topdown DP 快于 bottomup DP。典型的topdown可以避免一些无用
: 的计算。
|
j*****7
发帖数: 10575 | 78 哎呦，总算看明白了
是不work
【在 w***o 的大作中提到】
: 反例：
: a = "deab"
: b = "feac"
: c = "defeacab"
: 不管从头还是从尾扫都是false,但实际应该是true;
:
: 例如
|
b*******y
发帖数: 2048 | 79 发信人: wasco (wasco), 信区: JobHunting
标 题: Re: facebook的面试题
发信站: BBS 未名空间站 (Mon Sep 17 13:23:17 2012, 美东)
反例：
a = "deab"
b = "feac"
c = "defeacab"
这个case也过不了
【在 d******a 的大作中提到】
: ab ac => acab 这种情况应该返回true. 我面完后想了用递归写了个简单的，不知道可
: 能会有啥bug..
: bool interleave(const char *a, const char *b, const char *c)
: {
: assert(a != NULL && b != NULL && c!= NULL);
:
: if (*a == '\0' && *b == '\0' && *c == '\0')
: return true;
:
: if (*a == *c && *c != '\0' && interleave(a + 1, b, c + 1) )
|
t****a
发帖数: 1212 | 80 这个题目就是个DP啊... O(n)时间就可以解决。大家为什么在这题目上讨论这么久时间
？ |
|
|
o******e
发帖数: 81 | 81 发现一个bug，当a[i] == a[m]的时候，此时max可能在左边也可能在右边。比如：
5 6 (5) 5 5
5 5 (5) 6 5
(5) 6
(6) 5
改了一下，请指正：
int FindMax(int[] array)
{
if (array == null || array.Length == 0)
throw new ArgumentException("null or empty array");
int lo = 0, hi = array.Length - 1;
while (lo < hi)
{
int mid = lo + (hi - lo) / 2;
if (array[mid] > array[lo])
lo = mid;
else if (array[mid] < array[lo])
hi = mid - 1;
else if (array[lo] <= array[hi])
++lo;
else
--hi;
}
return array[lo];
}
【在 p*****2 的大作中提到】
: 写了一个这样子的，有点累赘
: int max(int[] A)
: {
: if(A==null || A.length==0)
: return -1;
:
: int n=A.length;
: int i=0;
: int j=n-1;
:
|
