标签： medium

目标

给你一个二维字符矩阵 grid，其中 grid[i][j] 可能是 'X'、'Y' 或 '.'，返回满足以下条件的子矩阵数量：

• 包含 grid[0][0]
• 'X' 和 'Y' 的频数相等。
• 至少包含一个 'X'。

示例 1：

输入： grid = [["X","Y","."],["Y",".","."]]
输出： 3

示例 2：

输入： grid = [["X","X"],["X","Y"]]
输出： 0
解释：
不存在满足 'X' 和 'Y' 频数相等的子矩阵。

示例 3：

输入： grid = [[".","."],[".","."]]
输出： 0
解释：
不存在满足至少包含一个 'X' 的子矩阵。

说明：

• 1 <= grid.length, grid[i].length <= 1000
• grid[i][j] 可能是 'X'、'Y' 或 '.'.

思路

有一个矩阵 grid，其元素为 X Y .，求满足条件的子矩阵数量。要求子矩阵包含左上角 grid[0][0]，并且至少包含一个 X，且 X 与 Y 的数量相等。

二维前缀和。

代码

/**
 * @date 2026-03-19 8:49
 */
public class NumberOfSubmatrices3212 {

    public int numberOfSubmatrices(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] xCnt = new int[m + 1][n + 1];
        int[][] yCnt = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                xCnt[i + 1][j + 1] = xCnt[i][j + 1] + xCnt[i + 1][j] - xCnt[i][j];
                yCnt[i + 1][j + 1] = yCnt[i][j + 1] + yCnt[i + 1][j] - yCnt[i][j];
                if (grid[i][j] == 'X') {
                    xCnt[i + 1][j + 1]++;
                } else if (grid[i][j] == 'Y') {
                    yCnt[i + 1][j + 1]++;
                }
            }
        }
        int res = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (xCnt[i][j] == yCnt[i][j] && xCnt[i][j] != 0) {
                    res++;
                }
            }
        }
        return res;
    }
}

性能

目标

给你一个下标从 0 开始的整数矩阵 grid 和一个整数 k。

返回包含 grid 左上角元素、元素和小于或等于 k 的 子矩阵的数目。

示例 1：

输入：grid = [[7,6,3],[6,6,1]], k = 18
输出：4
解释：如上图所示，只有 4 个子矩阵满足：包含 grid 的左上角元素，并且元素和小于或等于 18 。

示例 2：

输入：grid = [[7,2,9],[1,5,0],[2,6,6]], k = 20
输出：6
解释：如上图所示，只有 6 个子矩阵满足：包含 grid 的左上角元素，并且元素和小于或等于 20 。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= n, m <= 1000
• 0 <= grid[i][j] <= 1000
• 1 <= k <= 10^9

思路

有一个矩阵 grid，求包含左上角 grid[0][0] 的子矩阵中，元素和小于等于 k 的子矩阵数量。

二维前缀和。

代码

/**
 * @date 2026-03-18 8:47
 */
public class CountSubmatrices3070 {

    public int countSubmatrices(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] prefix = new int[m + 1][n + 1];
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j] + grid[i][j];
                if (prefix[i + 1][j + 1] <= k) {
                    res++;
                }
            }
        }
        return res;
    }
}

性能

目标

给你一个二进制矩阵 matrix ，它的大小为 m x n ，你可以将 matrix 中的 列 按任意顺序重新排列。

请你返回最优方案下将 matrix 重新排列后，全是 1 的子矩阵面积。

示例 1：

输入：matrix = [[0,0,1],[1,1,1],[1,0,1]]
输出：4
解释：你可以按照上图方式重新排列矩阵的每一列。
最大的全 1 子矩阵是上图中加粗的部分，面积为 4 。

示例 2：

输入：matrix = [[1,0,1,0,1]]
输出：3
解释：你可以按照上图方式重新排列矩阵的每一列。
最大的全 1 子矩阵是上图中加粗的部分，面积为 3 。

示例 3：

输入：matrix = [[1,1,0],[1,0,1]]
输出：2
解释：由于你只能整列整列重新排布，所以没有比面积为 2 更大的全 1 子矩形。

示例 4：

输入：matrix = [[0,0],[0,0]]
输出：0
解释：由于矩阵中没有 1 ，没有任何全 1 的子矩阵，所以面积为 0 。

