Hugh's Space

Happy to share some knowledge

LeetCode

LeetCode Contest 459

By hughqiao

欢迎大家加QQ群：623375442。最后一道数学题，来回改不对。

3622. 检查是否能被数位和与数位积之和整除

题目描述
给定一个正整数 n。计算 n 的数位和（即各位数字之和）和数位积（即各位数字的乘积），判断 n 是否能被这两个值之和整除。

如果能整除，返回 true；否则，返回 false。

示例：

输入：n = 99
输出：true
解释：99 的数位和为 9 + 9 = 18，数位积为 9 * 9 = 81，二者之和为 99，99 能被 99 整除，故返回 true。

解题思路

  1. 遍历整数 n 的每一位，累加各位的和；同时，累乘各位的积。
  2. 计算数位和 sum 与数位积 prod 之和 sum + prod。
  3. 判断 n % (sum + prod) == 0 即可得答案。

该方法时间复杂度为 O(d)，d 为数字的位数，常数级别，非常高效。

class Solution {
    public boolean checkDivisibility(int n) {
        // 如果 n 能被 (cal1(n) + cal2(n)) 整除，则返回 true
        return n % (cal1(n) + cal2(n)) == 0;
    }

    // 计算数位和
    private int cal1(int n) {
        int res = 0;
        while (n > 0) {
            res += n % 10;  // 取出最低位累加
            n /= 10;        // 去掉最低位
        }
        return res;
    }

    // 计算数位积
    private int cal2(int n) {
        int res = 1;
        while (n > 0) {
            res *= n % 10;  // 取出最低位累乘
            n /= 10;        // 去掉最低位
        }
        return res;
    }
}

3623. 统计水平梯形的数量 I

题目描述
给定一个二维整型数组 points，其中 points[i] = [x_i, y_i] 表示平面上的第 i 个点。

一个水平梯形是指在凸四边形中，至少有一对水平边（即与 x 轴平行）的梯形。返回从这些点中任选四个不同点组成的不同水平梯形的数量。由于结果可能很大，返回结果对 10^9 + 7 取模。

示例：

输入：points = [[1,0],[2,0],[3,0],[2,2],[3,2]]
输出：3

解题思路

  • 水平梯形需要两条水平边，水平边由 y 坐标相同的点对组成。
  • 统计每个水平线（固定 y 值）上点的数量 cnt。
  • 对于每条新增水平边，其可以和之前所有其他水平边配对，形成梯形。
  • 使用哈希表 map 记录每条水平线已有的点数，totalPair 记录所有已形成的点对总数，levelPair[y] 记录在相同 y 线上的点对数。

  • 当遍历到一条新边时，当前水平线已产生的水平边数 old = map.get(y)，

    • 新形成的梯形数为 (totalPair - levelPair[y]) * old。
  • 最终结果对 mod 取模。
class Solution {
    private static final int mod = 1_000_000_007;

    public int countTrapezoids(int[][] points) {
        // map: 记录每个 y 值线上已有的点数
        HashMap<Integer, Integer> map = new HashMap<>();
        // levelPair: 记录每个 y 值线上已有的点对数量
        HashMap<Integer, Long> levelPair = new HashMap<>();
        long totalPair = 0;  // 记录所有水平线上的点对总数
        long res = 0;
        for (int[] p : points) {
            int y = p[1];
            int old = map.getOrDefault(y, 0);
            // 新增的梯形数 = (之前所有点对总数 - 同一水平线上的点对) * 当前水平线已有的点数
            res = (res + (totalPair - levelPair.getOrDefault(y, 0L)) * old) % mod;
            // 更新
            map.put(y, old + 1);
            totalPair += old;
            levelPair.put(y, levelPair.getOrDefault(y, 0L) + old);
        }
        return (int) res;
    }
}

3624. Popcount 深度为 K 的整数数量 II

题目描述
给定一个整数数组 nums 和一个查询数组 queries，其中每个查询是两种类型之一：

  1. [1, l, r, k]：统计在索引区间 [l, r] 内，popcount-depth 等于 k 的元素个数。
  2. [2, idx, val]：将 nums[idx] 更新为 val。

其中，对于正整数 x，定义序列：

p0 = x
pi+1 = popcount(pi)  // popcount(y) 为 y 的二进制表示中 1 的个数

该序列最终会到达 1，popcount-depth 定义为最小的 d 使得 pd = 1。

返回所有类型 1 查询的结果数组。

示例：

输入：nums = [2,4], queries = [[1,0,1,1],[2,1,1],[1,0,1,0]]
输出：[2,1]

