Zero2Leetcode

大厂真题 / 虾皮

虾皮 5.9 笔试真题 - 研发岗

本场考试概述

考试时间：2026年5月9日 考试岗位：通用研发岗 难度评级：中等

考点分析：

  1. 第一题：反向贪心 + 不变量推理（难度中等偏难）
  2. 第二题：中心扩展（难度简单）
  3. 第三题：0/1 背包计数 DP（难度中等）

建议策略：

  1. 第一题先想清楚”差值必须是初始差的 $2^k$ 倍”这个不变量，再从目标倒推回起点
  2. 第二题直接中心扩展 $O(n^2)$ 即可通过，注意去重和按位置排序
  3. 第三题是标准 0/1 背包计数，注意空集方案数初始化为 1

第一题：最少计算次数

题目描述

给定两个数 $(x, y)$，允许两种操作：

  1. 同时加 1：$(x, y) \to (x+1, y+1)$
  2. 同时乘 2：$(x, y) \to (2x, 2y)$

求将 $(x, y)$ 转换成 $(X, Y)$ 的最少操作次数。如果不能转换，返回 $-1$。

样例

输入

10,100,22,202

输出

2

思路分析

第一步：正向搜索的困难

正向操作有两个分支（加 1 或乘 2），状态空间随步数指数膨胀。但反向操作是确定的：乘 2 的逆是同时除 2（要求两数都为偶），加 1 的逆是同时减 1。

第二步：不变量分析

差值 $Y - X$ 在加 1 操作下不变，在乘 2 操作下翻倍。因此从 $(x,y)$ 经若干次操作到达 $(X,Y)$，差值关系为 $(Y - X) = (y - x) \times 2^k$。这是可达的必要条件。

第三步：反向贪心策略

从 $(X, Y)$ 倒推回 $(x, y)$：

  • 能除 2 就除 2（让差值减半，最快对齐）
  • 两数任一为奇时无法除 2，必须先减 1 凑齐偶数
  • 当差值已对齐（$Y - X = y - x$）时，剩余只用减 1 操作即可

题解代码

import sys

input = sys.stdin.readline

def solve(x, y, X, Y):
    if X < x or Y < y:
        return -1
    ans = 0
    while X != x or Y != y:
        d = Y - X
        d0 = y - x
        if d == d0:
            if d == 0:
                while X > x:
                    if X % 2 == 0 and X // 2 >= x:
                        X //= 2
                    else:
                        X -= 1
                    ans += 1
                return ans
            return ans + (X - x)
        if (d > 0) != (d0 > 0) and d != 0 and d0 != 0:
            return -1
        if (d == 0) != (d0 == 0):
            return -1
        if abs(d) <= abs(d0):
            return -1
        if X % 2 != 0 or Y % 2 != 0:
            if X - 1 < x or Y - 1 < y:
                return -1
            X -= 1
            Y -= 1
            ans += 1
        else:
            nX, nY = X // 2, Y // 2
            if nX < x or nY < y:
                return -1
            X, Y = nX, nY
            ans += 1
    return ans

line = input().strip()
parts = line.split(',')
x, y, X, Y = int(parts[0]), int(parts[1]), int(parts[2]), int(parts[3])
print(solve(x, y, X, Y))

复杂度分析

时间复杂度：$O(\log V)$，$V$ 为数值范围，每次除 2 让数值减半 空间复杂度：$O(1)$

第二题：所有最长回文子串

题目描述

给定字符串 $s$，找出其中所有长度最大的回文子串。如果存在多个不同的最长回文子串则全部输出，按首次出现位置升序，相同子串只输出一次。

样例

输入

"babad"

输出

["bab","aba"]

思路分析

第一步：为什么用中心扩展

最长回文子串是经典题。暴力枚举子串 $O(n^3)$ 太慢，但中心扩展法 $O(n^2)$ 对 $n \leq 1000$ 完全够用。每个回文都有唯一的对称中心，枚举中心向两边扩展即可。

第二步：枚举所有中心

长度 $n$ 的字符串有 $2n - 1$ 个潜在中心：$n$ 个字符位置（奇数长度回文）和 $n-1$ 个间隔位置（偶数长度回文）。

第三步：维护最优集合

用变量记录当前最大长度，遇到更长的清空旧结果，长度持平且内容未见过则追加。最后按首次出现位置排序输出。

题解代码

import sys

input = sys.stdin.readline

line = input().strip()
s = line.strip('"')
n = len(s)

best_len = 0
positions = []
seen = set()

for center in range(2 * n - 1):
    if center % 2 == 0:
        l = r = center // 2
    else:
        l = center // 2
        r = l + 1
    while l >= 0 and r < n and s[l] == s[r]:
        l -= 1
        r += 1
    l += 1
    r -= 1
    if r < l:
        continue
    cur_len = r - l + 1
    if cur_len > best_len:
        best_len = cur_len
        positions = [l]
        seen = {s[l:r + 1]}
    elif cur_len == best_len:
        sub = s[l:r + 1]
        if sub not in seen:
            positions.append(l)
            seen.add(sub)

positions.sort()
parts = ['"' + s[i:i + best_len] + '"' for i in positions]
print('[' + ','.join(parts) + ']')

复杂度分析

时间复杂度：$O(n^2)$ 空间复杂度：$O(n)$

第三题：组合个数

题目描述

给定整数 $m$ 和 $n$，从 $1$ 到 $m$ 的整数中选出若干个互不相同的整数，使其和等于 $n$。求所有满足条件的组合个数。

样例

输入

6 8

输出

4

思路分析

第一步：识别问题模型

从 ${1, 2, \ldots, m}$ 中选若干不重复的数凑出和为 $n$。每个数最多用一次——这就是标准的 0/1 背包计数问题。

第二步：状态定义与转移

定义 $f[i][j]$ = 用 ${1, \ldots, i}$ 凑出和为 $j$ 的方案数。

  • 不取 $i$：$f[i][j] = f[i-1][j]$
  • 取 $i$（要求 $j \geq i$）：$f[i][j] += f[i-1][j-i]$

初始化 $f[0][0] = 1$（空集是合法方案），其余为 0。

第三步：答案

$f[m][n]$ 即为所求。可以用滚动数组优化空间到 $O(n)$，但 $O(mn)$ 也完全够用。

题解代码

import sys

input = sys.stdin.readline

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

f = [[0] * (n + 1) for _ in range(m + 1)]
f[0][0] = 1

for i in range(1, m + 1):
    for j in range(n + 1):
        f[i][j] = f[i - 1][j]
        if j >= i:
            f[i][j] += f[i - 1][j - i]

print(f[m][n])

复杂度分析

时间复杂度：$O(m \cdot n)$ 空间复杂度：$O(m \cdot n)$，可优化为 $O(n)$

小结

  • 第一题考察逆向思维和不变量分析，反向操作消除了搜索的分支爆炸问题
  • 第二题是回文子串的经典中心扩展法，注意去重和输出格式
  • 第三题是 0/1 背包计数的直接应用，关键是初始化 $f[0][0] = 1$