说明：

• m == matrix.length
• n == matrix[i].length
• 1 <= m * n <= 10^5
• matrix[i][j] 要么是 0 ，要么是 1 。

提示：

• For each column, find the number of consecutive ones ending at each position.
• For each row, sort the cumulative ones in non-increasing order and "fit" the largest submatrix.

思路

有一个 m x n 二进制矩阵 matrix，可以重新排列矩阵的列，求全 1 子矩阵的最大面积。

如果不允许重新排列，统计全1子矩阵的个数，参考 1504.统计全1子矩形 枚举底边与右边界。

针对每一列记录以当前行为终点连续 1 的高度，然后按高度排序，那么以当前行为底的最大子矩阵就可以求出来了。

代码

/**
 * @date 2026-03-17 9:37
 */
public class LargestSubmatrix1727 {

    public int largestSubmatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] ones = new int[m][n];
        System.arraycopy(matrix[0], 0, ones[0], 0, n);
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    ones[i][j] = ones[i - 1][j] + 1;
                }
            }
        }
        int res = 0;
        for (int[] row : ones) {
            Arrays.sort(row);
            int i = n - 1;
            int l = 1;
            int max = 0;
            while (i >= 0 && row[i] > 0) {
                max = Math.max(max, row[i--] * l++);
            }
            res = Math.max(res, max);
        }
        return res;
    }
}

性能

目标

给你一个 m x n 的整数矩阵 grid 。

菱形和 指的是 grid 中一个正菱形 边界 上的元素之和。本题中的菱形必须为正方形旋转45度，且四个角都在一个格子当中。下图是四个可行的菱形，每个菱形和应该包含的格子都用了相应颜色标注在图中。

注意，菱形可以是一个面积为 0 的区域，如上图中右下角的紫色菱形所示。

请你按照 降序 返回 grid 中三个最大的 互不相同的菱形和 。如果不同的和少于三个，则将它们全部返回。

示例 1：

输入：grid = [[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]]
输出：[228,216,211]
解释：最大的三个菱形和如上图所示。
- 蓝色：20 + 3 + 200 + 5 = 228
- 红色：200 + 2 + 10 + 4 = 216
- 绿色：5 + 200 + 4 + 2 = 211

示例 2：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
输出：[20,9,8]
解释：最大的三个菱形和如上图所示。
- 蓝色：4 + 2 + 6 + 8 = 20
- 红色：9 （右下角红色的面积为 0 的菱形）
- 绿色：8 （下方中央面积为 0 的菱形）

示例 3：

输入：grid = [[7,7,7]]
输出：[7]
解释：所有三个可能的菱形和都相同，所以返回 [7] 。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• 1 <= grid[i][j] <= 10^5

思路

有一个 m x n 矩阵 grid，返回矩阵中最大的三个 不相同 的菱形和。满足条件的菱形指矩阵内部的正方形顺时针旋转 45°，并且四个角必须占一个格子的正方形。菱形和就是其边界上的元素之和。

枚举所有合法的正菱形。针对每一个元素 (i, j)，枚举以它作为对角线交点的所有可能的正菱形（正方形）。

经过观察发现，如果边上元素个数为 k + 1，那么上顶点坐标为 (i - k, j)，下顶点坐标为 (i + k, j)，左顶点坐标为 (i, j - k)，右顶点坐标为 (i, j + k)。

枚举 (i, j) 所在行 [j - k, j + k] 范围内的元素。注意左右顶点的上下元素重合到自身，不能重复累加。特殊处理两端点，中间枚举 x ∈ [j - k + 1, j + k - 1] 累加上下 h 的元素值，即 (i - h, x) 与 (i + h, x)。其中 h = k - Math.abs(j - x)，k 表示中点到四个角的距离，x 表示列标，j - x 表示列标距离中点的距离。

上面的解法针对每一个中点重复累加了边上的元素和。更好做法是使用两个二维数组分别表示两个方向 ↘ ↙ 上截止到 (u, v) 的前缀和。中点确定之后，可以确定边的四个角，进而可以计算前缀和。注意不要重复计算四个角。

代码

/**
 * @date 2026-03-16 9:37
 */
public class GetBiggestThree1878 {

