刷墙选什么白色比较好？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Living

刷墙选什么白色比较好？

刷墙选什么白色比较好？# Living

c*t2014-06-14 07:06

1 楼

昨天做了道challenge的题，输入两个String, a and b, 要求返回能够满足（
subsequence of a) == (substring of b)的最大length。a和b的characters都是a-z。
我的做法代码复杂而且时间
复杂度也感觉不好。为了不误导大家，大牛先试试有没有好的解法，我再抛砖。

s*e2014-06-14 07:06

2 楼

连off white的颜色也那么多种，真没办法。让领导挑，就挑了一个linen white.
home depot的BEHR叫Table Linen。
准备楼上楼下都用这个颜色了。该没事吧。还是有其他白色可以推荐？

h*k2014-06-14 07:06

3 楼

这个？
https://en.m.wikipedia.org/wiki/Longest_common_substring_problem
面试要问这个，多半是来找茬的。

c*o2014-06-14 07:06

4 楼

雪白

l*u2014-06-14 07:06

5 楼

subsequance 和substring有什么区别？
如果是longest common substring，好像是用二维dp来解？

s*e2014-06-14 07:06

6 楼

容易脏，也盖不住缺陷。

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

: 雪白

c*t2014-06-14 07:06

7 楼

这样说来dp可以解决？但我遇到的是不是2 substring match, 是subsequence matches
substring。
2 substring match f(i,j)=f(i-1)(j-1)+1
subsequence matches substring, 难道要遍历row（i-1)? f(i,j)=Max(f(i-1,0)...
.f(i-1,j-1))+1
这样一来就是O(m*n*n)了，与dfs没区别了。
不过好像每个row去掉所有0，都是递增序列，可能可以找最后的值 f(i,j) = f(i-1, x
) ( x=max(0, j-1) and f(i-1, x)>0).
如果用一个一维array来记录所有row最大值, 应该可以吧。我试试。

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

: 这个？
: https://en.m.wikipedia.org/wiki/Longest_common_substring_problem
: 面试要问这个，多半是来找茬的。

c*o2014-06-14 07:06

8 楼

定义“缺陷”

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

: 容易脏，也盖不住缺陷。

c*t2014-06-14 07:06

9 楼

Subsequence 是指可以删除任意一些characters后的string (保持原顺序）
https://en.wikipedia.org/wiki/Subsequence

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

: subsequance 和substring有什么区别？
: 如果是longest common substring，好像是用二维dp来解？

d*w2014-06-14 07:06

10 楼

ivory white。可能需要调的

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

: 连off white的颜色也那么多种，真没办法。让领导挑，就挑了一个linen white.
: home depot的BEHR叫Table Linen。
: 准备楼上楼下都用这个颜色了。该没事吧。还是有其他白色可以推荐？

c*t2014-06-14 07:06

11 楼

试了一下DP，一维array记录所有row最大值不行，必须找最后的值 f(i,j) = f(i-1, x
) ( x=max(0, j-1) and f(i-1, x)>0). 可以用存一个index list, 用binary search,
O(m*n*log(m)) 。我觉得这个题还是直接用dfs好了，最坏情况是b里很多duplicate,
O(m*n*n)。

matches
..
x

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

: 这样说来dp可以解决？但我遇到的是不是2 substring match, 是subsequence matches
: substring。
: 2 substring match f(i,j)=f(i-1)(j-1)+1
: subsequence matches substring, 难道要遍历row（i-1)? f(i,j)=Max(f(i-1,0)...
: .f(i-1,j-1))+1
: 这样一来就是O(m*n*n)了，与dfs没区别了。
: 不过好像每个row去掉所有0，都是递增序列，可能可以找最后的值 f(i,j) = f(i-1, x
: ) ( x=max(0, j-1) and f(i-1, x)>0).
: 如果用一个一维array来记录所有row最大值, 应该可以吧。我试试。

N*c2014-06-14 07:06

12 楼

先漆在一块板子上,放在房间各面墙上看效果，并在不同时间，不同光线下看。

c*t2014-06-14 07:06

13 楼

今天返回来一看这题，马上O(m*n) dp写出了。状态太重要了。

x
search,
duplicate,

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

: 试了一下DP，一维array记录所有row最大值不行，必须找最后的值 f(i,j) = f(i-1, x
: ) ( x=max(0, j-1) and f(i-1, x)>0). 可以用存一个index list, 用binary search,
: O(m*n*log(m)) 。我觉得这个题还是直接用dfs好了，最坏情况是b里很多duplicate,
: O(m*n*n)。
:
: matches
: ..
: x