蝙蝠侠大战蜘蛛侠 - 未名空间MITBBS历史存档

h*n2012-08-23 07:08

1 楼

1. Question:
String s is called unique if all the characters of s are different.
String s2 is producible from string s1, if we can remove some characters of
s1 to obtain s2.
String s1 is more beautiful than string s2 if length of s1 is more than
length of s2 or they have equal length and s1 is lexicographically greater
than s2.
Given a string s you have to find the most beautiful unique string that is
producible from s.
Input:
First line of input comes a string s having no more than 1,000,000(10^6)
characters. all the characters of s are lowercase english letters.
Output:
Print the most beautiful unique string that is producable from s
Sample Input:
babab
Sample Output:
ba
Explanation
In the above test case all unique strings that are producible from s are "ab
" and "ba" and "ba" is more beautiful than "ab".
2. Question:
Mastermind is a game of two players. In the beginning, first player decides
a secret key, which is a sequence (s1,s2,...sk) where 0 < si <= n, Then
second player makes guesses in rounds, where each guess is of form (g1,g2, .
..gk), and after each guess first player calculates the score for the guess.
Score for a guess is equal to number of i's for which we have gi = si.
For example if the secret key is (4,2,5,3,1) and the guess is (1,2,3,7,1),
then the score is 2, because g2 = s2 and g5 = s5.
Given a sequence of guesses, and scores for each guess, your program must
decide if there exists at least one secret key that generates those exact
scores.

g*x2012-08-23 07:08

2 楼

最终谁会赢？

p*22012-08-23 07:08

3 楼

第一题先找unique string，这个比较容易，纪录出现过的字符就行。而且这个一定是
最长的。然后就找更漂亮的。也就是字母顺序更大的。
从后往前找到所有的字符出现以后，从这个点到最后就可以形成包括所有字符的unique
string. 然后从z往a找，从string的开头往后找。

l*e2012-08-23 07:08

4 楼

蝙蝠侠，因为蝙蝠可以吃蜘蛛

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

: 最终谁会赢？

h*n2012-08-23 07:08

5 楼

写个code看看？

unique

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

: 第一题先找unique string，这个比较容易，纪录出现过的字符就行。而且这个一定是
: 最长的。然后就找更漂亮的。也就是字母顺序更大的。
: 从后往前找到所有的字符出现以后，从这个点到最后就可以形成包括所有字符的unique
: string. 然后从z往a找，从string的开头往后找。

z*e2012-08-23 07:08

6 楼

终结者必胜

p*22012-08-23 07:08

7 楼

有test case吗？这题可能写和测要30分钟。

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

: 写个code看看？
:
: unique

g*x2012-08-23 07:08

8 楼

这个说的貌似很有道理哎

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

: 蝙蝠侠，因为蝙蝠可以吃蜘蛛

p*22012-08-23 07:08

9 楼

第二题貌似bf就可以了

h*n2012-08-23 07:08

10 楼

Input:
nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnq
sknbarpabgokbsrfhmeklrle
output: tsocrpkijgdqnbafhmle
上面这个testcase能过应该就差不多了

h*n2012-08-23 07:08

11 楼

Brute force很容易超时

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

: 第二题貌似bf就可以了

p*22012-08-23 07:08

12 楼

nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnq
Input:
nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnq
sknbarpabgokbsrfhmeklrle
这个是一行吧？

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

: Input:
: nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnq
: sknbarpabgokbsrfhmeklrle
: output: tsocrpkijgdqnbafhmle
: 上面这个testcase能过应该就差不多了

h*n2012-08-23 07:08

13 楼

是的呵呵，太长了

l*i2012-08-23 07:08

14 楼

bool used[26]; // char that have been used
int pos; // s[pos..len) haven't been explored
while pos < len
1. scan s[pos] to s[len-1], suppose s[pos..len) has k non-used chars, 2.
look for newpos such that s[newpos..len) has k non-used chars and s[newpos]
is the largest possible. this might need to be done from s[len-1] back to s[
pos]
3. set used[s[newpos]] = 1
the s[newpos] found in this order is the solution.

of

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

: 1. Question:
: String s is called unique if all the characters of s are different.
: String s2 is producible from string s1, if we can remove some characters of
: s1 to obtain s2.
: String s1 is more beautiful than string s2 if length of s1 is more than
: length of s2 or they have equal length and s1 is lexicographically greater
: than s2.
: Given a string s you have to find the most beautiful unique string that is
: producible from s.
: Input:

