LeetCode---391周赛

题目列表

3099. 哈沙德数

3100. 换水问题 II

3101. 交替子数组计数

3102. 最小化曼哈顿距离

一、哈沙德数

简单的模拟题，代码如下

class Solution {
public:int sumOfTheDigitsOfHarshadNumber(int x) {int s = 0, tmp = x;while(tmp){s+=tmp%10;tmp/=10;}return x%s==0?s:-1;}
};

二、换水问题II

这题也是一个模拟题，我们只要维护好空瓶数和喝掉的瓶数，就能很容易得出答案。

代码如下

class Solution {
public:int maxBottlesDrunk(int numBottles, int numExchange) {int ans = numBottles; // 记录喝掉的瓶数int empty = numBottles; // 记录剩余空瓶子的数量while(empty>=numExchange){// 用numExchange个空瓶子换一瓶empty-=numExchange;empty++;numExchange++;ans++;}return ans;}
};

我们来简单算一下该模拟算法的时间复杂度，假设一开始有sum个瓶子，循环执行了n次，从numExchange=1开始，那么会有 1+2+3+...+n+n+1 <= sum + n，粗略的估算一下n^2<=sum，n<=sqrt(sum)，所以该算法是根号级的时间复杂度(甚至更优)，所以模拟算法也可以很快

三、交替子数组计数

这题我们可以统计以i为右端点符合条件的子数组个数【以i为右端点的符合条件的最长子数组中的元素个数=以i为右端点的符合条件的子数组个数】

代码如下

class Solution {
public:long long countAlternatingSubarrays(vector<int>& nums) {int n = nums.size();long long ans = n; // 单独一个0/1组成的子数组符合条件// 统计 长度>=2 的符合要求的子数组个数for(int i=0;i<n;){int j=i++;while(i<n&&nums[i-1]!=nums[i]){ans += i-j; // 统计以i为右端点的符合条件的子数组个数i++;}}return ans;}
};

四、最小化曼哈顿距离

（曼哈顿距离：|x1 - x2| + |y1 - y2|）

这题的关键在于如何快速的找到一堆点的最大曼哈顿距离。

从公式出发：

|x1 - x2| + |y1 - y2|

= max(x1-x2+y1-y2，x1-x2+y2-y1，x2-x1+y1-y2，x2-x1+y2-y1)

= max( (x1+y1) - (x2+y2)，(x1-y1) - (x2-y2)，(x2-y2) - (x1-y1)，(x2+y2) - (x1+y1))

= max( |(x1+y1) - (x2+y2)|，|(x1-y1) - (x2-y2)| )

很显然，只要维护好x+y和x-y的最大值和最小值，就能在O(1)的时间中得到最大的曼哈顿距离
代码如下

class Solution {
public:int minimumDistance(vector<vector<int>>& points) {multiset<int>s1,s2;for(auto&v:points){s1.insert(v[0]+v[1]);s2.insert(v[0]-v[1]);}int ans = INT_MAX;for(auto&v:points){s1.extract(v[0]+v[1]);s2.extract(v[0]-v[1]);ans=min(ans,max(*s1.rbegin()-*s1.begin(),*s2.rbegin()-*s2.begin()));s1.insert(v[0]+v[1]);s2.insert(v[0]-v[1]);}return ans;}
};