leetcode biweekly contest 95

最近双周赛的题目质量明显高很多，里面非常多非常有意思的题目，非常值得学习与思考。本次双周赛的题目质量非常高，非常值得学习的题目。

2525. 根据规则将箱子分类

给你四个整数 length ，width ，height 和 mass ，分别表示一个箱子的三个维度和质量，请你返回一个表示箱子 类别 的字符串。

• 如果满足以下条件，那么箱子是

  "Bulky"

  的：

  • 箱子 至少有一个 维度大于等于 104 。
  • 或者箱子的 体积 大于等于 109 。

• 如果箱子的质量大于等于 100 ，那么箱子是 "Heavy" 的。

• 如果箱子同时是 "Bulky" 和 "Heavy" ，那么返回类别为 "Both" 。

• 如果箱子既不是 "Bulky" ，也不是 "Heavy" ，那么返回类别为 "Neither" 。

• 如果箱子是 "Bulky" 但不是 "Heavy" ，那么返回类别为 "Bulky" 。

• 如果箱子是 "Heavy" 但不是 "Bulky" ，那么返回类别为 "Heavy" 。

注意，箱子的体积等于箱子的长度、宽度和高度的乘积。

示例 1：

输入：length = 1000, width = 35, height = 700, mass = 300
输出："Heavy"
解释：
箱子没有任何维度大于等于 104 。
体积为 24500000 <= 109 。所以不能归类为 "Bulky" 。
但是质量 >= 100 ，所以箱子是 "Heavy" 的。
由于箱子不是 "Bulky" 但是是 "Heavy" ，所以我们返回 "Heavy" 。

示例 2：

输入：length = 200, width = 50, height = 800, mass = 50
输出："Neither"
解释：
箱子没有任何维度大于等于 104 。
体积为 8 * 106 <= 109 。所以不能归类为 "Bulky" 。
质量小于 100 ，所以不能归类为 "Heavy" 。
由于不属于上述两者任何一类，所以我们返回 "Neither" 。

提示：

• 1 <= length, width, height <= 105
• 1 <= mass <= 103

地址

https://leetcode.cn/problems/categorize-box-according-to-criteria/description/

题意

直接遍历

思路

1.我们直接判断每个箱子满足几个条件，然后按照题目要求进行分类即可。
2. 复杂度分析：

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

代码

class Solution {
public:
    string categorizeBox(int length, int width, int height, int mass) {
        long long volume  = (long long)length * height * width;
        bool isBulky = false,  isHeavy = false;
        if (volume >= 1e9 || length >= 10000 || width >= 10000 || height >= 10000) {
            isBulky = true;
        }
        if (mass >= 100) {
            isHeavy = true;
        }
        if (isBulky && isHeavy) {
            return "Both";
        } else if (!isBulky && !isHeavy) {
            return "Neither";
        } else if (isBulky) {
            return "Bulky";
        } else {
            return "Heavy";
        }
    }
};

2526. 找到数据流中的连续整数

给你一个整数数据流，请你实现一个数据结构，检查数据流中最后 k 个整数是否 等于 给定值 value 。

请你实现 DataStream 类：

• DataStream(int value, int k) 用两个整数 value 和 k 初始化一个空的整数数据流。
• boolean consec(int num) 将 num 添加到整数数据流。如果后 k 个整数都等于 value ，返回 true ，否则返回 false 。如果少于 k 个整数，条件不满足，所以也返回 false 。

示例 1：

输入：
["DataStream", "consec", "consec", "consec", "consec"]
[[4, 3], [4], [4], [4], [3]]
输出：
[null, false, false, true, false]

解释：
DataStream dataStream = new DataStream(4, 3); // value = 4, k = 3 
dataStream.consec(4); // 数据流中只有 1 个整数，所以返回 False 。
dataStream.consec(4); // 数据流中只有 2 个整数
                      // 由于 2 小于 k ，返回 False 。
dataStream.consec(4); // 数据流最后 3 个整数都等于 value， 所以返回 True 。
dataStream.consec(3); // 最后 k 个整数分别是 [4,4,3] 。
                      // 由于 3 不等于 value ，返回 False 。

提示：

• 1 <= value, num <= 109
• 1 <= k <= 105
• 至多调用 consec 次数为 105 次。

地址

https://leetcode.cn/problems/find-consecutive-integers-from-a-data-stream/

题意

栈

思路

