力扣第 391 场周赛

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int sumOfTheDigitsOfHarshadNumber(int x) 
    {
        int i=0;
        int m=x;
        int count=0;
        while(m)
        {
            count+=m%10;
            m/=10;
        }
        return x%count==0  ?  count  : -1;
    }
};

B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxBottlesDrunk(int numBottles, int numExchange) {
        int sum=numBottles;
        while(numBottles>=numExchange)
        {
            numBottles+=1;
            numBottles-=numExchange;
            numExchange++;
            sum+=1;
        }
    return sum;}
};

C

需要进行双指针，计算最右端的那个下标

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    long long countAlternatingSubarrays(vector<int>& nums) {
        int n = nums.size();
        long long ans = 0;
        for (int i = 0, j = 0; i < n; i++) 
        {
            if (i > 0 && nums[i] == nums[i - 1]) j = i;
            ans += i - j + 1;
        }
        return ans;
    }
};

D

作者：灵茶山艾府

主要知识点就是二维空间中的曼哈顿距离与切比雪夫距离

曼哈顿距离

定义

设平面空间内存在两点，它们的坐标为(𝑥1,𝑦1)(𝑥2,𝑦2)

则𝑑𝑖𝑠=|𝑥1−𝑥2|+|𝑦1−𝑦2|

切比雪夫距离

设平面空间内存在两点，它们的坐标为(𝑥1,𝑦1)(𝑥2,𝑦2)

则𝑑𝑖𝑠=𝑚𝑎𝑥(|𝑥1−𝑥2|,|𝑦1−𝑦2|)

即两点横纵坐标差的最大值

两者之间的关系

两者的定义看上去好像毛线关系都没有，但实际上，这两种距离可以相互转化！

我们考虑最简单的情况，在一个二维坐标系中，设原点为(0,0)

如果用曼哈顿距离表示，则与原点距离为1的点会构成一个边长为√2的正方形

如果用切比雪夫距离表示，则与原点距离为1的点会构成一个边长为2的正方形

将一个点\((x,y)\)的坐标变为\((x+y,x-y)\)后,原坐标系中的曼哈顿距离 \(=\) 新坐标系中的切比雪夫距离

将一个点\((x,y)\)的坐标变为\((\frac{x+y}{2},\frac{x-y}{2})\) 后,原坐标系中的切比雪夫距离 \(=\) 新坐标系中的曼哈顿距离

即两点横纵坐标差之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minimumDistance(vector<vector<int>> &points) {
        multiset<int> xs, ys;
        for (auto &p : points) {
            xs.insert(p[0] + p[1]);
            ys.insert(p[1] - p[0]);
        }
        int ans = INT_MAX;
        for (auto &p : points) {
            int x = p[0] + p[1], y = p[1] - p[0];
            xs.erase(xs.find(x));
            ys.erase(ys.find(y));
            ans = min(ans, max(*xs.rbegin() - *xs.begin(), *ys.rbegin() - *ys.begin()));
            xs.insert(x);
            ys.insert(y);
        }
        return ans;
    }
};