2025 题库（阶段三）

01、 非递减数组

给定一个长度为 n 的数组，每次只能对其中的一个元素进行加 1 操作，最少可以通过多少次操作使其变成非递减的数组。非递减数组：a1 ≤ a2 ≤ ... ≤ an。

解答：

    public static int makeNonDecreasing(int[] arr) {
        if (arr.length < 2) {
            return 0;
        }
        int count = 0;
        int prev = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < prev) {
                count += prev - arr[i];
            } else {
                prev = arr[i];
            }
        }
        return count;
    }

02、 满二叉树编号（LCA）

给定无穷大满二叉树，从其根节点开始，一层一层的从左向右依次编号，根节点编号为 1，求 a b 两个节点的最近公共祖先的编号。

思路：

在按层从左到右编号（堆式编号，根为 1）的无限满二叉树中，任意节点 x 的父节点是 x/2。因此，两个节点 a,b 的最近公共祖先（LCA）可以通过不断把较大的那个节点上移到其父节点，直到二者相等为止。

• 父节点关系：parent(x) = x / 2（整数除法）
• 终止条件：当 a == b 时，该值即为 LCA

时间复杂度：O(logmax(a,b))，空间复杂度：O(1)

解答：

    public static long lca(int a, int b) {
        if (a <= 0 || b <= 0) {
            return -1;
        }
        while (a != b) {
            if (a > b) {
                a >>= 1;
            } else {
                b >>= 1;
            }
        }
        return a;
    }

03、 好数组

一个组数，定义好数组的规则为不同元素的个数与数组的长度相等。比如{1,2,3}是好数组，{1,1,2,3}不是，但{}是好数组。

给定一个数组，每次可以删除任意 k 个元素，但删除前需要满足当前数组的长度大于等于 k，可以执行 0 次或任意次，如果能得到好数组输出 yes，否则输出 no。

示例：

测试数据组数 2，初始数组元素个数 5,4，k 值为 3,2，输出 no，yes

输入：
2
5 3
1 1 1 1 1
4 2
1 2 3 4
输出：
no
yes

思路：数组长度对 k 取余的值 小于等于 数组去重后的长度就是好数组。

解答：

    public static void isGoodNumArr(int[] arr, int k) {
        int[] distinct = Arrays.stream(arr).distinct().toArray();
        boolean flag = arr.length % k <= distinct.length;
        System.out.println(flag ? "yes" : "no");
    }

04、 未出现字符值的和

给定一个全部由大写字母 A~Z 组成的字符串，找出未出现的字符，计算这些字符 ASCII 码的和。

    public static int asciiSum(String s) {
        int[] marks = new int[26];
        Arrays.fill(marks, 0);
        for (char c : s.toCharArray()) {
            if ('A' <= c && c <= 'Z') {
                marks[c - 'A'] = 1;
            }
        }
        int sum = 0;
        for (int i = 0; i < marks.length; i++) {
            if (marks[i] == 0) {
                sum += 'A' + i;
            }
        }
        return sum;
    }

05、 数组整除

给定一个数字 num，依次判断这个数字是否可以被各个数位上的数字整除，统计能整除 num 的数位的个数。

    public static int countDivisibility(int num) {
        int count = 0;
        int n = num;
        int d;
        while (n != 0) {
            d = n % 10;
            if (num % d == 0) {
                count++;
            }
            n /= 10;
        }
        return count;
    }

06、 满足条件的数字对

给定两个数 A 和 B，且有 0 ≤ x ≤ y ≤ 2^31-1

• x <= y
• x & y = A
• x | y = B

计算有多少对 x, y 满足以上条件。

思路：

• 若存在某一位使得 A 为 1 而 B 为 0，则不可能满足（因为该位既要求两数都是 1，又要求至少一个是 0），即：
• 若 (A \& ~B) ≠ 0，答案为 0。
• 除去非法情况后，对于每一位：
• 若 Ai=1，则两数该位固定为 1；
• 若 Bi=0，则两数该位固定为 0（此时 Ai 必为 0）；
• 若 Ai=0, Bi=1，则该位两数必须一 0 一 1，有两种分配：(0,1) 或 (1,0)。
• 设“自由位”数 k = bitcount(A ⊕ B)（在合法情况下即为 B 是 1 而 A 是 0 的位数）。
• 若不考虑 x ≤ y，每个自由位 2 种分配，总计 2^k 个有序对。
• 加上 x ≤ y：
  • 若 k=0，唯一解为 x=y=A，答案 1。
  • 若 k>0，不存在 x=y（至少有一位不同），且通过“交换所有自由位上 x、y 的取值”可成双成对地构造大小相反的一一对应，因此恰好一半满足 x<y。答案为 2^k-1。