1. 保存栈顶元素 $x$ 的个数为 $freq[x]$，则此时加入新的元素 $num$ 时:

• 如果 $num = x$，则此时栈顶的元素仍然为 $x$，且栈顶元素的个数为 $freq[x] + 1$；
• 如果 $num \neq x$，则此时栈顶的元素为 $num$，且栈顶元素的个数为 $freq[num] = 1$；
  我们检测栈顶的元素是否为 $value$，且栈顶的元素个数是否大于等于 $k$ 即可。

2. 复杂度分析：

• 时间复杂度：$O(1)$，其中 $\text{consec}$ 的时间复杂度为 $O(1)$。
• 空间复杂度：$O(n)$，其中 $n$ 为插入元素的次数。

代码

• 二分查找

  class DataStream { public: DataStream(int value, int k) { this->value = value; this->k = k; arr.emplace_back(-1, 0); } bool consec(int num) { if (num == arr.back().first) { arr.back().second++; } else { arr.emplace_back(num, 1); } if (arr.back().first == value && arr.back().second >= k) { return true; } else { return false; } } private: vector<pair<int, int>> arr; int value, k; };

2527. 查询数组 Xor 美丽值

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

三个下标 i ，j 和 k 的 有效值 定义为 ((nums[i] | nums[j]) & nums[k]) 。

一个数组的 xor 美丽值 是数组中所有满足 0 <= i, j, k < n 的三元组 (i, j, k) 的 有效值 的异或结果。

请你返回 nums 的 xor 美丽值。

注意：

• val1 | val2 是 val1 和 val2 的按位或。
• val1 & val2 是 val1 和 val2 的按位与。

示例 1：

输入：nums = [1,4]
输出：5
解释：
三元组和它们对应的有效值如下：
- (0,0,0) 有效值为 ((1 | 1) & 1) = 1
- (0,0,1) 有效值为 ((1 | 1) & 4) = 0
- (0,1,0) 有效值为 ((1 | 4) & 1) = 1
- (0,1,1) 有效值为 ((1 | 4) & 4) = 4
- (1,0,0) 有效值为 ((4 | 1) & 1) = 1
- (1,0,1) 有效值为 ((4 | 1) & 4) = 4
- (1,1,0) 有效值为 ((4 | 4) & 1) = 0
- (1,1,1) 有效值为 ((4 | 4) & 4) = 4 
数组的 xor 美丽值为所有有效值的按位异或 1 ^ 0 ^ 1 ^ 4 ^ 1 ^ 4 ^ 0 ^ 4 = 5 。

示例 2：

输入：nums = [15,45,20,2,34,35,5,44,32,30]
输出：34
解释：数组的 xor 美丽值为 34 。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-326/problems/partition-string-into-substrings-with-values-at-most-k/

题意

数学思路

思路

1. 比赛的时候直接盲猜的答案，结果果真猜对了。题目看起来复杂的，实际解法都会非常的巧妙。但是实际的解法非常好的思考角度，根据题目给定的组合公式 $((nums[i] | nums[j]) \And nums[k])$，可以有如下结论:

• 如果 $i = j = k$，此时上述组合公式的结果一定为 $\textit{nums[i]}$；
• 如果 $i \neq j$，则此时或运算满足交换定理，则此时我们知道如果存在 $x = ((nums[i] | nums[j]) \And nums[k])$，则此时一定存在 $y = ((nums[j] | nums[i]) \And nums[k])$，此时我们知道 $x = y$，此时 $x \oplus y = 0$，因此最终的结果一定可以省略掉 $i \neq j$ 的项；
• 如果 $i = j, i \neq k$，此时上述等式即等于 $((nums[i] | nums[j]) \And nums[k]) = nums[i] \And nums[k]$，则此时与运算满足交换定理，则此时我们知道如果存在 $x = nums[i] \And nums[k]$，则此时一定存在 $y = nums[k]
  \And nums[i]$，此时我们知道 $x = y$，此时 $x \oplus y = 0$，因此最终的结果一定可以省略掉 $i = j, i \neq k$ 的项；
• 最终我们知道只剩下 $i = j = k$ 的项。

2. 还有另外一种数学解法解释的也非常详细，非常值得思考的题目，本次双周赛的题目质量非常高。
3. 复杂度分析

• 时间复杂度：时间复杂度为 $O(n)$，$n$ 表示数组的长度。
• 空间复杂度：时间复杂度为 $O(1)$。

代码

