常见题目

1 topk

快排

O(n)

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

堆排

O(k+nlog(k))

2

# 给定一个字符串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"))