san francisco airport sephora - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Fashion - 美丽时尚

san francisco airport sephora

san francisco airport sephora# Fashion - 美丽时尚

S*02010-05-31 07:05

1 楼

make any given string a palindrome by adding the minimum number of character
这道题是用DP解的吗？

j*r2010-05-31 07:05

2 楼

姐妹们请问三藩机场里的sephora免税吗？安检外有一个不免税的吧？安检以后里面
还有吗？

c*t2010-05-31 07:05

3 楼

这题看样子是kmp，O(n)的

s*n2010-05-31 07:05

4 楼

里面没有sephora，只有外面的那家
里面有DFS啊，也卖很多化妆品，就是种类没sephora那么多而已

b*u2010-05-31 07:05

5 楼

这个不就是leetcode上的longest palindrome吗，添最少等价于删最少

d*x2010-05-31 07:05

6 楼

肿么等价？愿闻其详

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

: 这个不就是leetcode上的longest palindrome吗，添最少等价于删最少

l*b2010-05-31 07:05

7 楼

是longest pal sub sequence吧? 比substring简单点.找到这个然后添加元素是不是就
可以啦?
貌似也可以这样想: 从一头开始看, 如果和另一头不一样, 那么两头必须有一头添加一
个, 添加以后同时删掉, 等价于减少了一个字符, 就可以用dp啦

f*e2010-05-31 07:05

8 楼

可以找S和S逆的最大公共字符串。

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

: 是longest pal sub sequence吧? 比substring简单点.找到这个然后添加元素是不是就
: 可以啦?
: 貌似也可以这样想: 从一头开始看, 如果和另一头不一样, 那么两头必须有一头添加一
: 个, 添加以后同时删掉, 等价于减少了一个字符, 就可以用dp啦

d*x2010-05-31 07:05

9 楼

我咋觉得是S和S逆的最大公共子序列呢

是就
加一

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

: 可以找S和S逆的最大公共字符串。

f*e2010-05-31 07:05

10 楼

Yes, that's what I mean.

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

: 我咋觉得是S和S逆的最大公共子序列呢
:
: 是就
: 加一

b*u2010-05-31 07:05

11 楼

不对，我想简单了，没有考虑到回文两头都多出不同字符的反例, 比如 cabad这样
never mind

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

: 肿么等价？愿闻其详

c*t2010-05-31 07:05

12 楼

顶，最近对原有字符串变形问题挺多。

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

: 我咋觉得是S和S逆的最大公共子序列呢
:
: 是就
: 加一

p*e2010-05-31 07:05

13 楼

找出对称点，越靠近中间越短

character

【在 S******0 的大作中提到】

: make any given string a palindrome by adding the minimum number of character
: 这道题是用DP解的吗？

S*02010-05-31 07:05

14 楼

然后呢？

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

: 我咋觉得是S和S逆的最大公共子序列呢
:
: 是就
: 加一

c*t2010-05-31 07:05

15 楼

然后brute force? 不知大牛们还有更好的解法吗？

【在 S******0 的大作中提到】

:
: 然后呢？

d*x2010-05-31 07:05

16 楼

是啊。。求出最大公共子序列之后，这就是原字符串中的最大对称子序列
然后标记所有子序列元素位置
从两头往中间走，如果两个元素不都是子序列里面的元素，就加一个或两个元素去
match，直到两个都是为止，然后继续往中间走。。多straight forward。。。
然后假设我们可以添加更少的字符找到一个解，那么去掉这些字符以及对应的对称元素
后我们必然还是得到一个对称的字串，且比最大对称字串长，矛盾

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

: 然后brute force? 不知大牛们还有更好的解法吗？

j*y2010-05-31 07:05

17 楼

感觉还是dp 吧
dp[i][j] 表示把 s[i,...j]变成 palindrome的最少添加的单词数目
dp[i][j]=
dp[i + 1][j - 1], if(s[i] == s[j])
1 + min(dp[i+ 1][j], dp[i][j - 1]), if(s[i] != s[j])

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

: 是啊。。求出最大公共子序列之后，这就是原字符串中的最大对称子序列
: 然后标记所有子序列元素位置
: 从两头往中间走，如果两个元素不都是子序列里面的元素，就加一个或两个元素去
: match，直到两个都是为止，然后继续往中间走。。多straight forward。。。
: 然后假设我们可以添加更少的字符找到一个解，那么去掉这些字符以及对应的对称元素
: 后我们必然还是得到一个对称的字串，且比最大对称字串长，矛盾

p*22010-05-31 07:05