p*22012-08-23 07:08

15 楼

我的算法有点问题，结果不太对。

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

: 是的呵呵，太长了

p*22012-08-23 07:08

16 楼

时间要求是多少呀？

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

: Brute force很容易超时

h*n2012-08-23 07:08

17 楼

没啥要求，但是感觉用BF复杂度会很大
你随便写写看看

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

:
: 时间要求是多少呀？

d*e2012-08-23 07:08

18 楼

Question 1:
def most_beautiful(s):
l = [None] * 26
for c in s:
i = 25 - (ord(c) - 97)
l[i] = c
l = [c for c in l if c]
return ''.join(l)

of

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

: 1. Question:
: String s is called unique if all the characters of s are different.
: String s2 is producible from string s1, if we can remove some characters of
: s1 to obtain s2.
: String s1 is more beautiful than string s2 if length of s1 is more than
: length of s2 or they have equal length and s1 is lexicographically greater
: than s2.
: Given a string s you have to find the most beautiful unique string that is
: producible from s.
: Input:

p*22012-08-23 07:08

19 楼

第二题貌似你把一些条件给删除了？我记得数据的规模很小呀。BF应该差不多了。当然
不能纯BF，要稍加一点优化。

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

: 没啥要求，但是感觉用BF复杂度会很大
: 你随便写写看看

f*e2012-08-23 07:08

20 楼

lanti的答案是对的，只要O(26n)

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

:
: 第二题貌似你把一些条件给删除了？我记得数据的规模很小呀。BF应该差不多了。当然
: 不能纯BF，要稍加一点优化。

p*22012-08-23 07:08

21 楼

那是第一题吧？第一题肯定不能超过O(n)的复杂度。

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

: lanti的答案是对的，只要O(26n)

l*82012-08-23 07:08

22 楼

第一题里面的characters 就是指a-z? 区分大小写吗？

of

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

: 1. Question:
: String s is called unique if all the characters of s are different.
: String s2 is producible from string s1, if we can remove some characters of
: s1 to obtain s2.
: String s1 is more beautiful than string s2 if length of s1 is more than
: length of s2 or they have equal length and s1 is lexicographically greater
: than s2.
: Given a string s you have to find the most beautiful unique string that is
: producible from s.
: Input:

s*l2012-08-23 07:08

23 楼

# The most beautiful substring
def f(s):
if len(s) <= 1:
return s
s1, s2 = split(s)
return ''.join(s1 + [c for c in f(s2)])
def split(s):
arr = [c for c in s]
last_seen = {}
max_v = 0
max_ind = -1
for i, c in enumerate(arr):
if c > max_v:
max_v = c
max_ind = i
last_seen[c] = i
i = max_ind - 1
s1 = [max_v]
while (i >= 0):
if last_seen[arr[i]] == i or arr[i] > s1[0]:
if arr[i] in s1:
s1.remove(arr[i])
s1.insert(0, arr[i])
i = i - 1
s2 = [c for c in arr[max_ind+1:] if c not in s1]
return s1, s2

f*e2012-08-23 07:08

24 楼

确实，第二题只想到了LP， feasibility的方法。

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

:
: 那是第一题吧？第一题肯定不能超过O(n)的复杂度。

z*i2012-08-23 07:08

25 楼

