常见题目

1 topk

快排

O(n)

每排一次,就知道基准的位置,就可以得出TopK是在基准左边部分还是右边部分,因此不需要全部排序

堆排

O(k+nlog(k))

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

# 给定一个字符串s和一个字符串p,请问最少去掉s中的多少个字符,才能使得p是s的子串呢?
# 解答要求时间限制:1000ms, 内存限制:100MB

# 输入
# 两行,第一行为字符串s,第二行为字符串p。(s和p只包含小写英文字母,s的长度不超过2000,p的长度不超过10,且保证有解)

# 输出
# 最少去掉的字符个数。

# 样例
# 输入样例 1
# axb
# ab
# 输出
# 1

# 输入样例 2
# axabc
# abc
# 输出
# 0

# 输入样例 3
# axbacxbc
# abc
# 输出
# 2

#dp[i][j] 表示 s[:i]最少需要删几个p[:j]是它的子串 O(mn) O(mn)
###

def minedit(str1,str2):
m=len(str1)
n=len(str2)
# max_num=9999
dp=[[None for i in range(n+1)]for j in range(m+1)]
dp[0][0]=0
for i in range(m):
dp[i][0]=0
for i in range(1,m+1):
for j in range(1,n+1):
if str1[i-1]==str2[j-1]:
dp[i][j]=dp[i-1][j-1]
else:
##
if dp[i-1][j]!=None:
dp[i][j]=dp[i-1][j]+1
result=None
for i in range(n,m+1):
if result==None:
result=dp[i][n]
else:
result=min(result,dp[i][n])
return result


print(minedit("axbacxbc","abc"))


:D 一言句子获取中...