同时还需保证 A、B 都在 [0, 2^31−1]，否则无解（因为 x、y 只能到 2^31−1，其按位或不可能产生第 31 位为 1）。

位运算的计算性质，x ⊕ y = (x | y) - (x & y) = B - A。

解答：

    public static long numberPairCount(long a, long b) {
        final long limit = 1L << 31; // 2^31
        // 范围检查：x,y <= 2^(31-1) -> A,B 也必须在此范围内且非负
        if (a < 0 || b < 0 || a >= limit || b >= limit) {
            return 0;
        }
        // 合法性检查：A 的 1 位不能出现在 B 的 0 位上
        if ((a & ~b) != 0) {
            return 0;
        }
        // 自由位个数：A 与 B 不同的位（在合法时即 A=0,B=1 的位）
        int k = Long.bitCount(a ^ b);
        // k=0 => x=y=A，唯一解；k>0 -> 2^(k-1)
        return k == 0 ? 1L : 1L << (k - 1);
    }

07、 树节点染色

一棵有 n 个节点的树，根节点为 1 号节点，给树的一部分节点染成红色，然后有 q 次询间，每次询问需要给出某点的子树中红色节点的数量。

示例：

输入4个整数代表2~5号节点的父节点
1 2 1 4
输入长度为5的"W"和"R"组成的字符串，W表示不染色，R表示红色
WWRRR
则树的样子为

      1W
      /\
    2W  4R
   /      \
 3R        5R

q为3，表示询问3次
询问3号节点的子树中红色节点的数量，返回1
询问1号节点的子树中红色节点的数量，返回3
询问4号节点的子树中红色节点的数量，返回2

解答：

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 节点2~n的父节点编号
        int[] parents = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 节点数量（包含根节点1
        int n = parents.length + 1;
        // 树的邻接表表示
        List<List<Integer>> tree = new ArrayList<>();
        for (int i = 0; i <= n; i++) { // 这里使用 i <= n 是因为节点从1开始编号，多一个可以避免越界
            tree.add(new ArrayList<>());
        }
        for (int i = 0; i < parents.length; i++) {
            int number = i + 2; // 节点编号从2开始
            int parent = parents[i];
            tree.get(parent).add(number);
        }
        // 读取染色字符串
        String colorStr = sc.nextLine().trim();
        int[] colors = new int[colorStr.length() + 1]; // 同样为了避免越界
        for (int i = 1; i <= colorStr.length(); i++) {
            colors[i] = colorStr.charAt(i - 1) == 'R' ? 1 : 0;
        }
        // 创建答案数组并进行DFS计算
        int[] counts = new int[colors.length];
        dfs(1, tree, colors, counts);
        // 处理查询
        int q = sc.nextInt();
        while (q-- > 0) {
            System.out.println(counts[sc.nextInt()]);
        }
    }

    private static void dfs(int i, List<List<Integer>> tree, int[] colors, int[] counts) {
        int total = colors[i]; // 当前节点的红色状态
        for (int child : tree.get(i)) {
            dfs(child, tree, colors, counts); // 递归处理子节点
            total += counts[child]; // 累加子树的红色节点数量
        }
        counts[i] = total;
    }

08、 最长合法前缀

一个全部由'('和')'组成的字符串，求该字符串的最长合法前缀，合法前缀定义为：()，(()) 都合法，而 )() 不合法。

解答：

    public static int longestLength(String s) {
        int balance = 0;
        int best = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                balance++;
            } else {
                balance--;
            }
            if (balance < 0) {
                break;
            }
            if (balance == 0) {
                best = i + 1;
            }
        }
        return best;
    }

09、去除字符

给定一个字符串 s，例如 2012，或 2012+2013+2015-2019+2020，其中的符号只有加减号，目前只去掉一个字符，例如 2012 去掉 0 得到 212，保证去掉一个字符后，得到的结果最大，输出这个结果。

    public static void removeOneChar(String str) {
        long max = Long.MIN_VALUE;
        for (int i = 0; i < str.length(); i++) {
            String s = str.substring(0, i) + str.substring(i + 1);
            max = Math.max(max, calc(s));
        }
        System.out.println(max);
    }

    public static long calc(String s) {
        if (s.isEmpty()) {
            return 0;
        }
        long result = 0;
        String[] pArr = s.split("\\+");
        String[] mArr;
        String text;
        long parsed;
        for (String pStr : pArr) {
            if (pStr.isEmpty()) {
                continue;
            }
            mArr = pStr.split("-");
            for (int j = 0; j < mArr.length; j++) {
                text = mArr[j];
                parsed = text.isEmpty() ? 0 : Long.parseLong(text);
                if (j == 0) {
                    result += parsed;
                } else {
                    result -= parsed;
                }
            }
        }
        return result;
    }

