Leetcode 第 391 场周赛题解

本文主要是介绍Leetcode 第 391 场周赛题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode 第 391 场周赛题解

题目1：3099. 哈沙德数

思路

模拟。

代码

/** @lc app=leetcode.cn id=3099 lang=cpp** [3099] 哈沙德数*/// @lc code=start
class Solution
{
private:int sumOfTheDigits(int x){int sum = 0;while (x){sum += x % 10;x /= 10;}return sum;}public:int sumOfTheDigitsOfHarshadNumber(int x){int dsum = sumOfTheDigits(x);if (x % dsum == 0)return dsum;return -1;}
};
// @lc code=end

复杂度分析

时间复杂度：O(logx)。

空间复杂度：O(1)。

题目2：3100. 换水问题 II

思路

模拟。

代码

/** @lc app=leetcode.cn id=3100 lang=cpp** [3100] 换水问题 II*/// @lc code=start
class Solution
{
public:int maxBottlesDrunk(int numBottles, int numExchange){// 一开始，把所有的满水瓶都喝掉int bottlesDrunk = numBottles; // 喝了多少瓶水int emptyBottles = numBottles; // 空水瓶数while (emptyBottles >= numExchange){// 用 numExchange 个空水瓶交换一个满水瓶emptyBottles -= numExchange;// 然后，将 numExchange 的值增加 1numExchange++;// 喝掉换的满水瓶bottlesDrunk++;emptyBottles++;}return bottlesDrunk;}
};
// @lc code=end

复杂度分析

时间复杂度：O(sqrt(numBottles))。

空间复杂度：O(1)。

题目3：3101. 交替子数组计数

思路

分组循环。

交替子数组的子数组一定是交替子数组，遍历数组 nums，分割出交替子数组。

假设当前交替子数组的长度为 len，那么这一段交替子数组总共有 len * (len + 1) / 2 个交替子数组，累加起来即为答案。

代码

/** @lc app=leetcode.cn id=3101 lang=cpp** [3101] 交替子数组计数*/// @lc code=start// 分组循环class Solution
{
public:long long countAlternatingSubarrays(vector<int> &nums){// 交替子数组的子数组一定是交替子数组int n = nums.size();long long ans = 0;int i = 0;while (i < n){int j = i + 1;while (j < n && nums[j] != nums[j - 1])j++;int len = j - i; // 当前交替子数组长度// 交替子数组的数量 = len * (len + 1) / 2ans += (long long)len * (len + 1) / 2;i = j;}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的元素个数。

空间复杂度：O(1)。

题目4：3102. 最小化曼哈顿距离

思路

题解：【图解】曼哈顿距离转切比雪夫距离（Python/Java/C++/Go）

将曼哈顿距离转化为切比雪夫距离。坐标轴旋转 45 度，原坐标 (x, y) 转换为 (x’, y’) = (x+y, y-x)。

曼哈顿距离 |x₁-x₂| + |y₁-y₂| = max(|x₁’-x₂’|, |y₁’-y₂’|)。

所以要求任意两点曼哈顿距离的最大值，根据上面的恒等式，我们只需要计算任意两个 (x’, y’) 切比雪夫距离的最大值，即横纵坐标差的最大值 max(max(x’) - min(x’), max(y’) - min(y’))。

本题可以删除一个点，我们可以枚举要删除的点，并用有序集合维护其它 n−1 个点的 x’ 和 y’ 的最大值和最小值。

代码

/** @lc app=leetcode.cn id=3102 lang=cpp** [3102] 最小化曼哈顿距离*/// @lc code=start
class Solution
{
public:int minimumDistance(vector<vector<int>> &points){multiset<int> xs, ys;for (vector<int> &point : points){// 曼哈顿距离 -> 切比雪夫距离xs.insert(point[0] + point[1]);ys.insert(point[1] - point[0]);}int ans = INT_MAX;for (auto &point : points){int x = point[0] + point[1], y = point[1] - point[0];xs.erase(xs.find(x));ys.erase(ys.find(y));int x_dis = *xs.rbegin() - *xs.begin();int y_dis = *ys.rbegin() - *ys.begin();ans = min(ans, max(x_dis, y_dis));xs.insert(x);ys.insert(y);}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(nlogn)，其中 n 是数组 points 的长度。

空间复杂度：O(n)，其中 n 是数组 points 的长度。

这篇关于Leetcode 第 391 场周赛题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---