leetcode第 381 场周赛最后一题差分，对称的处理-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode第 381 场周赛最后一题差分，对称的处理。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

第 381 场周赛 - 力扣（LeetCode）最后一题3017. 按距离统计房屋对数目 II - 力扣（LeetCode）

dijkstra超时了，看了灵神的解题方法力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台，其实是差分优化的暴力统计

灵神说的“撤销操作”，就是先不加那条xy新路，统计出所有距离对数，然后再加上那条路做修改。做修改需要推一下变短的位置。

灵神封装写的特别好，这道题不封装一下，有问题改起来很麻烦。

统计原始距离对数：

找规律：

灵神暴力左右：

差分：

做修改：

第一种：

第二种：

关于小于区间右端点(x+y)/2：(等于过不了)

当 x==y 及x == y+1时没有缩短任何距离。不需要操作

参考代码：

统计原始距离对数：

这里说两种方法，第一种是自己想的找规律（其实踩坑了，没弄好差分），第二种就是灵神暴力，时间复杂度是相同的O(n)

找规律：

分别对奇数和偶数找一下：

第一行1 2 3 4 5五个数是题目里的房屋，左边第一列是距离 t，表中的则是与这个房屋距离为t的房屋数。

我们暴力完成这个表。

比如第一行，对1来说距离为1的只有2一个，所以是1；对2来说距离为1的是1和3，即两个。

会发现每一行会比前一行少2，而第一行也是“1 2 2 .. 2 2 1”可以列式算出来，所以可以距离为1到n的房屋对数数组（我们要返回的数组）给初始化。

        //      1 2 3 4 5
        //1:    1 2 2 2 1   //2就算最多啦
        //2:    1 1 2 1 1   //-2
        //3:    1 1 0 1 1   //-2
        //4:    1 0 0 0 1   //-2
        //5:    0 0 0 0 0   //-2 这个要减成0

        //      1 2 3 4 5 6
        //1:    1 2 2 2 2 1
        //2:    1 1 2 2 1 1     //-2
        //3:    1 1 1 1 1 1     //-2
        //4:    1 1 0 0 1 1     //-2
        //5:    1 0 0 0 0 1     //-2
        //6:    0 0 0 0 0 0     //-2

注意：

房屋数为n的情况下，不存在距离为n的房屋对（最大也是1和n之间差n-1），所以返回数组最后一位必定是0.

灵神暴力左右：

对于房屋 i ，距离为1的就是 i-1 和 i+1 ，距离为2的就是 i-2 和 i+2 ，......

一直到两边，可得左侧距离最大为i-1，右侧为n-i，

所以距离为 1 ~ i -1 的都要加一对，距离为 1 ~ n - i 的也都要加一对

差分：

而我们正好用的是差分数组。差分就是第一位为初始值，后面的都表示和前一位相差的值。对这种连续的情况，用差分是秒算的。

做修改：

首先看情况，其实就四种会变短，而这四种是对称的，也就是说其实就两种情况。

我们 i 为始点，j为终点，(x，y)为新增的路，我们让x<y。