数学 – shelterofly

目标

给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 1：

输入：nums = [1,2,3]
输出：6

示例 2：

输入：nums = [1,2,3,4]
输出：24

示例 3：

输入：nums = [-1,-2,-3]
输出：-6

说明：

3 <= nums.length <= 10^4
-1000 <= nums[i] <= 1000

思路

从数组中取三个不同的下标，返回其乘积的最大值。

由于存在负数，分情况讨论，定义 max1、max2、max3 分别为前三大元素，min1、min2 分别是前二小元素：

如果 max1 < 0, 乘积只能为负，要使乘积最大，那么其绝对值应该最小，因此取 max1 * max2 * max3
如果 max2 < 0, 最大乘积可以为正，取最小的两个负数相乘，乘积最大，取 max1 * min1 * min2
如果 max3 < 0，乘积可能为正也可能为负（只有三个元素），不论那种情况，都可取 max1 * min1 * min2
如果 max3 > 0, 最大值可能是 max1 * max2 * max3 或者 max1 * min1 * min2

代码


/**
 * @date 2026-07-27 16:37
 */
public class MaximumProduct628 {

    public int maximumProduct_v1(int[] nums) {
        int max1 = -1001, max2 = -1001, max3 = -1001;
        int min1 = 1001, min2 = 1001;
        for (int num : nums) {
            if (num > max1) {
                max3 = max2;
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max3 = max2;
                max2 = num;
            } else if (num > max3) {
                max3 = num;
            }
            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
        }
        return Math.max(max1 * max2 * max3, max1 * min1 * min2);
    }

}

性能

目标

给定一个正整数 n。

返回任意两位数字相乘所得的最大乘积。

注意：如果某个数字在 n 中出现多次，你可以多次使用该数字。

示例 1：

输入： n = 31
输出： 3
解释：
n 的数字是 [3, 1]。
任意两位数字相乘的结果为：3 * 1 = 3。
最大乘积为 3。

示例 2：

输入： n = 22
输出： 4
解释：
n 的数字是 [2, 2]。
任意两位数字相乘的结果为：2 * 2 = 4。
最大乘积为 4。

示例 3：

输入： n = 124
输出： 8
解释：
n 的数字是 [1, 2, 4]。
任意两位数字相乘的结果为：1 * 2 = 2, 1 * 4 = 4, 2 * 4 = 8。
最大乘积为 8。

说明：

10 <= n <= 10^9

思路

给定一个数字 n，选择数位中的两个数字相乘，返回乘积的最大值。

找到最大的两个数字相乘即可。

代码


/**
 * @date 2026-07-27 14:22
 */
public class MaxProduct3536 {