10、 函数求和

给出函数 f(x)，如 f(12)=f(0b1100)=4(0b100)，f(4)=f(0b100)=4(0b100)，f(1)=f(0b1)=1，即 f(x)的输出是 x 的二进制表示从右往左数出现第一个 1 的二进制大小。

输入整数 N，求 1/f(1)+2/f(2)+i/f(i)+...+f(N)

解答：

    public static long sum(long n) {
        long sum = 0;
        for (long i = 1; i <= n; i++) {
            sum += i / lsb(i);
        }
        return sum;
    }

    /**
     * Last Set Bit
     */
    public static long lsb(long x) {
        return x & (-x);
    }

11、 牛牛太空人

牛有一艘太空飞船，牛牛想驾驶太空飞船飞出大气层，当前飞船的坐标是（x,y,z），速度向量是（vx,vy,vz），将大气层看做一个半径为 r 的球体，问什么时刻 t 飞船能到达大气层边缘（要求精度不低于 1*10^(-5)）。

    public static void timeToSphere(double x, double y, double z, double vx, double vy, double vz, double r) {
        double a = vx * vx + vy * vy + vz * vz;
        double b = 2 * (vx * x + vy * y + vz * z);
        double c = x * x + y * y + z * z - r * r;
        double delta = b * b - 4 * a * c;
        double result;
        if (delta < 0) {
            result = 0;
        } else if (delta == 0) {
            result = -b / 2 * a;
        } else {
            double t1 = (-b + Math.sqrt(delta)) / (2 * a);
            double t2 = (-b - Math.sqrt(delta)) / (2 * a);
            if (t1 > 0 && t2 > 0) {
                result = Math.min(t1, t2);
            } else if (t1 > 0) {
                result = t1;
            } else if (t2 > 0) {
                result = t2;
            } else {
                result = 0;
            }
        }
        System.out.printf("%.5f", result);
    }

12、 牛牛切割数

牛牛有一个数字 n，可以对 n 进行切割，把切割后的数字相加得到结果，问有几种不同的结果。

示例：

输入：123

情况1：1,2,3，结果为6
情况2：12,3， 结果为15
情况3：1，23，结果为24
情况4：123，  结果为123

输出：4

解答：

    public static int splitNum(String numStr) {
        int length = numStr.length();
        int size = 1 << (length - 1);
        Set<Integer> result = new HashSet<>();
        StringBuilder builder;
        for (int mark = 0; mark < size; mark++) {
            builder = new StringBuilder();
            for (int i = 0; i < length; i++) {
                builder.append(numStr.charAt(i));
                if (i < size && (mark >> i & 1) == 1) {
                    builder.append('+');
                }
            }
            int sum = Arrays.stream(builder.toString().split("\\+")).mapToInt(Integer::parseInt).sum();
            result.add(sum);
        }
        return result.size();
    }

13、 小红的区间数

小红拿到一个数组，取连续的一段区间，使区间中的数相乘不为 0，问这个区间的最大长度。

示例：

输入：1 0 2 3 5 0 1 1
输出：3

解答：

    public static int maxLen(int[] arr) {
        int max = 0;
        int len = 0;
        for (int i : arr) {
            if (i == 0) {
                len = 0;
            } else {
                len++;
                max = Math.max(max, len);
            }
        }
        return max;
    }

14、 牛牛扔骰子

牛牛有一个骰子共 n 面，每面有一个数字（数字可重复），牛牛的第一个幸运数为 A，第二个幸运数为 B。牛牛可以扔两次骰子，求当且仅当第一次得到 A，第二次得到 B 的期望次数（输出保留 1 位小数）。

输入：
3 1 2 （即 n A B）
1 2 3 （n 面上的数）
输出：
9.0

解答：

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        int countA = 0;
        int countB = 0;
        int v;
        for (int i = 0; i < n; i++) {
            v = sc.nextInt();
            if (v == a) countA++;
            if (v == b) countB++;
        }
        double pA = (double) countA / (double) n;
        double pB = (double) countB / (double) n;
        double result = 1d / (pA * pB);
        System.out.printf("%.1f", result);
    }

15、 牛牛大胃王

牛牛的胃口为 m，给定一个数组 vec（数组长度为 n），里面存放了 n 个食物的所能补充的能量，问牛牛能不能吃饱。能吃饱输出“Yes”，否则输出“No”

