1、快速排序
2、IP的有效值是1.0.0.1~255.255.255.255，写个程序参数是char*的IP,返
回IP是否合法
提示：IP不超过4位，是否每一位都在合法范围，是否包含非法字符
3、一个字符串数组char*A[]={'china','chinese',chese',...},求这个数
组中字符串的最长公共前缀
4、求两个字符串的最大公共子串，例：‘abcdefg’和 ‘zxdef’最长公共
子串为‘def’
def find_lcsubstr(s1, s2): m=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)] #生成0矩阵，为方便后续计算，比字符串长度多了一列 mmax=0 #最长匹配的长度 p=0 #最长匹配对应在s1中的最后一位 for i in range(len(s1)): for j in range(len(s2)): if s1[i]==s2[j]: m[i+1][j+1]=m[i][j]+1 if m[i+1][j+1]>mmax: mmax=m[i+1][j+1] p=i+1 return s1[p-mmax:p],mmax #返回最长子串及其长度 print find_lcsubstr('abcdfg','abdfg')#最长公共序列
import numpydef find_lcseque(s1, s2): # 生成字符串长度加1的0矩阵，m用来保存对应位置匹配的结果 m = [ [ 0 for x in range(len(s2)+1) ] for y in range(len(s1)+1) ] # d用来记录转移方向 d = [ [ None for x in range(len(s2)+1) ] for y in range(len(s1)+1) ] for p1 in range(len(s1)): for p2 in range(len(s2)): if s1[p1] == s2[p2]: #字符匹配成功，则该位置的值为左上方的值加1 m[p1+1][p2+1] = m[p1][p2]+1 d[p1+1][p2+1] = 'ok' elif m[p1+1][p2] > m[p1][p2+1]: #左值大于上值，则该位置的值为左值，并标记回溯时的方向 m[p1+1][p2+1] = m[p1+1][p2] d[p1+1][p2+1] = 'left' else: #上值大于左值，则该位置的值为上值，并标记方向up m[p1+1][p2+1] = m[p1][p2+1] d[p1+1][p2+1] = 'up' (p1, p2) = (len(s1), len(s2)) print numpy.array(d) s = [] while m[p1][p2]: #不为None时 c = d[p1][p2] if c == 'ok': #匹配成功，插入该字符，并向左上角找下一个 s.append(s1[p1-1]) p1-=1 p2-=1 if c =='left': #根据标记，向左找下一个 p2 -= 1 if c == 'up': #根据标记，向上找下一个 p1 -= 1 s.reverse() return ''.join(s) print find_lcseque('abdfg','abcdfg')5、单向链表反序
6、多个已序数组交集
7、遍历二叉树
8、对一篇文章中的单词按字母顺序排序
9、找出字符串里第一个重复出现的字符‘afdgdfdadfg’
10、对一个版本的字符串比较大小：1.2.2，1.0.1，1.3.2，排序
11、字符串‘welcom to tidn&di’，编码输出其中的‘tidndi’
第一种方法：
t='welcome to tidn&di'
r='tidndi'
e=t[11:]
w=e.replace('&','')
print(w)
第二种方法：
w=t[11:15]+t[16:]
print(w)
#冒泡排序
def sot(x):
for i in range(len(x)-1):
for j in range(len(x)-1-i):
if x[j]>x[j+1]:
x[j],x[j+1]=x[j+1],x[j]
return x
#选择排序
def sot(x):
for i in range(len(x)):
min=i
for j in range(i+1,len(x)):
if x[i]>x[j]:
min=j
t = x[min]
x[min] = x[i]
x[i] = t
#插入排序
def sot(x):
for i in range(1,len(x)):
j=i-1
while j>=0:
if x[j]>x[j+1]:
x[j],x[j+1]=x[j+1],x[j]
j=j-1
else:
break
return x
#快速排序(待确定)
def sot(x):
for i in range(1,len(x)):
key=x[i]
j=i-1
while j>=0:
if x[j]>key:
x[j+1]=x[j]
x[j]=key
j=j-1
else:
break
return x
#快速排序
def partion(nums,left,right):
key = nums[left]
while left < right:
# right下标位置开始，向左边遍历，查找不大于基准数的元素
while left < right and nums[right] >= key:
right -= 1
if left < right: # 找到小于准基数key的元素,然后交换nums[left],nums[right]
nums[left],nums[right] = nums[right],nums[left]
else: # left〉=right 跳出循环
break
# left下标位置开始，向右边遍历，查找不小于基准数的元素
while left < right and nums[left] < key:
left += 1
if left < right: # 找到比基准数大的元素，然后交换nums[left],nums[right]
nums[right],nums[left] = nums[left],nums[right]
else: # left〉=right 跳出循环
break
return left #此时left==right 所以返回right也是可以的
def quick_sort_standord(nums,left,right):
if left < right:
key_index = partion(nums,left,right)
quick_sort_standord(nums,left,key_index)
quick_sort_standord(nums,key_index+1,right)
if __name__ == '__main__':
nums = [5, 6, 4, 2, 3,1]
print nums
quick_sort_standord(nums,0,len(nums)-1)
print nums