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;
    }
};