标签： 数学

目标

3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。

给定一个由整数组成的row x col 的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？

注意：虽然幻方只能包含 1 到 9 的数字，但 grid 可以包含最多15的数字。

示例 1：

输入: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]

输出: 1

解释:

下面的子矩阵是一个 3 x 3 的幻方：

而这一个不是：

总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。

示例 2:

输入: grid = [[8]]
输出: 0

说明:

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 10
• 0 <= grid[i][j] <= 15

思路

判断给定矩阵中幻方的数量，幻方是一个九宫格，元素为 1 ~ 9 且行/列/对角线的元素和相等。

如果数字是 1 ~ 9，所有元素和为 45，幻方和为 sum / 3 = 15。将过中心的四条线相加，刚好等于 sum + 3 * center = 4 * 15 = 60，求得 center = 5。

使用 mask 记录出现过的数字，全部出现的二进制表示为 1111111110，即 2^10 - 1 - 1。

在保证数字是 1 ~ 9 的前提下，如果判断了前两行满足条件，则无需判断最后一行，同理，如果判断了前两列满足条件，无需判断最后一列。因为总和是 45，剩余的行/列和等于 45 - 30 = 15。在此基础上，对角线也无需判断，由于中间元素是 5，对角和一定是 10。

a b c
d e f
g h i

由于行/列和为 15，那么 b + h = d + f = 10。1 ~ 9 范围内和为 10 的组合只有四种 1 9，2 8，3 7，4 6。剩余四个位置 a c g i，如果对角和不等于 10，有 a + c 或 a + g 等于 10，但是 b 与 d 不可能为 5，矛盾。而如果 a i 和为 10，剩余的 c g 和也为 10。

代码

/**
 * @date 2025-12-30 9:10
 */
public class NumMagicSquaresInside840 {

    public int numMagicSquaresInside(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        if (m < 3 || n < 3) {
            return 0;
        }
        int res = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (check(grid, i, j)) {
                    res++;
                }
            }
        }
        return res;
    }

    public boolean check(int[][] grid, int i, int j) {
        if (grid[i][j] != 5) {
            return false;
        }
        int[] rowSum = new int[3];
        int[] colSum = new int[3];
        int mask = 0;
        int r = 0;
        for (int row = i - 1; row <= i + 1; row++) {
            int c = 0;
            for (int col = j - 1; col <= j + 1; col++) {
                rowSum[r] += grid[row][col];
                colSum[c++] += grid[row][col];
                mask |= 1 << grid[row][col];
            }
            r++;
        }
        return rowSum[0] == 15 && rowSum[1] == 15 && colSum[0] == 15 && colSum[1] == 15 && mask == (1 << 10) - 2;
    }

}

性能

目标

给你一个二维整数数组 points，其中 points[i] = [xi, yi] 表示第 i 个点在笛卡尔平面上的坐标。

水平梯形 是一种凸四边形，具有 至少一对 水平边（即平行于 x 轴的边）。两条直线平行当且仅当它们的斜率相同。

返回可以从 points 中任意选择四个不同点组成的 水平梯形 数量。

由于答案可能非常大，请返回结果对 10^9 + 7 取余数后的值。

示例 1：

输入： points = [[1,0],[2,0],[3,0],[2,2],[3,2]]
输出： 3
解释：
有三种不同方式选择四个点组成一个水平梯形：
使用点 [1,0]、[2,0]、[3,2] 和 [2,2]。
使用点 [2,0]、[3,0]、[3,2] 和 [2,2]。
使用点 [1,0]、[3,0]、[3,2] 和 [2,2]。

示例 2：

输入： points = [[0,0],[1,0],[0,1],[2,1]]
输出： 1
解释：
只有一种方式可以组成一个水平梯形。

说明：

• 4 <= points.length <= 10^5
• –10^8 <= xi, yi <= 10^8
• 所有点两两不同。

思路

有一些二维平面中的点 points，从中选取四个点组成水平梯形，返回水平梯形的数目。

水平梯形是有一对边平行于 x 轴的梯形。直接的想法是根据纵坐标分组，选两组，每组中选两个点。

可以直接计算每组的组合数 C(n, 2) = n * (n - 1) / 2，计算分组组合数的后缀和，根据乘法原理计算即可。

代码

/**
 * @date 2025-12-02 0:14
 */
public class CountTrapezoids2623 {

    /**
     * 执行通过
     */
    public int countTrapezoids(int[][] points) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int[] point : points) {
            cnt.merge(point[1], 1, Integer::sum);
        }
        int mod = 1000000007;
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
            Integer c = entry.getValue();
            cnt.put(entry.getKey(), (int) ((c * (c - 1L) / 2) % mod));
        }
        int[] comb = cnt.values().stream().mapToInt(x -> x).toArray();
        int n = comb.length;
        int[] suffix = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = (suffix[i + 1] + comb[i]) % mod;
        }
        long res = 0L;
        for (int i = 0; i < n; i++) {
            res = (res + ((long) comb[i] * suffix[i + 1])) % mod;
        }
        return (int) res;
    }
}

性能

目标

给定正整数 k ，你需要找出可以被 k 整除的、仅包含数字 1 的最 小 正整数 n 的长度。

返回 n 的长度。如果不存在这样的 n ，就返回-1。

注意： n 可能不符合 64 位带符号整数。

示例 1：

输入：k = 1
输出：1
解释：最小的答案是 n = 1，其长度为 1。

示例 2：

输入：k = 2
输出：-1
解释：不存在可被 2 整除的正整数 n 。

示例 3：

输入：k = 3
输出：3
解释：最小的答案是 n = 111，其长度为 3。

说明：

• 1 <= k <= 10^5

思路

求仅包含数字 1 且能够整除正整数 k 的数字的最小长度，如不存在返回 -1。

通俗讲就是多长的 11111…… 能够整除 k。为了防止溢出可以只考虑余数，关键是停止条件是什么？如何确定是否存在？

如果余数出现重复，由于计算的式子不变，后续会陷入循环。可以使用哈希表记录出现过的余数。或者循环 k 次，由于余数的范围只可能是 0 ~ k - 1 共 k 个，如果循环 k 次还没有使余数为 0，那么根据鸽巢原理一定存在重复的余数。

代码

/**
 * @date 2025-11-25 9:26
 */
public class SmallestRepunitDivByK1015 {

    public int smallestRepunitDivByK(int k) {
        if (k == 1) {
            return 1;
        }
        int res = 1;
        int num = 1;
        while (res < k) {
            num = (num * 10 + 1) % k;
            res++;
            if (num == 0) {
                return res;
            }
        }
        return -1;
    }
}

性能