京东 · 穷举 · 算法编程题
京东 穷举 n ≤ 1e3 时限 1 秒 / 256 MB

题目描述

小红有一个长度为 n 只包含小写字母的字符串，她想把这个字符串通过以下操作变成回文串：
1. 选择字符串的第一个字母，将其插在字符串的末尾。例如，对于字符串 abc ，得到 bca 。
2. 选择一个字符串的一个字符，将这个字符变成任意小写字母。
每次只能进行上述两种操作中的一种，小红想知道最少需要进行多少次操作才能将字符串变成回文串。

输入输出

输入描述
第一行一个正整数 n ，代表字符串的长度。
第二行一个长度为 n 的仅包含小写字母的字符串。
1≤ n ≤ 10^3
输出描述
一个整数，代表最小的操作次数，使得字符串变成回文串。

样例共 1 组

样例 1 · 先进行操作一，字符串变为 acdea。 再进行操作二，字符串变为 aedea。
输入
5
aacde
输出
2

算法解析依据充分

考点：字符串 · 穷举

数据规模 n ≤ 1e3 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 1e3
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：穷举

把候选答案空间全部列出来逐一检验，靠数据范围小来兜底。

思路框架（穷举 通法 · 非本题专属）

  1. 确定枚举什么（下标区间 / 子集 / 数值）。
  2. 用一层或多层循环（或递归）生成所有候选。
  3. 对每个候选判断是否满足题目条件，满足就统计或更新最优值。
  4. 先按数据范围估算枚举量，确认不会超时。

实现要点：多重循环是最直接的写法；枚举组合时可用递归 + 回溯，或用位掩码代表子集。

复杂度：时间 O(候选数 × 单次校验代价) ｜ 空间 O(1)

该范式的通法易错点

  • 没先估复杂度，枚举量超出时限（这是最常见的超时原因）。
  • 去重没做好，同一种方案被多次统计。

对照本题

  • 数据规模 n ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。

样例解读

样例 1：输入 5 / aacde → 输出 2

先进行操作一，字符串变为 acdea。

再进行操作二，字符串变为 aedea。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2023年秋招-京东-技术通用岗位-第一批笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解