18 楼

嗯。dp想法比较直接。

【在 j*****y 的大作中提到】

: 感觉还是dp 吧
: dp[i][j] 表示把 s[i,...j]变成 palindrome的最少添加的单词数目
: dp[i][j]=
: dp[i + 1][j - 1], if(s[i] == s[j])
: 1 + min(dp[i+ 1][j], dp[i][j - 1]), if(s[i] != s[j])

d*x2010-05-31 07:05

19 楼

一回事。。
这个dp的状态也是O(n^2)
不过说起来我一开始想的也是dp。。。

元素

【在 j*****y 的大作中提到】

r*n2010-05-31 07:05

20 楼

....我觉得是substring呢....
原题需要添加的字符等于 S - the longest palindromic substring ending at S[end
-1]
To find the longest palindromic substring ending at S[end-1]:
reverse S, using suffix tree to find the longest common substring (ending at
S[end-1]) of S and S_r at O(n) time
overall time complexity is O(n)
edit:
我以为只能在后面加，原来是不限位置。

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

: 我咋觉得是S和S逆的最大公共子序列呢
:
: 是就
: 加一

p*e2010-05-31 07:05

21 楼

s[0]也行的

end
at

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

: ....我觉得是substring呢....
: 原题需要添加的字符等于 S - the longest palindromic substring ending at S[end
: -1]
: To find the longest palindromic substring ending at S[end-1]:
: reverse S, using suffix tree to find the longest common substring (ending at
: S[end-1]) of S and S_r at O(n) time
: overall time complexity is O(n)
: edit:
: 我以为只能在后面加，原来是不限位置。

o*d2010-05-31 07:05

22 楼

end
这个不太对？考虑cbba 不能限制在ending在两端的

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

r*n2010-05-31 07:05

23 楼

结果是什么
cbbabbc
the longest palindromic substring ending at S[end-1] is S[end-1] itself,
which is a
hence we should pad bbc (from cbb before a) after a
又看了下原题，我理解错题了，我以为只能在后面加

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

:
: end
: 这个不太对？考虑cbba 不能限制在ending在两端的

c*32010-05-31 07:05

24 楼

这个是正解

【在 j*****y 的大作中提到】

f*s2010-05-31 07:05

25 楼

这个adding是只能在两头adding还是可以在任意位置adding？

character

【在 S******0 的大作中提到】

: make any given string a palindrome by adding the minimum number of character
: 这道题是用DP解的吗？

o*d2010-05-31 07:05

26 楼

是不是就是跟longest palindrome subsequence 等价的

【在 j*****y 的大作中提到】

f*e2010-05-31 07:05

27 楼

of course not.

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

: 是不是就是跟longest palindrome subsequence 等价的

x*w2010-05-31 07:05

28 楼

const char* minimumPadding(const char* szStr, char res[])
{
if (NULL == szStr || *szStr == 0 || NULL == res)
return 0;
int nLen = strlen(szStr);
int rec[100][100] = { 0 };
for (int i = 0; i < nLen-1; i++)
{
rec[i][i+1] = szStr[i] == szStr[i+1] ? 0 : 1;
}
for (int i = 2; i < nLen; i++)
{
for (int j = 0; j < nLen-i; j++)
{
rec[j][j+i] = 1 + min(rec[j+1][j+i], rec[j][j+i-1]);
if (szStr[j] == szStr[j+i])
rec[j][j+i] = min(rec[j+1][j+i-1], rec[j][j+i]);
}
}
int nResLen = rec[0][nLen-1] + nLen;
res[nResLen] = 0;
char* p = res;
char* q = res + nResLen - 1;
int i = 0;
int j = nLen-1;
while (p <= q)
{
char c = 0;
if (szStr[i] == szStr[j])
{
c = szStr[i];
i++, j--;
}
else
{
if (rec[i][j-1] < rec[i+1][j])
{
c = szStr[j];
j--;
}
else
{
c = szStr[i];
i++;
}
}
*p++ = c;
*q-- = c;
}
return res;
}
做的还是太慢了...

p*22010-05-31 07:05

29 楼

怎么还不转Java？转了之后拿offer的机率要大很多

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

: const char* minimumPadding(const char* szStr, char res[])
: {
: if (NULL == szStr || *szStr == 0 || NULL == res)
: return 0;
: int nLen = strlen(szStr);
: int rec[100][100] = { 0 };
: for (int i = 0; i < nLen-1; i++)
: {
: rec[i][i+1] = szStr[i] == szStr[i+1] ? 0 : 1;
: }