解答：

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int sum = 0;
            for (int j = 0; j < n; j++) {
                sum += sc.nextInt();
            }
            if (sum >= m) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

16、 报数游戏

牛牛和牛妹玩游戏，牛牛喊 x，牛妹只能喊 x+1，x+2，x+3（比如牛牛喊 2，则牛妹只能喊 [3,4,5] 中的一个），两个人互相轮询，如果喊的数超过 n 则判输，开始的数字为 k（不能喊 k，至少 k+1），输入 n，牛牛先开始喊，如果要牛牛必胜，列举 k 值。

示例：

输入：6
输出：1 3 4 5
解释：
n = 6
k = 1 时，牛妹喊3 4 5，牛牛喊6必胜
k = 3 时，牛牛喊6必胜

解答：

    public static void listNums(int n) {
        List<Integer> list = new ArrayList<>();
        for (int k = 1; k < n; k++) {
            if ((n - k) % 4 != 0) {
                list.add(k);
            }
        }
        for (int i = 0; i < list.size(); i++) {
            if (i > 0) System.out.print(" ");
            System.out.print(list.get(i));
        }
        System.out.println();
    }

17、 3 的倍数

一个由 0~9 组成的字符串，字符串长度 3~10^5，取任意个字符组成一个数，返回是 3 的倍数的最大值，如果没有返回-1。

要点：

一个数能否被 3 整除只取决于各位数字和对 3 的余数。

设各位数字和的余数为 m = sum mod 3
若 m = 0：全部保留，按降序排列即最大
若 m = 1：删除“总余数为 1”的最小代价：
  优先删 1 个最小的余 1 数字（1,4,7 中最小的）
  否则删 2 个最小的余 2 数字（2,5,8 中最小的两位）
若 m = 2：对称地处理：
  优先删 1 个最小的余 2 数字（2,5,8 中最小的）
  否则删 2 个最小的余 1 数字（1,4,7 中最小的两位）

删除后将剩余数字按降序拼接即为最大值
特殊处理：若最终只剩下若干个 0，答案应输出为 "0"；若一个数字也没有，输出 "-1"

解答：

    public static String createMultiples3(String str) {
        int[] cnt = new int[10]; // 统计0-9在字符串中出现的次数
        long sum = 0;
        int num;
        for (char ch : str.toCharArray()) {
            num = ch - '0';
            cnt[num]++;
            sum += num;
        }

        int mod = (int) (sum % 3);
        if (mod == 1) {
            if (!removeNum(cnt, new int[]{1, 4, 7}, 1)) {
                if (!removeNum(cnt, new int[]{2, 5, 8}, 2)) {
                    return "-1";
                }
            }
        } else if (mod == 2) {
            if (!removeNum(cnt, new int[]{2, 5, 8}, 1)) {
                if (!removeNum(cnt, new int[]{1, 4, 7}, 2)) {
                    return "-1";
                }
            }
        }

        int total = 0;
        StringBuilder sb = new StringBuilder();
        for (int d = 9; d >= 0; d--) {
            total += cnt[d];
            for (int k = 0; k < cnt[d]; k++) {
                sb.append((char) ('0' + d));
            }
        }
        if (total == 0) {
            return "-1";
        }
        if (sb.charAt(0) == '0') { // 若全为 0，输出单个 "0"
            return "0";
        } else {
            return sb.toString();
        }
    }

    private static boolean removeNum(int[] cnt, int[] choices, int need) {
        for (int choice : choices) {
            while (need > 0 && cnt[choice] > 0) {
                cnt[choice]--;
                need--;
            }
            if (need == 0) return true;
        }
        return false;
    }

18、 回文数组

小红有一个整数数组，长度为 n，他希望通过一系列操作将数组变为一个回文数组。每次操作可以选择数组中任务相邻的两个元素 a(i) 和 a(i+1)，将他们的值同时加 1。请你计算至少需要多少次操作使得数组变为一个回文数组，如果不可能，则输出-1。

思路：

设对每条相邻边 (i, i+1) 的操作次数为 x[i] ≥ 0。最终数组为：

• (b_1 = a_1 + x_1)
• (bj = a_j + x{j-1} + x_j)（2 ≤ j ≤ n−1）
• (bn = a_n + x{n-1})

回文条件 (bi = b{n+1-i}) 化为关于 x 的线性方程。定义：

• (gi = a_i - a{n+1-i})（i=1..⌊n/2⌋）
• (yi = x_i - x{n-i})，并令 (y_0 = 0)

可推出递推关系：

y_{i-1} + y_i = -g_i (i=1..m), m = n / 2