    public int maxProduct(int n) {
        int max = 0;
        int preMax = 0;
        int res = 0;
        while (n > 0) {
            int d = n % 10;
            if (d >= preMax) {
                preMax = Math.min(max, d);
                max = Math.max(max, d);
                res = Math.max(res, max * preMax);
            }
            n /= 10;
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums 。

XOR 三元组定义为三个元素的异或值 nums[i] XOR nums[j] XOR nums[k]，其中 i <= j <= k。

返回所有可能三元组 (i, j, k) 中不同的 XOR 值的数量。

示例 1：

输入： nums = [1,3]
输出： 2
解释：
所有可能的 XOR 三元组值为：
(0, 0, 0) → 1 XOR 1 XOR 1 = 1
(0, 0, 1) → 1 XOR 1 XOR 3 = 3
(0, 1, 1) → 1 XOR 3 XOR 3 = 1
(1, 1, 1) → 3 XOR 3 XOR 3 = 3
不同的 XOR 值为 {1, 3} 。因此输出为 2 。

示例 2：

输入： nums = [6,7,8,9]
输出： 4
解释：
不同的 XOR 值为 {6, 7, 8, 9} 。因此输出为 4 。

说明：

1 <= nums.length <= 1500
1 <= nums[i] <= 1500

思路

有一个正整数数组 nums，从中取三个数（可重复）的异或值 XOR，求不同的 XOR 值有多少个。

暴力枚举。

代码


/**
 * @date 2026-07-24 9:12
 */
public class UniqueXorTriplets3514 {

    public int uniqueXorTriplets(int[] nums) {
        int n = nums.length;
        int max = 0;
        for (int num : nums) {
            max = Math.max(max, num);
        }
        int upper = 1 << (32 - Integer.numberOfLeadingZeros(max));
        boolean[] tmp = new boolean[upper];
        boolean[] arr = new boolean[upper];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                tmp[nums[i] ^ nums[j]] = true;
            }
        }
        for (int i = 0; i < upper; i++) {
            if (tmp[i]) {
                for (int num : nums) {
                    arr[num ^ i] = true;
                }
            }
        }
        int res = 0;
        for (boolean b : arr) {
            if (b) {
                res++;
            }
        }
        return res;
    }

}

性能

目标

给你一个长度为 n 的整数数组 nums，其中 nums 是范围 [1, n] 内所有数的排列。

XOR 三元组定义为三个元素的异或值 nums[i] XOR nums[j] XOR nums[k]，其中 i <= j <= k。

返回所有可能三元组 (i, j, k) 中不同的 XOR 值的数量。

排列是一个集合中所有元素的重新排列。

示例 1：

输入： nums = [1,2]
输出： 2
解释：
所有可能的 XOR 三元组值为：
(0, 0, 0) → 1 XOR 1 XOR 1 = 1
(0, 0, 1) → 1 XOR 1 XOR 2 = 2
(0, 1, 1) → 1 XOR 2 XOR 2 = 1
(1, 1, 1) → 2 XOR 2 XOR 2 = 2
不同的 XOR 值为 {1, 2}，因此输出为 2。

示例 2：

输入： nums = [3,1,2]
输出： 4
解释：
可能的 XOR 三元组值包括：
(0, 0, 0) → 3 XOR 3 XOR 3 = 3
(0, 0, 1) → 3 XOR 3 XOR 1 = 1
(0, 0, 2) → 3 XOR 3 XOR 2 = 2
(0, 1, 2) → 3 XOR 1 XOR 2 = 0
不同的 XOR 值为 {0, 1, 2, 3}，因此输出为 4。

说明：

1 <= n == nums.length <= 10^5
1 <= nums[i] <= n
nums 是从 1 到 n 的整数的一个排列。

思路

有一个 1 ~ n 的排列，从中取三个数（可重复）的异或值 XOR，求不同的 XOR 值有多少个。

可以构造出 0 ~ 2^(k + 1) - 1 之间的任意数字，其中 k 是从右向左的最高位（从 0 开始）。

代码


/**
 * @date 2026-07-23 9:55
 */
public class UniqueXorTriplets3513 {

    public int uniqueXorTriplets(int[] nums) {
        int n = nums.length;
        return n <= 2 ? n : 1 << (32 - Integer.numberOfLeadingZeros(n));
    }
}

性能

目标

给你一个整数 n。请你计算以下两个值的最大公约数（GCD）：

sumOdd：最小的 n 个正奇数的总和。

sumEven：最小的 n 个正偶数的总和。

返回 sumOdd 和 sumEven 的 GCD。

示例 1：

输入： n = 4
输出： 4
解释：
前 4 个奇数的总和 sumOdd = 1 + 3 + 5 + 7 = 16
前 4 个偶数的总和 sumEven = 2 + 4 + 6 + 8 = 20
因此，GCD(sumOdd, sumEven) = GCD(16, 20) = 4。

示例 2：

输入： n = 5
输出： 5
解释：
前 5 个奇数的总和 sumOdd = 1 + 3 + 5 + 7 + 9 = 25
前 5 个偶数的总和 sumEven = 2 + 4 + 6 + 8 + 10 = 30
因此，GCD(sumOdd, sumEven) = GCD(25, 30) = 5。

提示：

1 <= n <= 1000

思路

计算最小的 n 个正奇数的和与最小的 n 个正偶数和的最大公约数。

(1 + 3 + 5 + …… + 2n - 1) = 2n * n / 2 = n^2
(2 + 4 + 6 + …… + 2n) = (2n + 2) * n / 2 = n * (n + 1)

最大公约数为 n。

代码


/**
 * @date 2026-07-15 8:51
 */
public class GcdOfOddEvenSums3658 {

    public int gcdOfOddEvenSums(int n) {
        int oddSum = 0;
        int evenSum = 0;
        for (int k = 0, i = 1, j = 2; k < n; i += 2, j += 2, k++) {
            oddSum += i;
            evenSum += j;
        }
        return gcd(oddSum, evenSum);
    }

