Leetcode 第 392 场周赛题解
- Leetcode 第 392 场周赛题解
- 题目1:3105. 最长的严格递增或递减子数组
- 思路
- 代码
- 复杂度分析
- 题目2:3106. 满足距离约束且字典序最小的字符串
- 思路
- 代码
- 复杂度分析
- 题目3:3107. 使数组中位数等于 K 的最少操作数
- 思路
- 代码
- 复杂度分析
- 题目4:3108. 带权图里旅途的最小代价
- 思路
- 代码
- 复杂度分析
Leetcode 第 392 场周赛题解
题目1:3105. 最长的严格递增或递减子数组
思路
动态规划。
代码
/*
* @lc app=leetcode.cn id=3105 lang=cpp
*
* [3105] 最长的严格递增或递减子数组
*/
// @lc code=start
class Solution
{
public:
int longestMonotonicSubarray(vector<int> &nums)
{
int n = nums.size();
vector<int> dp1(n, 1);
vector<int> dp2(n, 1);
for (int i = 1; i < n; i++)
{
if (nums[i] > nums[i - 1])
dp1[i] = max(dp1[i - 1] + 1, dp1[i]);
if (nums[i] < nums[i - 1])
dp2[i] = max(dp2[i - 1] + 1, dp2[i]);
}
return max(*max_element(dp1.begin(), dp1.end()), *max_element(dp2.begin(), dp2.end()));
}
};
// @lc code=end
复杂度分析
时间复杂度:O(n),其中 n 是数组 nums 的长度。
空间复杂度:O(n),其中 n 是数组 nums 的长度。
题目2:3106. 满足距离约束且字典序最小的字符串
思路
贪心。
为了使得修改后的字典序最小,我们从头开始遍历字符串 s,尽可能将当前字符 c 修改成 ‘a’。
我们定义一次操作为:将字符串 s 的一个字符 c 向前移动一位或向后移动一位。问题要求 distance(s, t) <= k,我们转化为:我们最多能进行 k 次上述操作。
因为字符 ‘a’ 到 ‘z’ 按循环顺序排列,所以字符 c 可以向左修改成 ‘a’,或者向右修改成 ‘a’:
- 向左修改,操作次数为:c - ‘a’。
- 向右修改,操作次数为:‘a’ + 26 - c。
我们当然是取其中的最小值作为我们的操作次数:minD = min(c - ‘a’, ‘a’ + 26 - c)。
算法:
遍历字符串 s,设当前字符为 c,它修改到 ‘a’ 的最小操作次数是 minD:
- 如果 k>=minD,说明该字符能修改到 ‘a’,将 c 修改成 ‘a’,k -= minD。
- 否则,为了修改后的字典序最小,我们将 c 向前移动 minD 位,将 c 修改成 c - minD,退出循环。
最后返回修改后的字符串 s。
代码
/*
* @lc app=leetcode.cn id=3106 lang=cpp
*
* [3106] 满足距离约束且字典序最小的字符串
*/
// @lc code=start
class Solution
{
public:
string getSmallestString(string s, int k)
{
// 特判
if (k == 0)
return s;
for (char &c : s)
{
if (c == 'a')
continue;
int minD = min(c - 'a', 'a' + 26 - c);
if (k >= minD)
{
c = 'a';
k -= minD;
}
else
{
c -= k;
break;
}
}
return s;
}
};
// @lc code=end
复杂度分析
时间复杂度:O(n),其中 n 是字符串 s 的长度。
空间复杂度:O(1)。
题目3:3107. 使数组中位数等于 K 的最少操作数
思路
排序 + 贪心。
题目要我们求将 nums 中位数变为 k 所需要的最少操作次数。
首先将数组 nums 排序,看看现在的中位数 median 是多少。
操作次数分为 3 部分:
- 将 median 修改成 k:操作次数 = abs(median - k)。
- 将 median 之前的大于 k 的元素修改成 k,操作次数 = sum(nums[i] - k)。
- 将 median 之后的小于 k 的元素修改成 k,操作次数 = sum(k - nums[i])。
三者之和就是答案。
代码
/*
* @lc app=leetcode.cn id=3107 lang=cpp
*
* [3107] 使数组中位数等于 K 的最少操作数
*/
// @lc code=start
class Solution
{
public:
long long minOperationsToMakeMedianK(vector<int> &nums, int k)
{
int n = nums.size();
sort(nums.begin(), nums.end());
int median = nums[n / 2];
// if (n % 2)
// median = nums[n / 2];
// else
// median = max(nums[n / 2 - 1], nums[n / 2]);
long long op = 0;
op += abs(median - k);
int i = n / 2 - 1;
while (i >= 0 && nums[i] > k)
{
op += nums[i] - k;
i--;
}
i = n / 2 + 1;
while (i < n && nums[i] < k)
{
op += k - nums[i];
i++;
}
return op;
}
};
// @lc code=end
复杂度分析
时间复杂度:O(nlogn),其中 n 是数组 nums 的长度。
空间复杂度:O(1)。
题目4:3108. 带权图里旅途的最小代价
思路
题解:两种方法:DFS / 并查集(Python/Java/C++/Go)
代码
DFS:
/*
* @lc app=leetcode.cn id=3108 lang=cpp
*
* [3108] 带权图里旅途的最小代价
*/
// @lc code=start
class Solution
{
vector<vector<pair<int, int>>> g;
vector<int> cc_and, ids;
int dfs(int x)
{
ids[x] = cc_and.size(); // 记录每个点所在连通块的编号
int and_ = -1; // 全为 1,性质:-1 & x = x
for (auto &[y, w] : g[x])
{
and_ &= w;
if (ids[y] < 0) // 没有访问过
and_ &= dfs(y);
}
return and_;
}
public:
vector<int> minimumCost(int n, vector<vector<int>> &edges, vector<vector<int>> &query)
{
g.resize(n);
for (auto &edge : edges)
{
int x = edge[0], y = edge[1], w = edge[2];
g[x].emplace_back(y, w);
g[y].emplace_back(x, w);
}
ids.resize(n, -1); // 记录每个点所在连通块的编号
for (int i = 0; i < n; i++)
{
if (ids[i] < 0) // 没有访问过
{
// 记录每个连通块的边权的 AND
cc_and.push_back(dfs(i));
}
}
vector<int> ans;
ans.reserve(query.size()); // 预分配空间
for (auto &q : query)
{
int s = q[0], t = q[1];
if (s == t)
ans.push_back(0);
else
ans.push_back(ids[s] != ids[t] ? -1 : cc_and[ids[s]]);
}
return ans;
}
};
// @lc code=end
并查集:
class Solution {
vector<int> fa, and_;
int find(int x) {
if (fa[x] != x) {
fa[x] = find(fa[x]);
}
return fa[x];
};
public:
vector<int> minimumCost(int n, vector<vector<int>> &edges, vector<vector<int>> &query) {
fa.resize(n);
iota(fa.begin(), fa.end(), 0);
and_.resize(n, -1);
for (auto &e: edges) {
int x = find(e[0]);
int y = find(e[1]);
and_[y] &= e[2];
if (x != y) {
and_[y] &= and_[x];
fa[x] = y;
}
}
vector<int> ans;
ans.reserve(query.size()); // 预分配空间
for (auto &q: query) {
int s = q[0], t = q[1];
ans.push_back(s == t ? 0 : find(s) != find(t) ? -1 : and_[find(s)]);
}
return ans;
}
};
复杂度分析
时间复杂度:O((n+m+q)logn),其中 n 是节点个数,m 是数组 edges 的长度,q 是数组 query 的长度。
空间复杂度:O(n),其中 n 是节点个数。