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 numpy def 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