leetcode biweekly contest 82

双周赛的难度挺好，终于不是全部四题水题了，感觉质量挺高，虽然有难度，但是还是喜欢这类题目。

6116. 计算布尔二叉树的值

题目

给你一棵完整二叉树的根，这棵树有以下特征：

叶子节点要么值为 0 要么值为 1 ，其中 0 表示 False ，1 表示 True 。
非叶子节点要么值为 2 要么值为 3 ，其中 2 表示逻辑或 OR ，3 表示逻辑与 AND 。
计算一个节点的值方式如下：

如果节点是个叶子节点，那么节点的值为它本身，即 True 或者 False 。
否则，计算两个孩子的节点值，然后将该节点的运算符对两个孩子值进行运算。
返回根节点 root 的布尔运算值。

完整二叉树是每个节点有 0 个或者 2 个孩子的二叉树。

叶子节点是没有孩子的节点。

示例 1：

输入：root = [2,1,3,null,null,0,1]
输出：true
解释：上图展示了计算过程。
AND 与运算节点的值为 False AND True = False 。
OR 运算节点的值为 True OR False = True 。
根节点的值为 True ，所以我们返回 true 。

示例 2：

输入：root = [0]
输出：false
解释：根节点是叶子节点，且值为 false，所以我们返回 false 。

提示：

树中节点数目在 [1, 1000] 之间。
0 <= Node.val <= 3
每个节点的孩子数为 0 或 2 。
叶子节点的值为 0 或 1 。
非叶子节点的值为 2 或 3 。

地址

https://leetcode.cn/problems/evaluate-boolean-binary-tree

题意

深度优先搜索

思路

直接按照深度有限搜索的方式进行遍历即可，每次在非叶子节点进行计算即可。
复杂度分析：

时间复杂度：$O(n))$, 其中 $n$ 为节点的数目。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    bool evaluateTree(TreeNode* root) {
       if (!root->right && !root->left) {
           return root->val;
       } 
       if (root->val == 2) {
           return evaluateTree(root->left) || evaluateTree(root->right);
       } else {
           return evaluateTree(root->left) && evaluateTree(root->right);
       }
    }
};

6117. 坐上公交的最晚时间

题目

给你一个下标从 0 开始长度为 n 的整数数组 buses ，其中 buses[i] 表示第 i 辆公交车的出发时间。同时给你一个下标从 0 开始长度为 m 的整数数组 passengers ，其中 passengers[j] 表示第 j 位乘客的到达时间。所有公交车出发的时间互不相同，所有乘客到达的时间也互不相同。

给你一个整数 capacity ，表示每辆公交车最多能容纳的乘客数目。

每位乘客都会搭乘下一辆有座位的公交车。如果你在 y 时刻到达，公交在 x 时刻出发，满足 y <= x 且公交没有满，那么你可以搭乘这一辆公交。最早到达的乘客优先上车。

返回你可以搭乘公交车的最晚到达公交站时间。你不能跟别的乘客同时刻到达。

注意：数组 buses 和 passengers 不一定是有序的。

示例 1：

输入：buses = [10,20], passengers = [2,17,18,19], capacity = 2
输出：16
解释：
第 1 辆公交车载着第 1 位乘客。
第 2 辆公交车载着你和第 2 位乘客。
注意你不能跟其他乘客同一时间到达，所以你必须在第二位乘客之前到达。

示例 2：

输入：buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2
输出：20
解释：
第 1 辆公交车载着第 4 位乘客。
第 2 辆公交车载着第 6 位和第 2 位乘客。
第 3 辆公交车载着第 1 位乘客和你。

提示：

n == buses.length
m == passengers.length
1 <= n, m, capacity <= 105
2 <= buses[i], passengers[i] <= 109
buses 中的元素互不相同。
passengers 中的元素互不相同。

地址

https://leetcode.cn/problems/the-latest-time-to-catch-a-bus

题意

数学问题

思路

这个题目类似于数学奥数，首先我们分析一下最后一个人可能的最晚上车时间。我们按照时间先后的顺序，和相应的 $capbility$ 可以很容易的求出每次班车的乘客。设最后一辆班车为 $i$, 可以载的乘客数量为 $m$ 个，此时可以有两种情况进行分析最后一个乘客的到达时间:

