360技术综合H卷笔试——编程题记录

360是我七月初就已经投的公司，同时也是我今年秋招第一个拿到笔试的公司。在考前按照往年的试卷估计题目应该是40道客观题2道编程题。实际结果也如预期一般，30多道的单选题，为数不多的多选题（每个卷子的题型不一样，maybe我这个卷子的少）以及2个编程题。接下来我将尽可能完整的复刻题目并阐述我自己的做法，同时也会附加我自己的代码，望各位看官满意。

第一题 加密算法

有两个人在研究加密算法，一个人提出对只包含小写英文字母的字符串，将 ’a’替换成 ’1’，将 ’b’;替换成 ’2’……，将 ’z’替换成 ’26’。比如一个字符串 ’aabac’（想不起来了，我编的），加密后变成了 ’11213’，但另外一个人提出困难会造成多个结果，就比如 ’11213’也可能是 ’kbm’，会产生多个结果。所以我们要做的就是计算某个加密后的字符串可能对应的原字符串个数，要求取模10^9+7。

输入：

第一行n是加密后的字符串长度

第二行是加密后的字符串

输出：

一个正整数表示原字符串个数

样例输入：

5

11213

样例输出：

8

在做题的时候我就感觉这题怎么这么熟悉，考完一看才发现这不就是leetcode 91 解码方法。

既然提到了那就顺便说一下这道题的思路吧，如果实在需要代码可以直接用笔试题的代码稍微改改应该maybe也能行？

首先这道题需要对一个问题进行多次匹配求解出多个情况。也就是说字符串’11213’可能被分为’1’和’1213’也可能被分为’11’和’213’类似于这样的不断进行。故而就想到了动态规划来解决。
接下来就需要具体构建：

  1. 定义一个数组dp，其中dp[i]表示长度为i的加密字符串可能解码出的原字符串个数。
  2. 设置初始条件dp[0] = 1，即空字符串有一种解码方式。
  3. 状态转移：
    • 如果当前字符可以作为有效的单字符解码(1 <= s[i - 1] <= 9)，则dp[i] += dp[i - 1]
    • 如果当前字符和前一个字符可以作为一个有效的双字符解码(10 <= s[i - 2:i] <= 26)，则dp[i] += dp[i - 2]
  4. 最终结果为dp[n]

好的，接下来回到笔试的考题加密算法本身。

首先分析问题，我们需要给每个字母进行一一对应；加密后的字符串可能对应多个原字符串；我们需要对结果进行取模。
接下来来说说具体的思路：

  1. 使用动态规划来解决
  2. 创建一个数组dp，其中dp[i]表示前i个数字可能对应的原字符串
  3. 对每个位置i，我们需要考虑单独解码和组合解码

借助这个大致思路得到了下面的代码

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
def count_possible_string(encoded):
    MOD = 1000000007
    n = len(encoded)
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1 if encoded[0] != '0' else 0
    
    for i in range(2, n + 1):
        # 单独解码
        if encoded[i - 1] != '0':
            dp[i] = dp[i - 1]
        # 组合解码
        two_digit = int(encoded[i - 2:i])
        if 10 <= two_digit <= 26:
            dp[i] = (dp[i] + dp[i - 2]) % MOD

    return dp[n]

# 输入
n = int(input())
encoded = input()

# 输出
result = count_possible_string(encoded)
print(result)

到这里第一题就结束了，不过我需要说明一点的是，我的代码并不是最优代码，只是能AC这道题，这里也只是提供一种代码和一种思路。

第二题 传染病防控

某市正在进行传染病防控，某市有n个人，每个人有一个位置$(x_{i},y_{i})$。现在已知有一个是高风险人员，但不知道是谁。同时我们定义一个安全距离k，如果某个人和这个高风险人员的距离不超过k，那么这个人也将被列为高风险人员。所以我们现在需要帮工作人员得到最多的高风险人员数量。两个人$(x_1,y_1),(x_2,y_2)$的距离公式为$|x_1-x_2| + |y_1 - y_2|$。

输入描述：

一行两个整数n，k

接下来一行n个整数分别表示$x_1$到$x_n$

接下来一行n个整数分别表示$y_1$到$y_n$

输出描述：

输出一个整数表示最多的高风险人员数量

样例输入：（这里因为debug了好几遍输了好几遍所以还有记录，可以用原本的数）

5 2

8 6 1 5 1

4 4 3 4 6

样例输出：

3

首先明确一点，这个距离公式就是常用的曼哈顿距离，所以在正式写算法前需要先把这个距离公式给写了。

接下来说一下我的大致思路：

  1. 首先构建图，根据输入的坐标和距离构建邻接矩阵ajd
  2. 图的遍历：这里根据惯例选择DFS或BFS来遍历图，我选的是BFS，以此计算出某一点出发的最大连通节点数。
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
def max_high_risk(n, k, x, y):
    from collections import deque

    # 曼哈顿距离公式
    def manhatten_distance(x1, y1, x2, y2):
        return abs(x1 - x2) + abs(y1 - y2)

    # 构建邻接表，adj[i]表示与第i个人相邻的所有人
    adj = [[] for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if manhatten_distance(x[i], y[i], x[j], y[j]) <= k:
                adj[i].append(j)
                adj[j].append(i)

    # 构建BFS            
    def bfs(start):
        queue = deque([start])
        visited = set([start])
        count = 1
        while queue:
            current = queue.popleft()
            for neighbor in adj[current]:
                if neighbor not in visited:
                    queue.append(neighbor)
                    visited.add(neighbor)
                    count += 1
        return count

    max_count = 0
    for i in range(n):
        max_count = max(max_count, bfs(i))
    return max_count

# 输入
n, k = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

# 输出
print(max_high_risk(n, k, x, y))

到这里第二题也就结束了，我当时这道题debug了好几遍，第一次是输入不对，第二次是邻接矩阵出问题，到第三次才成功AC。再次说明我的代码仅仅只能通过所有样例完成这道题，并不是最优解。

最后附上一张在食堂吃饭的时候拍到的学长，超乖的一只猫咪，就是动作有那么一丝丝不文雅。

alt text

笔试记录
#笔试 #算法题
360技术综合H卷笔试——编程题记录
https://www.lx02918.ltd/2024/07/20/My-First-Blog/
作者
Seth
发布于
2024年7月20日
许可协议