    public int[] getBiggestThree(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        TreeSet<Integer> set = new TreeSet<>((a, b) -> b - a);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; i + k < m && i - k >= 0 && j - k >= 0 && j + k < n; k++) {
                    int sum = 0;
                    if (k == 0) {
                        set.add(grid[i][j]);
                        continue;
                    }
                    sum += grid[i][j - k] + grid[i][j + k];
                    for (int x = j - k + 1; x <= j + k - 1; x++) {
                        int h = k - Math.abs(j - x);
                        sum += grid[i - h][x] + grid[i + h][x];
                    }
                    set.add(sum);
                }
            }
        }
        int size = Math.min(3, set.size());
        int[] res = new int[size];
        Iterator<Integer> iterator = set.iterator();
        for (int i = 0; i < size; i++) {
            res[i] = iterator.next();
        }
        return res;
    }

}

性能

目标

一个 「开心字符串」定义为：

• 仅包含小写字母 ['a', 'b', 'c'].
• 对所有在 1 到 s.length - 1 之间的 i ，满足 s[i] != s[i + 1] （字符串的下标从 1 开始）。

比方说，字符串 "abc"，"ac"，"b" 和 "abcbabcbcb" 都是开心字符串，但是 "aa"，"baa" 和 "ababbc" 都不是开心字符串。

给你两个整数 n 和 k ，你需要将长度为 n 的所有开心字符串按字典序排序。

请你返回排序后的第 k 个开心字符串，如果长度为 n 的开心字符串少于 k 个，那么请你返回 空字符串 。

示例 1：

输入：n = 1, k = 3
输出："c"
解释：列表 ["a", "b", "c"] 包含了所有长度为 1 的开心字符串。按照字典序排序后第三个字符串为 "c" 。

示例 2：

输入：n = 1, k = 4
输出：""
解释：长度为 1 的开心字符串只有 3 个。

示例 3：

输入：n = 3, k = 9
输出："cab"
解释：长度为 3 的开心字符串总共有 12 个 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"] 。第 9 个字符串为 "cab"

示例 4：

输入：n = 2, k = 7
输出：""

示例 5：

输入：n = 10, k = 100
输出："abacbabacb"

说明：

• 1 <= n <= 10
• 1 <= k <= 100

思路

使用小写字母 a b c 构造相邻不重复的长度为 n 的字符串，求字典序第 k 小的字符串。

按顺序回溯构造长度为 n 的字符串，直到第 k 个结束返回。

代码

/**
 * @date 2026-03-16 13:55
 */
public class GetHappyString1415 {

    private char[] curChar = new char[]{'a', 'b', 'c'};

    public String getHappyString(int n, int k) {
        List<String> list = new ArrayList<>(k);
        char[] chars = new char[n];
        dfs(n, k, '-', 0, chars, list);
        return list.size() < k ? "" : list.get(k - 1);
    }

    public void dfs(int n, int k, char prev, int l, char[] chars, List<String> list) {
        if (list.size() == k) {
            return;
        }
        if (l == n) {
            list.add(new String(chars));
            return;
        }
        for (char c : curChar) {
            if (c == prev) {
                continue;
            }
            chars[l] = c;
            dfs(n, k, c, l + 1, chars, list);
        }
    }

}

性能

目标

给你一个整数 mountainHeight 表示山的高度。

同时给你一个整数数组 workerTimes，表示工人们的工作时间（单位：秒）。

工人们需要 同时 进行工作以 降低 山的高度。对于工人 i :

• 山的高度降低 x，需要花费 workerTimes[i] + workerTimes[i] 2 + ... + workerTimes[i] x 秒。例如：
  • 山的高度降低 1，需要 workerTimes[i] 秒。
  • 山的高度降低 2，需要 workerTimes[i] + workerTimes[i] * 2 秒，依此类推。

返回一个整数，表示工人们使山的高度降低到 0 所需的 最少 秒数。

示例 1：

输入： mountainHeight = 4, workerTimes = [2,1,1]
输出： 3
解释：
将山的高度降低到 0 的一种方式是：
工人 0 将高度降低 1，花费 workerTimes[0] = 2 秒。
工人 1 将高度降低 2，花费 workerTimes[1] + workerTimes[1] * 2 = 3 秒。
工人 2 将高度降低 1，花费 workerTimes[2] = 1 秒。
因为工人同时工作，所需的最少时间为 max(2, 3, 1) = 3 秒。

