shelterofly

目标

给你两个整数：num1 和 num2 。

在一步操作中，你需要从范围 [0, 60] 中选出一个整数 i ，并从 num1 减去 2^i + num2 。

请你计算，要想使 num1 等于 0 需要执行的最少操作数，并以整数形式返回。

如果无法使 num1 等于 0 ，返回 -1 。

示例 1：

输入：num1 = 3, num2 = -2
输出：3
解释：可以执行下述步骤使 3 等于 0 ：
- 选择 i = 2 ，并从 3 减去 2^2 + (-2) ，num1 = 3 - (4 + (-2)) = 1 。
- 选择 i = 2 ，并从 1 减去 2^2 + (-2) ，num1 = 1 - (4 + (-2)) = -1 。
- 选择 i = 0 ，并从 -1 减去 2^0 + (-2) ，num1 = (-1) - (1 + (-2)) = 0 。
可以证明 3 是需要执行的最少操作数。

示例 2：

输入：num1 = 5, num2 = 7
输出：-1
解释：可以证明，执行操作无法使 5 等于 0 。

说明：

• 1 <= num1 <= 10^9
• -10^9 <= num2 <= 10^9

思路

已知整数 num1 和 num2，每次操作需要从 0 ~ 60 选一个整数 i，并将 num1 -= 2^i + num2，返回将 num1 变为 0 的最小操作次数，如果无法完成返回 -1。

假设最少需要操作 k 次，那么 num1 - k * num2 = 2^i1 + 2^i2 + …… + 2^ik，其中 ik 表示第 k 次选择的 i。

问题转换为 num1 - k * num2 能否用 k 个 2 的幂表示。

二进制中 1 的个数就是最少的 k 的个数，它自身的值就是最多可以拆分的个数 ，也就是说 num = num1 - k * num2 的二进制表示中 1 的个数应小于等于 k 并且 num >= k。

代码

/**
 * @date 2025-09-05 8:46
 */
public class MakeTheIntegerZero2749 {

    public int makeTheIntegerZero(int num1, int num2) {
        for (int i = 0; i < 61; i++) {
            long num = num1 - (long) i * num2;
            if (num <= 0) {
                return -1;
            } else if (Long.bitCount(num) <= i && num >= i) {
                return i;
            }
        }
        return -1;
    }

}

性能

目标

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。

给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。

一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10^-5 以内的结果都会视为正确结果。

示例 1：

输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2
输出：0.78333
解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。

示例 2：

输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出：0.53485

说明：

• 1 <= classes.length <= 10^5
• classes[i].length == 2
• 1 <= passi <= totali <= 10^5
• 1 <= extraStudents <= 10^5

思路

有一个二维数组 classes， classes[i][0] 表示班级 i 期末考试中通过考试的人数，classes[i][1] 表示班级 i 的总人数。有 extraStudents 个聪明学生一定可以通过期末考试，现在需要将这些学生分配到班级中去，使得班级通过率的平均值最大。返回最大平均通过率。

为了使平均值更大，可以优先将聪明学生安排到通过率提升最大的班级，使用优先队列。

代码

/**
 * @date 2025-09-01 21:21
 */
public class MaxAverageRatio1792 {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> (int) (((b[1] - b[0]) * (long) a[1] * (a[1] + 1) - (a[1] - a[0]) * (long) b[1] * (b[1] + 1)) % 1000000007));
        for (int[] item : classes) {
            q.offer(item);
        }
        for (int i = 0; i < extraStudents; i++) {
            int[] peek = q.poll();
            peek[0]++;
            peek[1]++;
            q.offer(peek);
        }
        double res = 0.0;
        for (int[] item : classes) {
            res += (double) item[0] / item[1];
        }
        return res / classes.length;
    }

}

性能

目标

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 空白格用 '.' 表示。

示例 1：

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

示例 2：

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字（1-9）或者 '.'

思路

依题意模拟即可。

代码

/**
 * @date 2025-01-19 20:00
 */
public class IsValidSudoku36 {

    public boolean isValidSudoku(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            boolean[] exists = new boolean[10];
            for (int j = 0; j < n; j++) {
                char c = board[i][j];
                if ('.' == c) {
                    continue;
                }
                if (exists[c - '0']) {
                    return false;
                }
                exists[c - '0'] = true;
            }
        }
        for (int j = 0; j < n; j++) {
            boolean[] exists = new boolean[10];
            for (int i = 0; i < m; i++) {
                char c = board[i][j];
                if ('.' == c) {
                    continue;
                }
                if (exists[c - '0']) {
                    return false;
                }
                exists[c - '0'] = true;
            }
        }
        boolean[] exists = null;
        for (int j = 0; j < n; j += 3) {
            for (int i = 0; i < m; i++) {
                if (i % 3 == 0) {
                    exists = new boolean[10];
                }
                for (int k = j; k < j + 3; k++) {
                    char c = board[i][k];
                    if ('.' == c) {
                        continue;
                    }
                    if (exists[c - '0']) {
                        return false;
                    }
                    exists[c - '0'] = true;
                }
            }
        }
        return true;
    }

}

性能

目标

给你一个大小为 n x n 的整数方阵 grid。返回一个经过如下调整的矩阵：

• 左下角三角形（包括中间对角线）的对角线按 非递增顺序 排序。
• 右上角三角形 的对角线按 非递减顺序 排序。

示例 1：

输入： grid = [[1,7,3],[9,8,2],[4,5,6]]
输出： [[8,2,3],[9,6,7],[4,5,1]]
解释：
标有黑色箭头的对角线（左下角三角形）应按非递增顺序排序：
[1, 8, 6] 变为 [8, 6, 1]。
[9, 5] 和 [4] 保持不变。
标有蓝色箭头的对角线（右上角三角形）应按非递减顺序排序：
[7, 2] 变为 [2, 7]。
[3] 保持不变。

示例 2：

输入： grid = [[0,1],[1,2]]
输出： [[2,1],[1,0]]
解释：
标有黑色箭头的对角线必须按非递增顺序排序，因此 [0, 2] 变为 [2, 0]。其他对角线已经符合要求。

示例 3：

输入： grid = [[1]]
输出： [[1]]
解释：
只有一个元素的对角线已经符合要求，因此无需修改。

说明：

• grid.length == grid[i].length == n
• 1 <= n <= 10
• -10^5 <= grid[i][j] <= 10^5

思路

参考 498.对角线遍历

代码

/**
 * @date 2025-08-28 8:57
 */
public class SortMatrix3446 {

    public int[][] sortMatrix(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int k = m + n - 1;
        for (int l = 1; l < n; l++) {
            int maxJ = Math.min(m + n - l - 1, n - 1);
            int minJ = Math.max(0, n - l);
            List<Integer> list = new ArrayList<>();
            for (int j = minJ; j <= maxJ; j++) {
                int i = j + l - n;
                list.add(grid[i][j]);
            }
            list.sort(null);
            int p = 0;
            for (int j = minJ; j <= maxJ; j++) {
                int i = j + l - n;
                grid[i][j] = list.get(p++);
            }
        }
        for (int l = n; l <= k; l++) {
            int maxJ = Math.min(m + n - l - 1, n - 1);
            int minJ = Math.max(0, n - l);
            List<Integer> list = new ArrayList<>();
            for (int j = minJ; j <= maxJ; j++) {
                int i = j + l - n;
                list.add(grid[i][j]);
            }
            list.sort(Collections.reverseOrder());
            int p = 0;
            for (int j = minJ; j <= maxJ; j++) {
                int i = j + l - n;
                grid[i][j] = list.get(p++);
            }
        }
        return grid;
    }
}

性能