现在用什么卡买白香草 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Money - 海外理财

现在用什么卡买白香草

现在用什么卡买白香草# Money - 海外理财

d*a2014-01-13 08:01

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

a*n2014-01-13 08:01

2 楼

貌似chase没有5%了

l*a2014-01-13 08:01

3 楼

常见题
电话中写成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

m*y2014-01-13 08:01

4 楼

难道不是dividend？

w*x2014-01-13 08:01

5 楼

abc算不算ab和bc的inter leave ??
abcde算不算ac和bd的inter leave?

a*92014-01-13 08:01

6 楼

dividend Q1 @ CVS，系统应该能刷过CC，可能有cap
freedom Q1 @ 711，基本刷不过
ink @ od，没这个卡，据说很多地方也刷不过？

d*a2014-01-13 08:01

7 楼

不算。a中字符数和b中字符数加起来应该与c中字符数相等。
我知道是常见题，但欢迎贴代码。。

d*l2014-01-13 08:01

8 楼

walgreens没有?

【在 a*****9 的大作中提到】

: dividend Q1 @ CVS，系统应该能刷过CC，可能有cap
: freedom Q1 @ 711，基本刷不过
: ink @ od，没这个卡，据说很多地方也刷不过？

h*n2014-01-13 08:01

9 楼

similar as merging in merge sort.

【在 d******a 的大作中提到】

: 不算。a中字符数和b中字符数加起来应该与c中字符数相等。
: 我知道是常见题，但欢迎贴代码。。

c*22014-01-13 08:01

10 楼

if one-vanilla VGC is available, you can get it at some 7-11(using Freedom)
and Walgreen (using Citi div) and get 5% this quarter.

w*x2014-01-13 08:01

11 楼

不简单啊,抛个砖:
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;

h*s2014-01-13 08:01

12 楼

OD的白香草不能用CC买，很早之前就这样的了。

【在 a*****9 的大作中提到】

: dividend Q1 @ CVS，系统应该能刷过CC，可能有cap
: freedom Q1 @ 711，基本刷不过
: ink @ od，没这个卡，据说很多地方也刷不过？

w*x2014-01-13 08:01

13 楼

问题是相等的时候不知道移哪个

【在 h*****n 的大作中提到】

: similar as merging in merge sort.

c*u2014-01-13 08:01

14 楼

不是7-11早就不能用cc了嗎，現在到底哪裡還可以買？

p*22014-01-13 08:01

15 楼

第二题dfs可解

h*s2014-01-13 08:01

16 楼

cvs

【在 c********u 的大作中提到】

: 不是7-11早就不能用cc了嗎，現在到底哪裡還可以買？

p*22014-01-13 08:01

17 楼

相等时候就变O(n)了。

【在 w****x 的大作中提到】

:
: 问题是相等的时候不知道移哪个

l*n2014-01-13 08:01

18 楼

bcp在菜店

f*e2014-01-13 08:01

19 楼

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 的大作中提到】

s*r2014-01-13 08:01

20 楼

哪家菜店有白香草？

【在 l*****n 的大作中提到】

: bcp在菜店

c*n2014-01-13 08:01

21 楼

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

t*u2014-01-13 08:01

22 楼

walmart，food city等，都应该有

【在 s********r 的大作中提到】

: 哪家菜店有白香草？

l*a2014-01-13 08:01

23 楼

不明白hashset有什么用

【在 p*****2 的大作中提到】

:
: 相等时候就变O(n)了。

h*s2014-01-13 08:01

24 楼

为什么应该有？

【在 t***u 的大作中提到】

: walmart，food city等，都应该有

w*x2014-01-13 08:01

25 楼

我靠, 二爷标准的dfs + cache

【在 p*****2 的大作中提到】

:
: 相等时候就变O(n)了。

l*n2014-01-13 08:01

26 楼

版上有人说kroger有，不过我看过一次，kroger没有，回头去别家店看看

【在 s********r 的大作中提到】

: 哪家菜店有白香草？

d*a2014-01-13 08:01

27 楼

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*a2014-01-13 08:01

28 楼

直接拿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*a2014-01-13 08:01

29 楼

*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*e2014-01-13 08:01

30 楼

标记c里面已经被a match的位置

【在 l*****a 的大作中提到】