示例 2：

输入： mountainHeight = 10, workerTimes = [3,2,2,4]
输出： 12
解释：
工人 0 将高度降低 2，花费 workerTimes[0] + workerTimes[0] * 2 = 9 秒。
工人 1 将高度降低 3，花费 workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12 秒。
工人 2 将高度降低 3，花费 workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12 秒。
工人 3 将高度降低 2，花费 workerTimes[3] + workerTimes[3] * 2 = 12 秒。
所需的最少时间为 max(9, 12, 12, 12) = 12 秒。

示例 3：

输入： mountainHeight = 5, workerTimes = [1]
输出： 15
解释：
这个示例中只有一个工人，所以答案是 workerTimes[0] + workerTimes[0] * 2 + workerTimes[0] * 3 + workerTimes[0] * 4 + workerTimes[0] * 5 = 15 秒。

说明：

• 1 <= mountainHeight <= 10^5
• 1 <= workerTimes.length <= 10^4
• 1 <= workerTimes[i] <= 10^6

思路

整数 mountainHeight 表示山的高度，workerTimes[i] 表示工人 i 的时效，工人 i 将山的高度降低 x 所需的时间是 workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x，求工人同时工作，将山的高度降为 0 所需要的最少时间。

移山所需的时间是所有工人消耗时间的最大值，最小化这个最大值，可以考虑二分答案。

工人 i 将高度降低 x 所需时间为 workerTimes[i] * (1 + 2 + …… + x) = workerTimes[i] * (1 + x) * x / 2。如果最大时间是 target，解方程可得工人 i 最多将高度降低 (sqrt(1 + (8 * target) / workerTimes[i]) - 1) / 2，只需判断降低的高度是否超过 mountainHeight 即可。

代码

/**
 * @date 2026-03-13 9:42
 */
public class MinNumberOfSeconds3296 {

    public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        int max = 0;
        int n = workerTimes.length;
        for (int wt : workerTimes) {
            max = Math.max(max, wt);
        }
        long p = (mountainHeight - 1) / n + 1;
        long l = 0L, r = max * (1 + p) * p / 2;
        long m = l + (r - l) / 2;
        while (l <= r) {
            if (check(mountainHeight, workerTimes, m)) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return l;
    }

    public boolean check(int mountainHeight, int[] workerTimes, long target) {
        int total = 0;
        for (int w : workerTimes) {
            total += (int) (Math.sqrt(1 + (8 * target) / w) - 1) / 2;
            if (total >= mountainHeight) {
                return true;
            }
        }
        return false;
    }

}

性能

目标

给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：

• 类型 1 ：删除 字符串 s 的第一个字符并将它 添加 到字符串结尾。
• 类型 2 ：选择 字符串 s 中任意一个字符并将该字符 反转 ，也就是如果值为 '0' ，则反转得到 '1' ，反之亦然。

请你返回使 s 变成 交替 字符串的前提下， 类型 2 的 最少 操作次数 。

我们称一个字符串是 交替 的，需要满足任意相邻字符都不同。

• 比方说，字符串 "010" 和 "1010" 都是交替的，但是字符串 "0100" 不是。

示例 1：

输入：s = "111000"
输出：2
解释：执行第一种操作两次，得到 s = "100011" 。
然后对第三个和第六个字符执行第二种操作，得到 s = "101010" 。

示例 2：

输入：s = "010"
输出：0
解释：字符串已经是交替的。

示例 3：

输入：s = "1110"
输出：1
解释：对第二个字符执行第二种操作，得到 s = "1010" 。

说明：

• 1 <= s.length <= 10^5
• s[i] 要么是 '0' ，要么是 '1' 。

思路

有一个二进制字符串 s，每次操作：1.可以将首字母移动到末尾；2.或者将任意字符反转，求将 s 变为交替字符串所需的最小反转次数，即最少的操作 2 的次数。

由于不考虑首尾移动的次数，可以将首尾相接，考虑字符串 s + s。交替字符串就两种，可以使用长度为 s.length 的滑动窗口计算反转的最小次数。

