LeetCode Contest 391

100263. Harshad Number

如果一个整数能够被其各个数位上的数字之和整除，则称之为 哈沙德数（Harshad number）。给你一个整数 x 。如果 x 是 哈沙德数 ，则返回 x 各个数位上的数字之和，否则，返回 -1 。

测试样例：

输入：18

输出：9

解释：x 各个数位上的数字之和为 9 。18 能被 9 整除。因此 18 是哈沙德数，答案是 9 。

解答：按照题意计算。

class Solution {
    public int sumOfTheDigitsOfHarshadNumber(int x) {
        String t = String.valueOf(x);
        int add = 0;
        for (int i = 0; i < t.length(); ++i) {
            add += (t.charAt(i) - '0');
        }
        return x % add == 0 ? add : -1;
    }
}

100235. Water Bottles II

给你两个整数 numBottles 和 numExchange 。

numBottles 代表你最初拥有的满水瓶数量。在一次操作中，你可以执行以下操作之一：

• 喝掉任意数量的满水瓶，使它们变成空水瓶。
• 用 numExchange 个空水瓶交换一个满水瓶。然后，将 numExchange 的值增加 1 。

注意，你不能使用相同的 numExchange 值交换多批空水瓶。例如，如果 numBottles == 3 并且 numExchange == 1 ，则不能用 3 个空水瓶交换成 3 个满水瓶。

返回你 最多 可以喝到多少瓶水。

测试样例：

输入：numBottles = 13, numExchange = 6

输出：15

解释：上表显示了满水瓶的数量、空水瓶的数量、numExchange 的值，以及累计喝掉的水瓶数量。

解答：范围不大，按照题意暴力计算。

class Solution {
    public int maxBottlesDrunk(int numBottles, int numExchange) {
        int emptyBottles = 0;
        int res = 0;
        while (true) {
            res += numBottles;
            emptyBottles += numBottles;
            numBottles = 0;
            if (emptyBottles < numExchange) {
                break;
            }
            while (emptyBottles >= numExchange) {
                ++numBottles;
                emptyBottles -= numExchange;
                ++numExchange;
            }
        }
        return res;
    }
}

100266. Count Alternating Subarrays

给你一个二进制数组 nums 。

如果一个子数组中 不存在 两个 相邻 元素的值 相同 的情况，我们称这样的子数组为 交替子数组 。

返回数组 nums 中交替子数组的数量。

测试样例：

输入：nums = [0,1,1,1]

输出：5

解释：以下子数组是交替子数组：[0] 、[1] 、[1] 、[1] 以及 [0,1] 。

解答：碰到两个相邻数字相同时，累和截断变成1，否则不断累和。并且增加一个long res对象，累和累和。

class Solution {
    public long countAlternatingSubarrays(int[] nums) {
        long res = 0;
        int add = 0, last = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] != last) {
                ++add;
            } else {
                add = 1;
            }
            res += add;
            last = nums[i];
        }
        return res;
    }
}

100240. Minimize Manhattan Distances

给你一个下标从 0 开始的数组 points ，它表示二维平面上一些点的整数坐标，其中 points[i] = [xi, yi] 。

两点之间的距离定义为它们的曼哈顿距离。

请你恰好移除一个点，返回移除后任意两点之间的 最大 距离可能的 最小 值。

测试样例：

输入：points = [[3,10],[5,15],[10,2],[4,4]]

输出：12

解释：移除每个点后的最大距离如下所示：

• 移除第 0 个点后，最大距离在点 (5, 15) 和 (10, 2) 之间，为 |5 - 10| + |15 - 2| = 18 。
• 移除第 1 个点后，最大距离在点 (3, 10) 和 (10, 2) 之间，为 |3 - 10| + |10 - 2| = 15 。
• 移除第 2 个点后，最大距离在点 (5, 15) 和 (4, 4) 之间，为 |5 - 4| + |15 - 4| = 12 。
• 移除第 3 个点后，最大距离在点 (5, 15) 和 (10, 2) 之间的，为 |5 - 10| + |15 - 2| = 18 。

在恰好移除一个点后，任意两点之间的最大距离可能的最小值是 12 。

解答：这道题目的关键是要明白：|Xi – Xj| + |Yi – Yj| = max((Xi – Yi) – (Xj – Yj), (-Xi + Yi) – (-Xj + Yj), (-Xi – Yi) – (-Xj – Yj), (Xi + Yi) – (Xj + Yj))。只要寻找到max(xi + y1), min(xi + y1), max(xi - y1), min(xi - y1)，四个位置，然后计算去掉这四个位置之后的最小值就行了。

class Solution {
    public int minimumDistance(int[][] points) {
        int len = points.length;
        int[] sum = new int[len], diff = new int[len];
        for (int i = 0; i < points.length; ++i) {
            sum[i] = points[i][0] + points[i][1];
            diff[i] = points[i][0] - points[i][1];
        }
        int[] removeCand = findPos(sum, diff);
        int res = Integer.MAX_VALUE;
        for (int n : removeCand) {
            res = Math.min(res, minimumDistance(sum, diff, n));
        }
        return res;
    }

    private int[] findPos(int[] sum, int[] diff) {
        int minsum, maxsum, mindiff, maxdiff;
        minsum = maxsum = 0;
        mindiff = maxdiff = 0;
        for (int i = 1; i < sum.length; i++) {
            if (sum[i] < sum[minsum]){
                minsum = i;
            } else if (sum[i] > sum[maxsum]){
                maxsum = i;
            }

            if (diff[i] < diff[mindiff]) {
                mindiff = i;
            }
            else if (diff[i] > diff[maxdiff]) {
                maxdiff = i;
            }
        }
        return new int[]{minsum, maxsum, mindiff, maxdiff};
    }

    private int minimumDistance(int[] sum, int[] diff, int skip) {
        int minsum = Integer.MAX_VALUE, maxsum = Integer.MIN_VALUE, mindiff = Integer.MAX_VALUE, maxdiff = Integer.MIN_VALUE;
        for (int i = 0; i < sum.length; ++i) {
            if (i == skip) continue;
            if (sum[i] < minsum) {
                minsum = sum[i];
            }
            if (sum[i] > maxsum) {
                maxsum = sum[i];
            }

            if (diff[i] < mindiff) {
                mindiff = diff[i];
            }
            if (diff[i] > maxdiff) {
                maxdiff = diff[i];
            }
        }
        return Math.max(maxsum - minsum, maxdiff - mindiff);
    }
}