h****n
发帖数: 1093 | 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. |
p*****2
发帖数: 21240 | 2 第一题先找unique string，这个比较容易，纪录出现过的字符就行。而且这个一定是
最长的。然后就找更漂亮的。也就是字母顺序更大的。
从后往前找到所有的字符出现以后，从这个点到最后就可以形成包括所有字符的unique
string. 然后从z往a找，从string的开头往后找。 |
h****n
发帖数: 1093 | 3 写个code看看？
unique
【在 p*****2 的大作中提到】
: 第一题先找unique string，这个比较容易，纪录出现过的字符就行。而且这个一定是
: 最长的。然后就找更漂亮的。也就是字母顺序更大的。
: 从后往前找到所有的字符出现以后，从这个点到最后就可以形成包括所有字符的unique
: string. 然后从z往a找，从string的开头往后找。
|
p*****2
发帖数: 21240 | 4
有test case吗？这题可能写和测要30分钟。
【在 h****n 的大作中提到】
: 写个code看看？
:
: unique
|
p*****2
发帖数: 21240 | |
h****n
发帖数: 1093 | 6 Input:
nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnq
sknbarpabgokbsrfhmeklrle
output: tsocrpkijgdqnbafhmle
上面这个testcase能过应该就差不多了 |
h****n
发帖数: 1093 | 7 Brute force很容易超时
【在 p*****2 的大作中提到】
: 第二题貌似bf就可以了
|
p*****2
发帖数: 21240 | 8
nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnq
Input:
nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnq
sknbarpabgokbsrfhmeklrle
这个是一行吧？
【在 h****n 的大作中提到】
: Input:
: nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnq
: sknbarpabgokbsrfhmeklrle
: output: tsocrpkijgdqnbafhmle
: 上面这个testcase能过应该就差不多了
|
h****n
发帖数: 1093 | |
l***i
发帖数: 1309 | 10 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*****2
发帖数: 21240 | 11
我的算法有点问题，结果不太对。
【在 h****n 的大作中提到】
: 是的呵呵，太长了
|
p*****2
发帖数: 21240 | 12
时间要求是多少呀？
【在 h****n 的大作中提到】
: Brute force很容易超时
|
h****n
发帖数: 1093 | 13 没啥要求，但是感觉用BF复杂度会很大
你随便写写看看
【在 p*****2 的大作中提到】
:
: 时间要求是多少呀？
|
d******e
发帖数: 164 | 14 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*****2
发帖数: 21240 | 15
第二题貌似你把一些条件给删除了？我记得数据的规模很小呀。BF应该差不多了。当然
不能纯BF，要稍加一点优化。
【在 h****n 的大作中提到】
: 没啥要求，但是感觉用BF复杂度会很大
: 你随便写写看看
|
f*****e
发帖数: 2992 | 16 lanti的答案是对的，只要O(26n)
【在 p*****2 的大作中提到】
:
: 第二题貌似你把一些条件给删除了？我记得数据的规模很小呀。BF应该差不多了。当然
: 不能纯BF，要稍加一点优化。
|
p*****2
发帖数: 21240 | 17
那是第一题吧？第一题肯定不能超过O(n)的复杂度。
【在 f*****e 的大作中提到】
: lanti的答案是对的，只要O(26n)
|
l*********8
发帖数: 4642 | 18 第一题里面的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*********l
发帖数: 103 | 19 # 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*****e
发帖数: 2992 | 20 确实，第二题只想到了LP， feasibility的方法。
【在 p*****2 的大作中提到】
:
: 那是第一题吧？第一题肯定不能超过O(n)的复杂度。
|
|
|
z********i
发帖数: 568 | 21 不是很明白。
但用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******9
发帖数: 47 | 22 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*********8
发帖数: 4642 | 23 void convertToMostBeautiful(string & s)
{
unordered_map count;
unordered_map chosen;
for (int i=0; i
count[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****n
发帖数: 1093 | 24 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*****2
发帖数: 21240 | 25 第一题先找unique string，这个比较容易，纪录出现过的字符就行。而且这个一定是
最长的。然后就找更漂亮的。也就是字母顺序更大的。
从后往前找到所有的字符出现以后，从这个点到最后就可以形成包括所有字符的unique
string. 然后从z往a找，从string的开头往后找。 |
h****n
发帖数: 1093 | 26 写个code看看？
unique
【在 p*****2 的大作中提到】
: 第一题先找unique string，这个比较容易，纪录出现过的字符就行。而且这个一定是
: 最长的。然后就找更漂亮的。也就是字母顺序更大的。
: 从后往前找到所有的字符出现以后，从这个点到最后就可以形成包括所有字符的unique
: string. 然后从z往a找，从string的开头往后找。
|
p*****2
发帖数: 21240 | 27
有test case吗？这题可能写和测要30分钟。
【在 h****n 的大作中提到】
: 写个code看看？
:
: unique
|
p*****2
发帖数: 21240 | |
h****n
发帖数: 1093 | 29 Input:
nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnq
sknbarpabgokbsrfhmeklrle
output: tsocrpkijgdqnbafhmle
上面这个testcase能过应该就差不多了 |
h****n
发帖数: 1093 | 30 Brute force很容易超时
【在 p*****2 的大作中提到】
: 第二题貌似bf就可以了
|
|
|
p*****2
发帖数: 21240 | 31
nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnq
Input:
nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnq
sknbarpabgokbsrfhmeklrle
这个是一行吧？
【在 h****n 的大作中提到】
: Input:
: nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnq
: sknbarpabgokbsrfhmeklrle
: output: tsocrpkijgdqnbafhmle
: 上面这个testcase能过应该就差不多了
|
h****n
发帖数: 1093 | |
l***i
发帖数: 1309 | 33 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*****2
发帖数: 21240 | 34
我的算法有点问题，结果不太对。
【在 h****n 的大作中提到】
: 是的呵呵，太长了
|
p*****2
发帖数: 21240 | 35
时间要求是多少呀？
【在 h****n 的大作中提到】
: Brute force很容易超时
|
h****n
发帖数: 1093 | 36 没啥要求，但是感觉用BF复杂度会很大
你随便写写看看
【在 p*****2 的大作中提到】
:
: 时间要求是多少呀？
|
d******e
发帖数: 164 | 37 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*****2
发帖数: 21240 | 38
第二题貌似你把一些条件给删除了？我记得数据的规模很小呀。BF应该差不多了。当然
不能纯BF，要稍加一点优化。
【在 h****n 的大作中提到】
: 没啥要求，但是感觉用BF复杂度会很大
: 你随便写写看看
|
f*****e
发帖数: 2992 | 39 lanti的答案是对的，只要O(26n)
【在 p*****2 的大作中提到】
:
: 第二题貌似你把一些条件给删除了？我记得数据的规模很小呀。BF应该差不多了。当然
: 不能纯BF，要稍加一点优化。
|
p*****2
发帖数: 21240 | 40
那是第一题吧？第一题肯定不能超过O(n)的复杂度。
【在 f*****e 的大作中提到】
: lanti的答案是对的，只要O(26n)
|
|
|
l*********8
发帖数: 4642 | 41 第一题里面的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*********l
发帖数: 103 | 42 # 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*****e
发帖数: 2992 | 43 确实，第二题只想到了LP， feasibility的方法。
【在 p*****2 的大作中提到】
:
: 那是第一题吧？第一题肯定不能超过O(n)的复杂度。
|
z********i
发帖数: 568 | 44 不是很明白。
但用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******9
发帖数: 47 | 45 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*********8
发帖数: 4642 | 46 void convertToMostBeautiful(string & s)
{
unordered_map count;
unordered_map chosen;
for (int i=0; i
count[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*********m
发帖数: 726 | 47 感觉这个方法是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***o
发帖数: 17 | 48 第一题感觉是Longest Increase Sequence, 找出最beautiful那个. |
c********t
发帖数: 5706 | 49 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********t
发帖数: 5706 | 50 我基本也是这个思路。写了一个50行的罗嗦代码。和前面几位大牛的没法比。
unique
【在 p*****2 的大作中提到】
: 第一题先找unique string，这个比较容易，纪录出现过的字符就行。而且这个一定是
: 最长的。然后就找更漂亮的。也就是字母顺序更大的。
: 从后往前找到所有的字符出现以后，从这个点到最后就可以形成包括所有字符的unique
: string. 然后从z往a找，从string的开头往后找。
|
|
|
c********t
发帖数: 5706 | 51 感觉不太对，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*******3
发帖数: 206 | 52 第2题是不是dfs? 从match最多的字符开始，不match的用hash记录该位置不可放置的元
素，每次update剩下位置，直到所有位置都填上. 最坏情况是指数2^n,因为集合n的子
集最多有2^n个。 |
c********t
发帖数: 5706 | 53 看懂你的了，很巧妙，和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********t
发帖数: 5706 | 54 但并不知道哪些字符是match, 如果所有组合都试，也就是brute force了吧。
【在 f*******3 的大作中提到】
: 第2题是不是dfs? 从match最多的字符开始，不match的用hash记录该位置不可放置的元
: 素，每次update剩下位置，直到所有位置都填上. 最坏情况是指数2^n,因为集合n的子
: 集最多有2^n个。
|
c********t
发帖数: 5706 | 55 结果应该是zkba
【在 f*********m 的大作中提到】
: 感觉这个方法是O(n^2),怎么会是O(26n)?
:
: ]
: s[
|
c********t
发帖数: 5706 | 56 第二题有没有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****d
发帖数: 2835 | 57 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*********m
发帖数: 726 | 58 看晕了，longway是对的。
【在 c********t 的大作中提到】
: 结果应该是zkba
|
f*********m
发帖数: 726 | 59 如何证明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****d
发帖数: 2835 | 60 看了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; i
vector res;
for(int i=0; i
char 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; i
return 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********t
发帖数: 5706 | 61 严格证明不会，不过你的思路我觉得挺对。
在一个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********x
发帖数: 2330 | 62 第一题是个好题啊，coding和思考比重恰当，coding的corner case不多
这题区分度一定高。。。 |
c********t
发帖数: 5706 | 63 第二题不好做啊，有人写出来了吗？
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:
|