可以只考虑交替字符串 010101... 所需的反转次数 k，那么 10101010... 所需的反转次数为 n - k，参考 1758_生成交替二进制字符串的最少操作数。

010101... 这种交替字符串可以用下标的奇偶性来表示。移出窗口时，如果下标的奇偶性与元素值的奇偶性不同，说明差异个数减一。移入窗口同理，操作次数加一。

代码

/**
 * @date 2026-03-09 11:42
 */
public class MinFlips1888 {

    public int minFlips(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int ops = 0;
        for (int i = 0; i < n; ++i) {
            ops += (chars[i] ^ i) & 1;
        }
        int res = Math.min(ops, n - ops);
        if ((n & 1) == 0) {
            return res;
        }
        for (int i = 0; i < n; ++i) {
            ops -= (chars[i] ^ i) & 1;
            ops += (chars[i] ^ (n + i)) & 1;
            res = Math.min(res, Math.min(ops, n - ops));
        }
        return res;
    }

}

性能

目标

给你一个字符串数组 nums ，该数组由 n 个 互不相同 的二进制字符串组成，且每个字符串长度都是 n 。请你找出并返回一个长度为 n 且 没有出现 在 nums 中的二进制字符串。如果存在多种答案，只需返回 任意一个 即可。

示例 1：

输入：nums = ["01","10"]
输出："11"
解释："11" 没有出现在 nums 中。"00" 也是正确答案。

示例 2：

输入：nums = ["00","01"]
输出："11"
解释："11" 没有出现在 nums 中。"10" 也是正确答案。

示例 3：

输入：nums = ["111","011","001"]
输出："101"
解释："101" 没有出现在 nums 中。"000"、"010"、"100"、"110" 也是正确答案。

说明：

• n == nums.length
• 1 <= n <= 16
• nums[i].length == n
• nums[i] 为 '0' 或 '1'
• nums 中的所有字符串 互不相同

思路

有 n 个长度为 n 的二进制字符串数组，构造一个长度为 n 的字符串，使它与数组中的字符串不同，答案可能有多个返回任一一个即可。

康托对角线，构造字符串的第 i 个位置 与 nums[i] 的第 i 个位置不同，这样可以保证构造出的字符串与数组中的所有字符串都不同。

代码

/**
 * @date 2026-03-09 18:08
 */
public class FindDifferentBinaryString1980 {

    public String findDifferentBinaryString_v1(String[] nums) {
        int n = nums.length;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int c = nums[i].charAt(i) - '0';
            sb.append(c ^ 1);
        }
        return sb.toString();
    }

}

性能

目标

给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：

• 类型 1 ：删除 字符串 s 的第一个字符并将它 添加 到字符串结尾。
• 类型 2 ：选择 字符串 s 中任意一个字符并将该字符 反转 ，也就是如果值为 '0' ，则反转得到 '1' ，反之亦然。

请你返回使 s 变成 交替 字符串的前提下， 类型 2 的 最少 操作次数 。

我们称一个字符串是 交替 的，需要满足任意相邻字符都不同。

• 比方说，字符串 "010" 和 "1010" 都是交替的，但是字符串 "0100" 不是。

示例 1：

输入：s = "111000"
输出：2
解释：执行第一种操作两次，得到 s = "100011" 。
然后对第三个和第六个字符执行第二种操作，得到 s = "101010" 。

示例 2：

输入：s = "010"
输出：0
解释：字符串已经是交替的。

示例 3：

输入：s = "1110"
输出：1
解释：对第二个字符执行第二种操作，得到 s = "1010" 。

说明：

• 1 <= s.length <= 10^5
• s[i] 要么是 '0' ，要么是 '1' 。

思路

有一个二进制字符串 s，每次操作：1.可以将首字母移动到末尾；2.或者将任意字符反转，求将 s 变为交替字符串所需的最小反转次数，即最少的操作 2 次数。

由于不考虑首尾移动的次数，可以将首尾相接，考虑字符串 s + s。交替字符串就两种，可以使用长度为 s.length 的滑动窗口计算反转的最小次数。

可以只考虑交替字符串 010101...，假设所需的反转次数为 k，那么 10101010... 所需的反转次数为 n - k，参考 1758.生成交替二进制字符串的最少操作数。