class Solution {
public:
    int xorBeauty(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        for (auto x : nums) {
            res ^= x;
        }
        return res;
    }
};

2528. 最大化城市的最小供电站数目

给你一个下标从 0 开始长度为 n 的整数数组 stations ，其中 stations[i] 表示第 i 座城市的供电站数目。

每个供电站可以在一定 范围 内给所有城市提供电力。换句话说，如果给定的范围是 r ，在城市 i 处的供电站可以给所有满足 |i - j| <= r 且 0 <= i, j <= n - 1 的城市 j 供电。

• |x| 表示 x 的 绝对值 。比方说，|7 - 5| = 2 ，|3 - 10| = 7 。

一座城市的 电量 是所有能给它供电的供电站数目。

政府批准了可以额外建造 k 座供电站，你需要决定这些供电站分别应该建在哪里，这些供电站与已经存在的供电站有相同的供电范围。

给你两个整数 r 和 k ，如果以最优策略建造额外的发电站，返回所有城市中，最小供电站数目的最大值是多少。

这 k 座供电站可以建在多个城市。

示例 1：

输入：stations = [1,2,4,5,0], r = 1, k = 2
输出：5
解释：
最优方案之一是把 2 座供电站都建在城市 1 。
每座城市的供电站数目分别为 [1,4,4,5,0] 。
- 城市 0 的供电站数目为 1 + 4 = 5 。
- 城市 1 的供电站数目为 1 + 4 + 4 = 9 。
- 城市 2 的供电站数目为 4 + 4 + 5 = 13 。
- 城市 3 的供电站数目为 5 + 4 = 9 。
- 城市 4 的供电站数目为 5 + 0 = 5 。
供电站数目最少是 5 。
无法得到更优解，所以我们返回 5 。

示例 2：

输入：stations = [4,4,4,4], r = 0, k = 3
输出：4
解释：
无论如何安排，总有一座城市的供电站数目是 4 ，所以最优解是 4 。

提示：

• n == stations.length
• 1 <= n <= 105
• 0 <= stations[i] <= 105
• 0 <= r <= n - 1
• 0 <= k <= 109

地址

https://leetcode.cn/problems/maximize-the-minimum-powered-city/

题意

二分查找 + 差分数组

思路

1. 根据题目给定的数量级即可知道本题一定要用到二分查找，但是存在一定的技巧。我们二分查边枚举可能的最小供电站的最大数目 $val$，每次检测如下:

• 我们首先使用差分数组每半径范围的的数组进行处理，这样即可线性时间求出每个城市的供电站的数目；
• 我们从左向右或者从右向左依次检测每个城市的供电站的数目，如果当前第 $i$ 个城市的变电站的数目为 $cnt$，且少于 $val$，即 $cnt < val$，此时我们需要从 $k$ 中取出 $val - cnt$ 个电站，此时根据左右策略，我们应该将电站建在最右边，即 $i + r$ 处，此时增加的 $val - cnt$ 个电站覆盖的范围为 $[i, i + 2r]$，此时我们需要在差分数组中进行相应的改变，即在 $i + 2r + 1$ 处减去 $val - cnt$。
• 感觉还算是非常好的面试题目，有一定的技巧性。

2. 复杂度分析：

• 时间复杂度：$O(n \log C)$，其中 $n$ 表示数组的长度。
• 空间复杂度：$O(n)$，其中 $n$ 表示数组的长度。

代码

class Solution {
public:
    bool check(vector<long long> cnt, int r, long long k, long long val) {
        int n = cnt.size() - 1;
        long long curr = 0;
        for (int i = 0; i < n; i++) {
            curr += cnt[i];
            if (curr < val) {
                long long add = val - curr;
                if (k < add) {
                    return false;
                }
                k -= add;
                int end = min(n, i + 2 * r + 1);
                cnt[end] -= add;
                curr += add;
            }
        }
        return true;
    }

    long long maxPower(vector<int>& stations, int r, int k) {
        int n = stations.size();
        vector<long long> cnt(n + 1);
        for (int i = 0; i < n; i++) {
            int left = max(0, i - r);
            int right = min(n, i + r + 1);
            cnt[left] += stations[i];
            cnt[right] -= stations[i];
        }
        long long left = *min_element(stations.begin(), stations.end()); 
        long long right = LONG_MAX;
        long long res = 0;
        while (left <= right) {
            long long mid = left + (right - left) / 2;
            if (check(cnt, r, k, mid)) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
};

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

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