今天非常无聊的决定去试一下python。找了一个题，大意如下：
- 给定一个输入字符串，找出最漂亮的无重复子字符串。
- 子字符串：从原字符串中减掉某些字符可得到的。
- 无重复字符串：没有重复的字符
- 甲比乙漂亮：甲的长度>乙，或者甲的字典排序在乙之后。
因为都是无重复的，所以肯定不需要甲的长度大于乙，故而是所有长度一样的无重复子字符串中，找出字典排序最大的。
这个先用R写的，为的是写出一个有效的算法来。基本的思路就是强行的逐层递归。
x = 'nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnqsknbarpabgokbsrfhmeklrle'
x_split = strsplit(x,split="")[[1]]
unique_x = unique(x_split)
unique_x_order = sort(unique_x,decreasing=T)
x_remain = character()
# find the largest character than can be remained
#initialize
current_string = x_split
current_unique = unique_x
current_order = unique_x_order
while ( length(x_remain) < 20)
{
for(i in 1:length(current_order))
{ character = current_order[i]
index = which(current_string == character)
sub_string = current_string[min(index):length(current_string)]
if (length(setdiff(unique(current_string),unique(sub_string)))==0) #no lose of characters
{x_remain = c(x_remain,character);
current_string = current_string[-c(1:min(index),index)];
current_unique = unique(current_string);
current_order = sort(current_unique,decreasing=T);
break;
}
}
}
#answer is 'tsocrpkijgdqnbafhmle'
后面用python重写了一遍。基本就是等价函数的替换...我是不是在暴殄天物的利用python？完全不理解program on the fly的感觉...
x = 'nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnqsknbarpabgokbsrfhmeklrle';
x_split = list(x);
unique_x = list(set(x_split));
unique_x.sort(reverse=True)
x_remain = list();
###initialize
current_string = x_split;current_unique = unique_x;current_order = unique_x;
while len(x_remain) < len(unique_x):
for character in current_order:
index = current_string.index(character);
sub_string = current_string[index:len(current_string)];
#print(character);
if (len(set(current_string)-set(sub_string))==0): #no lose of characters
x_remain.append(character);
for i in range(sub_string.count(character)):
sub_string.remove(character);
current_string= sub_string;
current_unique = list(set(current_string));
current_unique.sort(reverse=True);
current_order = current_unique;
break;
print(x_remain);
最后好不容易写完python之后，发现网断了...没法在线提交了。等重新连上，时间已经过了，sigh。就当周末无聊历练一下了。
