标签： 数学

目标

给你一个以二进制形式表示的数字 s 。请你返回按下述规则将其减少到 1 所需要的步骤数：

如果当前数字为偶数，则将其除以 2 。

如果当前数字为奇数，则将其加上 1 。

题目保证你总是可以按上述规则将测试用例变为 1 。

示例 1：

输入：s = "1101"
输出：6
解释："1101" 表示十进制数 13 。
Step 1) 13 是奇数，加 1 得到 14 
Step 2) 14 是偶数，除 2 得到 7
Step 3) 7  是奇数，加 1 得到 8
Step 4) 8  是偶数，除 2 得到 4  
Step 5) 4  是偶数，除 2 得到 2 
Step 6) 2  是偶数，除 2 得到 1  

示例 2：

输入：s = "10"
输出：1
解释："10" 表示十进制数 2 。
Step 1) 2 是偶数，除 2 得到 1 

示例 3：

输入：s = "1"
输出：0

说明：

• 1 <= s.length <= 500
• s 由字符 '0' 或 '1' 组成。
• s[0] == '1'

思路

有一个二进制表示的数字，如果当前是偶数，可以将数字除以 2，即右移；如果当前是奇数，将数字加 1。求将数字变为 1 需要的操作数。

根据题意模拟，使用变量 carry 保存进位，从右向左遍历，判断最后一位数字 d 与 carry 相加后的奇偶性，即 sum = d + carry。如果 sum 是偶数（0 或者 2），右移后这一位消失，只需考虑 carry = sum / 2；如果 sum 是奇数，加一后进位 carry = 1，此时当前数字变为偶数，可以将这两个操作合并。

代码

/**
 * @date 2026-02-26 8:51
 */
public class NumSteps1404 {

    public int numSteps(String s) {
        int res = 0;
        int n = s.length();
        char[] chars = s.toCharArray();
        int carry = 0;
        for (int i = n - 1; i > 0; i--) {
            int d = chars[i] - '0';
            int sum = d + carry;
            if (sum % 2 == 0) {
                carry = sum / 2;
                res++;
            } else {
                carry = 1;
                res += 2;
            }
        }
        return res + carry;
    }

}

性能

目标

在二维平面上存在 n 个矩形。给你两个下标从 0 开始的二维整数数组 bottomLeft 和 topRight，两个数组的大小都是 n x 2 ，其中 bottomLeft[i] 和 topRight[i] 分别代表第 i 个矩形的 左下角 和 右上角 坐标。

我们定义 向右 的方向为 x 轴正半轴（x 坐标增加），向左 的方向为 x 轴负半轴（x 坐标减少）。同样地，定义 向上 的方向为 y 轴正半轴（y 坐标增加），向下 的方向为 y 轴负半轴（y 坐标减少）。

你可以选择一个区域，该区域由两个矩形的 交集 形成。你需要找出能够放入该区域 内 的 最大 正方形面积，并选择最优解。

返回能够放入交集区域的正方形的 最大 可能面积，如果矩形之间不存在任何交集区域，则返回 0。

示例 1：

输入：bottomLeft = [[1,1],[2,2],[3,1]], topRight = [[3,3],[4,4],[6,6]]
输出：1
解释：边长为 1 的正方形可以放入矩形 0 和矩形 1 的交集区域，或矩形 1 和矩形 2 的交集区域。因此最大面积是边长 * 边长，即 1 * 1 = 1。
可以证明，边长更大的正方形无法放入任何交集区域。

示例 2：

输入：bottomLeft = [[1,1],[2,2],[1,2]], topRight = [[3,3],[4,4],[3,4]]
输出：1
解释：边长为 1 的正方形可以放入矩形 0 和矩形 1，矩形 1 和矩形 2，或所有三个矩形的交集区域。因此最大面积是边长 * 边长，即 1 * 1 = 1。
可以证明，边长更大的正方形无法放入任何交集区域。
请注意，区域可以由多于两个矩形的交集构成。

示例 3：

输入：bottomLeft = [[1,1],[3,3],[3,1]], topRight = [[2,2],[4,4],[4,2]]
输出：0
解释：不存在相交的矩形，因此，返回 0 。

说明：

• n == bottomLeft.length == topRight.length
• 2 <= n <= 10^3
• bottomLeft[i].length == topRight[i].length == 2
• 1 <= bottomLeft[i][0], bottomLeft[i][1] <= 10^7
• 1 <= topRight[i][0], topRight[i][1] <= 10^7
• bottomLeft[i][0] < topRight[i][0]
• bottomLeft[i][1] < topRight[i][1]

思路

二维平面上有一些矩形，第 i 个矩形的左下坐标为 bottomLeft[i]，右上坐标为 topRight[i]，求其中任意两个矩形交集区域的最大正方形面积。

针对每一个矩形，枚举其它矩形，计算交集区域最大的正方形边长。

令 bl1 表示矩形 1 的左下坐标，tr1 表示矩形 1 的右上坐标，bl2、tr2 同理。

• 相交区域的垂直边长为 Math.min(tr1[1], tr2[1]) - Math.max(bl1[1], bl2[1])
• 相交区域的水平边长为 Math.min(tr1[0], tr2[0]) - Math.max(bl1[0], bl2[0])

代码

/**
 * @date 2026-01-21 9:08
 */
public class LargestSquareArea3047 {

    public long largestSquareArea_v1(int[][] bottomLeft, int[][] topRight) {
        long res = 0L;
        int n = bottomLeft.length;
        for (int i = 0; i < n; i++) {
            int[] bl1 = bottomLeft[i], tr1 = topRight[i];
            for (int j = i + 1; j < n; j++) {
                int[] bl2 = bottomLeft[j], tr2 = topRight[j];
                res = Math.max(res, Math.min(Math.min(tr1[1], tr2[1]) - Math.max(bl1[1], bl2[1]), Math.min(tr1[0], tr2[0]) - Math.max(bl1[0], bl2[0])));
            }
        }
        return res * res;
    }

}

性能

目标

给你一个整数数组 nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。如果数组中不存在满足题意的整数，则返回 0 。

示例 1：

输入：nums = [21,4,7]
输出：32
解释：
21 有 4 个因数：1, 3, 7, 21
4 有 3 个因数：1, 2, 4
7 有 2 个因数：1, 7
答案仅为 21 的所有因数的和。

示例 2:

输入: nums = [21,21]
输出: 64

示例 3:

输入: nums = [1,2,3,4,5]
输出: 0

说明：

• 1 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^5

思路

有一个整数数组 nums，返回恰好有 4 个因数的元素的这些因数之和，如果不存在，返回 0。

首先数组元素至少有两个因数（1 和它本身），只需要再找到两个因数即可。从 2 ~ sqrt(num) 判断能否整除 num，如果可以加上 i 与 num / i，需要特殊处理 i * i = num 的情况，这时因数只能算一个。

代码

/**
 * @date 2026-01-04 9:05
 */
public class SumFourDivisors1390 {

    public int sumFourDivisors(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res += sum(num);
        }
        return res;
    }

    public int sum(int num) {
        int cnt = 2;
        int sum = num + 1;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                if (cnt == 4) {
                    sum = 0;
                    break;
                }
                if (i * i == num) {
                    sum += i;
                    cnt++;
                } else {
                    sum += i + num / i;
                    cnt += 2;
                }

            }
        }
        return cnt == 4 ? sum : 0;
    }

}

性能

目标

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;
    }

}

性能