月度归档： 2024 年 10 月

目标

给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。

如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。

返回 优质数对 的总数。

示例 1：

输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1
输出：5
解释：
5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。

示例 2：

输入：nums1 = [1,2,4,12], nums2 = [2,4], k = 3
输出：2
解释：
2个优质数对分别是 (3, 0) 和 (3, 1)。

说明：

• 1 <= n, m <= 10^5
• 1 <= nums1[i], nums2[j] <= 10^6
• 1 <= k <= 10^3

思路

这与昨天 3162.优质数对的总数I 的区别是数据范围变大了，暴力解法不可行。

枚举因子的时间复杂度为 O(n * sqrt(max1/k) + m)， 代入计算 10^5 * 10^3 + 10^5 大约 10^8，耗时560ms。

枚举倍数的时间复杂度为 O(n + m + max1/k * log(m))，10^5 + 10^5 + 10^6 * ln(10^5) ≈ 10^5 + 10^5 + 10^6 * 11.51，10^7，耗时 88ms。

代码

/**
 * @date 2024-10-11 8:40
 */
public class NumberOfPairs3164 {

    /**
     * 枚举因子 560ms
     */
    public long numberOfPairs_v1(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> factorCnt = new HashMap<>();
        for (int num : nums1) {
            if (num % k != 0) {
                continue;
            }
            num /= k;
            for (int i = 1; i * i <= num; i++) {
                if (num % i != 0) {
                    continue;
                }
                factorCnt.merge(i, 1, Integer::sum);
                if (i * i < num) {
                    factorCnt.merge(num / i, 1, Integer::sum);
                }
            }
        }
        long res = 0L;
        for (int num : nums2) {
            res += factorCnt.getOrDefault(num, 0);
        }
        return res;
    }

    /**
     * 枚举倍数 88ms
     */
    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> map1 = new HashMap<>(nums1.length);
        Map<Integer, Integer> map2 = new HashMap<>(nums2.length);
        int max1 = 0;
        for (int num : nums1) {
            map1.merge(num, 1, Integer::sum);
            max1 = Math.max(max1, num);
        }
        for (int num : nums2) {
            map2.merge(num, 1, Integer::sum);
        }
        long res = 0L;
        for (int num : map2.keySet()) {
            int multiple = num * k;
            for (int i = multiple; i <= max1; i += multiple) {
                if (map1.containsKey(i)) {
                    res += (long) map1.get(i) * map2.get(num);
                }
            }
        }
        return res;
    }

}

性能

目标

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2:

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

说明:

• gas.length == n
• cost.length == n
• 1 <= n <= 10^5
• 0 <= gas[i], cost[i] <= 10^4

思路

一条环线上有 n 个加油站，加油站 i 有 gas[i] 升汽油，从加油站 i 到达加油站 i + 1 需要消耗汽油 cost[i] 升，假设有一辆油箱无限大的汽车，初始油箱为空，问从哪个加油站出发可以绕环线行驶一周，测试用例保证如果解存在则唯一，如果解不存在返回 -1。

枚举起点，模拟加油与耗油过程，记录剩余汽油，直到完成环线或者无法抵达下一加油站。值得注意的是，如果从起点 a 出发无法到达 b，那么从 (a, b) 之间的任意加油站出发都无法到达 b，因为到达下一站剩余的汽油是大于等于 0 的，如果带着剩余汽油都无法抵达，那么初始汽油为空更无法到达。我们可以将起点设为 b 继续枚举。

最开始写的是两次循环，后来又改成在一个while循环中，时间复杂度为 O(2n)。之所以是 2n 是因为 start 如果为 n - 1 那么需要再判断能否到达 0 ~ n - 1。

优化：如果 gasSum >= costSum， 那么解一定存在。注意到 remainder += gas[i] - cost[i] 其实就是在计算 gasSum - costSum，只是中间小于零的时候重置了，我们只需要一个变量 diff 将其保存起来，直接判断 diff 是否大于 0， 没必要再进行后续判断了。

代码

/**
 * @date 2024-04-13 21:02
 */
public class CanCompleteCircuit134 {

    public int canCompleteCircuit_v2(int[] gas, int[] cost) {
        int n = gas.length;
        int remainder = 0;
        int start = 0;
        int diff = 0;
        for (int i = start; i < n; i++) {
            remainder += gas[i] - cost[i];
            if (remainder < 0) {
                start = i + 1;
                diff += remainder;
                remainder = 0;
            }
        }
        diff += remainder;
        return diff < 0 ? -1 : start;
    }

    public int canCompleteCircuit_v1(int[] gas, int[] cost) {
        int start = 0;
        int cur = 0;
        int n = gas.length;
        int remainder = 0;
        while (start < n) {
            int i = cur % n;
            remainder += gas[i] - cost[i];
            if (remainder < 0) {
                start = ++cur;
                remainder = 0;
            } else if ((i + 1) % n == start) {
                return start;
            } else {
                cur++;
            }
        }
        return -1;
    }

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int remainder = 0;
        int start = 0;
        // 第一次循环，遇到断点就重新开始
        for (int i = start; i < n; i++) {
            remainder += gas[i] - cost[i];
            if (remainder < 0) {
                start = i + 1;
                remainder = 0;
            }
        }
        // 第二次循环，遇到断点说明不可达
        for (int i = 0; i < start; i++) {
            remainder += gas[i] - cost[i];
            if (remainder < 0) {
                return -1;
            }
        }
        return start;
    }

}

性能

两次循环

写成一次循环，实际上是循环了两个变量，并且循环中的操作也翻倍了

一次循环

目标

有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。

剩下的乘客将会：

• 如果他们自己的座位还空着，就坐到自己的座位上，
• 当他们自己的座位被占用时，随机选择其他座位

第 n 位乘客坐在自己的座位上的概率是多少？

示例 1：

输入：n = 1
输出：1.00000
解释：第一个人只会坐在自己的位置上。

示例 2：

输入: n = 2
输出: 0.50000
解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。

说明：

• 1 <= n <= 10^5

思路

飞机上有 n 个座位，第一位乘客的票丢了，它随机找了一个位置坐下。后面的乘客如果发现自己的位置空着就直接入座，否则随机找一个位置坐下，问最后一个人坐在自己位置上的概率是多少？

这是一个纯数学问题，使用数学归纳法可以证明概率为：n == 1 ? 1 : 0.5。

代码

性能