Categories
读书有感

python小试

今天非常无聊的决定去试一下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。就当周末无聊历练一下了。

36 replies on “python小试”

我至今没法踏进Python之门的一个重要原因是下标从0开始,感觉充满了各种违和感……但是很奇怪写C的时候又完全没有障碍觉得特别自然。请问这是分裂的症状吗,求被洗脑求被拯救。

我在想,是因为python跟R太像了,所以各种不适应?话说不写显示index还是蛮好的习惯。
C的话,整个程序都是在跟指针玩,实在是跑不掉index故也不觉得违和了?

python号称万能胶水,用来挑大梁不是不能干,但翔的感觉会多于飞翔的感觉
我感觉python和R最像的地方,是都有一大堆数不清楚的函数,库,包,不同的库,包有不同的规则,上手都很快,深入学习的成本都不低。。。

所以我是进入了一个大坑么?至今无法理解为啥interactive mode只能一行一行的运行命令,一下子贴多行居然会报错,头痛。

应该是缩进的问题。interactive mode 比较麻烦。楼主试一下 ipython notebook

因为缩进是语法一部分,所以复制粘贴过去的话出错就编译不能了。
如果输入 for 循环,末尾有冒号的话,回车可以继续输入。
python notebook 和网页版自动化的 knitr 差不多吧。不是完整的 ide。

notebook 确实不是完整的IDE,不过在数据分析中很实用。可以图文并茂的记录下来整个的分析过程,甚至包括出错、调试的过程。而不像IDE那样,调试到最后只剩下一段正确的能运行的代码,急着要结果的时候甚至连注释都没有,几个月后翻出来自己都看的莫名其妙。
interactive mode 弄一个快捷方式,基本上就用来当计算器了。

等我有空研究一下...真的是modelling的话我还是离不开R,学python更多是为了做数据清洗和整理...

就是很简单的两行都没法搞定... 比如:
a=1
b=2
直接拷贝过去会报错“SyntaxError: multiple statements found while compiling a single statement”,一行行拷过去就没事...

直接拷贝有时会连同回车、换行符、缩进符、空格一并拷贝进去。还有当前复制光标位置是否已经缩进了,都会影响编译,不好说具体问题。比如就目前打开一个新的IDLE,无缩进,直接复制你的这条留言里面的a=1b=2,就不会报错,而且光标是停在b=2后面,不会自动编译,需要再回车。总之就是回车换行缩进空格等特殊字符引起的。

呵呵,貌似复制粘贴代码应该是有更好的办法。印象中在哪里看到过,但是没记住。要是再发现了,告诉你哈。
另外对于缩进,看起来同样宽度的4个空格和一个tab 混合使用,也会出问题的哦,复制有的时候也会遇到。

话说我刚看到你的blog上对这个算法的分析...瞬间表示完全看不懂。好吧我基本上不关心内存开销什么的,这种题目本来就是考逻辑思维所以不会给太大的测试数据的。我只是在有限的时间里面强行写了一个可用的算法出来,呃。果然不是CS专业出身的,写代码各种野蛮强横。

本人业余中的菜鸟中的业余菜鸟^_^。连CS的边也摸不着。也不懂内存开销,只是在小心着:有时候以为修改了一个变量,其实它没变;有时候以为没有修改,其实它被修改了。这个是重点。

还有字典序那个...就是你打开字典的单词排列顺序啊。a肯定在b之前,随便找本英文字典就是那个顺序。

Comments are closed.