leetcode biweekly contes 113

这次的双周赛题目还算不错，确实不太难的题目，比拼的还是手速场。

8039. 使数组成为递增数组的最少右移次数

给你一个长度为 n 下标从 0 开始的数组 nums ，数组中的元素为 互不相同 的正整数。请你返回让 nums 成为递增数组的 最少右移 次数，如果无法得到递增数组，返回 -1 。

一次右移指的是同时对所有下标进行操作，将下标为 i 的元素移动到下标 (i + 1) % n 处。

示例 1：

输入：nums = [3,4,5,1,2]
输出：2
解释：
第一次右移后，nums = [2,3,4,5,1] 。
第二次右移后，nums = [1,2,3,4,5] 。
现在 nums 是递增数组了，所以答案为 2 。

示例 2：

输入：nums = [1,3,5]
输出：0
解释：nums 已经是递增数组了，所以答案为 0 。

示例 3：

输入：nums = [2,1,4]
输出：-1
解释：无法将数组变为递增数组。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100
nums 中的整数互不相同。

地址

https://leetcode.cn/contest/weekly-contest-363/problems/sum-of-values-at-indices-with-k-set-bits/

题意

直接模拟

思路

检测数组是否为循环递增数组，假设数组的长度为 $n$，即找到是否存在索引 $i$ 满足:
- $[0,i-1]$ 之间数组为递增，$[i,n-1]$ 之间数组递增，且满足 $nums[n-1] < nums[0]$；
- 是否满足将数组 $nums$ 循环移动 $x$ 位置后数组变为递增；
复杂度分析：

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

代码

[sol1-C++]

class Solution {
public:
    int minimumRightShifts(vector<int>& nums) {
        int last = -1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < nums[i - 1]) {
                last = i;
                break;
            }
        }
        if (last < 0) return 0;
        for (int i = last; i < nums.size(); i++) {
            if (nums[i] > nums[0]) return -1;
            if (i + 1 < nums.size()) {
                if (nums[i + 1] < nums[i]) {
                    return -1;
                }
            }
        }
        return nums.size() - last;
    }
};

2856. 删除数对后的最小数组长度

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

你可以执行以下操作任意次：

选择两个下标 i 和 j ，满足 i < j 且 nums[i] < nums[j] 。
将 nums 中下标在 i 和 j 处的元素删除。剩余元素按照原来的顺序组成新的数组，下标也重新从 0 开始编号。

请你返回一个整数，表示执行以上操作任意次后（可以执行 0 次），nums 数组的最小数组长度。

示例 1：

输入：nums = [1,3,4,9]
输出：0
解释：一开始，nums = [1, 3, 4, 9] 。
第一次操作，我们选择下标 0 和 1 ，满足 nums[0] < nums[1] <=> 1 < 3 。
删除下标 0 和 1 处的元素，nums 变成 [4, 9] 。
下一次操作，我们选择下标 0 和 1 ，满足 nums[0] < nums[1] <=> 4 < 9 。
删除下标 0 和 1 处的元素，nums 变成空数组 [] 。
所以，可以得到的最小数组长度为 0 。

示例 2：

输入：nums = [2,3,6,9]
输出：0
解释：一开始，nums = [2, 3, 6, 9] 。
第一次操作，我们选择下标 0 和 2 ，满足 nums[0] < nums[2] <=> 2 < 6 。
删除下标 0 和 2 处的元素，nums 变成 [3, 9] 。
下一次操作，我们选择下标 0 和 1 ，满足 nums[0] < nums[1] <=> 3 < 9 。
删除下标 0 和 1 处的元素，nums 变成空数组 [] 。
所以，可以得到的最小数组长度为 0 。

示例 3：

输入：nums = [1,1,2]
输出：1
解释：一开始，nums = [1, 1, 2] 。
第一次操作，我们选择下标 0 和 2 ，满足 nums[0] < nums[2] <=> 1 < 2 。
删除下标 0 和 2 处的元素，nums 变成 [1] 。
无法对数组再执行操作。
所以，可以得到的最小数组长度为 1 。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109
nums 是 非递减 数组。

地址

https://leetcode.cn/contest/biweekly-contest-113/problems/minimum-array-length-after-pair-removals/

题意

数学题目

思路

