1.二分查找变形(首次出现的目标)
一般二分查找,如果目标多次出现,不能保证找到第一次出现的。
当然你也可以找到目标后,不停往前试探,从而找到第一次出现的目标。
下面的更优雅(high单侧二分移动)
def binary_search_first(array, target):
low, high = -1, len(array)while low + 1 != high: # 避免low,high相邻,middle始终等于low,且array[low]<target死循环middle = (low + high) / 2if array[middle] < target: #仅在array[middle] < target时移动low到middle,避免跳过第一次出现的targetlow = middleelse:high = middle # array[middle] >= target时移动high到middle,仅在high一端缩小折半范围assert low + 1 == highif high < len(array): # 当target大于所有数时,high始终为len(array),小心越界assert array[high] >= targetif low > -1: # 当target小于所有数时,low始终为-1,小心越界assert array[low] < target# 当target小于所有数时,high是0,不会越界,指向最小数if high < len(array) and array[high] == target:return highreturn -1
2. 最长重复子序列
后缀数组法
def com_prefix(str1, str2):
result = []for c1, c2 in zip(str1, str2):if c1 == c2:result.append(c1)else:breakreturn "".join(result), len(result)
def max_repeat_sub_str(string):
suffixs = []for i in range(len(string)):suffixs.append(string[i:])suffixs.sort() # 建立后缀数组并排序(排序后相邻元素才可能前缀一致)# 依次比较后缀数组相邻元素,最长相同前缀max_len_repeat, max_len = "", 0for i in range(len(suffixs) - 1):cur_repeat, cur_len = com_prefix(suffixs[i], suffixs[i+1])if cur_len > max_len:max_len_repeat, max_len = cur_repeat, cur_lenreturn max_len_repeat比如输入banana后缀数组: a[0]:banana a[1]:anana a[2]:nana a[3]:ana a[4]:na a[5]:a排序后的后缀数组: a[0]:a a[1]:ana a[2]:anana a[3]:banana a[4]:na a[5]:nana很显然最长前缀a[1]和a[2]的ana建立后缀数组O(N)。排序O(N*NlogN)第一个N是字符串比较,NlogN是排序。后缀的最大公有前缀O(N*N),第1个N字符串比较,第2个N后缀数组长度(元素个数)总的时间复杂度是O(N*NlogN)3.最长不重复子序列
动态规划def max_non_repeat_str(string):dp = [0] * len(string)dp[0] = 1 # 至少1号元素自己last_start, max_dp, max_index = 0, 0, 0for i in range(1, len(string)):for j in range(i-1, last_start-1, -1):if string[j] == string[i]: # 如果相等,i---j之间即为所求dp[i] = i - jlast_start = jbreakelif j == last_start: # 到循环最后一个元素还不相等dp[i] = dp[i-1] + 1if dp[i] > max_dp: # 记录dp数组最大值,以及最大值下标max_dp = dp[i]max_index = ireturn string[max_index+1-max_dp:max_index+1] # 根据dp最大值下标以及长度计算切片