leetcode contest 312

周赛题目质量不错的一次，不过排名也100往后了，还是思路不够快。

6188. 按身高排序

题目

给你一个字符串数组 names ，和一个由互不相同的正整数组成的数组 heights 。两个数组的长度均为 n 。

对于每个下标 i，names[i] 和 heights[i] 表示第 i 个人的名字和身高。

请按身高降序顺序返回对应的名字数组 names 。

示例 1：

输入：names = ["Mary","John","Emma"], heights = [180,165,170]
输出：["Mary","Emma","John"]
解释：Mary 最高，接着是 Emma 和 John 。

示例 2：

输入：names = ["Alice","Bob","Bob"], heights = [155,185,150]
输出：["Bob","Alice","Bob"]
解释：第一个 Bob 最高，然后是 Alice 和第二个 Bob 。

提示：

n == names.length == heights.length
1 <= n <= 103
1 <= names[i].length <= 20
1 <= heights[i] <= 105
names[i] 由大小写英文字母组成
heights 中的所有值互不相同

地址

https://leetcode.cn/contest/weekly-contest-312/problems/sort-the-people/

题意

排序

思路

按照题目要求进行排序即可。
复杂度分析：

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

代码

class Solution {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        vector<pair<string, int>> arr;
        for (int i = 0; i < names.size(); i++) {
            arr.emplace_back(names[i], heights[i]);
        }
        sort(arr.begin(), arr.end(), [](const pair<string, int> &a, const pair<string, int> &b) {
           return a.second > b.second; 
        });
        vector<string> ans;
        for (auto [name, _] : arr) {
            ans.emplace_back(name);
        }
        return ans;
    }
};

6189. 按位与最大的最长子数组

题目

给你一个长度为 n 的整数数组 nums 。

考虑 nums 中进行按位与（bitwise AND）运算得到的值最大的非空子数组。

换句话说，令 k 是 nums 任意子数组执行按位与运算所能得到的最大值。那么，只需要考虑那些执行一次按位与运算后等于 k 的子数组。
返回满足要求的最长子数组的长度。

数组的按位与就是对数组中的所有数字进行按位与运算。

子数组是数组中的一个连续元素序列。

示例 1：

输入：nums = [1,2,3,3,2,2]
输出：2
解释：
子数组按位与运算的最大值是 3 。
能得到此结果的最长子数组是 [3,3]，所以返回 2 。

示例 2：

输入：nums = [1,2,3,4]
输出：1
解释：
子数组按位与运算的最大值是 4 。 
能得到此结果的最长子数组是 [4]，所以返回 1 。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 106

地址

https://leetcode.cn/contest/cnunionpay2022/problems/6olJmJ/

题意

数学

思路

连续子数组与运算的最大值即为数组的最大值 $maxV$，数组的最大值与上任何元素的结果均小于等于它本身，因此我们的目标即为找到连续 $maxV$ 的最大长度即可。
复杂度分析：

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

代码

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int n = nums.size();
        int ans = 1;
        int maxN = *max_element(nums.begin(), nums.end());
        int i = 0;
        while (i < n) {
            if (nums[i] == maxN) {
                int tot = 0;
                while (i < n && nums[i] == maxN) {
                    i++;
                    tot++;
                }
                ans = max(ans, tot);
            }
            i++;
        }
        return ans;
    }
};

6190. 找到所有好下标

题目

给你一个大小为 n 下标从 0 开始的整数数组 nums 和一个正整数 k 。

对于 k <= i < n - k 之间的一个下标 i ，如果它满足以下条件，我们就称它为一个好下标：

下标 i 之前的 k 个元素是非递增的。
下标 i 之后的 k 个元素是非递减的。
按升序返回所有好下标。

示例 1：

输入：nums = [2,1,1,1,3,4,1], k = 2
输出：[2,3]
解释：数组中有两个好下标：
- 下标 2 。子数组 [2,1] 是非递增的，子数组 [1,3] 是非递减的。
- 下标 3 。子数组 [1,1] 是非递增的，子数组 [3,4] 是非递减的。
注意，下标 4 不是好下标，因为 [4,1] 不是非递减的。

示例 2：

输入：nums = [2,1,1,2], k = 2
输出：[]
解释：数组中没有好下标。

提示：

n == nums.length
3 <= n <= 105
1 <= nums[i] <= 106
1 <= k <= n / 2

地址

https://leetcode.cn/contest/weekly-contest-312/problems/find-all-good-indices/

题意

滑动窗口

思路

题目本身比较简单，对于每个位置的 $i$，我们找到 $i$ 的左侧连续非递增的最大长度为 $left[i]$，我们找到 $i$ 的右侧连续非递减的最大长度为 $right[i]$，对于每个索引 $i$ 处，只需要满足：
$$
left[i-1] >= k, right[i+1] >= k
$$
则索引 $i$ 即可满足要求。
复杂度分析

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

代码

class Solution {
public:
    vector<int> goodIndices(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> left(n, 1), right(n, 1);
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i-1]) {
                left[i] = 1;
            } else {
                left[i] = left[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] > nums[i+1]) {
                right[i] = 1;
            } else {
                right[i] = right[i + 1] + 1;
            }
        }
        vector<int> ans;
        for (int i = k; i < n - k; i++) {
            if (left[i - 1] >= k && right[i + 1] >= k) {
                ans.emplace_back(i);
            }
        }
        return ans;
    }
};

