周赛 - 😺 第 82 场力扣夜喵双周赛 - 《学习笔记》

6116. 计算布尔二叉树的值
6117. 坐上公交的最晚时间
6118. 最小差值平方和
6119. 元素值大于变化阈值的子数组

对我来讲难度爆炸的一场，t2边界处理太麻烦了，做到后面属于是脑子不清楚了

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 。

思路：
后序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean evaluateTree(TreeNode root) {
        return dfs(root) == 1 ? true : false;
    }
    int dfs(TreeNode root) {
        if (root.val == 1 || root.val == 0)
            return root.val;
        int l = dfs(root.left);
        int r = dfs(root.right);
        if (root.val == 2)
            return l | r;
        else return l & r;
    }
}

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 中的元素 互不相同

思路：
贪心只要能坐到最后一辆公家车上即可
时间复杂度：O(n)

class Solution {
    public int latestTimeCatchTheBus(int[] b, int[] p, int c) {
        Arrays.sort(b);
        Arrays.sort(p);
        Set<Integer> set = new HashSet<>();
        for (int x : p)
            set.add(x);
        int s = 0, last = 0;
        for (int i = 0, j = 0; i < b.length; i++) {
            s = 0;
            while (j < p.length && p[j] <= b[i] && s < c) {
                last = p[j];
                j++;
                s++;
            }
        }
        int x = b[b.length - 1];
        if (s == c) x = last;
        while (set.contains(x))
            x--;
        return x;
    }
}

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

思路：
二分 + 贪心
时间复杂度：O(nlogn)

class Solution {
    public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {
        int n = nums1.length;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Math.abs(nums1[i] - nums2[i]);
        }
        long sum = 1L * k1 + k2;
        int l = 0, r = 100000;
        while (l < r) {
            int mid = l + r >> 1;
            long s = get(a, mid);
            if (s <= sum)
                r = mid;
            else
                l = mid + 1;
        }
        if (l == 0) return 0;
        long s = get(a, l);
        long minus = sum - s;
        long res = 0;
        for (int x : a) {
            if (x < l)
                res += 1L * x * x;
            else {
                if (minus > 0) {
                    res += 1L * (l - 1) * (l - 1);
                    minus--;
                } else res += 1L * l * l;
            }
        }
        return res;
    }
    long get(int[] a, int x) {
        long res = 0;
        for (int v : a) {
            if (v > x) res += v - x;
        }
        return res;
    }
}

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

思路：
单调栈
时间复杂度：O(n)

class Solution {
    public int validSubarraySize(int[] nums, int t) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            nums[i] = t / nums[i] + 1;
        }
        int[] stk = new int[n];
        int p = -1;
        int[] pre = new int[n], last = new int[n];
        for (int i = 0; i < n; i++) {
            while (p > -1 && nums[stk[p]] <= nums[i])
                p--;
            if (p == -1) pre[i] = -1;
            else pre[i] = stk[p];
            stk[++p] = i;
        }
        p = -1;
        for (int i = n - 1; i >= 0; i--) {
            while (p > -1 && nums[stk[p]] <= nums[i])
                p--;
            if (p == -1) last[i] = n;
            else last[i] = stk[p];
            stk[++p] = i;
        }
        for (int i = 0; i < n; i++) {
            if (last[i] - pre[i] - 1 >= nums[i])
                return nums[i];
        }
        return -1;
    }
}