leetcode weekly contest 330

本周的周赛题目基本上都偏向于数学问题，难得见到比较好的题目

6337. 统计桌面上的不同数字

给你一个正整数 n ，开始时，它放在桌面上。在 109 天内，每天都要执行下述步骤：

• 对于出现在桌面上的每个数字 x ，找出符合 1 <= i <= n 且满足 x % i == 1 的所有数字 i 。
• 然后，将这些数字放在桌面上。

返回在 109 天之后，出现在桌面上的 不同 整数的数目。

注意：

• 一旦数字放在桌面上，则会一直保留直到结束。
• % 表示取余运算。例如，14 % 3 等于 2 。

示例 1：

输入：n = 5
输出：4
解释：最开始，5 在桌面上。 
第二天，2 和 4 也出现在桌面上，因为 5 % 2 == 1 且 5 % 4 == 1 。 
再过一天 3 也出现在桌面上，因为 4 % 3 == 1 。 
在十亿天结束时，桌面上的不同数字有 2 、3 、4 、5 。

示例 2：

输入：n = 3 
输出：2
解释： 
因为 3 % 2 == 1 ，2 也出现在桌面上。 
在十亿天结束时，桌面上的不同数字只有两个：2 和 3 。 

提示：

• 1 <= n <= 100

地址

https://leetcode.cn/contest/weekly-contest-330/problems/count-distinct-numbers-on-board/

题意

数学问题

思路

1. 我们思考一个等式 $x \mod (x - 1) = 1, x > 1$，当 $x > 1$ 时上述等式恒成立，因此我们可以推出

• 如果 $x > 1$ 时，此时一定存在 $2,3,4,5,\cdots x -1$;
• 如果 $x = 1$ 时，此时无法继续执行，只剩下 $1$ 这个数字;

2. 复杂度分析：

• 时间复杂度：$O(1)$。
• 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int distinctIntegers(int n) {
        return n == 1 ? 1 : (n - 1);
    }
};

6338. 猴子碰撞的方法数

现在有一个正凸多边形，其上共有 n 个顶点。顶点按顺时针方向从 0 到 n - 1 依次编号。每个顶点上 正好有一只猴子 。下图中是一个 6 个顶点的凸多边形。

每个猴子同时移动到相邻的顶点。顶点 i 的相邻顶点可以是：

• 顺时针方向的顶点 (i + 1) % n ，或
• 逆时针方向的顶点 (i - 1 + n) % n 。

如果移动后至少有两个猴子位于同一顶点，则会发生 碰撞 。

返回猴子至少发生 一次碰撞 的移动方法数。由于答案可能非常大，请返回对 109+7 取余后的结果。

注意，每只猴子只能移动一次。

示例 1：

输入：n = 3
输出：6
解释：共计 8 种移动方式。
下面列出两种会发生碰撞的方式：
- 猴子 1 顺时针移动；猴子 2 逆时针移动；猴子 3 顺时针移动。猴子 1 和猴子 2 碰撞。
- 猴子 1 逆时针移动；猴子 2 逆时针移动；猴子 3 顺时针移动。猴子 1 和猴子 3 碰撞。
可以证明，有 6 种让猴子碰撞的方法。

示例 2：

输入：n = 4
输出：14
解释：可以证明，有 14 种让猴子碰撞的方法。

提示：

• 3 <= n <= 109

地址

https://leetcode.cn/contest/biweekly-contest-96/problems/minimum-operations-to-make-array-equal-ii/

题意

数学

思路

1. 典型的排列组合，每个猴子有两种走法，要么顺时针要么逆时针，因此 $n$ 只猴子一共有 $2^n$ 种不同的移动方法，有且仅有所有的猴子都逆势针或者顺时针这两种移动方法时不会发生碰撞，因此总的方法数目为 $2^n - 2$。我们可以用二分快速乘法，即可完成。
2. 复杂度分析：

• 时间复杂度：$O(\log n)$，其中 $n$ 为给定的数。
• 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int monkeyMove(int n) {
        long long mod = 1e9 + 7;
        long long res = 1;
        long long curr = 2;
        while (n) {
            if (n & 1) {
                res = (res* curr) % mod;
            }
            curr = (curr * curr) % mod;
            n >>= 1;
        }
        return (res - 2 + mod) % mod;
    }
};

6339. 将珠子放入背包中

你有 k 个背包。给你一个下标从 0 开始的整数数组 weights ，其中 weights[i] 是第 i 个珠子的重量。同时给你整数 k 。

请你按照如下规则将所有的珠子放进 k 个背包。

• 没有背包是空的。
• 如果第 i 个珠子和第 j 个珠子在同一个背包里，那么下标在 i 到 j 之间的所有珠子都必须在这同一个背包中。
• 如果一个背包有下标从 i 到 j 的所有珠子，那么这个背包的价格是 weights[i] + weights[j] 。

一个珠子分配方案的 分数 是所有 k 个背包的价格之和。

请你返回所有分配方案中，最大分数 与 最小分数 的 差值 为多少。

示例 1：

输入：weights = [1,3,5,1], k = 2
输出：4
解释：
分配方案 [1],[3,5,1] 得到最小得分 (1+1) + (3+1) = 6 。
分配方案 [1,3],[5,1] 得到最大得分 (1+3) + (5+1) = 10 。
所以差值为 10 - 6 = 4 。

示例 2：

输入：weights = [1, 3], k = 2
输出：0
解释：唯一的分配方案为 [1],[3] 。
最大最小得分相等，所以返回 0 。