    public int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

}

性能

目标

给你一个整数 n 。现有一个包含 n 个顶点的无向图，顶点按从 0 到 n - 1 编号。给你一个二维整数数组 edges 其中 edges[i] = [ai, bi] 表示顶点 ai 和 bi 之间存在一条无向边。

返回图中完全连通分量的数量。

如果在子图中任意两个顶点之间都存在路径，并且子图中没有任何一个顶点与子图外部的顶点共享边，则称其为连通分量。

如果连通分量中每对节点之间都存在一条边，则称其为完全连通分量。

示例 1：

输入：n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]
输出：3
解释：如上图所示，可以看到此图所有分量都是完全连通分量。

示例 2：

输入：n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]
输出：1
解释：包含节点 0、1 和 2 的分量是完全连通分量，因为每对节点之间都存在一条边。
包含节点 3 、4 和 5 的分量不是完全连通分量，因为节点 4 和 5 之间不存在边。
因此，在图中完全连接分量的数量是 1 。

说明：

1 <= n <= 50
0 <= edges.length <= n * (n - 1) / 2
edges[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
不存在重复的边

思路

求无向图中完全连通分量的个数。完全连通分量指连通分量中任意两个节点之间都有一条边。

暴力解法是使用并查集维护连通分量，找出同一连通分量内的节点，判断两两之间是否有边。

优化点：可以利用节点与边的关系来判断是否是完全连通分量，节点 v 与边 e 的关系为：e = C(v, 2) = v * (v - 1) / 2。

代码


/**
 * @date 2026-07-14 11:27
 */
public class CountCompleteComponents2685 {

    private class UnionFind {

        private final int[] fa;

        public UnionFind(int n) {
            fa = new int[n];
            Arrays.setAll(fa, i -> i);
        }

        public int find(int e) {
            if (e != fa[e]) {
                fa[e] = find(fa[e]);
            }
            return fa[e];
        }

        public void union(int a, int b) {
            int x = find(a);
            int y = find(b);
            if (x > y) {
                fa[x] = y;
            } else {
                fa[y] = x;
            }
        }

        public int getCompleteComponents(Set<Integer>[] g) {
            int n = fa.length;
            int res = 0;
            Set<Integer> visited = new HashSet<>();
            for (int i = 0; i < n; i++) {
                if (visited.contains(i)) {
                    continue;
                }
                visited.add(i);
                List<Integer> list = new ArrayList<>();
                for (int j = 0; j < n; j++) {
                    if (find(j) == find(i)) {
                        visited.add(j);
                        list.add(j);
                    }
                }
                int size = list.size();
                boolean flag = true;
                here:
                for (int p = 0; p < size; p++) {
                    for (int q = p + 1; q < size; q++) {
                        if (!g[list.get(p)].contains(list.get(q))) {
                            flag = false;
                            break here;
                        }
                    }
                }
                if (flag) {
                    res++;
                }
            }
            return res;
        }
    }

    public int countCompleteComponents(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        Set<Integer>[] g = new HashSet[n];
        Arrays.setAll(g, x -> new HashSet<>());
        for (int[] edge : edges) {
            int a = edge[0];
            int b = edge[1];
            uf.union(a, b);
            g[a].add(b);
            g[b].add(a);
        }
        return uf.getCompleteComponents(g);
    }

}

性能

目标

给你一个长度为 m 的字符串 s，其中仅包含数字。另给你一个二维整数数组 queries，其中 queries[i] = [li, ri]。

对于每个 queries[i]，提取子串 s[li..ri]，然后执行以下操作：

将子串中所有非零数字按照原始顺序连接起来，形成一个新的整数 x。如果没有非零数字，则 x = 0。
令 sum 为 x 中所有数字的数字和。答案为 x * sum。

返回一个整数数组 answer，其中 answer[i] 是第 i 个查询的答案。

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

子串是字符串中的一个连续、非空字符序列。

示例 1：

输入： s = "10203004", queries = [[0,7],[1,3],[4,6]]
输出： [12340, 4, 9]
解释：
s[0..7] = "10203004"
    x = 1234
    sum = 1 + 2 + 3 + 4 = 10
    因此，答案是 1234 * 10 = 12340。
s[1..3] = "020"
    x = 2
    sum = 2
    因此，答案是 2 * 2 = 4。
s[4..6] = "300"
    x = 3
    sum = 3
    因此，答案是 3 * 3 = 9。

示例 2：

输入： s = "1000", queries = [[0,3],[1,1]]
输出： [1, 0]
解释：
s[0..3] = "1000"
    x = 1
    sum = 1
    因此，答案是 1 * 1 = 1。
s[1..1] = "0"
    x = 0
    sum = 0
    因此，答案是 0 * 0 = 0。

示例 3：

输入： s = "9876543210", queries = [[0,9]]
输出： [444444137]
解释：
s[0..9] = "9876543210"
    x = 987654321
    sum = 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45
    因此，答案是 987654321 * 45 = 44444444445。
    返回结果为 44444444445 mod (10^9 + 7) = 444444137。

说明：

1 <= m == s.length <= 10^5
s 仅由数字组成。
1 <= queries.length <= 10^5
queries[i] = [li, ri]
0 <= li <= ri < m

思路

有一个数字字符串 s，针对每一个子串 s[queries[i][0], queries[i][1]]，返回其非零数字所表示的数字乘以每位数字之和对 1000000007 取余的结果。

与 3754.连接非零数字并乘以其数字和I 相比，本题的数字是由 queries 给出的子串，需要返回每一个子串的结果。

数位和可以使用前缀和快速计算。子串非零数字所表示的数字也可以通过前缀计算。

区间 [l, r] 所表示的数字对 MOD 取模的值为 (prefixNum[r + 1] + MOD - prefixNum[l] * base[k] % MOD) % MOD，例如，1230456，[2, 4] 中的非零数字所表示的数字是 34，它等于 prefixNum[5]:1234 - prefixNum[2]:12 * 100，其中 100 = 10^k，k 表示 [l, r] 中非零数字的个数。

代码


/**
 * @date 2026-07-08 9:50
 */
public class SumAndMultiply3756 {

    public int[] sumAndMultiply(String s, int[][] queries) {
        int n = s.length();
        int[] prefix = new int[n + 1];
        int[] prefixLength = new int[n + 1];
        long[] prefixNum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            int d = s.charAt(i) - '0';
            prefix[i + 1] = prefix[i] + d;
            prefixLength[i + 1] = prefixLength[i] + (d != 0 ? 1 : 0);
            prefixNum[i + 1] = (prefixNum[i] * (d != 0 ? 10 : 1) + d) % MOD;
        }
        int ql = queries.length;
        int[] res = new int[ql];
        for (int i = 0; i < ql; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            int sum = prefix[r + 1] - prefix[l];
            long x = (prefixNum[r + 1] + MOD - prefixNum[l] * base[prefixLength[r + 1] - prefixLength[l]] % MOD) % MOD;
            res[i] = (int) (x * sum % MOD);
        }
        return res;
    }

}

