Zero2Leetcode

大厂真题 / 哔哩哔哩

哔哩哔哩 4.11 笔试真题

本场考试概述

考试时间：2026年4月11日 考试岗位：通用 难度评级：中等偏难

考点分析：

  1. 第一题：数位DP（难度困难）
  2. 第二题：矩阵遍历/模拟（难度简单）

建议策略：

  1. 第二题模拟题是送分题，务必先拿下
  2. 第一题数位 DP 是高频考点，建议提前掌握记忆化搜索框架

第一题：AK机与区间

题目描述

给定区间 [l, r]，统计其中满足”十进制表示的第一位数字和最后一位数字相等”的数的个数。不含前导零。

样例

输入

1 10

输出

9

输入

88 100

输出

2

思路分析

第一步：观察题目性质

l, r 高达 10^18，逐个枚举不可行，需要按位分析每个数字的结构。经典的前缀差分思路：答案 = f(r) - f(l-1)，其中 f(n) 表示 [1, n] 中满足条件的数的个数。

第二步：数位 DP 状态设计

从高位到低位逐位填入数字，用记忆化搜索统计。状态为 (pos, first, tight, started)：pos 为当前位，first 记录首位数字，tight 表示是否仍贴着上界，started 标记是否已填过非零数字。

第三步：实现要点

在尚未开始时遇到 0 继续跳过（前导零），遇到非零数字则记为首位。填到最后一位时，只有该位数字等于 first 时才计数。对于单位数（首位即末位），直接计数。

题解代码

from functools import lru_cache

def count(n):
    if n <= 0:
        return 0
    s = str(n)
    length = len(s)

    @lru_cache(maxsize=None)
    def dp(pos, first, tight, started):
        if pos == length:
            return 1 if started else 0
        limit = int(s[pos]) if tight else 9
        res = 0
        for d in range(0, limit + 1):
            nt = tight and (d == limit)
            if not started and d == 0:
                res += dp(pos + 1, 0, nt, False)
            elif not started and d > 0:
                if pos == length - 1:
                    # 单位数，首位即末位
                    res += 1
                else:
                    res += dp(pos + 1, d, nt, True)
            else:
                if pos == length - 1:
                    # 最后一位必须等于首位
                    if d == first:
                        res += 1
                else:
                    res += dp(pos + 1, first, nt, True)
        return res

    return dp(0, 0, True, False)

l, r = map(int, input().split())
print(count(r) - count(l - 1))

复杂度分析

时间复杂度：O(D * 10 * 10 * 2 * 2)，其中 D 为数字位数（最多 19 位），总状态数约 7600。 空间复杂度：O(D * 10 * 2 * 2)，用于记忆化表。

第二题：斜行矩阵

题目描述

给出一个 n×m 的矩阵，检查对于所有满足条件的 i 和 j 是否都满足 a[i][j] == a[i+1][j+1]。即判断矩阵是否为 Toeplitz 矩阵（同一条左上到右下的对角线上元素全部相同）。

样例

输入

1
3 3
1 2 3
4 1 2
0 4 1

输出

Yes

思路分析

Toeplitz 矩阵的判定条件很直接：对每个位置 (i, j)（i < n-1, j < m-1），检查 a[i][j] 是否等于 a[i+1][j+1]。一旦发现不等即输出 No，全部满足则输出 Yes。

题解代码

import sys
input = sys.stdin.readline

def is_toeplitz(mat, n, m):
    for i in range(n - 1):
        for j in range(m - 1):
            if mat[i][j] != mat[i + 1][j + 1]:
                return False
    return True

T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    mat = []
    for i in range(n):
        row = list(map(int, input().split()))
        mat.append(row)
    print("Yes" if is_toeplitz(mat, n, m) else "No")

复杂度分析

时间复杂度：O(n * m)，每组数据遍历一次矩阵。 空间复杂度：O(n * m)，存储当前矩阵。

小结

  • 第一题数位 DP 是高频考点，关键在于状态设计：用 first 记录首位数字，在最后一位与 first 比较
  • 第二题 Toeplitz 矩阵判定是经典模拟题，逐元素检查对角线一致性即可