6191. 好路径的数目

题目

给你一棵 n 个节点的树（连通无向无环的图），节点编号从 0 到 n - 1 且恰好有 n - 1 条边。

给你一个长度为 n 下标从 0 开始的整数数组 vals ，分别表示每个节点的值。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条无向边。

一条好路径需要满足以下条件：

开始节点和结束节点的值相同。
开始节点和结束节点中间的所有节点值都小于等于开始节点的值（也就是说开始节点的值应该是路径上所有节点的最大值）。
请你返回不同好路径的数目。
注意，一条路径和它反向的路径算作同一路径。比方说， 0 -> 1 与 1 -> 0 视为同一条路径。单个节点也视为一条合法路径。

示例 1：

输入：vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]]
输出：6
解释：总共有 5 条单个节点的好路径。
还有 1 条好路径：1 -> 0 -> 2 -> 4 。
（反方向的路径 4 -> 2 -> 0 -> 1 视为跟 1 -> 0 -> 2 -> 4 一样的路径）
注意 0 -> 2 -> 3 不是一条好路径，因为 vals[2] > vals[0] 。

示例 2：

输入：vals = [1,1,2,2,3], edges = [[0,1],[1,2],[2,3],[2,4]]
输出：7
解释：总共有 5 条单个节点的好路径。
还有 2 条好路径：0 -> 1 和 2 -> 3 。

示例 3：

输入：vals = [1], edges = []
输出：1
解释：这棵树只有一个节点，所以只有一条好路径。

提示：

n == vals.length
1 <= n <= 3 * 104
0 <= vals[i] <= 105
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges 表示一棵合法的树。

地址

https://leetcode.cn/contest/weekly-contest-312/problems/number-of-good-paths/

题意

排序 + 加并查集

思路

题目出的还可以，稍微有点思考难度。两点之间是否存在路径，最优先考虑到的是并查集，如果两个节点在同一个子集下，则两点之间一定存在路径，为了保证两点 $(a,b)$ 之间的路径上的节点值都满足小于等于 $vals[a],vals[b]$，则此时我们应当只把节点值小于 $vals[a]$ 的节点加入到并查集中，因此我们可以首先进行排序，按照每条边的节点值的最大值进行排序。
我们每次遍历当前节点值为 $x$ 时，我们将所有的边中的两个节点值都小于 $x$ 的边加入到并查集中，因为此时大于 $x$ 的边加入到并查集中无效，因为此时无法使用该条边。
对于对一个子集中且节点值相同的节点数目为 $cnt$，则此时可以构造题目要求的节点对的数目为 $\dfrac{cnt * (cnt + 1)}{2}$，因此我们将所有可能的节点对的数目相加即可。
复杂度分析：

时间复杂度：$O(m \log m + n \times \alpha(n))$，其中 $m$ 表示边的数目，$n$ 表示节点的数目。
空间复杂度：$O(n)$，$n$ 表示节点的数目。

代码

namespace data_structure
{
	// DisjointSet implements a (0-indexed) disjoint set. 
	class DisjointSet
	{
	private:
		int n;
		std::vector<int> parent, size;
	public:
		explicit DisjointSet(int n) : n(n), 
			parent(n), size(n)
		{
			Reset();
		}
		void Reset()
		{
			for (int x = 0; x < n; ++x)
			{
				parent[x] = x;
				size[x] = 1;
			}
		}
		// Find the representative of x.
		int Find(int x)
		{
			return parent[x] == x ? x : parent[x] = Find(parent[x]);
		}
		// Return the size of component of x.
		int Size(int x)
		{
			return size[Find(x)];
		}
		// Union x and y.
		void Union(int x, int y)
		{
			x = Find(x);
			y = Find(y);
			if (x != y)
			{
				if (size[x] > size[y]) std::swap(x, y);
				size[y] += size[x];
				parent[x] = y;
			}
		}
		// Union x into y
		void UnionOblivious(int x, int y)
		{
			x = Find(x);
			y = Find(y);
			if (x != y)
			{
				size[y] += size[x];
				parent[x] = y;
			}
		}
	};
}

class Solution {
public:
    
    int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
        int n = vals.size();
        map<int, vector<int>> cnt;
        for (int i = 0; i < n; i++) {
            cnt[vals[i]].emplace_back(i);
        }
        sort(edges.begin(), edges.end(), [&](const vector<int> &a, const vector<int> &b) {
           return max(vals[a[0]], vals[a[1]]) <  max(vals[b[0]], vals[b[1]]);
        });
        long long ans = n;
        data_structure::DisjointSet djset(n);
        int j = 0;
        for (auto [val, vec] : cnt) {
            while (j < edges.size() && vals[edges[j][0]] <= val && vals[edges[j][1]] <= val) {
                djset.Union(edges[j][0], edges[j][1]);
                j++;
            }
            unordered_map<int,int> count;
            for (int i = 0; i < vec.size(); i++) {
                count[djset.Find(vec[i])]++;
            }
            for (auto [_, v] : count) {
                ans += v * (v - 1) / 2;
            }
        }
        return ans;
    }
};

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

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

Tags: 力扣周赛

← leetcode weekly contest 316 中国银联专场竞赛（2023届校园招聘专场） →

扫描二维码，分享此文章