据此自左向右得到唯一的 (y_1 ... y_m)。

• 若 (n) 为偶数，则中间那条边与自己成对，必须满足 (y_m = 0)，否则无解（输出 -1）。
• 该方法不要求元素非负，整数即可。

解答：

    public static long palindrome(int[] nums) {
        int n = nums.length;
        int m = n / 2;
        long yPrev = 0;
        long count = 0;

        for (int i = 1; i <= m; i++) {
            long gi = nums[i - 1] - nums[n - i]; // g_i
            long yi = -gi - yPrev;               // y_i = -g_i - y_{i-1}
            if ((n % 2 == 0) && i == m) {
                if (yi != 0) { // 偶数长度的中间边需满足 y_m == 0 才可行
                    return -1;
                }
            } else {
                count += Math.abs(yi);
            }
            yPrev = yi;
        }
        return count;
    }

19、 01 翻转

输入一个由 0 和 1 构成的字符串 a，有一个字符串 b，包含的 0 和 1 的数量与 a 一样多，每次可以操作相邻的两个字符进行翻转，经过多次翻转后可以得到 b。小红只记得 b 是经过最大次操作得到的，请输出最大的操作次数。

解答：

    // 这个答案没看懂
    public static int reverseCount(String s) {
        int lCount = count(s);
        int rCount = count(new StringBuilder(s).reverse().toString());
        return Math.max(lCount, rCount);
    }

    public static int count(String s) {
        int res = 0;
        int cnt = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                res += i - cnt;
                cnt++;
            }
        }
        return res;
    }

20、 买文具

一条街上有 n 个文具店，第 i 个店里卖 yi 个文具，问小红买 m 个文具，最少花费多少钱。

输入：
3 2 // 文具店数 要买文具的总个数
1 1 // 第一家店的文具数量 文具单价
2 2 // 第二家店的文具数量 文具单价
6 3 // 第三家店的文具数量 文具单价

解答：

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int count = sc.nextInt();
            int price = sc.nextInt();
            for (int j = 0; j < count; j++) {
                list.add(count);
            }
        }
        Collections.sort(list);
        int total = 0;
        for (int i = 0; i < m; i++) {
            total += list.get(i);
        }
        System.out.println(total);
    }

21、 病毒扩散

病毒体积按照 i^2 形式增长（i 为秒数，例如第 1 秒的体积为 1，第二秒增加体积 2*2=4，则总体积 1+4=5）；有一种武器每秒可消灭体积为 k 的病毒，消灭不完病毒就会扩散，问人类最多一次可以消灭体积多大的病毒；若无法消灭，则输出 0。

解答：

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int k = sc.nextInt();
            int sum = 0;
            int i = 1;
            while (true) {
                if (sum + Math.pow(i, 2) <= k) {
                    sum += (int) Math.pow(i, 2);
                    i++;
                } else {
                    break;
                }
            }
            System.out.println(sum);
        }
    }

22、 数字严格递增或递减

给定 n 组字符串，比如：fbgrgf212345dsf，求最大的连续数字子串，可以是严格递增或递减。复合规则的输出 yes，否则输出 no。

解答：

    public static void detectNumStr(String s) {
        Pattern pattern = Pattern.compile("\\d+");
        Matcher matcher = pattern.matcher(s);
        List<String> list = new ArrayList<>();
        while (matcher.find()) {
            list.add(matcher.group());
        }
        if (list.isEmpty()) {
            System.out.println("false");
            return;
        }

        String flag = "false";
        for (String str : list) {
            if (isConsecutive(str)) {
                flag = "true";
            }
        }
        System.out.println(flag);
    }

    public static boolean isConsecutive(String str) {
        int trend = 0;
        char prev, curr;
        for (int i = 1; i < str.length(); i++) {
            prev = str.charAt(i - 1);
            curr = str.charAt(i);
            if (prev == curr) {
                return false;
            }
            if (trend == 0) {
                trend = curr - prev;
                if (Math.abs(trend) != 1) {
                    return false;
                }
            } else {
                if (curr - prev != trend) {
                    return false;
                }
            }
        }
        return true;
    }

23、 求使得异或值最大的 y 的值

给定一个正整数 x 和一个数 m，选择一个数 y 不大于 m，使得 x xor y 的值最大，求 y 的值。

示例：

输入：
5 4
输出：
2 （最大的异或值为7，则 y = 2）

解答：

    public static int findMaxY(int x, int m) {
        int y = 0;
        int t;
        for (int i = 30; i >= 0; i--) {
            t = 1 << i;
            if ((x & t) == 0 && (y | t) <= m) {
                y |= t;
            }
        }
        return y;
    }