最简单的做法每次选取频次最高的两个数进行配对，最后知道剩下的即可，另一种数学方法，假设当前数组的长度为 $n$，此时出现次数最多的元素为 $nums[i]$, 出现的次数为 $x$，
- 如果 $2x > n$, 即 $x$ 出现的次数超过数组的长度的一半，此时超出 $n -x$ 的部分无法配对，此时可以配对的次数为 $n - x$ 次，剩余 $n - 2(n-x) = 2x - n$；
- 如果 $2x \le n$:
  - 如果 $n$ 为偶数则一定可以完成配对；
  - 如果 $n$ 为奇数则一定存在一个元素无法完成配对；
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 为数组的长度。
空间复杂度：$O(n)$，其中 $n$ 为数组的长度。

代码

class Solution {
public:
    int minLengthAfterRemovals(vector<int>& nums) {
        int ans = nums.size();
        unordered_map<int, int> cnt;
        for (auto v : nums) cnt[v]++;
        vector<int> arr;
        for (auto [k, v] : cnt) {
            arr.emplace_back(v);
        }
        
        priority_queue<int, vector<int>, less<int>> pq(arr.begin(), arr.end());
        while (pq.size() > 1) {
            int x = pq.top();
            pq.pop();
            int y = pq.top();
            pq.pop();
            x--;
            y--;
            ans -= 2;
            if (x > 0) pq.emplace(x);
            if (y > 0) pq.emplace(y);
        }
        
        return ans;
    }
};

class Solution {
public:
    int minLengthAfterRemovals(vector<int> &nums) {
        int n = nums.size();
        int x = nums[n / 2];
        int max_cnt = upper_bound(nums.begin(), nums.end(), x) -
                      lower_bound(nums.begin(), nums.end(), x);
        return max(max_cnt * 2 - n, n % 2);
    }
};

6988. 统计距离为 k 的点对

给你一个二维整数数组 coordinates 和一个整数 k ，其中 coordinates[i] = [xi, yi] 是第 i 个点在二维平面里的坐标。

我们定义两个点 (x1, y1) 和 (x2, y2) 的距离为 (x1 XOR x2) + (y1 XOR y2) ，XOR 指的是按位异或运算。

请你返回满足 i < j 且点 i 和点 j之间距离为 k 的点对数目。

示例 1：

输入：coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5
输出：2
解释：以下点对距离为 k ：
- (0, 1)：(1 XOR 4) + (2 XOR 2) = 5 。
- (2, 3)：(1 XOR 5) + (3 XOR 2) = 5 。

示例 2：

输入：coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0
输出：10
解释：任何两个点之间的距离都为 0 ，所以总共有 10 组点对。

提示：

2 <= coordinates.length <= 50000
0 <= xi, yi <= 106
0 <= k <= 100

地址

https://leetcode.cn/contest/biweekly-contest-113/problems/count-pairs-of-points-with-distance-k/

题意

枚举

思路

题目初看起来貌似很难，但是关键在于 $k \in[0,100]$, $k$ 的取值范围非常小，所以导致题目就不是很难了。根据公式可以知道：

$$k = a \oplus x + b \oplus y$$，当然我们直接求 $a,b$ 比较困难，但是我们知道 $k= 100$，则此时假设 $a\oplus x = c$，则 $b \oplus y = 100 -c$，由于 $k$ 的范围非常小我们直接枚举 $c$ 的取值，则此时 $a = c \oplus x, b = y \oplus (100 - c)$, 此时我们即可知道另一个点的取值，此时我们利用哈希统计当前值为 $(a,b)$ 的点的数量，依次统计即可。
复杂度分析：

时间复杂度：$O(nk)$，其中 $n$ 表示数组的长度，$k$ 表示给定的元素；
空间复杂度：$O(n)$，其中 $n$ 表示数组的长度；

代码

class Solution {
public:
    int countPairs(vector<vector<int>>& coordinates, int k) {
        int n = coordinates.size();
        unordered_map<long long, int> cnt;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            long long x = coordinates[i][0];
            long long y = coordinates[i][1];
            for (int j = 0; j <= k; j++) {
                long long a = x ^ j;
                long long b = y ^ (k - j);
                long long key = (a << 32) + b;
                if (cnt.count(key)) {
                    ans += cnt[key];
                }
            }
            cnt[(x << 32) + y]++;
        }
        return ans;
    }
};

100041. 可以到达每一个节点的最少边反转次数

给你一个 n 个点的 简单有向图 （没有重复边的有向图），节点编号为 0 到 n - 1 。如果这些边是双向边，那么这个图形成一棵树。