如果最后一辆班车 $i$ 的乘客数量 $m < capacity$，假如不考虑时间重复的问题，此时最后一个乘客可以在 $buses[i]$ 时间坐上班车，此时我们从 $time = buses[i]$ 开始检测，是否存在相同的时间，如果存在相同时间则将 $time$ 减 $1$, 知道不会出现重复时间为止。
如果最后一辆班车 $i$ 的乘客数量 $m = capacity$, 最后一个乘客的时间为 $last$，此时我们知道如果以 $last -1$ 时间达到时肯定可以上车，此时只需要沿着 $last - 1$ 找到第一个不重复的时间即可。

复杂度分析：

时间复杂度：$O(n\log n + m \log m)$，其中 $m,n$ 分别为两个数组的长度。
空间复杂度：$O(n)$，时间复杂度为 $O(n)$。

代码

class Solution {
public:
    int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers, int capacity) {
        sort(buses.begin(), buses.end());
        sort(passengers.begin(), passengers.end());
        unordered_set<int> cnt;
        for (auto v : passengers) {
            cnt.emplace(v);
        }
        int m = buses.size();
        int n = passengers.size();
        int res = 0;
        for (int i = 0, j = 0; i < m; i++) {
            int tot = 0;
            while (j < n && tot < capacity && passengers[j] <= buses[i]) {
                tot++;
                j++;
            }
            if (tot < capacity) {
                res = buses[i];
            } else {
                res = passengers[j - 1] - 1;
            }
        }
        while (cnt.count(res)) {
            res--;
        }
        return res;
    }
};

6118. 最小差值平方和

题目

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度为 n 。

数组 nums1 和 nums2 的差值平方和定义为所有满足 0 <= i < n 的 (nums1[i] - nums2[i])2 之和。

同时给你两个正整数 k1 和 k2 。你可以将 nums1 中的任意元素 +1 或者 -1 至多 k1 次。类似的，你可以将 nums2 中的任意元素 +1 或者 -1 至多 k2 次。

请你返回修改数组 nums1 至多 k1 次且修改数组 nums2 至多 k2 次后的最小差值平方和。

注意：你可以将数组中的元素变成负整数。

示例 1：

输入：nums1 = [1,2,3,4], nums2 = [2,10,20,19], k1 = 0, k2 = 0
输出：579
解释：nums1 和 nums2 中的元素不能修改，因为 k1 = 0 和 k2 = 0 。
差值平方和为：(1 - 2)2 + (2 - 10)2 + (3 - 20)2 + (4 - 19)2 = 579 。

示例 2：

输入：nums1 = [1,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1
输出：43
解释：一种得到最小差值平方和的方式为：
- 将 nums1[0] 增加一次。
- 将 nums2[2] 增加一次。
最小差值平方和为：
(2 - 5)2 + (4 - 8)2 + (10 - 7)2 + (12 - 9)2 = 43 。
注意，也有其他方式可以得到最小差值平方和，但没有得到比 43 更小答案的方案。

提示：

n == nums1.length == nums2.length
1 <= n <= 105
0 <= nums1[i], nums2[i] <= 105
0 <= k1, k2 <= 109

地址

https://leetcode.cn/problems/minimum-sum-of-squared-difference

题意

数学+ 贪心算法

思路

题目本质为贪心算法，首先我们求出两个数组中每个索引上两个元素的差值绝对值为 $diff[i]$。对于 $k1,k2$ 不管用加还是减，我们都可以使得绝对值 $diff[i]$ 变小，假设目前还剩下 $1$ 个可以改变，对于 $x,y$, 此时如果满足 $x > y$, 此时我们应该将 $x$ 进行减 $1$, 因为我们可以知道如下不等式，$(x-1)^2 + y^2 < x ^ 2 + (y-1)^2$，因此我们应当的将 $diff$ 数组的元素最大值尽可能的小，此时我们将 $diff$ 中的最大值依次减小到跟第二大的值相等，按照上述步骤进行递减，直到 $k1 + k2$ 减到 $0$ 为止。
复杂度分析：

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

代码

class Solution {
public:
    long long minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2) {
        map<int, int> cnt;
        cnt[0] = 1;
        for (int i = 0; i < nums1.size(); i++) {
            cnt[abs(nums1[i] - nums2[i])]++;
        }
        long long tot = k1 + k2;
        while (tot > 0 && cnt.size() > 0) {
            auto [curr, freq1] = *cnt.rbegin();
            cnt.erase(curr);
            if (cnt.size() > 0) {
                auto [prev, freq2] = *cnt.rbegin();
                long long need = (long long)freq1 * (curr - prev);
                if (need <= tot) {
                    cnt[prev] += freq1;
                    tot -= need;
                } else {
                    int x = tot / freq1;
                    int y = tot % freq1;
                    cnt[curr - x - 1] += y;
                    cnt[curr - x] += freq1 - y;
                    tot = 0;
                }
            }
        }
        long long ans = 0;
        for (auto [curr, freq] : cnt) {
            ans += (long long)curr * curr * freq;
        }
        return ans;
    }
};