性能

3754.连接非零数字并乘以其数字和I

目标

给你一个整数 n。

将 n 中所有的非零数字按照它们的原始顺序连接起来，形成一个新的整数 x。如果不存在非零数字，则 x = 0。

sum 为 x 中所有数字的数字和。

返回一个整数，表示 x * sum 的值。

示例 1：

输入： n = 10203004
输出： 12340
解释：
非零数字是 1、2、3 和 4。因此，x = 1234。
数字和为 sum = 1 + 2 + 3 + 4 = 10。
因此，答案是 x * sum = 1234 * 10 = 12340。

示例 2：

输入： n = 1000
输出： 1
解释：
非零数字是 1，因此 x = 1 且 sum = 1。
因此，答案是 x * sum = 1 * 1 = 1。

说明：

0 <= n <= 10^9

思路

计算整数 n 的所有非零数字之和记为 sum，去掉 n 中的 0 形成的新整数记为 x，返回 x * sum 的值。

依题意模拟即可。

代码


/**
 * @date 2026-07-07 9:13
 */
public class SumAndMultiply3754 {

    public long sumAndMultiply(int n) {
        long sum = 0;
        long x = 0;
        int base = 1;
        while (n > 0) {
            int rem = n % 10;
            sum += rem;
            x += rem * base;
            base *= rem == 0 ? 1 : 10;
            n /= 10;
        }
        return x * sum;
    }
}

性能

1344.时钟指针的夹角

目标

给你两个数 hour 和 minutes 。请你返回在时钟上，由给定时间的时针和分针组成的较小角的角度（60 单位制）。

示例 1：

输入：hour = 12, minutes = 30
输出：165

示例 2：

输入：hour = 3, minutes = 30
输出；75

示例 3：

输入：hour = 3, minutes = 15
输出：7.5

