#快排 class Solution(object): def swap(self,x,i,j): tmp,x[i] = x[i],x[j] x[j] = tmp def partitionSort(self,x,l,r): i,j = l,r key = l while True: while x[j] >= x[key] and j > l:j -= 1 while x[i] <= x[key] and i < r:i += 1 if i >= j:break self.swap(x,i,j) self.swap(x,j,key) return j def quickSort(self,x,l,r): if l >= r:return p = self.partitionSort(x,l,r) print(x) self.quickSort(x,l,p-1) self.quickSort(x,p+1,r) x = [6, 1 , 2, 7, 9 , 3 , 4 ,5 ,10 , 8] Solution().quickSort(x,0,len(x)-1) print(x)
#堆排序 def heapSort(arr,n,i): miniest,l,r = i,2*i+1,2*i+2 if l<n and arr[l] < arr[miniest]: miniest = l if r<n and arr[r] < arr[miniest]: miniest = r if miniest != i: arr[miniest],arr[i] = arr[i],arr[miniest] heapSort(arr,n,miniest) def minHeapSort(arr): n = len(arr) for i in range(n-1,-1,-1): heapSort(arr,n,i) for i in range(n-1,0,-1): arr[i],arr[0] = arr[0],arr[i] heapSort(arr,i,0) arr = [10,46,22,81,91,60,31,30,77,96,13,20,65,35,65] minHeapSort(arr) n = len(arr) print("排序后") for i in range(n): print("%d" % arr[i])
# KMP
def get_pnext(p):
pnext, L = [0], len(p)
for i in range(1, L):
k = pnext[i - 1]
while k | 0 and p[k] != p[i]: k = pnext[k - 1]
if p[k] == p[i]:
pnext.append(k + 1)
else:
pnext.append(0)
return pnext
def strStr(s, p):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if not p: return 0
Ls, Lp = len(s), len(p)
if Ls < Lp: return -1
i, j, pnext = 0, 0, get_pnext(p)
print(pnext)
while i < Ls and j < Lp:
if s[i] == p[j]:
i += 1
j += 1
elif j != 0:
j = pnext[j - 1]
else:
i += 1
if j == Lp:
return i - Lp
return -1
# 马拉车 寻找回文子串
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
s1 = ‘#‘.join(s)
s1 = ‘#‘ + s1 + ‘#‘
l1 = len(s1)
r = [0] * l1
for i in range(0, l1):
if r[i] != 0:
continue
r[i] = 1
for j in range(i - 1, -1, -1):
delta = i - j
tmp = i + delta
if tmp == l1 or s1[j] != s1[tmp]:
break
r[i] += 1
for delta in range(1, r[i]):
j = i - delta
r2 = r[i] - delta
if r[j] < r2:
r[i + delta] = r[j]
if r[j] > r2:
r[i + delta] = r2
max_r = max(r)
index = r.index(max_r)
return s1[index - max_r + 1:index + max_r - 1].replace(‘#‘, ‘‘)
‘‘‘
#动态规划版本
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
l = len(s)
if l == 0:
return ‘‘
m = [[False for _ in range(l)] for _ in range(l)]
index = 0
max_l = 1
for k in range(0,l):
for i in range(l-k):
j = i + k
if (j-i<2 or m[i+1][j-1]) and s[i] == s[j]:
m[i][j] = True
if m[i][j] and j+1-i>max_l:
max_l = j+1-i
index = i
return s[index:index+max_l]
‘‘‘
# 最大字段和
def maxSubSum(nums):
"""
:type nums: List[int]
:rtype: int
"""
b, sub_sum = 0, float(‘-inf‘)
for x in nums:
if b > 0:
b += x
else:
b = x
if b > sub_sum: sub_sum = b
return sub_sum
# 最小表示 class Solution(object): def minimumRepresentation(self, s): i,j,k,l = 0,1,0,len(s) while k<l and i<l and j<l: if s[(i+k)%l] == s[(j+k)%l]: k+=1 else: if s[(i+k)%l]>s[(j+k)%l]:i=max(i+k+1,j+1) else:j=max(j+k+1,i+1) k=0 print(‘i‘+str(i)+‘ j‘+str(j)+‘ k‘+str(k)) return min(i,j)
原文：https://www.cnblogs.com/yvlian/p/11613914.html