6119. 元素值大于变化阈值的子数组

题目

给你一个整数数组 nums 和一个整数 threshold 。

找到长度为 k 的 nums 子数组，满足数组中每个元素都大于 threshold / k 。

请你返回满足要求的任意子数组的大小。如果没有这样的子数组，返回 -1 。

子数组是数组中一段连续非空的元素序列。

示例 1：

输入：nums = [1,3,4,3,1], threshold = 6
输出：3
解释：子数组 [3,4,3] 大小为 3 ，每个元素都大于 6 / 3 = 2 。
注意这是唯一合法的子数组。

示例 2：

输入：nums = [6,5,6,5,8], threshold = 7
输出：1
解释：子数组 [8] 大小为 1 ，且 8 > 7 / 1 = 7 。所以返回 1 。
注意子数组 [6,5] 大小为 2 ，每个元素都大于 7 / 2 = 3.5 。
类似的，子数组 [6,5,6] ，[6,5,6,5] ，[6,5,6,5,8] 都是符合条件的子数组。
所以返回 2, 3, 4 和 5 都可以。

提示：

1 <= nums.length <= 105
1 <= nums[i], threshold <= 109

地址

https://leetcode.cn/problems/subarray-with-elements-greater-than-varying-threshold

题意

单调栈

思路

我们直接求出结果的话比较难求出来，我们依次遍历第 $i$ 个元素，并找到以 $nums[i]$ 为最小的元素的最大长度，我们可以分开计算计算，计算 $i$ 的左边连续有多少个元素比 $nums[i]$ 小，记为 $left[i]$,计算 $i$ 的右边连续有多少个元素比 $nums[i]$ 小，记为 $right[i]$，此时我们知道以 $num[i]$ 为最小的连续子数组的长度为 $left[i] + right[i] + 1$，如果满足 $(left[i] + right[i] + 1) \times nums[i] > threshold$ 时，则就满足题目要求。
我们可以利用单调栈分别求出左右两边第一个小于 $nums[i]$ 的元素的索引 $j$。
复杂度分析：

时间复杂度：$n$，$n$ 表示数组的长度。
空间复杂度：$n$，$n$ 表示数组的长度。

代码

class Solution {
public:
    int validSubarraySize(vector<int>& nums, int threshold) {
        int n = nums.size();
        stack<pair<int,int>> st1, st2;
        vector<int> left(n), right(n);
        st1.emplace(0, -1);
        for (int i = 0; i < n; i++) {
            while (!st1.empty() && nums[i] <= st1.top().first) {
                st1.pop();
            }
            left[i] = i - st1.top().second - 1;
            st1.emplace(nums[i], i);
        }
        for (int i = n - 1; i >= 0; i--) {
            while (!st2.empty() && nums[i] <= st2.top().first) {
                st2.pop();
            }
            if (st2.empty()) {
                right[i] = n - i - 1;
            } else {
                right[i] = st2.top().second - i - 1; 
            }
            st2.emplace(nums[i], i);
        }
        for (int i = 0; i < n; i++) {
            long long x = (long long)(left[i] + right[i] + 1) * nums[i];
            if ( x > threshold) {
                return left[i] + right[i] + 1;
            }
        }
        return -1;
    }
};

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

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

Tags: 力扣周赛

← leetcode conttest 301 2022 年度杭州未来科技城数字经济人才编程大赛 →

扫描二维码，分享此文章