解题思路

  • 由于 popcount-depth 的值域有限（题中预设了 popcount-depth 表 depth[]），我们可以为每个可能的深度 k 建立一个线段树，维护该深度下的元素出现次数。
  • 初始化时，根据 nums[i] 的 popcount-depth，将对应树上位置 i 的值设为 1。
  • 对于更新操作类型 2：先在旧深度树上将该位置值设为 0，再在新深度树上将该位置值设为 1。
  • 对于查询操作类型 1：直接在对应深度 k 的线段树上查询区间和，即为答案。
  • 线段树支持 update(pos, delta) 和 sumRange(l, r)，时间复杂度 O(log n)。
class Solution {
    // 预先计算好 0~64 范围内整数的 popcount-depth
    private static final int[] depth = {0, 1, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 3,
                                       2, 3, 3, 4, 3, 4, 4, 3, 3, 4, 4, 3, 4, 3, 3, 4,
                                       2, 3, 3, 4, 3, 4, 4, 3, 3, 4, 4, 3, 4, 3, 3, 4,
                                       3, 4, 4, 3, 4, 3, 3, 4, 4, 3, 3, 4, 3, 4, 4, 4};

    public int[] popcountDepth(long[] nums, long[][] queries) {
        int len = 0;
        // 统计类型 1 查询的数量
        for (long[] q : queries) {
            if (q[0] == 1) ++len;
        }
        SegmentTree[] trees = new SegmentTree[6];
        for (int i = 0; i < trees.length; ++i) {
            trees[i] = new SegmentTree(nums.length);
        }
        // 初始化：根据每个数的 popcount-depth 更新对应线段树
        for (int i = 0; i < nums.length; ++i) {
            trees[getDepth(nums[i])].update(i, 1);
        }
        int[] res = new int[len];
        int pos = 0;
        for (long[] q : queries) {
            if (q[0] == 2) {
                // 更新操作：先将原值在旧深度树中移除，再在新深度树中加入
                int updatePos = (int) q[1];
                long old = nums[updatePos];
                trees[getDepth(old)].update(updatePos, -1);
                nums[updatePos] = q[2];
                trees[getDepth(nums[updatePos])].update(updatePos, 1);
            } else {
                // 查询操作：直接在深度 k 的线段树上查询区间和
                int st = (int) q[1], ed = (int) q[2], k = (int) q[3];
                res[pos++] = trees[k].sumRange(st, ed);
            }
        }
        return res;
    }

    // 获取一个数的 popcount-depth
    private int getDepth(long n) {
        if (n == 1) return 0;
        int count = 0;
        while (n > 0) {
            count += (n & 1);  // 累加最低位
            n >>= 1;           // 右移一位
        }
        return depth[count];
    }
}

// 线段树实现，用于区间更新和区间查询
class SegmentTree {
    int[] tree;
    int n;

    public SegmentTree(int length) {
        n = length;
        tree = new int[n * 2];
    }

    // 在位置 pos 增加 val（可为正负）
    void update(int pos, int val) {
        pos += n;
        tree[pos] += val;
        while (pos > 0) {
            int left = (pos % 2 == 0 ? pos : pos - 1);
            int right = (pos % 2 == 0 ? pos + 1 : pos);
            tree[pos / 2] = tree[left] + tree[right];
            pos /= 2;
        }
    }

    // 查询区间 [l, r] 的和
    public int sumRange(int l, int r) {
        l += n;
        r += n;
        int sum = 0;
        while (l <= r) {
            if ((l & 1) == 1) sum += tree[l++];
            if ((r & 1) == 0) sum += tree[r--];
            l >>= 1;
            r >>= 1;
        }
        return sum;
    }
}  

---

## 3625. 统计任意梯形的数量 II

**题目描述**
给定一个二维整型数组 points，其中 points[i] = [x_i, y_i] 表示平面上的第 i 个点。

**梯形** 是指在凸四边形中，至少有一对平行边（平行即斜率相同）。

返回从这些点中任选四个不同点组成的不同梯形的数量。