示例 4：

输入：hour = 4, minutes = 50
输出：155

示例 5：

输入：hour = 12, minutes = 0
输出：0

说明：

1 <= hour <= 12
0 <= minutes <= 59
与标准答案误差在 10^-5 以内的结果都被视为正确结果。

思路

计算时钟时针与分针的较小夹角。

问题的关键是时针转动的角度不能直接按 hour 来算，根据分针的指向有一定的偏移，偏移的角度是 minutes / 60 * 30，其中 30 是一个小时格子的角度。hour / 12 * 360 + minutes / 60 * 30 - minutes / 60 * 360 = 30 * hour - minutes * 5.5

代码


/**
 * @date 2026-06-18 9:17
 */
public class AngleClock1344 {

    public double angleClock(int hour, int minutes) {
        double res = Math.abs(30 * hour - minutes * 5.5);
        return Math.min(res, 360 - res);
    }
}

性能

3558.给边赋权值的方案数I

目标

给你一棵 n 个节点的无向树，节点从 1 到 n 编号，树以节点 1 为根。树由一个长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间有一条边。

一开始，所有边的权重为 0。你可以将每条边的权重设为 1 或 2。

两个节点 u 和 v 之间路径的代价是连接它们路径上所有边的权重之和。

选择任意一个深度最大的节点 x。返回从节点 1 到 x 的路径中，边权重之和为奇数的赋值方式数量。

由于答案可能很大，返回它对 10^9 + 7 取模的结果。

注意：忽略从节点 1 到节点 x 的路径外的所有边。

示例 1：

输入： edges = [[1,2]]
输出： 1
解释：
从节点 1 到节点 2 的路径有一条边（1 → 2）。
将该边赋权为 1 会使代价为奇数，赋权为 2 则为偶数。因此，合法的赋值方式有 1 种。

示例 2：

输入： edges = [[1,2],[1,3],[3,4],[3,5]]
输出： 2
解释：
最大深度为 2，节点 4 和节点 5 都在该深度，可以选择任意一个。
例如，从节点 1 到节点 4 的路径包括两条边（1 → 3 和 3 → 4）。
将两条边赋权为 (1,2) 或 (2,1) 会使代价为奇数，因此合法赋值方式有 2 种。

提示：

2 <= n <= 10^5
edges.length == n - 1
edges[i] == [ui, vi]
1 <= ui, vi <= n
edges 表示一棵合法的树。

思路

有一颗含有 n 个节点的树，编号为 1 ~ n，根节点编号是 1。edges[i] = [ui, vi]，表示节点 ui 与 vi 之间有一条边。定义节点 u 与 v 之间的代价为它们之间路径上边的权重之和。可以为每一条边赋予权重 1 或 2，求使得根节点到最远叶子节点代价为奇数的赋权方案数。

定义到达当前节点代价为奇数或偶数的方案数为 dp[i][1] 与 dp[i][0]，状态转移方程为 dp[i][0] = dp[prev][0] + dp[prev][1]，dp[i][1] = dp[prev][0] + dp[prev][1]。

观察发现 dp[i][0] == dp[i][1]，因此代价为奇数的方案数为 dp[i][1] = 2 * dp[prev][1]。假设树的深度为 d，方案数为 2^(d - 1)。

求出树的深度 d，从中选取奇数条边赋值为 1，方案数为 2^(d - 1)。

代码


/**
 * @date 2026-06-11 10:16
 */
public class AssignEdgeWeights3558 {

    public int assignEdgeWeights(int[][] edges) {
        int n = edges.length + 1;
        List<Integer>[] g = new ArrayList[n + 1];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] edge : edges) {
            g[edge[0]].add(edge[1]);
            g[edge[1]].add(edge[0]);
        }
        int d = dfs(0, 1, g);
        return pow(2, d - 1, 1000000007);
    }

    public int dfs(int fa, int cur, List<Integer>[] g) {
        int res = 0;
        for (Integer next : g[cur]) {
            if (next == fa) {
                continue;
            }
            res = Math.max(res, dfs(cur, next, g) + 1);
        }
        return res;
    }

    public int pow(int base, int exp, int mod) {
        long res = 1L;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                res = res * base % mod;
            }
            base = (int) ((long) base * base % mod);
            exp >>= 1;
        }
        return (int) res;
    }

}

2026 年 8 月
一	二	三	四	五	六	日
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31