Python算法学习: 蓝桥杯官方省赛真题(持续更新)

Python算法

字数统计: 12.2k阅读时长: 52 min

 2020/02/23   Share

置顶 |

全部代码我全部托管到我的GitHub上了,喜欢的麻烦点个关注和star吧😀

资源限制
时间限制：1.0s   内存限制：256.0MB
问题描述
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

输入格式
输入包含一个整数n。
输出格式
输出一行，包含一个整数，表示Fn除以10007的余数。
说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。

样例输入
10
样例输出
55
样例输入
22
样例输出
7704
数据规模与约定
1 <= n <= 1,000,000

代码示例:

n=int(input())
f1=f2=f3=1
if n == 1 or n == 2:
    print(1)
elif n > 2:
    for i in range(3,n+1):
        f3 = (f1 + f2) % 10007
        f1 = f2
        f2 = f3
    print(f3)

试题入门训练圆的面积

资源限制
时间限制：1.0s   内存限制：256.0MB
问题描述
给定圆的半径r，求圆的面积。
输入格式
输入包含一个整数r，表示圆的半径。
输出格式
输出一行，包含一个实数，四舍五入保留小数点后7位，表示圆的面积。
说明：在本题中，输入是一个整数，但是输出是一个实数。

对于实数输出的问题，请一定看清楚实数输出的要求，比如本题中要求保留小数点后7位，则你的程序必须严格的输出7位小数，输出过多或者过少的小数位数都是不行的，都会被认为错误。

实数输出的问题如果没有特别说明，舍入都是按四舍五入进行。

样例输入
4
样例输出
50.2654825
数据规模与约定
1 <= r <= 10000。
提示
本题对精度要求较高，请注意π的值应该取较精确的值。你可以使用常量来表示π，比如PI=3.14159265358979323，也可以使用数学公式来求π，比如PI=atan(1.0)*4。

代码详细:

r = int(input())
PI=3.1415926535
area = r**2 * PI
print('%.7f' % area)

试题入门训练序列求和

资源限制
时间限制：1.0s   内存限制：256.0MB
问题描述
求1+2+3+...+n的值。
输入格式
输入包括一个整数n。
输出格式
输出一行，包括一个整数，表示1+2+3+...+n的值。
样例输入
4
样例输出
10
样例输入
100
说明：有一些试题会给出多组样例输入输出以帮助你更好的做题。

一般在提交之前所有这些样例都需要测试通过才行，但这不代表这几组样例数据都正确了你的程序就是完全正确的，潜在的错误可能仍然导致你的得分较低。

样例输出
5050
数据规模与约定
1 <= n <= 1,000,000,000。
说明：请注意这里的数据规模。

本题直接的想法是直接使用一个循环来累加，然而，当数据规模很大时，这种“暴力”的方法往往会导致超时。此时你需要想想其他方法。你可以试一试，如果使用1000000000作为你的程序的输入，你的程序是不是能在规定的上面规定的时限内运行出来。

本题另一个要值得注意的地方是答案的大小不在你的语言默认的整型(int)范围内，如果使用整型来保存结果，会导致结果错误。

如果你使用C++或C语言而且准备使用printf输出结果，则你的格式字符串应该写成%I64d以输出long long类型的整数。

def sum():
    n = int(input())
    return n*(1+n)/2 # 等差数列时间短 直接使用a+b会超时
s = int(sum())
print(s)

试题入门训练 A+B问题

资源限制
时间限制：1.0s   内存限制：256.0MB
问题描述
输入A、B，输出A+B。
说明：在“问题描述”这部分，会给出试题的意思，以及所要求的目标。
输入格式
输入的第一行包括两个整数，由空格分隔，分别表示A、B。
说明：“输入格式”是描述在测试你的程序时，所给的输入一定满足的格式。

做题时你应该假设所给的输入是一定满足输入格式的要求的，所以你不需要对输入的格式进行检查。多余的格式检查可能会适得其反，使用你的程序错误。

在测试的时候，系统会自动将输入数据输入到你的程序中，你不能给任何提示。比如，你在输入的时候提示“请输入A、B”之类的话是不需要的，这些多余的输出会使得你的程序被判定为错误。

输出格式
输出一行，包括一个整数，表示A+B的值。
说明：“输出格式”是要求你的程序在输出结果的时候必须满足的格式。

在输出时，你的程序必须满足这个格式的要求，不能少任何内容，也不能多任何内容。如果你的内容和输出格式要求的不一样，你的程序会被判断为错误，包括你输出了提示信息、中间调试信息、计时或者统计的信息等。

样例输入
12 45
说明：“样例输入”给出了一组满足“输入格式”要求的输入的例子。

这里给出的输入只是可能用来测试你的程序的一个输入，在测试的时候，还会有更多的输入用来测试你的程序。

样例输出
57
说明：“样例输出”给出了一组满足“输出格式”要求的输出的例子。

样例输出中的结果是和样例输入中的是对应的，因此，你可以使用样例的输入输出简单的检查你的程序。

要特别指出的是，能够通过样例输入输出的程序并不一定是正确的程序，在测试的时候，会用很多组数据进行测试，而不局限于样例数据。有可能一个程序通过了样例数据，但测试的时候仍只能得0分，可能因为这个程序只在一些类似样例的特例中正确，而不具有通用性，再测试更多数据时会出现错误。

比如，对于本题，如果你写一个程序不管输入是什么都输入57，则样例数据是对的，但是测试其他数据，哪怕输入是1和2，这个程序也输出57，则对于其他数据这个程序都不正确。

数据规模与约定
-10000 <= A, B <= 10000。
说明：“数据规模与约定”中给出了试题中主要参数的范围。

这个范围对于解题非常重要，不同的数据范围会导致试题需要使用不同的解法来解决。比如本题中给的A、B范围不大，可以使用整型(int)来保存，如果范围更大，超过int的范围，则要考虑其他方法来保存大数。

有一些范围在方便的时候是在“问题描述”中直接给的，所以在做题时不仅要看这个范围，还要注意问题描述。

代码详细:

1 2	a,b=map(int,input().split()) print(a+b)

基础练习

试题基础练习数列排序

资源限制
时间限制：1.0s   内存限制：512.0MB
问题描述
　　给定一个长度为n的数列，将这个数列按从小到大的顺序排列。1<=n<=200
输入格式
　　第一行为一个整数n。
　　第二行包含n个整数，为待排序的数，每个整数的绝对值小于10000。
输出格式
　　输出一行，按从小到大的顺序输出排序后的数列。
样例输入
5
8 3 6 4 9
样例输出
3 4 6 8 9

代码详细:

n = int(input())
list = list(map(int, input().split()))
list = sorted(list)
for i in range(len(list)):
    print(list[i], end= ' ')

试题基础练习十六进制转八进制

  资源限制
时间限制：1.0s   内存限制：512.0MB
问题描述
　　给定n个十六进制正整数，输出它们对应的八进制数。

输入格式
　　输入的第一行为一个正整数n （1<=n<=10）。
　　接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。

输出格式
　　输出n行，每行为输入对应的八进制正整数。

　　【注意】
　　输入的十六进制数不会有前导0，比如012A。
　　输出的八进制数也不能有前导0。

样例输入
　　2
　　39
　　123ABC

样例输出
　　71
　　4435274

　　【提示】
　　先将十六进制数转换成某进制数，再由某进制数转换成八进制。

代码详细:

n = int(input())

for line in range(n):
    num = input()
    ans = format(int(num, 16), 'o')
    print(ans)

详细可以查阅python的int函数和format函数转换进制

试题基础练习十六进制转十进制

资源限制
时间限制：1.0s   内存限制：512.0MB
问题描述
　　从键盘输入一个不超过8位的正的十六进制数字符串，将它转换为正的十进制数后输出。
　　注：十六进制数中的10~15分别用大写的英文字母A、B、C、D、E、F表示。
样例输入
FFFF
样例输出
65535

代码详细:

1 2	n = input() print(int(n, 16))

试题基础练习十进制转十六进制

资源限制
时间限制：1.0s   内存限制：512.0MB
问题描述
　　十六进制数是在程序设计时经常要使用到的一种整数的表示方式。它有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16个符号，分别表示十进制数的0至15。十六进制的计数方法是满16进1，所以十进制数16在十六进制中是10，而十进制的17在十六进制中是11，以此类推，十进制的30在十六进制中是1E。
　　给出一个非负整数，将它表示成十六进制的形式。
输入格式
　　输入包含一个非负整数a，表示要转换的数。0<=a<=2147483647
输出格式
　　输出这个整数的16进制表示
样例输入
30
样例输出
1E

代码详细:

1 2	n = int(input()) print(format(n, 'X')) #X为大写,x是小写

试题基础练习特殊回文数

资源限制
时间限制：1.0s   内存限制：512.0MB
问题描述
　　123321是一个非常特殊的数，它从左边读和从右边读是一样的。
　　输入一个正整数n， 编程求所有这样的五位和六位十进制数，满足各位数字之和等于n 。
输入格式
　　输入一行，包含一个正整数n。
输出格式
　　按从小到大的顺序输出满足条件的整数，每个整数占一行。
样例输入
52
样例输出
899998
989989
998899
数据规模和约定
　　1<=n<=54。

代码详细:

def is_pal(num):
    num = str(num)
    if num == num[::-1]:
        return True
    else:
        return False
def sum_num(num):
    sum = 0
    num = str(num)
    for i in range(len(num)):
        sum += int(num[i])
    return sum

if __name__ == '__main__':
    n = int(input())
    for num in range(10000, 1000000):
        if is_pal(num) and sum_num(num) == n:
            print(num)

试题基础练习回文数

资源限制
时间限制：1.0s   内存限制：512.0MB
问题描述
　　1221是一个非常特殊的数，它从左边读和从右边读是一样的，编程求所有这样的四位十进制数。
输出格式
　　按从小到大的顺序输出满足条件的四位十进制数。

代码详细:

def is_pal(num):
    num = str(num)
    if num == num[::-1]:
        return True
    else:
        return False
if __name__ == '__main__':
    for i in range(1000, 10000):
        if is_pal(i):
            print(i)

试题基础练习特殊的数字

问题描述
　　153是一个非常特殊的数，它等于它的每位数字的立方和，即153=1*1*1+5*5*5+3*3*3。编程求所有满足这种条件的三位十进制数。
输出格式
　　按从小到大的顺序输出满足条件的三位十进制数，每个数占一行。

代码详细:

def is_ans(num):
    num_sum = pow(int(str(num)[0]), 3) + pow(int(str(num)[1]), 3) + pow(int(str(num)[2]), 3)
    if num == num_sum:
        return True

for ans in range(100, 1000):
    if is_ans(ans):
        print(ans)

这里使用了str转换字符串取位数,或者可以直接用除法取位数