*示例*：
```text
输入：points = [[-3,2],[3,0],[2,3],[3,2],[2,-3]]
输出：2

解题思路

  • 任意线段由两点 (i,j) 确定，通过计算斜率来判断是否平行。

  • 枚举所有点对，维护一个哈希表 slopeData，键为斜率（归一化后的有理数对），值为对应的 SlopeInfo：

    • totalCount：当前斜率下已统计的线段总数。
    • lengthCounts：记录不同长度平方值的线段出现次数。
    • lineCounts：记录同一条直线上线段的数量（避免共线情况误计）。
    • lineLengthCounts：同一条直线上，不同长度的线段数。

  • 对于每条新线段：

    • 平行对数 T 增加 prevCount - prevOnThisLine，其中 prevCount 为此斜率下总线段数，prevOnThisLine 为同一直线上已有线段数。
    • 平行且等长对数 P 增加 totalLenPrev - sameLineLenPrev，同斜率相同长度，但不在同一直线上。
  • 最终结果为 T + P（减去平行四边形重复计数）
class Solution {
    /**
     * 存储同一斜率相关统计信息的辅助类
     */
    static class SlopeInfo {
        int totalCount = 0;  // 该斜率下总线段数
        HashMap<Integer, Integer> lengthCounts = new HashMap<>();      // 各长度平方 -> 计数
        HashMap<Long, Integer> lineCounts = new HashMap<>();          // 同一直线标识 -> 计数
        HashMap<Long, HashMap<Integer, Integer>> lineLengthCounts = new HashMap<>(); // 同一直线上各长度 -> 计数
    }

    public int countTrapezoids(int[][] points) {
        HashMap<Long, SlopeInfo> slopeData = new HashMap<>();
        int[] res = new int[2];  // res[0] = T + 2P, res[1] = 2P
        int n = points.length;

        for (int i = 0; i < n; ++i) {
            int x1 = points[i][0], y1 = points[i][1];
            for (int j = i + 1; j < n; ++j) {
                int x2 = points[j][0], y2 = points[j][1];
                long key1, key2;
                int length_sq;

                // 垂直线处理
                if (x1 == x2) {
                    key1 = pack(Integer.MAX_VALUE, Integer.MAX_VALUE);
                    key2 = pack(x1, Integer.MAX_VALUE);
                    length_sq = (y1 - y2) * (y1 - y2);
                }
                // 水平线处理
                else if (y1 == y2) {
                    key1 = pack(Integer.MAX_VALUE/2, Integer.MAX_VALUE/2);
                    key2 = pack(y1, Integer.MAX_VALUE);
                    length_sq = (x1 - x2) * (x1 - x2);
                }
                // 普通斜率处理
                else {
                    int dx = x2 - x1, dy = y2 - y1;
                    int gcd1 = gcd(Math.abs(dx), Math.abs(dy));
                    int nx1 = dx / gcd1, ny1 = dy / gcd1;
                    // 标准化斜率符号
                    if (nx1 < 0 || (nx1 == 0 && ny1 < 0)) {
                        nx1 = -nx1; ny1 = -ny1;
                    }
                    key1 = pack(nx1, ny1);

                    // 唯一标识直线
                    long diff3 = (long) y1 * x2 - (long) y2 * x1;
                    int gcd2 = gcd(Math.abs(dx), Math.abs((int) diff3));
                    int nx2 = dx / gcd2, ny2 = (int) (diff3 / gcd2);
                    if (nx2 < 0 || (nx2 == 0 && ny2 < 0)) {
                        nx2 = -nx2; ny2 = -ny2;
                    }
                    key2 = pack(nx2, ny2);
                    length_sq = dx*dx + dy*dy;
                }

                SlopeInfo info = slopeData.computeIfAbsent(key1, k -> new SlopeInfo());
                int prevCount = info.totalCount;
                int prevOnThisLine = info.lineCounts.getOrDefault(key2, 0);
                // 累计平行对 T
                res[0] += prevCount - prevOnThisLine;

                int totalLenPrev = info.lengthCounts.getOrDefault(length_sq, 0);
                HashMap<Integer, Integer> sameLineMap = info.lineLengthCounts
                        .computeIfAbsent(key2, k -> new HashMap<>());
                int sameLineLenPrev = sameLineMap.getOrDefault(length_sq, 0);
                // 累计平行等长对 P
                res[1] += totalLenPrev - sameLineLenPrev;

                // 更新统计
                info.totalCount++;
                info.lineCounts.put(key2, prevOnThisLine + 1);
                info.lengthCounts.put(length_sq, totalLenPrev + 1);
                sameLineMap.put(length_sq, sameLineLenPrev + 1);
            }
        }
        // 最终结果 = T + P
        return res[0] - res[1]/2;
    }

    // 打包两个整数为一个 long 作为哈希键
    private long pack(int a, int b) {
        return ((long) a << 32) | (b & 0xFFFFFFFFL);
    }

    // 计算最大公约数
    private int gcd(int x, int y) {
        while (y != 0) {
            int t = y;
            y = x % y;
            x = t;
        }
        return x;
    }
}

By hughqiao

Related Post

LeetCode

LeetCode Contest 460

hughqiao
LeetCode

Biweekly Contest 161

hughqiao
LeetCode

Weekly Contest 458

hughqiao

Leave a Reply

Your email address will not be published. Required fields are marked *

You Missed

LeetCode

LeetCode Contest 460

AI评股

美股市场周评：2025年7月21日- 2025年7月25日

LeetCode

LeetCode Contest 459

LeetCode

Biweekly Contest 161