吉利笔试——编程代码题

Q1:

假设有一个n 行m 列的表格，可以分成n✖️m 个块。

• 有一根从左上角到右下角的对角线连接，所有接触对角线的表格中的块为白色，也就是对角线会从该表格中的 小块中经过。
• 输入 表格的大小，输出白色块的数量。

一个矩形n行m列，可以看作分为n✖️m个大小为一的正方形块。计算输出对角线上经过的块的数量。

例如：输入3，4。应该输出6

• 如果n和m中的任一个数为1，那么对角线只会经过一个块，即n * m。
• 否则，对角线将依次穿过矩形的第一行、最后一行、第一列和最后一列，这四条线上的块会被重复计数。其余的块只会被计数一次。因此，对角线上经过的块的数量可以计算为：
  • 对角线块数量 = $n+m-1-gcd(n,m)+1$
  • 其中，gcd(n, m) 表示n和m的最大公约数。

import math

def count_diagonal_blocks(n, m):
    if n == 1 or m == 1:
        return n * m
    else:
        return n + m - math.gcd(n, m)

# 输入表格的大小
n = 3
m = 4

# 计算对角线上经过的块的数量
diagonal_blocks = count_diagonal_blocks(n, m)
print("对角线上经过的块的数量:", diagonal_blocks)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

Q2：

输入一个字符串列表，表示一个迷宫。

• 其中，j 表示墙，空格表示可以进入，k表示人的起始位置。
• 人只能向左或者右或者上或者下移动。
• 请注意，迷宫不一定是正方形。
• 请输出true表示人可以走出来，否则输出false。

例如，输人[“j jj”,”j kj”,”jjjj”]。输出true

如果只有一个元素k时，也输出true
如果外围一圈全是墙j的话，则也是false

def can_escape_maze(maze):
    if not maze:
        return False

    def dfs(x, y):
        if x < 0 or x >= len(maze) or y < 0 or y >= len(maze[0]) or maze[x][y] == 'j':
            return False

        if maze[x][y] == ' ':
            return True

        maze[x] = maze[x][:y] + 'j' + maze[x][y + 1:]

        if (dfs(x + 1, y) or
            dfs(x - 1, y) or
            dfs(x, y + 1) or
            dfs(x, y - 1)):
            return True

        return False

    # 检查外围一圈是否都是墙
    for i in range(len(maze)):
        if i == 0 or i == len(maze) - 1:
            for j in range(len(maze[i])):
                if maze[i][j] != 'j':
                    return False
        else:
            if maze[i][0] != 'j' or maze[i][-1] != 'j':
                return False

    # 找到起始位置
    for i in range(1, len(maze) - 1):
        for j in range(1, len(maze[i]) - 1):
            if maze[i][j] == 'k':
                return dfs(i, j)

    return False

# 输入迷宫
maze = [
    "jjjjjjjj",
    "j j jj j",
    "j jkj  j",
    "j j j jj",
    "j j j  j",
    "j      jj",
    "jjjjjjjj"
]

# 检查是否可以走出迷宫
result = can_escape_maze(maze)
print(result)

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

---

Q3:

输入一个 n✖️n 大小的数组，需要按照从外到里的方向顺时针排列输出。

• 例如，输入 $[[1,2,3],[4,5,6],[7,8,9]]$ 输出应该为 $[1,2,3,6,9,8,7,4,5]$

按照从外到里的顺时针方向，依次遍历矩阵的外围元素，然后逐层向内遍历

def spiral_order(matrix):
    if not matrix:
        return []

    result = []
    while matrix:
        # 从左到右
        result += matrix[0]

        # 从上到下
        if len(matrix) > 1:
            for row in matrix[1:-1]:
                if row:
                    result.append(row[-1])

        # 从右到左
        if len(matrix) > 1:
            result += matrix[-1][::-1]

        # 从下到上
        if len(matrix) > 2:
            for row in matrix[-2:0:-1]:
                if row:
                    result.append(row[0])

        # 剔除已经遍历的外围元素
        matrix = matrix[1:-1]
        for i in range(len(matrix)):
            if matrix[i]:
                matrix[i] = matrix[i][1:-1]

    return result

# 输入矩阵
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

# 获取顺时针排列的结果
result = spiral_order(matrix)
print(result)

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