: 不明白hashset有什么用

l*a2014-01-13 08:01

31 楼

我的意思说，感觉是多余的
可以不用

【在 g**e 的大作中提到】

: 标记c里面已经被a match的位置

p*22014-01-13 08:01

32 楼

的确。
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*a2014-01-13 08:01

33 楼

我觉得我代码里单独处理了啊。你能给个反例吗？

【在 l*****a 的大作中提到】

: *a==*b==*c的时候要单独处理

l*a2014-01-13 08:01

34 楼

又多用了一个参数
我认为 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*22014-01-13 08:01

35 楼

确实是。改正了。多谢指导。

【在 l*****a 的大作中提到】

: 又多用了一个参数
: 我认为 i+j ==k
: 不是吗？

i*e2014-01-13 08:01

36 楼

大牛，你这个是你最后的version吗？好像不对啊。没考虑相等情况啊

【在 p*****2 的大作中提到】

:
: 确实是。改正了。多谢指导。

p*22014-01-13 08:01

37 楼

相等是什么情况呀？举个例子好吗？

【在 i***e 的大作中提到】

: 大牛，你这个是你最后的version吗？好像不对啊。没考虑相等情况啊

i*e2014-01-13 08:01

38 楼

再看了一下大牛的程序。你的是对的！

【在 p*****2 的大作中提到】

:
: 相等是什么情况呀？举个例子好吗？

i*e2014-01-13 08:01

39 楼

感觉大牛程序越写月精妙了，一点都不累赘啊！佩服啊！！这是一次到位的吗？

【在 p*****2 的大作中提到】

:
: 相等是什么情况呀？举个例子好吗？

p*22014-01-13 08:01

40 楼

不是。lolhaha指点了两次。第一次没好好想写了一个累赘的。第二次多用了一个变量
，第三次写成这样子的。还是得多练呀。

【在 i***e 的大作中提到】

: 感觉大牛程序越写月精妙了，一点都不累赘啊！佩服啊！！这是一次到位的吗？

i*e2014-01-13 08:01

41 楼

刚加了这题，题目为 "Interleaving String"。可以网上测试程序。

i*e2014-01-13 08:01

42 楼

这题可以优化用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*22014-01-13 08:01

43 楼

写了一个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(idp[i][j]=true;

if(jdp[i][j]=true;
}

return dp[0][0];
}

p*22014-01-13 08:01

44 楼

感觉两个月没怎么做题，脑子不怎么转了呀。做题感觉可很是退步不少。

p*22014-01-13 08:01

45 楼

这题挺有意思。貌似topdown DP 快于 bottomup DP。典型的topdown可以避免一些无用
的计算。

w*x2014-01-13 08:01

46 楼

你给改成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*a2014-01-13 08:01

47 楼

你拍的真不错

【在 i***e 的大作中提到】

: 感觉大牛程序越写月精妙了，一点都不累赘啊！佩服啊！！这是一次到位的吗？

p*22014-01-13 08:01

48 楼

代码要麻烦一些。
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(jdp[id][j]=true;
}
}

return dp[0][0];
}

【在 w****x 的大作中提到】

:
: 你给改成O(n)空间的吧, O(n^2)没必要

p*22014-01-13 08:01

49 楼

貌似隐形拍你。

【在 l*****a 的大作中提到】

: 你拍的真不错

l*a2014-01-13 08:01

50 楼

it will be better to use >>1 to replace %2

【在 p*****2 的大作中提到】

:
: 貌似隐形拍你。

p*22014-01-13 08:01

51 楼

>>1 是／2吧？

【在 l*****a 的大作中提到】

: it will be better to use >>1 to replace %2

l*a2014-01-13 08:01

52 楼

oh
then &0x1

【在 p*****2 的大作中提到】

:
: >>1 是／2吧？

l*c2014-01-13 08:01

53 楼

第二题，小测试过了，大测试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*22014-01-13 08:01

54 楼

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*c2014-01-13 08:01

55 楼

嗯，明白了，只允许n^2的大O啊。。。
recursion都不允许啊。。。。
学习了，大牛。
是不是这种找组合的都最好用DP啊？

【在 p*****2 的大作中提到】

:
: index,
: 你这个不是DP。

p*22014-01-13 08:01

56 楼