提示：

• 1 <= k <= weights.length <= 105
• 1 <= weights[i] <= 109

地址

https://leetcode.cn/contest/biweekly-contest-96/problems/maximum-subsequence-score/

题意

排列组合

思路

1. 当然如果我们直接用动态规划的算法也可以算出来，此时需要的时间复杂度为 $O(n^2)$，因此需要一定的技巧。我们仔细思考一下，我们需要选择哪些珠子：

• 最开始与最结尾的珠子一定要选；
  我们可以换种思路来思考这个问题，类似于排列组合，我们有 $n$ 个数，在这 $n$ 个数中间放置 $k-1$ 个隔板，此时 $n$ 个数就被分成了 $k$ 组，类似于如下结构:
  $$
  0,1,2,|3,4,5,|6,|7,8,|9,10
  $$
  假设我们在 $A=[2,5,6,9]$ 处放置了四个隔板，此时我们可以分数的总和为 $s = nums[0] + nums[2][2 + 1] + nums[5][5+1] + nums[6][6+1] + nums[9][9 + 1] + nums[10]$；
  我们可以看到无论怎么选都可以选到 $nums[0] + nums[10]$，因此我们只需要考虑 $k-1$ 个隔板处总和大小即可。因此我们将所有可能的隔板的和按照从小到大进行排序，选择最大的 $k-1$ 个即构成最大的分数，选择最小的 $k-1$ 个即构成最小的分数，这步转换非常重要。我们求出最大的和与最小的和之差即可。

2. 复杂度分析

• 时间复杂度：时间复杂度为 $O(k + n \log n)$，$n$ 表示数组的长度，$k$ 表示给定的数字。
• 空间复杂度：时间复杂度为 $O(n)$。

代码

class Solution {
public:
    long long putMarbles(vector<int>& weights, int k) {
        int n = weights.size();
        vector<long long> arr;
        for (int i = 0; i < n - 1; i++) {
            arr.emplace_back((long long)weights[i] + weights[i + 1]);
        }
        sort(arr.begin(), arr.end());
        long long res = 0;
        int m = arr.size();
        for (int i = 0; i < k - 1; i++) {
            res += arr[m - i - 1] - arr[i];
        }
        return res;
    }
};

6340. 统计上升四元组

给你一个长度为 n 下标从 0 开始的整数数组 nums ，它包含 1 到 n 的所有数字，请你返回上升四元组的数目。

如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的：

• 0 <= i < j < k < l < n 且
• nums[i] < nums[k] < nums[j] < nums[l] 。

示例 1：

输入：nums = [1,3,2,4,5]
输出：2
解释：
- 当 i = 0 ，j = 1 ，k = 2 且 l = 3 时，有 nums[i] < nums[k] < nums[j] < nums[l] 。
- 当 i = 0 ，j = 1 ，k = 2 且 l = 4 时，有 nums[i] < nums[k] < nums[j] < nums[l] 。
没有其他的四元组，所以我们返回 2 。

示例 2：

输入：nums = [1,2,3,4]
输出：0
解释：只存在一个四元组 i = 0 ，j = 1 ，k = 2 ，l = 3 ，但是 nums[j] < nums[k] ，所以我们返回 0 。

提示：

• 4 <= nums.length <= 4000
• 1 <= nums[i] <= nums.length
• nums 中所有数字 互不相同 ，nums 是一个排列。

地址

https://leetcode.cn/contest/biweekly-contest-96/problems/check-if-point-is-reachable/

题意

动态规划

思路

1. 题目的提示也非常明显，包含几个明显的条件:

• $4 \le nums.length \le 4000$。
• nums 中所有数字 互不相同 ，nums 是一个排列。
  我们根据以上条件可以知道本题目需要用到动态规划，我们设 $dp1[i][j]$ 表示数组从 $0$ 开始到 $i$ 之间存在小于 $j$ 的数目；$dp2[i][j]$ 表示数组从 $i$ 开始到存在大于 $j$ 的数目；此时假设我们已经找到一对符合条件的 $j,k$，此时满足 $j < k, nums[k] < nums[j]$，则此时符合要求的数对 $i, l$ 的数目为 $dp1[j-1][nums[k]] * dp2[k + 1][nums[j]]$，此时我们利用上述的递推公式即可求出，上述的两个动态规划也非常容易计算出来，感觉还算是非常棒的题目。

2. 复杂度分析：

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(n^2)$。

代码

class Solution {
public:
    long long countQuadruplets(vector<int>& nums) {
        int n = nums.size();
        int m = *max_element(nums.begin(), nums.end());
        vector<vector<int>> dp1(n + 1, vector<int>(m + 1));
        vector<vector<int>> dp2(n + 1, vector<int>(m + 1));
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= m; j++) {
                if (nums[i] < j) {
                    dp1[i + 1][j] = dp1[i][j] + 1;
                } else {
                    dp1[i + 1][j] = dp1[i][j];
                }
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 1; j <= m; j++) {
                if (nums[i] > j) {
                    dp2[i][j] = dp2[i + 1][j] + 1;
                } else {
                    dp2[i][j] = dp2[i + 1][j];
                }
            }
        }
        long long res = 0;
        for (int k = 0; k < n; k++) {
            for (int j = 0; j < k; j++) {
                if (nums[k] < nums[j]) {
                    res += (long long)dp2[k][nums[j]] * dp1[j][nums[k]];
                }
            }
        }
        return res;
    }
};

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://whistle-wind.com/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