不是很明白。
但用int chars[26][26]会简单可行吧：chars[i][j]保存字符'a+i'第j+1次出现的位置。

]
s[

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

: bool used[26]; // char that have been used
: int pos; // s[pos..len) haven't been explored
: while pos < len
: 1. scan s[pos] to s[len-1], suppose s[pos..len) has k non-used chars, 2.
: look for newpos such that s[newpos..len) has k non-used chars and s[newpos]
: is the largest possible. this might need to be done from s[len-1] back to s[
: pos]
: 3. set used[s[newpos]] = 1
: the s[newpos] found in this order is the solution.
:

p*92012-08-23 07:08

26 楼

public String findMostBeautifulString(String s){
int M = 256;
int[] count = new int[M];
boolean[] used = new boolean[M];
int num = 0;
for(int i = 0 ; i < s.length() ; i ++){
int index = s.charAt(i);
if(count[index] == 0)
num ++;
count[index] ++;
used[index] = false;
}
char[] output = new char[num];
int k = 0;
for(int i = 0 ; i < s.length(); i ++){
char ch = s.charAt(i);
count[ch] --;
if(!used[ch]){
while(k > 0 && output[k - 1] < ch && count[output[k - 1]] >
0 ){
used[output[k - 1]] = false;
k --;
}
output[k ++] = ch;
used[ch] = true;
}
}
return new String(output);
}

l*82012-08-23 07:08

27 楼

void convertToMostBeautiful(string & s)
{
unordered_map count;
unordered_map chosen;
for (int i=0; icount[s[i]]++;
chosen[s[i]] = false;
}
int tail = -1;
for (int i=0; i < s.size(); i++) {
if (chosen[s[i]]) {
count[s[i]]--;
} else {
while (tail >=0 && s[tail] <= s[i] && count[s[tail]] > 1) {
chosen[s[tail]] = false;
count[s[tail--]]--;
}
s[++tail] = s[i];
chosen[s[i]] = true;
}
}
s.resize(tail+1);
}

h*n2012-08-23 07:08

28 楼

1. Question:
String s is called unique if all the characters of s are different.
String s2 is producible from string s1, if we can remove some characters of
s1 to obtain s2.
String s1 is more beautiful than string s2 if length of s1 is more than
length of s2 or they have equal length and s1 is lexicographically greater
than s2.
Given a string s you have to find the most beautiful unique string that is
producible from s.
Input:
First line of input comes a string s having no more than 1,000,000(10^6)
characters. all the characters of s are lowercase english letters.
Output:
Print the most beautiful unique string that is producable from s
Sample Input:
babab
Sample Output:
ba
Explanation
In the above test case all unique strings that are producible from s are "ab
" and "ba" and "ba" is more beautiful than "ab".
2. Question:
Mastermind is a game of two players. In the beginning, first player decides
a secret key, which is a sequence (s1,s2,...sk) where 0 < si <= n, Then
second player makes guesses in rounds, where each guess is of form (g1,g2, .
..gk), and after each guess first player calculates the score for the guess.
Score for a guess is equal to number of i's for which we have gi = si.
For example if the secret key is (4,2,5,3,1) and the guess is (1,2,3,7,1),
then the score is 2, because g2 = s2 and g5 = s5.
Given a sequence of guesses, and scores for each guess, your program must
decide if there exists at least one secret key that generates those exact
scores.

p*22012-08-23 07:08

29 楼

第一题先找unique string，这个比较容易，纪录出现过的字符就行。而且这个一定是
最长的。然后就找更漂亮的。也就是字母顺序更大的。
从后往前找到所有的字符出现以后，从这个点到最后就可以形成包括所有字符的unique
string. 然后从z往a找，从string的开头往后找。

h*n2012-08-23 07:08

30 楼

写个code看看？

unique

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

: 第一题先找unique string，这个比较容易，纪录出现过的字符就行。而且这个一定是
: 最长的。然后就找更漂亮的。也就是字母顺序更大的。
: 从后往前找到所有的字符出现以后，从这个点到最后就可以形成包括所有字符的unique
: string. 然后从z往a找，从string的开头往后找。

p*22012-08-23 07:08

31 楼

有test case吗？这题可能写和测要30分钟。

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

: 写个code看看？
:
: unique

p*22012-08-23 07:08

32 楼

第二题貌似bf就可以了

h*n2012-08-23 07:08

33 楼

Input:
nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnq
sknbarpabgokbsrfhmeklrle
output: tsocrpkijgdqnbafhmle
上面这个testcase能过应该就差不多了

h*n2012-08-23 07:08

34 楼

Brute force很容易超时

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

: 第二题貌似bf就可以了

p*22012-08-23 07:08

35 楼

nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnq
Input:
nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnq
sknbarpabgokbsrfhmeklrle
这个是一行吧？

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

: Input:
: nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnq
: sknbarpabgokbsrfhmeklrle
: output: tsocrpkijgdqnbafhmle
: 上面这个testcase能过应该就差不多了

h*n2012-08-23 07:08

36 楼

是的呵呵，太长了

l*i2012-08-23 07:08

37 楼

bool used[26]; // char that have been used
int pos; // s[pos..len) haven't been explored
while pos < len
1. scan s[pos] to s[len-1], suppose s[pos..len) has k non-used chars, 2.
look for newpos such that s[newpos..len) has k non-used chars and s[newpos]
is the largest possible. this might need to be done from s[len-1] back to s[
pos]
3. set used[s[newpos]] = 1
the s[newpos] found in this order is the solution.

of

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

: 1. Question:
: String s is called unique if all the characters of s are different.
: String s2 is producible from string s1, if we can remove some characters of
: s1 to obtain s2.
: String s1 is more beautiful than string s2 if length of s1 is more than
: length of s2 or they have equal length and s1 is lexicographically greater
: than s2.
: Given a string s you have to find the most beautiful unique string that is
: producible from s.
: Input:

p*22012-08-23 07:08

38 楼

我的算法有点问题，结果不太对。

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

: 是的呵呵，太长了

p*22012-08-23 07:08

39 楼

时间要求是多少呀？

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

: Brute force很容易超时

h*n2012-08-23 07:08

40 楼

没啥要求，但是感觉用BF复杂度会很大
你随便写写看看

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

:
: 时间要求是多少呀？

d*e2012-08-23 07:08

41 楼

Question 1:
def most_beautiful(s):
l = [None] * 26
for c in s:
i = 25 - (ord(c) - 97)
l[i] = c
l = [c for c in l if c]
return ''.join(l)

of

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

: 1. Question:
: String s is called unique if all the characters of s are different.
: String s2 is producible from string s1, if we can remove some characters of
: s1 to obtain s2.
: String s1 is more beautiful than string s2 if length of s1 is more than
: length of s2 or they have equal length and s1 is lexicographically greater
: than s2.
: Given a string s you have to find the most beautiful unique string that is
: producible from s.
: Input:

p*22012-08-23 07:08

42 楼

第二题貌似你把一些条件给删除了？我记得数据的规模很小呀。BF应该差不多了。当然
不能纯BF，要稍加一点优化。

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

: 没啥要求，但是感觉用BF复杂度会很大
: 你随便写写看看

f*e2012-08-23 07:08

43 楼

lanti的答案是对的，只要O(26n)

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

:
: 第二题貌似你把一些条件给删除了？我记得数据的规模很小呀。BF应该差不多了。当然
: 不能纯BF，要稍加一点优化。

p*22012-08-23 07:08

44 楼

那是第一题吧？第一题肯定不能超过O(n)的复杂度。

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

: lanti的答案是对的，只要O(26n)

l*82012-08-23 07:08

45 楼

第一题里面的characters 就是指a-z? 区分大小写吗？

of

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

: 1. Question:
: String s is called unique if all the characters of s are different.
: String s2 is producible from string s1, if we can remove some characters of
: s1 to obtain s2.
: String s1 is more beautiful than string s2 if length of s1 is more than
: length of s2 or they have equal length and s1 is lexicographically greater
: than s2.
: Given a string s you have to find the most beautiful unique string that is
: producible from s.
: Input:

s*l2012-08-23 07:08

46 楼

# The most beautiful substring
def f(s):
if len(s) <= 1:
return s
s1, s2 = split(s)
return ''.join(s1 + [c for c in f(s2)])
def split(s):
arr = [c for c in s]
last_seen = {}
max_v = 0
max_ind = -1
for i, c in enumerate(arr):
if c > max_v:
max_v = c
max_ind = i
last_seen[c] = i
i = max_ind - 1
s1 = [max_v]
while (i >= 0):
if last_seen[arr[i]] == i or arr[i] > s1[0]:
if arr[i] in s1:
s1.remove(arr[i])
s1.insert(0, arr[i])
i = i - 1
s2 = [c for c in arr[max_ind+1:] if c not in s1]
return s1, s2

f*e2012-08-23 07:08

47 楼

确实，第二题只想到了LP， feasibility的方法。

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

:
: 那是第一题吧？第一题肯定不能超过O(n)的复杂度。

z*i2012-08-23 07:08

48 楼

不是很明白。
但用int chars[26][26]会简单可行吧：chars[i][j]保存字符'a+i'第j+1次出现的位置。

]
s[

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

: bool used[26]; // char that have been used
: int pos; // s[pos..len) haven't been explored
: while pos < len
: 1. scan s[pos] to s[len-1], suppose s[pos..len) has k non-used chars, 2.
: look for newpos such that s[newpos..len) has k non-used chars and s[newpos]
: is the largest possible. this might need to be done from s[len-1] back to s[
: pos]
: 3. set used[s[newpos]] = 1
: the s[newpos] found in this order is the solution.
:

p*92012-08-23 07:08

49 楼

public String findMostBeautifulString(String s){
int M = 256;
int[] count = new int[M];
boolean[] used = new boolean[M];
int num = 0;
for(int i = 0 ; i < s.length() ; i ++){
int index = s.charAt(i);
if(count[index] == 0)
num ++;
count[index] ++;
used[index] = false;
}
char[] output = new char[num];
int k = 0;
for(int i = 0 ; i < s.length(); i ++){
char ch = s.charAt(i);
count[ch] --;
if(!used[ch]){
while(k > 0 && output[k - 1] < ch && count[output[k - 1]] >
0 ){
used[output[k - 1]] = false;
k --;
}
output[k ++] = ch;
used[ch] = true;
}
}
return new String(output);
}

l*82012-08-23 07:08

50 楼

void convertToMostBeautiful(string & s)
{
unordered_map count;
unordered_map chosen;
for (int i=0; icount[s[i]]++;
chosen[s[i]] = false;
}
int tail = -1;
for (int i=0; i < s.size(); i++) {
if (chosen[s[i]]) {
count[s[i]]--;
} else {
while (tail >=0 && s[tail] <= s[i] && count[s[tail]] > 1) {
chosen[s[tail]] = false;
count[s[tail--]]--;
}
s[++tail] = s[i];
chosen[s[i]] = true;
}
}
s.resize(tail+1);
}

f*m2012-08-23 07:08

51 楼

感觉这个方法是O(n^2),怎么会是O(26n)?

]
s[

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

: bool used[26]; // char that have been used
: int pos; // s[pos..len) haven't been explored
: while pos < len
: 1. scan s[pos] to s[len-1], suppose s[pos..len) has k non-used chars, 2.
: look for newpos such that s[newpos..len) has k non-used chars and s[newpos]
: is the largest possible. this might need to be done from s[len-1] back to s[
: pos]
: 3. set used[s[newpos]] = 1
: the s[newpos] found in this order is the solution.
:

a*o2012-08-23 07:08

52 楼

第一题感觉是Longest Increase Sequence, 找出最beautiful那个.

c*t2012-08-23 07:08

53 楼

lz. 这两道是onsite题 or phone interview题？

of

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

: 1. Question:
: String s is called unique if all the characters of s are different.
: String s2 is producible from string s1, if we can remove some characters of
: s1 to obtain s2.
: String s1 is more beautiful than string s2 if length of s1 is more than
: length of s2 or they have equal length and s1 is lexicographically greater
: than s2.
: Given a string s you have to find the most beautiful unique string that is
: producible from s.
: Input:

c*t2012-08-23 07:08

54 楼

我基本也是这个思路。写了一个50行的罗嗦代码。和前面几位大牛的没法比。

unique

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

: 第一题先找unique string，这个比较容易，纪录出现过的字符就行。而且这个一定是
: 最长的。然后就找更漂亮的。也就是字母顺序更大的。
: 从后往前找到所有的字符出现以后，从这个点到最后就可以形成包括所有字符的unique
: string. 然后从z往a找，从string的开头往后找。

c*t2012-08-23 07:08

55 楼

感觉不太对，newpos只是保证后面能生成max length, 但不能保证most beautiful

]
s[

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

: bool used[26]; // char that have been used
: int pos; // s[pos..len) haven't been explored
: while pos < len
: 1. scan s[pos] to s[len-1], suppose s[pos..len) has k non-used chars, 2.
: look for newpos such that s[newpos..len) has k non-used chars and s[newpos]
: is the largest possible. this might need to be done from s[len-1] back to s[
: pos]
: 3. set used[s[newpos]] = 1
: the s[newpos] found in this order is the solution.
:

f*32012-08-23 07:08

56 楼

第2题是不是dfs? 从match最多的字符开始，不match的用hash记录该位置不可放置的元
素，每次update剩下位置，直到所有位置都填上. 最坏情况是指数2^n,因为集合n的子
集最多有2^n个。

c*t2012-08-23 07:08

57 楼

看懂你的了，很巧妙，和longway2008解法应该差不多。

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

: public String findMostBeautifulString(String s){
: int M = 256;
: int[] count = new int[M];
: boolean[] used = new boolean[M];
: int num = 0;
: for(int i = 0 ; i < s.length() ; i ++){
: int index = s.charAt(i);
: if(count[index] == 0)
: num ++;
: count[index] ++;

c*t2012-08-23 07:08

58 楼

但并不知道哪些字符是match, 如果所有组合都试，也就是brute force了吧。

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

: 第2题是不是dfs? 从match最多的字符开始，不match的用hash记录该位置不可放置的元
: 素，每次update剩下位置，直到所有位置都填上. 最坏情况是指数2^n,因为集合n的子
: 集最多有2^n个。

c*t2012-08-23 07:08

59 楼

结果应该是zkba

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

: 感觉这个方法是O(n^2),怎么会是O(26n)?
:
: ]
: s[

c*t2012-08-23 07:08

60 楼

第二题有没有test cases?

of

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

: 1. Question:
: String s is called unique if all the characters of s are different.
: String s2 is producible from string s1, if we can remove some characters of
: s1 to obtain s2.
: String s1 is more beautiful than string s2 if length of s1 is more than
: length of s2 or they have equal length and s1 is lexicographically greater
: than s2.
: Given a string s you have to find the most beautiful unique string that is
: producible from s.
: Input:

o*d2012-08-23 07:08

61 楼

mark

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

: public String findMostBeautifulString(String s){
: int M = 256;
: int[] count = new int[M];
: boolean[] used = new boolean[M];
: int num = 0;
: for(int i = 0 ; i < s.length() ; i ++){
: int index = s.charAt(i);
: if(count[index] == 0)
: num ++;
: count[index] ++;

f*m2012-08-23 07:08

62 楼

看晕了，longway是对的。

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

: 结果应该是zkba

f*m2012-08-23 07:08

63 楼

如何证明longway2008的是线性时间？
是不是这样？
while (tail >=0 && s[tail] <= s[i] && count[s[tail]] > 1) {
chosen[s[tail]] = false;
count[s[tail--]]--;
}
最多执行n次（对于for(i = 0; i < s.size(), ++i){}),因为count[s[i]]的和为
n.

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

: 看懂你的了，很巧妙，和longway2008解法应该差不多。

o*d2012-08-23 07:08

64 楼

看了patrick9的思路照着写了一个 c++
#define N 256
string findMostBeuatiful(string s){
string ans;
int len = s.size();
if(len<=1) return s;
int count[N]={0};
bool used[N]={false};
for(int i=0; ivector res;
for(int i=0; ichar ch=s[i];
count[ch]--;
if(used[ch]) continue;
while(res.size()>0) {
char ch2=res.back();
if(ch20) {
res.pop_back();
used[ch2]=false;
}
else
break;
}
res.push_back(ch);
used[ch]=true;
}
stringstream ss;
for(int i=0; ireturn ss.str();
}

of

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

: 1. Question:
: String s is called unique if all the characters of s are different.
: String s2 is producible from string s1, if we can remove some characters of
: s1 to obtain s2.
: String s1 is more beautiful than string s2 if length of s1 is more than
: length of s2 or they have equal length and s1 is lexicographically greater
: than s2.
: Given a string s you have to find the most beautiful unique string that is
: producible from s.
: Input:

c*t2012-08-23 07:08

65 楼

严格证明不会，不过你的思路我觉得挺对。
在一个n的循环里有一个内循环，这个内循环总共最多执行n次。所以平均起来，对每个
外循环，内循环执行1次。所以是O(n)。这样的文科解释能行不？

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

: 如何证明longway2008的是线性时间？
: 是不是这样？
: while (tail >=0 && s[tail] <= s[i] && count[s[tail]] > 1) {
: chosen[s[tail]] = false;
: count[s[tail--]]--;
: }
: 最多执行n次（对于for(i = 0; i < s.size(), ++i){}),因为count[s[i]]的和为
: n.

j*x2012-08-23 07:08

66 楼

第一题是个好题啊，coding和思考比重恰当，coding的corner case不多
这题区分度一定高。。。

c*t2012-08-23 07:08

67 楼

第二题不好做啊，有人写出来了吗？

of

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

: 1. Question:
: String s is called unique if all the characters of s are different.
: String s2 is producible from string s1, if we can remove some characters of
: s1 to obtain s2.
: String s1 is more beautiful than string s2 if length of s1 is more than
: length of s2 or they have equal length and s1 is lexicographically greater
: than s2.
: Given a string s you have to find the most beautiful unique string that is
: producible from s.
: Input: