Just Do IT !

Python算法学习: 计蒜客蓝桥杯训练营题解(持续更新)

Python算法
字数统计: 2.3k阅读时长: 12 min
2020/02/23 Share

day1字符串和日期:

特殊的三角形

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
'''
特殊的三角形

输入:9
输出:
        1
       121
      12321
     1234321
    123454321
   12345654321
  1234567654321
 123456787654321
12345678987654321
输入:C
输出:
  A
 ABA
ABCBA
'''
n = input()
if ord(n) < 65:
    n = int(n)
    for i in range(1, n+1):
        for j in range(1, n + 1 - i):
            print(' ', end='')
        for j in range(1, i+1):
            print(j, end='')
        for j in range(i , 1, -1):
            print(j-1, end='')
        print()
else:
    ch = ord(n)
    for i in range(65, ch + 1):
        for j in range(1, ch - i + 1):
            print(' ', end='')
        for j in range(65, i + 1):
            print(chr(j), end='')
        for j in range(i, 65, -1):
            print(chr(j - 1), end='')
        print()

字母三角形

1
2
3
4
5
6
7
8
9
10
11
'''
3
  A
 BBB
CCCCC
'''
n = int(input())
for i in range(1, n+1):
    space = (n - i) * ' '
    ch = chr(i+64) * (2*i - 1)
    print(space+ch)

字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
str = list(input())
# a=97 z=122 A=65 Z=90
for i in range(len(str)):
    if 65 <= ord(str[i]) <=122:
        if str[i] == 'z':
            str[i] = 'a'
        elif str[i] == 'Z':
            str[i] = 'A'
        else:
            str[i] = chr(ord(str[i])+1)
    else:
        continue
for i in str:
    print(i, end='')

寻找字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'''
输入:
ossosso
osso

输出:
2
'''
str = input()
target = input()
ans = 0
len_t = len(target)
for i in range(len(str)):
    if str[i] == target[0]:
        if str[i:i+len_t-1] == target[0:len_t-1]:
            ans += 1
print(ans)

恋爱纪念日

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
year, month, day, k = map(int, input().split())
day_ = [0, 31,28,31,30,31,30,31,31,30,31,30,31]
for i in range(1, k+1):
    if year % 100 != 0 and year % 4 == 0 or year % 400 == 0:   #判断是否为闰年
        day_[2] = 29
    else:
        day_[2] = 28
    day += 1
    if day == day_[month]:
        day = 0
        month += 1
    if month == 13:
        month = 1
        year += 1
print("{:d}-{:0>2d}-{:0>2d}".format(year, month, day))

day3代码能力提升

机器人

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
'''
蒜头君收到了一份礼物，是一个最新版的机器人。这个机器人有 4 种指令：
forward x，前进x米。
back x，先向后转，然后前进x米。
left x，先向左转，然后前进x米。
right x，先向右转，然后前进x米。
现在把机器人放在坐标轴原点，起始朝向为x轴正方向。经过一系列指令以后，你能告诉蒜头君机器人的坐标位置吗。坐标轴上一个单位长度表示1米。

样例输入:
10
back -9
left 3
left 8
back 15
right 10
right -7
right -3
left 11
right 17
left 3

样例输出:
9 -7

'''
n = int(input())

dx = [0,-1, 0, 1]  #上左下右
dy = [1, 0,-1, 0]  #上左下右

now_dir = 3

nowx = 0
nowy = 0
for i in range(n):
    dir, x = map(str, input().split())
    x = int(x)
    if dir[0] == 'b':
        now_dir = (now_dir+2) % 4  # 向后
    elif dir[0] == 'l':
        now_dir = (now_dir+1) % 4  # 向左
    elif dir[0] == 'r':
        now_dir = (now_dir+3) % 4  # 向右
    nowx += dx[now_dir] * x
    nowy += dy[now_dir] * x

print(nowx, nowy)

矩阵旋转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
'''
输入:
3 4
-1 3 6 3
7 7 9 1
10 3 4 6
输出:
10 7 -1
3 7 3
4 9 6
6 1 3
'''
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
arr_ans = [[0 for i in range(n)] for _ in range(m)]
for i in range(m):
    for j in range(n):
        arr_ans[i][j] = arr[n-j-1][i]

for i in range(m):
    for j in range(n):
        print(arr_ans[i][j], end=' ')
    print()

矩阵最大子阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
'''
矩阵本身可看作是一个特殊的子矩阵
输入:
3 3
2 -4 1
-1 2 1
4 -2 2
输出:
6
'''
n, m = map(int, input().split())
arr  = [list(map(int, input().split())) for _ in range(n)]
ans  = 0
for i in range(n):
    for j in range(i, n):
        for k in range(m):
            for l in range(k, m):
                tmp = 0
                for p in range(i, j+1):
                    for q in range(k, l+1):
                        tmp += arr[p][q]
                if tmp > ans:
                    ans = tmp
print(ans)

day4:常用STL

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
'''
锯齿矩阵是指每一行包含的元素个数不相同的矩阵，比如：
3 5 2 6 1
2 3 4
1 6 2 7
读入若干对整数 (x,y)，表示在第 x 行的末尾加上一个元素 y。输出最终的锯齿数组。初始时矩阵为空。
输入格式
第一行输入两个整数n,m(1≤n,m≤10000)，其中 n 表示锯齿数组的行数，m 表示插入的元素总数。
接下来一共 m 行，每行两个整数 x,y(1≤x≤n,0≤y≤10000)，表示在第 x 行的末尾插入一个元素 y。
输出格式
一共输出 n 行，每行若干个用空格分隔的整数。如果某行没有任何元素，则输出一个空行。
样例输入
3 12
1 3
2 2
2 3
2 4
3 1
3 6
1 5
1 2
1 6
3 2
3 7
1 1
样例输出
3 5 2 6 1
2 3 4
1 6 2 7
'''

n, m = map(int, input().split())
ans_arr = [[] for _ in range(n)]

# 输入数据
for i in range(m):
    x,y = map(int, input().split())
    ans_arr[x-1].append(y)

# 输出数组
for i in range(n):
    for j in range(len(ans_arr[i])):
        print(ans_arr[i][j], end=' ')
    print()

蒜头君面试

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
'''
蒜头君来蒜厂面试的时候，曾经遇到这样一个面试题：
给定 n 个整数，求里面出现次数最多的数，如果有多个重复出现的数，求出值最大的一个。当时可算是给蒜头君难住了。现在蒜头君来考考你。
输入格式
第一行输入一个整数n(1≤n≤100000)，接下来一行输入n个 int 范围内的整数。
输出格式
输出出现次数最多的数和出现的次数，中间用一个空格隔开，如果有多个重复出现的数，输出值最大的那个。
样例输入
10
9 10 27 4 9 10 3 1 2 6
样例输出
10 2
'''

from collections import Counter

n = int(input())
arr = list(input().split())

count = Counter(arr).most_common()
top = Counter(arr).most_common(1) # 取出现最多数的次数为top

ans = 0
for i in range(len(count)):
    tmp = 0
    if count[i][1] == top[0][1]:
        tmp = count[i][0]
    if int(tmp) > ans:
        ans = int(tmp)

print(ans, top[0][1])

day5:栈和递归练习

括号匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def brace_match(str):
    stack = []
    for ch in str:
        if ch in {'(', '{', '['}:
            stack.append(ch)
        elif len(stack) == 0:
            return False
        elif brace_arr[stack[-1]] == ch:
            stack.pop()
        else:
            return False
    if len(stack) == 0:
        return True

if __name__ == '__main__':
    str = input()
    brace_arr = {'(':')', '{':'}', '[':']'}
    if brace_match(str):
        print('Yes')

蒜头君吃桃

1
2
3
4
5
6
7
8
9
10
11
'''
猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了，求第一天共摘了多少桃子？
'''
def solve(x):
    if x == n:
        return 1
    else:
        return (solve(x+1)+1) * 2
if __name__ == '__main__':
    n = int(input()) # n=10时就是猴子吃桃问题
    print(solve(1))

day6:深度优先搜索

踏青

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
'''
5 6
.#....
..#...
..#..#
...##.
.#....

5 6
. # . . . .
. . # . . .
. . # . . #
. . . # # .
. # . . . .
'''
def dfs(x, y):
    if x < 0 or y < 0 or x > n - 1 or y > m - 1 or vis[x][y] == 1 or arr[x][y] == '.':
        return
    vis[x][y] = 1
    dfs(x - 1, y)
    dfs(x + 1, y)
    dfs(x, y + 1)
    dfs(x, y - 1)

if __name__ == '__main__':
    n, m = map(int, input().split())
    # 当输入中有空格分隔开时
    arr = [list(map(str, input().split())) for _ in range(n)]
    # 当输入没有空格分隔开时

    # arr = []
    # for i in range(n):
    #     str = input()
    #     arr.append(list(str))
    vis = [[0 for _ in range(m)] for _ in range(n)] # 判断是否走过,0为未走过,1为走过
    ans = 0
    for i in range(n):
        for j in range(m):
            if vis[i][j] == 0 and arr[i][j] == '#':
                dfs(i,j)
                ans += 1
    print(ans)

最大的蛋糕数

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
'''
5 6
.#....
..#...
..#..#
...##.
.#....

2
'''
def dfs(x, y):
    if x < 0 or y < 0 or x > n - 1 or y > m - 1 or vis[x][y] == 1 or arr[x][y] == '.':
        return
    vis[x][y] = 1
    global tmp
    tmp += 1
    dfs(x - 1, y)
    dfs(x + 1, y)
    dfs(x, y + 1)
    dfs(x, y - 1)

if __name__ == '__main__':
    n, m = map(int, input().split())
    # 当输入中有空格分隔开时
    # arr = [list(map(str, input().split())) for _ in range(n)]
    # 当输入没有空格分隔开时

    arr = []
    for i in range(n):
        str = input()
        arr.append(list(str))
    vis = [[0 for _ in range(m)] for _ in range(n)] # 判断是否走过,0为未走过,1为走过
    ans = 0
    for i in range(n):
        for j in range(m):
            if vis[i][j] == 0 and arr[i][j] == '#':
                tmp = 0
                dfs(i,j)
                if tmp > ans:
                    ans = tmp
    print(ans)

迷宫的方案数

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
'''
输入:
5 5
s####
.####
.####
.####
....e

输出:
1
'''
def dfs(x,y):
    if x > n - 1 or y > m - 1 or x < 0 or y < 0 or vis[x][y] == 1 or maze[x][y] == '#':
        return

    if maze[x][y] == 'e':
        global ans
        ans += 1
        return

    vis[x][y] = 1
    dfs(x-1,y)
    dfs(x+1,y)
    dfs(x,y-1)
    dfs(x,y+1)
    vis[x][y] = 0     # 将走过的路删除



if __name__ == '__main__':
    n,m = map(int, input().split())
    # 输入迷宫
    maze = []
    vis = [[0 for _ in range(m)] for _ in range(n) ]
    ans = 0

    for _ in range(n):
        val = input()
        maze.append(list(val))
    # 起始坐标
    x = 0
    y = 0
    for i in range(n):
        for j in range(m):
            if maze[i][j] == 's':
                x = i
                y = j
                break
        else:
            continue
        break

    dfs(x,y)
    print(ans)

家谱

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

'''
题意：输入一个n,接下来有n-1行。
输入父亲和儿子
求n个人,每个人的直系后代有多少

输入:
4
1 2
1 3
2 4

输出:
1 3
2 1
3 0
4 0
'''
def dfs(u):
    cnt = 0
    for i in range(len(son[u])):
        cnt += dfs(son[u][i])
    ans[u] = cnt
    return cnt + 1

if __name__ == '__main__':
    n = int(input())
    son = [[] for _ in range(n+1)] # 存放各个父辈的孩子
    ans = [0 for _ in range(n+1)]
    f = [0 for _ in range(n+1)]    # 非True即为祖宗
    for i in range(n-1):
        x,y = map(int, input().split())
        son[x].append(y)
        f[y] = True
    for i in range(1, n+1):
        if f[i] != True:
            u = i                    # 找到祖宗
            break
    dfs(u)
    for i in range(1, n+1):
        print(i, ans[i])

马的覆盖点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def dfs(x, y, step):
    if step > 3 or x < 0 or y < 0 or x > n-1 or y > m-1:
        return
    arr[x][y] = '#'
    for i in range(8):
        dfs(x + dir[i][0], y + dir[i][1], step + 1)
if __name__ == '__main__':
    n, m = map(int, input().split())
    x, y = map(int, input().split())
    arr = [['.' for j in range(m)] for i in range(n)]
    dir = [[-2,-1],[1,2],[-1,-2],[2,1],[2, -1],[1,-2],[-1,2],[-2,1]]

    dfs(x-1,y-1,0)

    for i in range(n):
        for j in range(m):
            print(arr[i][j], end='')
        print()

原文作者：浩翰

原文链接：https://plutoacharon.github.io/2020/02/23/Python算法学习-计蒜客蓝桥杯训练营题解-持续更新/

发表日期：February 23rd 2020, 8:29:16 pm

更新日期：February 23rd 2020, 8:40:42 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. day1字符串和日期:
    1. 1.1. 特殊的三角形
    2. 1.2. 字母三角形
    3. 1.3. 字符串
    4. 1.4. 寻找字符串
    5. 1.5. 恋爱纪念日
  2. 2. day3代码能力提升
    1. 2.1. 机器人
    2. 2.2. 矩阵旋转
    3. 2.3. 矩阵最大子阵
  3. 3. day4:常用STL
    1. 3.1. 蒜头君面试
  4. 4. day5:栈和递归练习
    1. 4.1. 括号匹配
    2. 4.2. 蒜头君吃桃
  5. 5. day6:深度优先搜索
    1. 5.1. 踏青
    2. 5.2. 最大的蛋糕数
    3. 5.3. 迷宫的方案数
    4. 5.4. 家谱
    5. 5.5. 马的覆盖点
Total : 190
2020
2019
CTF Liunx 高可用负载均衡 Java Hadoop Docker Esxi Dokcer Flume GitHub Kafka Golang Golang日志收集系统 Hbase Hive Git Kali Kubernetes Shell Python算法 Spark Sqoop Vmware 机器学习 Zookeeper PHP Hexo 安全 Python PySpark Maven 网络 数据采集 CDN AWD ZooKeeper
CTF Liunx Hadoop Docker GitHub Golang Golang日志收集系统 高可用负载均衡 Hive Java Kubernetes 其他 Python算法 Spark Vmware 机器学习 博客 Python 网络 CDN