def is_ans(num):
    a = num % 10
    b = (num // 10) % 10
    c = (num // 100) % 10
    if num == pow(a, 3) + pow(b, 3) + pow(c, 3):
        return True

for ans in range(100, 1000):
    if is_ans(ans):
        print(ans)

试题基础练习杨辉三角形

问题描述
杨辉三角形又称Pascal三角形，它的第i+1行是(a+b)i的展开式的系数。

　　
它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。

　　
下面给出了杨辉三角形的前4行：

　　
   1

　　
  1 1

　　
 1 2 1

　　
1 3 3 1

　　
给出n，输出它的前n行。

输入格式
输入包含一个数n。

输出格式
输出杨辉三角形的前n行。每一行从这一行的第一个数开始依次输出，中间使用一个空格分隔。请不要在前面输出多余的空格。
样例输入
4
样例输出
1
1 1
1 2 1
1 3 3 1
数据规模与约定
1 <= n <= 34。

def triangles(num):
    n = [1]
    while num > 0:
        for i in range(len(n)):
            print(n[i], end=' ') # 将列表转为要求的格式
        n = [1] + [n[i] + n[i+1] for i in range(len(n) - 1)] + [1]
        num -= 1
        print()                  # 换行
if __name__ == '__main__':
    n = int(input())
    triangles(n)

试题基础练习查找整数

问题描述
给出一个包含n个整数的数列，问整数a在数列中的第一次出现是第几个。

输入格式
第一行包含一个整数n。

第二行包含n个非负整数，为给定的数列，数列中的每个数都不大于10000。

第三行包含一个整数a，为待查找的数。

输出格式
如果a在数列中出现了，输出它第一次出现的位置(位置从1开始编号)，否则输出-1。
样例输入
6
1 9 4 8 3 9
9
样例输出
2
数据规模与约定
1 <= n <= 1000。

def is_ans(num, list):
    for i in range(len(list)):
        if num == list[i]:
            print(i+1)
            break
    if num not in list:
        print(-1)


if __name__ == '__main__':
    n = int(input())
    list = list(map(int, input().split()))
    num = int(input())
    is_ans(num, list)

试题基础练习数列特征

问题描述
给出n个数，找出这n个数的最大值，最小值，和。

输入格式
第一行为整数n，表示数的个数。

第二行有n个数，为给定的n个数，每个数的绝对值都小于10000。

输出格式
输出三行，每行一个整数。第一行表示这些数中的最大值，第二行表示这些数中的最小值，第三行表示这些数的和。

def is_ans(n, list):
    list = sorted(list)
    max = list[-1]
    min = list[0]
    sum = 0
    for i in list:
        sum += i
    print(max)
    print(min)
    print(sum)

if __name__ == '__main__':
    n = int(input())
    list = list(map(int, input().split()))
    is_ans(n, list)

试题基础练习字母图形

问题描述
利用字母可以组成一些美丽的图形，下面给出了一个例子：

ABCDEFG

BABCDEF

CBABCDE

DCBABCD

EDCBABC

这是一个5行7列的图形，请找出这个图形的规律，并输出一个n行m列的图形。

输入格式
输入一行，包含两个整数n和m，分别表示你要输出的图形的行数的列数。
输出格式
输出n行，每个m个字符，为你的图形。
样例输入
5 7
样例输出
ABCDEFG
BABCDEF
CBABCDE
DCBABCD
EDCBABC

def is_ans(n, m):
    graph = [[0 for j in range(m)] for i in range(n)]
    for i in range(n):
        for j in range(m):
            if j >= i:
                graph[i][j] = chr(ord('A')+ j - i)
            else:
                graph[i][j] = chr(ord('A') + i - j)
    return graph
if __name__ == '__main__':
    n, m = map(int, input().split())
    gragh = is_ans(n ,m)
    for i in range(n):
        for j in range(m):
            print(gragh[i][j], end='')
        print()

参考链接

试题基础练习 01字串

问题描述
对于长度为5位的一个01串，每一位都可能是0或1，一共有32种可能。它们的前几个是：

00000

00001

00010

00011

00100

请按从小到大的顺序输出这32种01串。

输入格式
本试题没有输入。
输出格式
输出32行，按从小到大的顺序每行一个长度为5的01串。
样例输出
00000
00001
00010
00011
<以下部分省略>

1 2	for i in range(32): print("{0:0>5}".format(format(i, 'b')))

参考链接

试题基础练习闰年判断

问题描述
给定一个年份，判断这一年是不是闰年。

当以下情况之一满足时，这一年是闰年：

1. 年份是4的倍数而不是100的倍数；

2. 年份是400的倍数。

其他的年份都不是闰年。

输入格式
输入包含一个整数y，表示当前的年份。
输出格式
输出一行，如果给定的年份是闰年，则输出yes，否则输出no。

def is_leapyear(num):
    if num % 4 == 0 and num % 100 != 0 or num % 400 == 0:
        return True
    return False

if __name__ == '__main__':
    num = int(input())
    if is_leapyear(num):
        print('yes')
    else:
        print('no')

试题基础练习阶乘计算

n = int(input())
ans = 1
for i in range(1, n+1):
    ans =  ans * i

print(ans)

试题基础练习高精度加法

这道题挺迷的,python比其他语言的方便用途之一就是大数的处理
蓝桥杯满分通过

# python 大数
a = int(input())
b = int(input())
print(a+b)

正确做法:

将每个大数存入列表中,一一相加,进位的进位,最后输出ans_num

def change_length(str_num, l):
    # 添加前导0
    str_num = '0' * (l -len(str_num)) + str_num
    return str_num

if __name__ == '__main__':
    num1 = input()
    num2 = input()
    # 修改长度
    if len(num1) > len(num2):
        num2 = change_length(num2, len(num1))
    elif len(num1) < len(num2):
        num1 = change_length(num1, len(num2))
    # 结果最多比最长的num长1个单位
    ans_num = [0 for _ in range(len(num1) + 1)]
    # 进位
    k = 0

    for i in range(len(num1)):
        val = k + int(num1[len(num1) - i - 1]) + int(num2[len(num2) - i - 1])
        ans_num[len(num1) - i] = val % 10
        k = 0
        if  val >= 10:
            k = int(val // 10)

    if k != 0:
        ans_num[0] = k
        for i in range(len(ans_num) - 1):
            print(ans_num[i], end='')
        print(ans_num[-1])
    else:
        for i in range(len(ans_num) - 2):
            print(ans_num[i+1], end='')
        print(ans_num[-1])

试题基础练习 Huffuman树

n = int(input())
value = 0
list = list(map(int, input().split()))

for i in range(n - 1):
    list = sorted(list)
    value += list[0] + list[1]
    value_list = list[0] + list[1]
    list.pop(0)
    list.pop(0)
    list.append(value_list)
print(value)

试题基础练习 2n皇后问题

此题先留个坑,目前只解决了N皇后的思路
方法1:dfs深度优先搜索

class Solution(object):
    def solveNQueens(self, n):

        k = 0
        ans, q = [], [None] * n

        def dfs(k, n):
            if k == n:
                tmp = []
                for i in range(n):
                    s = ""
                    for j in range(n):
                        s += "Q" if q[i] == j else '.'
                    tmp.append(s)
                ans.append(tmp)

            else:
                for j in range(n):
                    if self.place(k, j, q):
                        q[k] = j
                        dfs(k + 1, n)

        dfs(k, n)
        return ans, len(ans)

    def place(self, k, j, q):
        for i in range(k):
            if q[i] == j or abs(q[i] - j) == abs(i - k):
                return False
        return True

if __name__ == '__main__':
    solu = Solution()
    # solu.solveNQueens(4)
    print(solu.solveNQueens(4)) # 当为8时就是8皇后问题

输出:

[['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]
4个皇后时的两种情况

方法2:回溯法

def queen(A, cur=0):

    # 递归回溯思想解决n皇后问题
    if cur == len(A): # 所有的皇后都正确放置完毕，输出每个皇后所在的位置
        tmp = []
        for i in range(n):
            s = ''
            for j in range(n):
                s+='Q' if A[i] == j else '.'
            tmp.append(s)
        ans.append(tmp)
        return 0
    for col in range(len(A)):
        A[cur], flag = col, True
        for row in range(cur): # 检测本次所放皇后的位置是否在同行同列或同一对角线上
            if A[row] == col or abs(col - A[row]) == cur - row: # 是的话，该位置不能放，向上回溯
                flag = False
                break
        if flag: # 否的话，继续放下一个皇后
            queen(A, cur+1)


n = int(input())
ans = []
queen([None] * n)
print(ans)

上述算法简述了N皇后的放置方法,这里同理。

思路：

先在条件合法的情况下放置白皇后，并且将白皇后暂时存储在tmpWhite数组中。
然后在白皇后全部放置的基础上，开始放置黑皇后

def correctWhite(tmpWhite, row):
    if arr[row][tmpWhite[row]] == 1: # tmpWhite[row]表示第几列 ,如果此位置是1, 则表示可以放置
        for i in range(row):        # 判断条件为不在同一列,和不在同一对角线上
            if abs(tmpWhite[i] - tmpWhite[row]) == abs(i - row) or tmpWhite[i] == tmpWhite[row]:
                return False
        return True

def correctBlack(tmpBlack, row, tmpWhite):
    if arr[row][tmpBlack[row]] == 1 and tmpBlack[row] != tmpWhite[row]: # tmpBlack[row]表示第几列 ,如果此位置是1和此位置不和白皇后冲突, 则表示可以放置
        for i in range(row):            # 判断条件为不在同一列,和不在同一对角线上
            if abs(tmpBlack[i] - tmpBlack[row]) == abs(i - row) or tmpBlack[i] == tmpBlack[row]:
                return False
        return True

def dfs_Black(tmpBlack, row):
    if row == n: # 此时黑皇后和白皇后的位置全部确定, 将结果输入到ans列表中
        ans.append(tmpBlack[:])
        return    # 退出递归
    else:
        for col in range(n):
            tmpBlack[row] = col
            if correctBlack(tmpBlack, row, tmpWhite): # 如果位置合法
                dfs_Black(tmpBlack, row + 1)         # 开始下一个黑皇后的放置


def dfs_White(tmpWhite, row):
    if row == n:   # 如果此时确定了白皇后的全部位置,开始放置黑皇后
        dfs_Black(tmpBlack,0)
    else:
        for col in range(n):    # 从第一个白皇后开始放置
            tmpWhite[row] = col
            if correctWhite(tmpWhite, row): # 如果位置可以放置
                dfs_White(tmpWhite, row+1)  # 开始放置下一个白皇后
if __name__ == '__main__':

    # 输入n与棋盘, 其中棋盘用二维数组表示
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    # 设置临时存放黑白皇后的棋盘
    tmpWhite = [None for _ in range(n)]
    tmpBlack = [None for _ in range(n)]
    ans = []
    # 先从白皇后放置开始
    dfs_White(tmpWhite, 0)
    print(len(ans))

试题基础练习报时助手

h, m = map(int, input().split())

time = {0: 'zero', 1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine',
        10: 'ten', 11: 'eleven', 12: 'twelve', 13: 'thirteen', 14: 'fourteen', 15: 'fifteen', 16: 'sixteen',
        17: 'seventeen', 18: 'eighteen', 19: 'nineteen', 20: 'twenty', 21: 'twenty one', 22: 'twenty two',
        23: 'twenty three', 30: 'thirty', 40: 'forty', 50: 'fifty'}

if m == 0:
    print(time[h] + ' o\'clock')
else:
    print(time[h], end=' ')
    if 0 < m <= 20 or m == 30 or m == 40 or m == 50:
        print(time[m])
    elif 20 < m < 30:
        print(time[20] + ' ' + time[m - 20])
    elif 30 < m < 40:
        print(time[30] + ' ' + time[m - 30])
    elif 40 < m < 50:
        print(time[40] + ' ' + time[m - 40])
    else:
        print(time[50] + ' ' + time[m - 50])

试题基础练习回形取数

思路:

通过x表示纵坐标,因为x表示行数,行数+1时纵坐标就会加一
同理 y表示横坐标

n, m = map(int, input().split())
tmp = [] # 存放答案
vis = [[0 for i in range(m)] for i in range(n)] # 验证位置是否走过 当vis[x][y] = 1时即为走过
arr = [list(map(int, input().split())) for _ in range(n)]
# 注意: 向下为x, 向右为y
x = 0 # 当前纵坐标
y = 0 # 当前横坐标
while len(tmp) < n*m :
    while x < n and vis[x][y] == 0:
        tmp.append(arr[x][y])
        vis[x][y] = 1
        x += 1  # 纵坐标加一
    x -= 1 # 将上步多余的步数删除,防止溢出
    y += 1 # 将横坐标右移
    while y < m and vis[x][y] == 0:
        tmp.append(arr[x][y])
        vis[x][y] = 1
        y += 1
    x -= 1 # 将纵坐标减一
    y -= 1 # 将上步多余步数删除,防止溢出
    while x >= 0 and vis[x][y] == 0:
        tmp.append(arr[x][y])
        vis[x][y] = 1
        x -= 1 # 将纵坐标上移
    x += 1 # 将上步多余步数删除,防止溢出
    y -= 1 # 将横坐标左移
    while y >=0 and vis[x][y] == 0:
        tmp.append(arr[x][y])
        vis[x][y] = 1
        y -= 1 # 将横坐标左移
    y += 1 # 将上步多余步数删除
    x += 1 # 将纵坐标下移

# 输出数据
for i in range(len(tmp)):
    print(tmp[i], end=' ')

试题基础练习龟兔赛跑预测

data = list(map(int, input().split()))
rabbit = turtle = 0
time = 0 #目前的时间
flag = False
while True:
    if  rabbit == data[-1] or turtle == data[-1]: # 到达终点
        break
    if  rabbit - turtle >= data[2]:
        for i in range(data[3]):
            turtle += data[1]
            time += 1
            if turtle >= data[-1]:
                flag = True
                break
        if flag:
            break

    time += 1
    rabbit += data[0]
    turtle += data[1]

if rabbit > turtle:  # 谁先到达终点，谁的距离大
    print('R')
    print(time)
elif rabbit < turtle:
    print('T')
    print(time)
else:  # 相等则平局
    print('D')
    print(time)

试题基础练习芯片测试

思路:

这道题需仔细审题, 当好芯片测好芯片时为1, 测坏芯片时为0,坏芯片测试的时候情况不一定。
所以我们可以知道 当每一列0的个数大于n的一半时，此芯片为坏芯片
按列查找

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
tmp = [True] * n # tmp[i]为False时为坏芯片
for i in range(n):
    count = 0
    for j in range(n):
        if arr[j][i] == 0: # 按列查找
            count += 1
        if count >= n/2:
            tmp[i] = False
            break
for i in range(n):
    if tmp[i]:
        print(i+1, end=' ')

试题基础练习 FJ的字符串

n = int(input())
str = 'ABA'
if n == 1:
    print('A')
elif n == 2:
    print('ABA')
else:
    for i in range(3, n+1):
        str = str + chr((i + 64)) + str
    print(str)

试题基础练习 Sine之舞

思路:

递归调用

def Sine_An(n, k):
    if n == k: # 返回值
        return
    print('sin(%d' % (n+1), end='')

    if n + 1 != k: # 当n小于输入的值,即后面还有式子
        if n % 2 == 1: # 如果n是奇数 输出+号
            print('+', end='')
        else:         # 如果n是偶数 输出-号
            print('-', end='')
    else:          # 如果后面没有式子输出右括号
        print(')', end='')

    Sine_An(n+1, k)

def Sine_Sn(n):
    k = t = 1

    if n == 0:
        return

    for i in range(n-1): # 补全左边括号
        print('(', end='')

    while n != 0:
        Sine_An(0,k)
        for i in range(t-1):
            print(')', end='') # 补全An的右括号
        print('+%d' % n, end='')
        if n !=1:
            print(')', end='')

        k+=1
        t+=1
        n-=1
if __name__ == '__main__':
    n = int(input())
    Sine_Sn(n)

试题基础练习数的读法

思路:

考虑多种情况
如前置1有的位置是不读的,11读作shi yi而不是yi shi yi
连续0的处理问题

n = input()

pin_yin = {'0': 'ling', '1': 'yi', '2': 'er', '3': 'san', '4': 'si', '5': 'wu',
           '6': 'liu', '7': 'qi', '8': 'ba', '9': 'jiu'}
pin_yin_2 = {0: '', 1: '', 2: 'shi', 3: 'bai', 4: 'qian', 5: 'wan', 6: 'shi',
             7: 'bai', 8: 'qian', 9: 'yi', 10: 'shi'}
n = n + ' '
#
l = len(n) - 1
for i in range(l):
    j = int(n[i])
    if j != 0:  # 不为0时的读法
        if (l - i == 2 or l - i == 6 or l - i == 10) and j == 1:
            # 在十位，十万位，十亿位置且位于开头的1不读
            # 例子：
            # 1111111111 会读出 yi shi yi yi yi qian yi bai yi shi yi wan yi qian yi bai yi shi yi
            # 111111 会读出 yi shi yi wan yi qian yi bai yi shi yi
            # 11 会读出 yi shi yi
            # 加上此约束后，则不会读出开头的 yi
            if i != 0:  # 第一个1不输出1， 若不添加此条件，12会读出 yi shi er
                print(pin_yin['1'], end=' ')
            print(pin_yin_2[2], end=' ')
            continue
        print(pin_yin[n[i]], end=' ')
        print(pin_yin_2[l - i], end=' ')
    else:  # 处理0的读法问题
        if l - i == 5 or l - i == 9:  # 如果此0是在万位或亿位，则读出万或亿
            print(pin_yin_2[l - i], end=' ')
        if n[i + 1] == '0' or i == l - 1:  # 如果后一位仍然为0，或者，当前是最后一位，则不读此0
            continue
        print(pin_yin['0'], end=' ')  # 否则才读出这个零

试题基础练习完美的代价

思路:

两种情况：
1.impossible的情况：如果有一个字符出现的次数是奇数次数，而且n是偶数，那么不可能构成回文。
如果n是奇数，但是已经有一个字符出现的次数是奇数次数了，那么如果又有一个字符是奇数次数，就不可能构成回文。
2.如果n是奇数，计算中间那个字符交换的次数的时候，不需要模拟把这个数移动到中间去，因为移动到中间的话假设有一对数都在左边或者都在右边。那么交换成回文的时候就要经过中间，就会每次把cnt多加了1，而这个1是没有必要的，因为可以所有的回文移动完了之后再把这个独立的奇数移动过去，才能保证交换次数最少

原文链接：https://blog.csdn.net/qq_31910669/article/details/103641497

该方法蓝桥杯有一组数据超时

n = int(input())

pal = list(input())

count = flag = 0  # count计数，flag判断是否已经有一个单独的奇个数的字符了

m = n - 1

for i in range(m):  # 从头遍历到倒数第二个字符
    for k in range(m, i - 1, -1):  # 从后面往前一直到i寻找和pal[i]相同的pal[k]
        if k == i:  # 如果找不到相同的
            if n % 2 == 0 or flag == 1:  # impossible的两种情况
                print('Impossible')
                exit()
            flag = 1
            count += int(n / 2) - i
        elif pal[k] == pal[i]:
            for j in range(k, m):  # 找到相同的，进行交换
                pal[j], pal[j + 1] = pal[j + 1], pal[j]
                count += 1  # 计数器加1
            m -= 1  # 最后拍好序的不在进行比较
            break

print(count)

方法2:
思路来源:干啥啥不会～

def is_pal(n, s):
    temp = set()
    if n % 2 == 0:
        for i in range(26):
            if s.count(chr(ord('a') + i)) % 2 != 0:
                print('Impossible') # 如果字符串字符为偶数,但是存在不成对字符
                return False
        else:
            return True
    else:
        for i in range(26):
            if s.count(chr(ord('a') + i)) % 2 != 0:
                temp.add(chr(ord('a') + i))
            if len(temp) > 1:
                print('Impossible')  # 如果字符串字符为奇数,但是存在不成对字符超过一个
                return False
        else:
            return True

def count_step(n, s, s1):
    global ans
    for i in range(n // 2):
        if s[i:].count(s[i]) != 1:
            temp = s1[:n - i].index(s[i])
            s1.pop(temp)
            ans += temp
            s = s1[::-1]
        else:
            ans += n // 2 - i
            s[i] = None # 将此奇数移动到中间后清除
            s1 = s[::-1]
    return ans

if __name__ == '__main__':
    n = int(input()) # 字符串的长度
    s = list(input()) # 输入字符串
    s1 = s[::-1]
    ans = 0

    if is_pal(n, s):    # 如果是回文数 计算挪动的步数
        print(count_step(n, s, s1))

试题基础练习矩形面积交

问题描述
　　平面上有两个矩形，它们的边平行于直角坐标系的X轴或Y轴。对于每个矩形，我们给出它的一对相对顶点的坐标，请你编程算出两个矩形的交的面积。
输入格式
　　输入仅包含两行，每行描述一个矩形。
　　在每行中，给出矩形的一对相对顶点的坐标，每个点的坐标都用两个绝对值不超过10^7的实数表示。
输出格式
　　输出仅包含一个实数，为交的面积，保留到小数后两位。

思路:

重点是找到两个矩形产生交集的条件
矩阵1的对角点坐标的横坐标取最小，矩阵2的对角点坐标的横坐标取最小，然后再从这两个值中取最大，得x1
矩阵1的对角点坐标的横坐标取最大，矩阵2的对角点坐标的横坐标取最大，然后再从这两个值中取最小，得x2
如果x1<x2，这两个矩形才会有交集
纵坐标同理
最后交集的面积就为：
area = (x2 - x1) * (y2 - y1)
原文链接：https://blog.csdn.net/qq_31910669/article/details/103641497
题号2.26
1
2
3
4
5
6
7
8
9
10
11
12
13
list1 = list(map(float, input().split()))
list2 = list(map(float, input().split()))

x1 = max(min(list1[0], list1[2]), min(list2[0], list2[2]))
x2 = min(max(list1[0], list1[2]), max(list2[0], list2[2]))
y1 = max(min(list1[1], list1[3]), min(list2[1], list2[3]))
y2 = min(max(list1[1], list1[3]), max(list2[1], list2[3]))

if x1 < x2 and y1 < y2:
    area = (x2 - x1)*(y2 - y1)
    print('%.2f' % area)
else:
    print('%.2f' % 0.00)

试题基础练习矩阵乘法

问题描述
　　给定一个N阶矩阵A，输出A的M次幂（M是非负整数）
　　例如：
　　A =
　　1 2
　　3 4
　　A的2次幂
　　7 10
　　15 22
输入格式
　　第一行是一个正整数N、M（1<=N<=30, 0<=M<=5），表示矩阵A的阶数和要求的幂数
　　接下来N行，每行N个绝对值不超过10的非负整数，描述矩阵A的值
输出格式
　　输出共N行，每行N个整数，表示A的M次幂所对应的矩阵。相邻的数之间用一个空格隔开

def slove(N, rect1, rect_ans):
    rect2 = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):  # 行
        for j in range(N):  # 列
            for n in range(N):
                rect2[i][j] += rect1[i][n] * rect_ans[n][j]
    return rect2

if __name__ == '__main__':
    N, M =map(int, input().split())     # 输入数据
    rect1 = [[] for _ in range(N)]       # 定义矩阵

    for i in range(N):
        arr = input().split()
        for j in range(N):
            rect1[i].append(int(arr[j])) # 输入数据

    if M > 0:
        # 矩阵的幂
        rect_ans = rect1
        for i in range(M-1):
            rect_ans = slove(N, rect1, rect_ans)
    else:
        # 幂等于0时,输出单位矩阵
        rect_ans = [[0 for _ in range(N)] for _ in range(N)]
        for i in range(N):
            rect_ans[i][i] = 1

    # 格式化输出
    for i in range(N):
        for j in range(N):
            print(rect_ans[i][j], end=' ')
        print()

试题基础练习分解质因数

问题描述
　　求出区间[a,b]中所有整数的质因数分解。
输入格式
　　输入两个整数a，b。
输出格式
　　每行输出一个数的分解，形如k=a1*a2*a3...(a1<=a2<=a3...，k也是从小到大的)(具体可看样例)

目前此题代码优化的不是很好, 有两组数据超时,有更好的可以发在评论区分享,互相学习
在这里插入图片描述

def slove(num):
    list = []
    tmp = 2
    if num == tmp:
        print(num,'=', num, sep='')
    else:
        print(num,'=', sep='', end='')
        while num >= tmp:
            if num % tmp ==0:
                list.append(tmp)
                num = num / tmp
            else:
                tmp += 1
        for i in range(len(list)-1):
            print(list[i], '*', sep='', end='')
        print(list[-1])
if __name__ == '__main__':
    a, b = map(int, input().split())
    for i in range(a, b+1):
        slove(i)

下方代码完美通过,思路来源干啥啥不会～
在这里插入图片描述

def solve(res, n, result):
    for i in range(2, n+1):
        if n % i ==0:
            res += str(i)
            n = n // i
            if n == 1:
                return res
            elif n in result.keys():
                res += '*'
                res += result[n]
                return res
            else:
                res += '*'
                return solve(res, n, result)
        else:
            continue

if __name__ == '__main__':
    a, b = map(int, input().split()) # 输入两个整数
    result = {}   # result存放值与其分解质因数的对应关系
    # {3: '3', 4: '2*2', 5: '5', 6: '2*3', 7: '7', 8: '2*2*2', 9: '3*3', 10: '2*5'}
    
    for i in range(a, b+1):
        res = ''  # 存放各个因数
        result[i] = solve(res, i, result)
    
    # 输出
    for k, v in result.items():
        s = str(k)+ '='+ str(v)
        print(s)

试题基础练习字符串对比

问题描述
　　给定两个仅由大写字母或小写字母组成的字符串(长度介于1到10之间)，它们之间的关系是以下4中情况之一：
　　1：两个字符串长度不等。比如 Beijing 和 Hebei
　　2：两个字符串不仅长度相等，而且相应位置上的字符完全一致(区分大小写)，比如 Beijing 和 Beijing
　　3：两个字符串长度相等，相应位置上的字符仅在不区分大小写的前提下才能达到完全一致（也就是说，它并不满足情况2）。比如 beijing 和 BEIjing
　　4：两个字符串长度相等，但是即使是不区分大小写也不能使这两个字符串一致。比如 Beijing 和 Nanjing
　　编程判断输入的两个字符串之间的关系属于这四类中的哪一类，给出所属的类的编号。
输入格式
　　包括两行，每行都是一个字符串
输出格式
　　仅有一个数字，表明这两个字符串的关系编号

def slove(str1, str2):
    if len(str1) != len(str2):
        return 1
    else:
        if str1 == str2:
            return 2
        elif str1.lower() != str2.lower():
            return 4
        return 3
if __name__ == '__main__':
    str1 = input()
    str2 = input()
    print(slove(str1, str2))

Python 字符串大小写转换

试题基础练习时间转换

问题描述
　　给定一个以秒为单位的时间t，要求用“<H>:<M>:<S>”的格式来表示这个时间。<H>表示时间，<M>表示分钟，而<S>表示秒，它们都是整数且没有前导的“0”。例如，若t=0，则应输出是“0:0:0”；若t=3661，则输出“1:1:1”。
输入格式
　　输入只有一行，是一个整数t（0<=t<=86399）。
输出格式
　　输出只有一行，是以“<H>:<M>:<S>”的格式所表示的时间，不包括引号。

time = int(input())
hour = time // 3600
minute = (time - hour*3600) // 60
second = (time - hour*3600 - minute*60) % 60

print(hour,':',minute,':',second, sep='')

算法训练

试题算法训练预测身高

data = list(map(float, input().split()))

if data[0] == 0:
    ans = (data[1]*0.923 + data[2]) / 2
    print("%.3f" % ans)
else:
    ans = (data[1] + data[2]) / 2 * 1.08
    print("%.3f" % ans)

试题算法训练 1的个数

'''
问题描述
　　输入正整数n，判断从1到n之中，数字1一共要出现几次。例如1123这个数，则出现了两次1。例如15，那么从1到15之中，一共出现了8个1。
输入格式
　　一个正整数n
输出格式
　　一个整数，表示1出现的资料
样例输入
15
样例输出
8
'''
n = int(input())
ans = 0
for i in range(1, n+1):
    strn = str(i)
    ans += strn.count('1')
print(ans)

试题算法训练 5-1最小公倍数

'''
问题描述
　　编写一函数lcm，求两个正整数的最小公倍数。
样例输入
一个满足题目要求的输入范例。
例：

3 5
样例输出
15
'''
# 最小公倍数 lcm = a*b/gcd(a,b)
# gcd为最大公约数
def gcd(a,b):
    c = a % b
    while c!=0:
        a = b
        b = c
        c = a % b
    return b

if __name__ == '__main__':
    a,b = map(int, input().split())
    lcm = a*b/gcd(a,b)
    print(int(lcm))

试题算法训练 6-1 递归求二项式系数值

'''
# 方法一 递归
def C(k,n):
    if k == n or k == 0:
        return 1
    else:
        return C(k, n-1)+C(k-1,n-1)

k,n = map(int, input().split())
print(C(k,n))
'''

# 方法二 动态规划
'''
k = 3 n = 10
[0, 0, 0, 0],
[1, 1, 0, 0], 
[1, 2, 1, 0], 
[1, 3, 3, 1], 
[1, 4, 6, 4], 
[1, 5, 10, 10], 
[1, 6, 15, 20], 
[1, 7, 21, 35], 
[1, 8, 28, 56], 
[1, 9, 36, 84], 
[1, 10, 45, 120]
'''
k,n = map(int, input().split())
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
# k=0时候, 1填入dp数组中
for i in range(1, n+1):
    dp[i][0] = 1

# k=n时候, 1填入dp数组中
for i in range(1, k+1):
    dp[i][i] = 1

for i in range(2, n+1):
    for j in range(1, k+1):
        if i > j:
            dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

print(dp[n][k])

试题算法训练 k好数

k, l = map(int, input().split())
mod = 1000000007
ans = 0
dp = [[0 for _ in range(l+1)] for _ in range(k)]

for i in range(k):
    dp[i][1] = 1

for i in range(2, l+1): # 按列遍历 l表示l位数
    for j in range(k):  # 按行遍历
        for w in range(k):
            if w != j+1 and w != j-1: # 相邻的数字不添加
                dp[j][i] = (dp[j][i] + dp[w][i-1])%mod

# 将第l列的数字相加即为ans
for i in range(1,k):
    ans = (ans + dp[i][l])%mod

print(ans)

试题算法训练区间k大数查询

'''
问题描述
给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。

输入格式
第一行包含一个数n，表示序列长度。

第二行包含n个正整数，表示给定的序列。

第三个包含一个正整数m，表示询问个数。

接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。

输出格式
总共输出m行，每行一个数，表示询问的答案。
样例输入
5
1 2 3 4 5
2
1 5 2
2 3 2
样例输出
4
2
'''
# 输入数据
n = int(input())
list_q = list(map(int, input().split()))
m = int(input())

for _ in range(m):
    l,r,k = map(int, input().split())
    ans = list_q[l-1:r]
    ans = sorted(ans, reverse=True)
    print(ans[k-1])

试题算法训练寻找数组中最大值

'''
问题描述
　　对于给定整数数组a[],寻找其中最大值，并返回下标。
输入格式
　　整数数组a[],数组元素个数小于1等于100。输出数据分作两行：第一行只有一个数，表示数组元素个数；第二行为数组的各个元素。
输出格式
　　输出最大值，及其下标
'''
n = int(input())
list1 = list(map(int, input().split()))
max = max(list1)
num = list1.index(max)
print(max,num)

试题算法训练最大的算式

'''
问题描述
　　题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如：
　　N=5，K=2，5个数字分别为1、2、3、4、5，可以加成：
　　1*2*(3+4+5)=24
　　1*(2+3)*(4+5)=45
　　(1*2+3)*(4+5)=45
　　……
输入格式
　　输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中（2<=N<=15, 0<=K<=N-1）。第二行为 N个用空格隔开的数字（每个数字在0到9之间）。
输出格式
　　输出文件仅一行包含一个整数，表示要求的最大的结果
样例输入
5 2
1 2 3 4 5
样例输出
120
'''
# 输入数据
n,k = map(int, input().split())
listq = list(map(int, input().split()))
tmp = listq[0]
# 建立dp数组
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
dp[1][0] = tmp #  提前将第一个数放入dp数组中,方便下面for循环放置
# 将dp数组第一列数据添加
for i in range(1, n):
    tmp += listq[i]
    dp[i+1][0] = tmp
# 当没有乘号时
if k == 0:
    print(dp[n][k])
else:
    for j in range(1, k+1): # 按列循环
        for i in range(2, n+1): # 按行循环
            if i > j: # 乘号小于要计算的各个数字
                '''
                ①dp[5][1] = dp[1][0]x(dp[5][0] - dp[1][0]) = 14
                ②dp[5][1] = dp[2][0]x(dp[5][0] - dp[2][0]) = 36
                ③dp[5][1] = dp[3][0]x(dp[5][0] - dp[3][0]) = 54
                ④dp[5][1] = dp[4][0]x(dp[5][0] - dp[4][0]) = 50
                max函数取其中最大的得数
                '''
                for p in range(1,i):
                    dp[i][j] = max(dp[i][j], dp[p][j-1]*(dp[i][0] - dp[p][0]))

    print(dp[n][k])

试题算法训练石子游戏

思路:
首先将数据存入列表中, 然后进行排序, 直接取尾部最大的两个数

'''
问题描述
　　石子游戏的规则如下：
　　地上有n堆石子，每次操作可选取两堆石子（石子个数分别为x和y）并将它们合并，操作的得分记为(x+1)×(y+1)，对地上的石子堆进行操作直到只剩下一堆石子时停止游戏。
　　请问在整个游戏过程中操作的总得分的最大值是多少？
输入格式
　　输入数据的第一行为整数n，表示地上的石子堆数；第二行至第n+1行是每堆石子的个数。
输出格式
　　程序输出一行，为游戏总得分的最大值。
样例输入
10
5105
19400
27309
19892
27814
25129
19272
12517
25419
4053
样例输出
15212676150
'''
def solve(arr):
    ans = 0
    arr = sorted(arr)
    for i in range(len(arr) - 1):
        tmp = (arr[-1] + 1) * (arr[-2] + 1)
        num = arr[-1] + arr[-2]
        arr.pop()  # 将最后相加的石子堆弹出
        arr.pop()  # 将最后相加的石子堆弹出
        arr.append(num)
        ans += tmp
    return ans


if __name__ == '__main__':
    n = int(input())
    arr = [int(input()) for _ in range(n)]
    ans = solve(arr)
    print(ans)

试题算法训练 Torry的困惑(基本型)

思路:
这里直接暴力应该可以过, 我这里使用了一个质数的特性, 一个质数肯定不会被小于它的质数除尽
根据这个特性可以优化代码

详细的最优质数代码

prime = []
        if n == 0 or n == 1 or n == 2:
            print(0)
        for i in range(n + 1):
            prime.append(True)
        for i in range(2, n + 1):
            if prime[i] == True:
                p = i
                j = 2
                while p * j <= n:
                    prime[p * j] = False
                    j += 1
        prime = prime[2:len(prime) - 1]
        ans = prime.count(True)
        return ans

本题代码:

def is_prime(num):
    for i in tmp: # 遍历质数数组
        if num % i == 0:
            return False
    tmp.append(num)
    return True


if __name__ == '__main__':
    i = 3 # 如果n大于2, 从数字3开始遍历
    ans = 2 # 默认填入第一个质数
    tmp = [2] # 质数数组
    n = int(input())
    while True:
        if len(tmp) >= n:
            break
        if is_prime(i):
            ans *= i
        i += 1
    print(ans % 50000)

试题算法训练最小乘积(基本型)

思路:
将两组数据一个降序排序, 一个升序排序, 遍历相乘再相加即可

t = int(input())
for _ in range(t):
    ans = 0
    n = int(input())
    arr1 = list(map(int, input().split()))
    arr2 = list(map(int, input().split()))

    numList1 = sorted(arr1)  # 升序
    numList2 = sorted(arr2, reverse=True)  # 降序
    for i in range(n):
        ans += numList1[i] * numList2[i]
    print(ans)

###

算法提高

试题算法提高最长滑雪道

思路:

深度优先搜索(dfs),将搜索到的每个位置的答案存入dp中

def dfs(x, y):
    max_height = 1
    if dp[x][y] > 0: # 如果前面dfs已经将该点的高度存入dp中,则直接返回,不用计算
        return dp[x][y]
    for k in range(4):
        tx = x + next_[k][0]
        ty = y + next_[k][1]
        if tx < 0 or tx >= row or ty < 0 or ty >= col:
            continue
        if arr[tx][ty] >= arr[x][y]:
            continue
        max_height = max(max_height, dfs(tx, ty) + 1)

    dp[x][y] = max_height
    return dp[x][y]

if __name__ == '__main__':
    ans = 0
    row, col = map(int, input().split())
    dp = [[0 for _ in range(col)] for _ in range(row)]
    arr = [list(map(int, input().split())) for _ in range(row)]

    next_ = [[0, 1], [1,0], [0,-1], [-1, 0]]

    for i in range(row):
        for j in range(col):
            ans = max(ans, dfs(i, j))

    print(ans)

试题算法提高最长公共子序列

这道题是典型的LCS(Longest Common Subsequence)

具体思路是动态规划: 详细可以参考b站视频: 虽然是英文的但是也很好理解

'''
问题描述
　　给定两个字符串，寻找这两个字串之间的最长公共子序列。
输入格式
　　输入两行，分别包含一个字符串，仅含有小写字母。
输出格式
　　最长公共子序列的长度。
样例输入
abcdgh
aedfhb
样例输出
3
样例说明
　　最长公共子序列为a，d，h。
数据规模和约定
　　字串长度1~1000。
'''


def lcs(str1, str2):
    l1 = len(str1)
    l2 = len(str2)
    arr = [[0 for _ in range(l1 + 1)] for _ in range(l2 + 1)]

    for i in range(l2 + 1):
        for j in range(l1 + 1):
            if i == 0 or j == 0:  # arr[0][j] 与 arr[i][0]全部置为0
                arr[i][j] = 0
            elif i > 0 and j > 0 and str2[i - 1] == str1[j - 1]: # 如果有相等的字符, 则加1
                arr[i][j] = 1 + arr[i - 1][j - 1]
            else:
                arr[i][j] = max(arr[i][j - 1], arr[i - 1][j])

    return arr


if __name__ == '__main__':
    str1 = input()
    str2 = input()
    ansList = lcs(str1, str2)
    print(ansList[-1][-1])

原文作者：浩翰

原文链接：https://plutoacharon.github.io/2020/02/23/Python算法学习-蓝桥杯官方省赛真题-持续更新/

发表日期：February 23rd 2020, 8:35:41 pm

更新日期：April 21st 2020, 6:04:17 pm

Next Post

Kubernetes(K8s)入门到实践(一)----Kubernetes入门
Previous Post

Python算法学习: 任意进制转换

CATALOG



Python算法学习: 蓝桥杯官方省赛真题(持续更新)

目录

入门训练

试题 入门训练 Fibonacci数列

试题 入门训练 圆的面积

试题 入门训练 序列求和

试题 入门训练 A+B问题

基础练习

试题 基础练习 数列排序

试题 基础练习 十六进制转八进制

试题 基础练习 十六进制转十进制

试题 基础练习 十进制转十六进制

试题 基础练习 特殊回文数

试题 基础练习 回文数

试题 基础练习 特殊的数字

试题 基础练习 杨辉三角形

试题 基础练习 查找整数

试题 基础练习 数列特征

试题 基础练习 字母图形

试题 基础练习 01字串

试题 基础练习 闰年判断

试题 基础练习 阶乘计算

试题 基础练习 高精度加法

试题 基础练习 Huffuman树

试题 基础练习 2n皇后问题

试题 基础练习 报时助手

试题 基础练习 回形取数

试题 基础练习 龟兔赛跑预测

试题 基础练习 芯片测试

试题 基础练习 FJ的字符串

试题 基础练习 Sine之舞

试题 基础练习 数的读法

试题 基础练习 完美的代价

试题 基础练习 矩形面积交

试题 基础练习 矩阵乘法

试题 基础练习 分解质因数

试题 基础练习 字符串对比

试题 基础练习 时间转换

算法训练

试题 算法训练 预测身高

试题 算法训练 1的个数

试题 算法训练 5-1最小公倍数

试题 算法训练 6-1 递归求二项式系数值

试题 算法训练 k好数

试题 算法训练 区间k大数查询

试题 算法训练 寻找数组中最大值

试题 算法训练 最大的算式

试题 算法训练 石子游戏

试题 算法训练 Torry的困惑(基本型)

试题 算法训练 最小乘积(基本型)

算法提高

试题 算法提高 最长滑雪道

试题 算法提高 最长公共子序列

试题入门训练 Fibonacci数列

试题入门训练圆的面积

试题入门训练序列求和

试题入门训练 A+B问题

试题基础练习数列排序

试题基础练习十六进制转八进制

试题基础练习十六进制转十进制

试题基础练习十进制转十六进制

试题基础练习特殊回文数

试题基础练习回文数

试题基础练习特殊的数字

试题基础练习杨辉三角形

试题基础练习查找整数

试题基础练习数列特征

试题基础练习字母图形

试题基础练习 01字串

试题基础练习闰年判断

试题基础练习阶乘计算

试题基础练习高精度加法

试题基础练习 Huffuman树

试题基础练习 2n皇后问题

试题基础练习报时助手

试题基础练习回形取数

试题基础练习龟兔赛跑预测

试题基础练习芯片测试

试题基础练习 FJ的字符串

试题基础练习 Sine之舞

试题基础练习数的读法

试题基础练习完美的代价

试题基础练习矩形面积交

试题基础练习矩阵乘法

试题基础练习分解质因数

试题基础练习字符串对比

试题基础练习时间转换

试题算法训练预测身高

试题算法训练 1的个数

试题算法训练 5-1最小公倍数

试题算法训练 6-1 递归求二项式系数值

试题算法训练 k好数

试题算法训练区间k大数查询

试题算法训练寻找数组中最大值

试题算法训练最大的算式

试题算法训练石子游戏

试题算法训练 Torry的困惑(基本型)

试题算法训练最小乘积(基本型)

试题算法提高最长滑雪道

试题算法提高最长公共子序列