【Python】：用python做下百度2014笔试题

y23335793

         国庆节最后一天，明天就要上班了，闲来无事做做百度2014笔试题，好久没用过C++了，索性就用python简单的写一下，体验下题目难度。题目是从【大卫David】那里copy过来的。
　　1、给定任意一个正整数，求比这个数大且最小的“不重复数”，“不重复数”的含义是相邻两位不相同，例如1101是重复数，而1201是不重复数。（15分）
　　2、长度为N(N很大)的字符串，求这个字符串里的最长回文子串。（15分）
　　3、数轴上从左到右有n各点a[0], a[1], ……,a[n -1]，给定一根长度为L的绳子，求绳子最多能覆盖其中的几个点。（15分）
　　流程都是A介绍思路，B贴出代码，代码写的也不是很漂亮，凑凑活活贴下
　　一：
　　A.获取输入base的位数，然后分为两种情况，情况1是在该位数下寻找所需要的最小不重复数，情况2是在比该位数+1的位数下找最小不重复数
　　情况2比较简单，就是1010...的罗列，一直到满足位数要求，情况1也就是从base+1开始挨个判断。。。感觉就这么简单，没有想什么高深的算法，
　　如果理解错了同志们轻拍。。
　　B.代码





  1 #!/bin/env/python
2 # -*- encoding:utf-8 -*-
3 #Filename: 1.py
4
5 import sys
6
7 def Get_base_out(num, length):
8     '''Get_base_out method'''
9     for i in range(int(num)+1, 10**length):
10         result = Judge(i, length)
11         if result == True:
12             return i
13     return -1
14
15
16 def Get_base1_out(num, length):
17     '''Get_base1_out method'''
18     no_repeated_num = str(1)
19     for i in range(0,length):
20         if i % 2 == 0:
21             no_repeated_num += '0'
22         else:
23             no_repeated_num += '1'
24     return no_repeated_num
25
26
27 def Judge(suspect, length):
28     ''' Judge method'''
29     temp = str(suspect)
30     for i in range(0,length-1):
31         if temp == temp[i+1]:
32             return False
33     return True
34
35
36 if __name__ == "__main__":
37     for line in sys.stdin:
38         base = line.strip()
39         length = len(base)
40         court = Get_base_out(base, length)
41         if court == -1:
42             court = Get_base1_out(base, length)
43         print court
View Code　　二:
　　A.既然找东西，肯定都遍历一遍喽，那只有想办法在一遍遍历中就完成任务，计划用两个变量分别存储回文自串的位置和回文字串的长度。从头到尾遍历
　　判断下就完事。
　　B.代码：
　　注：没写123321这种类型的回文自串，方法一样就得再敲点代码
　　python有个好处，就是列表负向不会越界，HoHo~





  1 #!/bin/env/python
2 # -*- encoding:utf-8 -*-
3 #Filename: 2.py
4
5 import sys
6
7 def Find_point(base, index):
8     '''Find point method'''
9     rt_point = -1
10     if base[index-1] == base[index+1]:
11         rt_point = index
12     return rt_point
13
14 def Get_length(base, point, length):
15     '''Get huiwen length'''
16     rt_len = -1
17     for i in range(1, (length+1)/2):
18         if point - i >= 0 and point + i < length:
19             if base[point-i] == base[point+i]:
20                 rt_len = i
21             else:
22                 break
23         else:
24             break
25     return rt_len
26
27
28 def Get_huiwen(init_in):
29     '''Get huiwen'''
30     base = str(init_in)
31     length = len(base)
32     huiwen_point = -1
33     huiwen_len = -1
34     for i in range(0, length - 1):
35         tmp_point = -1
36         tmp_len = -1
37         tmp_point = Find_point(base, i)
38         if tmp_point != -1:
39             tmp_len = Get_length(base, tmp_point, length)
40         if tmp_len > huiwen_len:
41             huiwen_point = tmp_point
42             huiwen_len = tmp_len
43     if huiwen_point == -1 and huiwen_len == -1:
44         return "None"
45     start = huiwen_point - huiwen_len
46     end = huiwen_point + huiwen_len + 1
47     return base[start:end]
48
49 if __name__ == "__main__":
50     for line in sys.stdin:
51         arg = line.strip()
52         rt_value = Get_huiwen(arg)
53         print "base:\n%s\nhuiwen:\n%s" % (arg, rt_value)
View Code 　　
　　肚子咕咕叫了，下次补第三题。。。