Leetcode每日一题题解(10月每日更新).

3164. 优质数对的总数 II (10月11日, 枚举)

题目地址: https://leetcode.cn/problems/find-the-number-of-good-pairs-ii/description/
思路: 题目要求我们寻找 nums1[i] 可以被 nums2[j] * k 整除的 (i, j)对数, 假如 nums1[i] 可以被 nums2[j] * k 整除, 那么存在一个整数p使得 nums1[i] = nums2[j] * k * p 成立, 所以我们会得出一个第一个非常重要的结论: “nums1[i] 能被 k 整除”。
那么 nums1[i] / k 也能被 nums2[j] 整除, 也就是说 nums1[i] / k的因子的某个因子 d == nums2[j], 于是问题就转化为 对于每一个 (i, j) 里面的 j就代表有多少个 nums1[i] / k的因子能被 nums2[j]所整除.
于是大致思路就出来了, 我们先构造一个HashMap, 记录 nums1[i] / k 的每一个因子数量, 然后枚举 nums2, 如果 nums2 能被某个 nums1[i] / k的因子 所整除, 那么对答案的贡献也是那个因子出现的次数(从HashMap取值即可): 

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
class Solution {

    private List<Integer> getAllFactors(int n) {
        List<Integer> factors = new ArrayList<>();
        for (int d = 1;  d * d <= n; d++) {
            if (n % d == 0) {
                factors.add(d);
                if (d * d != n) {
                    factors.add(n / d);
                }
            }
        }
        return factors;
    }

    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        long ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        IntStream.of(nums1)
            .filter(x -> x % k == 0)
            .forEach(x -> {
                List<Integer> factors = getAllFactors(x / k);
                factors.parallelStream().forEach(i -> {
                    cnt.merge(i, 1, Integer::sum);
                });
        });

        return IntStream.of(nums2).mapToLong(x -> cnt.getOrDefault(x, 0)).sum();
    }
}

1884. 鸡蛋掉落-两枚鸡蛋(10月13日, DP)

题目地址: https://leetcode.cn/problems/egg-drop-with-2-eggs-and-n-floors/
思路: 有两个鸡蛋, 题目给定一个数字n代表整栋楼的高度, 假设仅存在一个数f(0 <= f <= n), 也就是在第 f 层丢鸡蛋不会被丢碎。
问怎么用最少的丢蛋次数确定f。
由于题目中只有两个鸡蛋, 并且如果一个鸡蛋从某层楼丢下来没有碎的话可以进行重复使用。假设有 n 层楼, 我们在第 i 层楼丢第一个鸡蛋, 分两种情况:

  • 如果鸡蛋碎了, 那么我们要在第 (1, 2, … i - 1) 层楼尝试丢第二科鸡蛋才能确定出 f。 也就是需要 1 + (i - 1) = i 步。
  • 如果鸡蛋没有碎掉, 我们要往上走继续进行尝试, 那么问题就转化为只有在 n - i 层楼时最少的丢蛋次数 x, 那么就需要 1 + x 步。

于是假设 f[n] 为有 n 层楼时的最少的丢蛋次数, 显然 f[0] = 0,
对于 n > 0, 状态可以由[1, n]转移过来(从1到n楼中尝试丢蛋时的结果), 由于我们要最优解, 我们对所有状态转移取min, 即对于(1 <= j <= n), f[n] = min(f[n], max(j, f[n - j] + 1))
时间复杂度: O(n^2) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int twoEggDrop(int n) {
        int f[n+1];
        f[0] = 0;
        for (int i = 1; i <= n; i++) {
            f[i] = INT_MAX;
            for (int j = 1; j <= i; j++) {
                f[i] = min(f[i], max(j, f[i - j] + 1));
            }
        }
       return f[n];
    }
};