LeetCode 91 双周赛_leetcode双周赛

2465. 不同的平均值数目

给你一个下标从 0 开始长度为 偶数 的整数数组 nums 。

只要 nums 不是 空数组，你就重复执行以下步骤：

• 找到 nums 中的最小值，并删除它。
• 找到 nums 中的最大值，并删除它。
• 计算删除两数的平均值。

两数 a 和 b 的 平均值 为 (a + b) / 2 。

• 比方说，2 和 3 的平均值是 (2 + 3) / 2 = 2.5 。

返回上述过程能得到的 不同 平均值的数目。

注意 ，如果最小值或者最大值有重复元素，可以删除任意一个。

提示

• 2 <= nums.length <= 100
• nums.length 是偶数。
• 0 <= nums[i] <= 100

示例

输入：nums = [4,1,4,0,3,5]
输出：2
解释：
1. 删除 0 和 5 ，平均值是 (0 + 5) / 2 = 2.5 ，现在 nums = [4,1,4,3] 。
2. 删除 1 和 4 ，平均值是 (1 + 4) / 2 = 2.5 ，现在 nums = [4,3] 。
3. 删除 3 和 4 ，平均值是 (3 + 4) / 2 = 3.5 。
2.5 ，2.5 和 3.5 之中总共有 2 个不同的数，我们返回 2 。
1
2
3
4
5
6
7

思路

简单模拟

先排序，然后用双指针进行模拟，并用set去重。

// C++ 
class Solution {
public:
    int distinctAverages(vector<int>& nums) {
        unordered_set<int> s;
        sort(nums.begin(), nums.end());
        int i = 0, j = nums.size() - 1;
        while (i < j) {
            s.emplace(nums[i] + nums[j]); // 不需要算平均值
            i++;
            j--;
        }
        return s.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2466. 统计构造好字符串的方案数

给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：

• 将 '0' 在字符串末尾添加 zero 次。
• 将 '1' 在字符串末尾添加 one 次。

以上操作可以执行任意次。

如果通过以上过程得到一个 长度 在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为 好 字符串。

请你返回满足以上要求的 不同 好字符串数目。由于答案可能很大，请将结果对 10^9 + 7 取余 后返回。

提示：

• 1 <= low <= high <= 10^5
• 1 <= zero, one <= low

示例

输入：low = 3, high = 3, zero = 1, one = 1
输出：8
解释：
一个可能的好字符串是 "011" 。
可以这样构造得到："" -> "0" -> "01" -> "011" 。
从 "000" 到 "111" 之间所有的二进制字符串都是好字符串。
1
2
3
4
5
6

思路

本质是个组合问题，可以将问题抽象成这样：x初始为0，每次操作可以选择加上zero或者one，问经过若干次操作后，能使得x位于[low, high]区间内，总的操作方案数。

周赛当晚，最直观的想法当然就是暴力枚举了。然而由于最大的数据是low = 1，high = 10^5，zero = one = 1，每次有2个选择，而一共可以做10^5次选择，那么总的时间复杂度就能达到 $2^{10^5}$，这超时都超到太阳系外边去了。肯定是不行的。

// C++
const int MOD = 1e9 + 7;
class Solution {
public:
    
    int ans = 0;
    
    void dfs(int i, int z, int o, int low, int high) {
        if (i > high) return ;
        if (i >= low && i <= high) {
            ans++;
            ans = ans % MOD;
        }
        // 填0
        dfs(i + z, z, o, low, high);
        // 填1
        dfs(i + o, z, o, low, high);
    }
    
    int countGoodStrings(int low, int high, int zero, int one) {
        dfs(0, zero, one, low, high);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

看着这种每次加上一个数，有点动态规划那意思。于是就往动态规划上面想。

状态 f[i]表示，构造出的字符串长度为i时的总方案数。

接下来看状态转移，因为状态转移肯定跟某一次我们的选择有关系，而我们每次有2种选择。所以我们将状态数组开成二维，用f[i][0]表示，最后一次选择的是zero，且构造出的字符串长度为i时的方案数；f[i][1]表示，最后一次选择是one。

对于f[i][0]，由于最后一次选择的是zero，则我们最后一次选择之前，得到的字符串长度是i - zero，所以f[i][0] = f[i - zero][0] + f[i - zero][1]

同理，有f[i][1] = f[i - one][0] + f[i - one][1]

// C++
const int MOD = 1e9 + 7;
class Solution {
public:
    
    int countGoodStrings(int low, int high, int zero, int one) {
        vector<vector<int>> f(high + 10, vector<int>(2, 0));
        f[zero][0] = f[one][1] = 1;
        long long ans = 0;
        for (int i = 1; i <= high; i++) {
            if (i - zero > 0) {
                f[i][0] = (f[i - zero][0] + f[i - zero][1]) % MOD;
            }
            if (i - one > 0) {
                f[i][1] = (f[i - one][0] + f[i - one][1]) % MOD;
            }
            if (i >= low && i <= high) {
                ans += f[i][0] + f[i][1];
                ans = ans % MOD;
            }
        }
        return (int) ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

上面的代码还能优化，这里就不再赘述。

其实这道题就是爬楼梯。