010101... 这种交替字符串可以用下标的奇偶性来表示。移出窗口时，如果下标的奇偶性与元素值的奇偶性不同，说明差异个数减一。移入窗口同理，操作次数加一。

代码

/**
 * @date 2026-03-09 11:42
 */
public class MinFlips1888 {

    public int minFlips(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int ops = 0;
        for (int i = 0; i < n; ++i) {
            ops += (chars[i] ^ i) & 1;
        }
        int res = Math.min(ops, n - ops);
        if ((n & 1) == 0) {
            // 如果长度为偶数，操作1不会改变下标的奇偶性，比如 i，i + n 的奇偶性相同，后面循环中 ops 并不会发生变化
            return res;
        }
        for (int i = 0; i < n; ++i) {
            ops -= (chars[i] ^ i) & 1;
            ops += (chars[i] ^ (n + i)) & 1;
            res = Math.min(res, Math.min(ops, n - ops));
        }
        return res;
    }

}

性能

目标

给你两个正整数 n 和 k，二进制字符串 Sn 的形成规则如下：

• S1 = "0"
• 当 i > 1 时，Si = Si-1 + "1" + reverse(invert(Si-1))

其中 + 表示串联操作，reverse(x) 返回反转 x 后得到的字符串，而 invert(x) 则会翻转 x 中的每一位（0 变为 1，而 1 变为 0）。

例如，符合上述描述的序列的前 4 个字符串依次是：

• S1 = "0"
• S2 = "011"
• S3 = "0111001"
• S4 = "011100110110001"

请你返回 Sn 的 第 k 位字符 ，题目数据保证 k 一定在 Sn 长度范围以内。

示例 1：

输入：n = 3, k = 1
输出："0"
解释：S3 为 "0111001"，其第 1 位为 "0" 。

示例 2：

输入：n = 4, k = 11
输出："1"
解释：S4 为 "011100110110001"，其第 11 位为 "1" 。

示例 3：

输入：n = 1, k = 1
输出："0"

示例 4：

输入：n = 2, k = 3
输出："1"

说明：

• 1 <= n <= 20
• 1 <= k <= 2^n - 1

思路

长度为 n 的二进制字符串的递推公式为 S_1 = 0, S_i = S_(i-1) + "1" + reverse(invert(S_(i-1)))，返回 S_n 的 第 k 位 字符，k 从 1 开始。

简单的做法是根据题意模拟，改写一下递推公式的下标，从 i = 0 开始，已知递推公式 s[0] = '0', s[i] = s[i - 1] + '1' + invertAndReverse(s[i - 1])，求 s[n - 1].charAt(k - 1)。

一个更优的做法是递归。s[i] 的长度 len[i] = 2 * len[i - 1] + 1 => len[i] + 1 = 2 (len[i - 1] + 1)，len[i] + 1 是一个首项为 2，公比为 2 的等比数列，第 i 项长度为 2^i - 1。可以将它划分成三部分，注意这里下标从 1 开始：

• 1 ~ 2^(i - 1) - 1 即 s[i - 1]，如果 k 在左半边，问题变为 s[i - 1] 的第 k 个字符
• 2^(i - 1) 值是 1，直接返回
• 2^(i - 1) + 1 ~ 2^i - 1 即 invertAndReverse(s[i - 1])，如果 k 在右半边，问题变为 invertAndReverse(s[i - 1]) 的第 k - 2^(i - 1) 个字符，也是 invert(s[i - 1]) 的第 2^(i - 1) - k + 2^(i - 1) = 2^i - k 个字符。

代码

/**
 * @date 2026-03-03 14:13
 */
public class FindKthBit1545 {

    public char findKthBit(int n, int k) {
        StringBuilder[] s = new StringBuilder[n];
        Arrays.setAll(s, x -> new StringBuilder());
        s[0].append('0');
        for (int i = 1; i < n; i++) {
            s[i].append(s[i - 1]).append('1').append(invertAndReverse(s[i - 1]));
        }
        return s[n - 1].charAt(k - 1);
    }

    public StringBuilder invertAndReverse(StringBuilder origin) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < origin.length(); i++) {
            if (origin.charAt(i) == '0') {
                res.append('1');
            } else {
                res.append('0');
            }
        }
        return res.reverse();
    }

}

性能