leetcode 第 391 场算法比赛

零、背景

今天比赛最后一题是模版题，知道了就很简单。

A: 简单计算。
B: 简单模拟。
C: 数学公式。
D: 最大曼哈顿距离模版。

排名：160
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/3/391

一、哈沙德数

题意：问一个数字是否可以整除各位数字之和。

思路：先计算各位之和，然后判断是否可以整除。

int v = 0;
while(n) {
    v += n%10;
    n /= 10;
}

二、换水问题 II

题意：原先有 n 瓶水, K 个瓶子可以换一瓶水，之后 K 需要加一。问最终可以喝多少瓶水。

思路：按题意每次喝 K 瓶水再加一瓶水去模拟即可。

while( n>= k){
    ans += k;
    n = n - k + 1;
    k++;
}
ans += n;

三、交替子数组计数

题意：给一个二进制数组，问有多少个子数组是 01 交替出现的。

思路：数组分为几个最长的 01 交替子数组分组，这些分组的所有子数组都满足答案。

长度为 n 的分组，子数组个数为 C(n+1, 2)个。

四、最小化曼哈顿距离

题意：给 N 个坐标，问删除一个点后得到的所有最大曼哈顿距离离的最小值。

思路：先看如何求 n 个点的最大曼哈顿距离，然后再看如何把删除操作加进入。

假设有两点 (x0,y0) 和 (x1,y1)。
曼哈顿距离为 abs(x0-x1)+abs(y0-y1)。

如果把绝对值展开，则分为四种情况，蔓哈顿距离为四种情况的最大值。

+(x0-x1) + (y0-y1)
+(x0-x1) - (y0-y1)
-(x0-x1) - (y0-y1)
-(x0-x1) - (y0-y1)

分为两个坐标的关系，即如下

(x0+y0) - (x1+y1)
(x0-y0) - (x1-y1)
(-x0-y0) - (-x1-y1)
(-x0+y0) - (-x0+y1)

可以发现，四种情况两个坐标中 X 与 Y 的符号是相同的。

n 个坐标时，有 4N 个这样的公式，根据符号可以分为四组。
每一组的最大值显然是组内的最大值减去组内的最小值。

故可以对组内公式的值排序，从而得到每组内的最大值。
四组内的最大值中的最大值就是 n 个坐标的最大曼哈顿距离。

复杂度：n log(n)

模板可以参考这里： https://github.com/tiankonguse/leetcode-solutions/blob/master/doc/geometry/max_manhattan.cpp

现在题意要求删除一个元素，如何处理呢？

枚举删除的元素，每组内求最大值与最小值时，忽略删除的元素即可。

具体来说，看最大值是不是删除的元素，是了就用次大值代替最大值。
最小值也是相同的逻辑。

代码： https://github.com/tiankonguse/leetcode-solutions/blob/master/contest/3/391/D.cpp

五、最后

这次比赛最后一题是模板题，属于知道这个就可以通过，不知道就很难通过，没啥技术含量。

思考题：如何求最小曼哈顿距离呢？

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code