不对。这题我感觉recursion更快一些。过大数据比较容易。但是你要加DP才行。
DP分两种，recursion也可以DP。今天有人发了相关的帖子，你看看就明白了。

【在 l****c 的大作中提到】

: 嗯，明白了，只允许n^2的大O啊。。。
: recursion都不允许啊。。。。
: 学习了，大牛。
: 是不是这种找组合的都最好用DP啊？

l*c2014-01-13 08:01

57 楼

加DP的recursion是指 dp_table[m][n] = foo(...m-1,n|| ...m,n-1)吗？
我用的是不好的recursion。。。。

【在 p*****2 的大作中提到】

:
: 不对。这题我感觉recursion更快一些。过大数据比较容易。但是你要加DP才行。
: DP分两种，recursion也可以DP。今天有人发了相关的帖子，你看看就明白了。

p*22014-01-13 08:01

58 楼

看我的例子。
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(idp[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*c2014-01-13 08:01

59 楼

换了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*e2014-01-13 08:01

60 楼

哎呀，吓我一跳，还以为系统出了问题。
没关系，只是你程序出了个小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*e2014-01-13 08:01

61 楼

>>: 您的那个代码也是只能过小测试。。。。。。
我现在改了一下large input，现在二爷的程序能过large 了。你现在可以试试。
主要是之前的large input 需要太多内存了，我机器可没有那么多内存，而导致运行速
度巨慢。之前二爷能过large 很有可能是当时机器内存比较足够。jvm 确实是麻烦，用
太多内存了。

【在 l****c 的大作中提到】

l*c2014-01-13 08:01

62 楼

感谢大牛啊～～昨晚挑灯熬夜的，糊涂了。
谢谢谢谢:)

【在 i**********e 的大作中提到】

:
: >>: 您的那个代码也是只能过小测试。。。。。。
: 我现在改了一下large input，现在二爷的程序能过large 了。你现在可以试试。
: 主要是之前的large input 需要太多内存了，我机器可没有那么多内存，而导致运行速
: 度巨慢。之前二爷能过large 很有可能是当时机器内存比较足够。jvm 确实是麻烦，用
: 太多内存了。

p*22014-01-13 08:01

63 楼

这题我测试的时候DFS非常容易过大数据。

【在 i**********e 的大作中提到】

: 哎呀，吓我一跳，还以为系统出了问题。
: 没关系，只是你程序出了个小bug。
: dpt[i] = (bool*)malloc(sizeof(bool)*l1);
: 应该是 * l2 才对阿 :)

d*a2014-01-13 08:01

64 楼

第二题老印说递归就行了，他都没想到过dp.其实大家也可以贴下第一题的代码,交流下
代码有助于提高。

p*22014-01-13 08:01

65 楼

第一题careercup上有现成的。如果没练过的话其实不好写。
这两道题都属于中等偏上难度的题。电面搞两道真是不容易了。

【在 d******a 的大作中提到】

: 第二题老印说递归就行了，他都没想到过dp.其实大家也可以贴下第一题的代码,交流下
: 代码有助于提高。

d*a2014-01-13 08:01

66 楼

careercup上是找一个元素的索引吧，和这个还是有些不同的，您可以贴下代码试试。

【在 p*****2 的大作中提到】

:
: 第一题careercup上有现成的。如果没练过的话其实不好写。
: 这两道题都属于中等偏上难度的题。电面搞两道真是不容易了。

p*22014-01-13 08:01

67 楼

我刚才也重新看了一下题。不一样。这题感觉更容易呀。等一下。

【在 d******a 的大作中提到】

: careercup上是找一个元素的索引吧，和这个还是有些不同的，您可以贴下代码试试。

d*a2014-01-13 08:01

68 楼

注意数组元素可能有重复的。

p*22014-01-13 08:01

69 楼

OK.刚写了一个没有重复的。

【在 d******a 的大作中提到】

: 注意数组元素可能有重复的。

p*22014-01-13 08:01

70 楼

写了一个这样子的，有点累赘
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*a2014-01-13 08:01

71 楼

你这个程序写得很好的，我当时写的应该有bug.
while(i < j) 和 while (i <= j)有些不同啊。

p*22014-01-13 08:01

72 楼

我感觉只剩一个元素的时候就不用比了，就是它了。