给你一个整数 n 和一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示从节点 ui 到节点 vi 有一条 有向边 。

边反转 指的是将一条边的方向反转，也就是说一条从节点 ui 到节点 vi 的边会变为一条从节点 vi 到节点 ui 的边。

对于范围 [0, n - 1] 中的每一个节点 i ，你的任务是分别独立计算最少需要多少次 边反转 ，从节点 i 出发经过 一系列有向边 ，可以到达所有的节点。

请你返回一个长度为 n 的整数数组 answer ，其中 answer[i]表示从节点 i 出发，可以到达所有节点的 最少边反转 次数。

示例 1：

输入：n = 4, edges = [[2,0],[2,1],[1,3]]
输出：[1,1,0,2]
解释：上图表示了与输入对应的简单有向图。
对于节点 0 ：反转 [2,0] ，从节点 0 出发可以到达所有节点。
所以 answer[0] = 1 。
对于节点 1 ：反转 [2,1] ，从节点 1 出发可以到达所有节点。
所以 answer[1] = 1 。
对于节点 2 ：不需要反转就可以从节点 2 出发到达所有节点。
所以 answer[2] = 0 。
对于节点 3 ：反转 [1,3] 和 [2,1] ，从节点 3 出发可以到达所有节点。
所以 answer[3] = 2 。

示例 2：

输入：n = 3, edges = [[1,2],[2,0]]
输出：[2,0,1]
解释：上图表示了与输入对应的简单有向图。
对于节点 0 ：反转 [2,0] 和 [1,2] ，从节点 0 出发可以到达所有节点。
所以 answer[0] = 2 。
对于节点 1 ：不需要反转就可以从节点 2 出发到达所有节点。
所以 answer[1] = 0 。
对于节点 2 ：反转 [1,2] ，从节点 2 出发可以到达所有节点。
所以 answer[2] = 1 。

提示：

2 <= n <= 105
edges.length == n - 1
edges[i].length == 2
0 <= ui == edges[i][0] < n
0 <= vi == edges[i][1] < n
ui != vi
输入保证如果边是双向边，可以得到一棵树。

地址

https://leetcode.cn/contest/biweekly-contest-112/problems/count-k-subsequences-of-a-string-with-maximum-beauty/

题意

换根 dp

思路

题目还是经典的题目变形，跟「834. 树中距离之和」基本类似的题目，
- 首先我们统计以 $0$ 点为根时需要反转的次数，这个就用简单的 $dfs$ 即可，即统计当前从孩子节点指向父亲节点的边的数目，总的数目为 $tot$；
- 其次我们从 $0$ 点开始依次遍历每个节点 $x$，此时我们只需要反装从 $0$ 到 $x$ 这条路径上的边即可，其余的边保证不再反转即可，
  - 此时如果当前的边是孩子节点指向父亲节点的边，则此时反转的边的数目减 $1$, 即 $tot-1$；
  - 此时如果当前的边是父亲节点指向孩子节点的边，则此时反转的边的数目加 $1$, 即 $tot+1$；
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 表示节点的数目。
空间复杂度：$O(n)$，其中 $n$ 表示节点的数目。

代码

class Solution {
public:
    vector<int> minEdgeReversals(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        vector<unordered_set<int>> cnt(n);
        for (auto e : edges) {
            graph[e[0]].emplace_back(e[1]);
            graph[e[1]].emplace_back(e[0]);
            cnt[e[0]].emplace(e[1]);
        }
       
        function<int(int, int)> dfs1 = [&](int root, int parent) -> int {
            int res = 0;
            for (auto v : graph[root]) {
                if (v == parent) continue;
                res += dfs1(v, root);
                if (cnt[v].count(root)) res++;
            }
            return res;
        };
        
        int tot = dfs1(0, -1);
         vector<int> ans(n);
        function<void(int, int, int)> dfs2 = [&](int root, int parent, int tot) {
            ans[root] = tot;
            for (auto v : graph[root]) {
                if (v == parent) continue;
                if (cnt[v].count(root)) {
                    dfs2(v, root, tot - 1);
                } else {
                    dfs2(v, root, tot + 1);
                }
            }
        };
        dfs2(0, -1, tot);
        
        return ans;
    }
};

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

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

Tags: 题解力扣周赛赛

← leetcode biweekly contes 112 leetcode biweekly contes 363 →

扫描二维码，分享此文章