【在 d******a 的大作中提到】

: 你这个程序写得很好的，我当时写的应该有bug.
: while(i < j) 和 while (i <= j)有些不同啊。

i*e2014-01-13 08:01

73 楼

DFS 暴力解过不了大数据吧？

【在 p*****2 的大作中提到】

:
: 我感觉只剩一个元素的时候就不用比了，就是它了。

p*22014-01-13 08:01

74 楼

DFS＋cache更容易。应该是skip掉了不需要的计算。

【在 i**********e 的大作中提到】

: DFS 暴力解过不了大数据吧？

l*a2014-01-13 08:01

75 楼

能山掉中间冗余的行吗？

【在 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*22014-01-13 08:01

76 楼

大牛帮我把逻辑简化一下吧。

【在 l*****a 的大作中提到】

: 能山掉中间冗余的行吗？

j*22014-01-13 08:01

77 楼

大牛稍微解释一下O(N) space 的吧

【在 p*****2 的大作中提到】

:
: 大牛帮我把逻辑简化一下吧。

l*a2014-01-13 08:01

78 楼

先吧这桑行变成两行
其他的等你找人把我的简历递到卖力公司HM手里之后再谈
int n=A.length;
: int i=0;
: int j=n-1;

【在 p*****2 的大作中提到】

:
: 大牛帮我把逻辑简化一下吧。

j*72014-01-13 08:01

79 楼

感觉大家是不是太过复杂了，还是我看漏边界条件了。最简单的办法是从后往前找。例如
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*r2014-01-13 08:01

80 楼

这题不需要m*n内存，用2*（min(m,n))就可以了，update时循环使用buffer即可

【在 i**********e 的大作中提到】

: DFS 暴力解过不了大数据吧？

H*r2014-01-13 08:01

81 楼

循环使用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*r2014-01-13 08:01

82 楼

建议加大large input, 此题空间复杂度是O(min(m,n))不应该内存不够的

【在 i**********e 的大作中提到】

: DFS 暴力解过不了大数据吧？

t*a2014-01-13 08:01

83 楼

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*x2014-01-13 08:01

84 楼

我靠，这个程序太牛B了！！
我用rec[l1][l2]复杂的死翘翘了.....

【在 p*****2 的大作中提到】

H*r2014-01-13 08:01

85 楼

北2爷这个程序很有意思啊！难道是dfs+dp? 为啥这样会更加efficient? 有一段没来，
北2爷貌似全语言制霸了啊。

【在 p*****2 的大作中提到】

:
: 大牛帮我把逻辑简化一下吧。

w*o2014-01-13 08:01

86 楼

反例：
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*r2014-01-13 08:01

87 楼

这个过OJ了？

【在 w***o 的大作中提到】

: 反例：
: a = "deab"
: b = "feac"
: c = "defeacab"
: 不管从头还是从尾扫都是false,但实际应该是true;
:
: 例如

w*o2014-01-13 08:01

88 楼

好像有问题。再考虑

【在 H****r 的大作中提到】

: 这个过OJ了？

w*x2014-01-13 08:01

89 楼

上个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*r2014-01-13 08:01

90 楼

这一步是我一直没搞透的一个地方，能展开讲讲吗？

【在 p*****2 的大作中提到】

: 这题挺有意思。貌似topdown DP 快于 bottomup DP。典型的topdown可以避免一些无用
: 的计算。

j*72014-01-13 08:01

91 楼

哎呦，总算看明白了
是不work

【在 w***o 的大作中提到】

: 反例：
: a = "deab"
: b = "feac"
: c = "defeacab"
: 不管从头还是从尾扫都是false,但实际应该是true;
:
: 例如

b*y2014-01-13 08:01

92 楼

发信人: wasco (wasco), 信区: JobHunting
标题: Re: facebook的面试题
发信站: BBS 未名空间站 (Mon Sep 17 13:23:17 2012, 美东)
反例：
a = "deab"
b = "feac"
c = "defeacab"
这个case也过不了

【在 d******a 的大作中提到】

t*a2014-01-13 08:01

93 楼

这个题目就是个DP啊... O(n)时间就可以解决。大家为什么在这题目上讨论这么久时间
？

o*e2014-01-13 08:01

94 楼

发现一个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;
: