net网站建设多少前,怎么建设网站平台,做网站诊断步骤,怎么把淘宝店放到自己做的网站去第 381 场周赛 - 力扣#xff08;LeetCode#xff09;最后一题3017. 按距离统计房屋对数目 II - 力扣#xff08;LeetCode#xff09;
dijkstra超时了#xff0c;看了灵神的解题方法力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台#xff0c;其…第 381 场周赛 - 力扣LeetCode最后一题3017. 按距离统计房屋对数目 II - 力扣LeetCode
dijkstra超时了看了灵神的解题方法力扣LeetCode官网 - 全球极客挚爱的技术成长平台其实是差分优化的暴力统计
灵神说的“撤销操作”就是先不加那条xy新路统计出所有距离对数然后再加上那条路做修改。做修改需要推一下变短的位置。
灵神封装写的特别好这道题不封装一下有问题改起来很麻烦。
目录
统计原始距离对数
找规律
灵神暴力左右
差分
做修改
第一种
第二种
关于小于区间右端点(xy)/2(等于过不了)
当 xy 及x y1时没有缩短任何距离。不需要操作
参考代码 统计原始距离对数
这里说两种方法第一种是自己想的找规律其实踩坑了没弄好差分第二种就是灵神暴力时间复杂度是相同的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 和 i1 距离为2的就是 i-2 和 i2 ......
一直到两边可得左侧距离最大为i-1右侧为n-i
所以距离为 1 ~ i -1 的都要加一对距离为 1 ~ n - i 的也都要加一对
差分
而我们正好用的是差分数组。差分就是第一位为初始值后面的都表示和前一位相差的值。对这种连续的情况用差分是秒算的。
做修改
首先看情况其实就四种会变短而这四种是对称的也就是说其实就两种情况。
我们 i 为始点j为终点(xy)为新增的路我们让xy。
第一种
i 在 x左边 i x
只有当 j 在y左右的时候才会缩短距离 j在y左的位置的计算就是算什么时候走新路更短 偶数的话会有一个点这个点不走大于号嘛不取
奇数的话本是两点之间正好向下取整了如下图的a中间是正好所以b可取 第二种
x i (xy)/2 剩下的区间就是对称的 第二种的y左这个j的计算 关于小于区间右端点(xy)/2(等于过不了)
这个短点也没有缩短的
奇数情况 x - - i - - y 很明显i到x和y一样远
偶数情况 x - i - - y i直接到y为3i到x再到y为21 3
所以(xy)/2
——————
当 xy 及x y1时没有缩短任何距离。不需要操作 参考代码
灵神那个写的好我没封装。不过对称的处理可以看看处理是类似的。
他用函数会还原我是用个if 还原的然而if条件有关于对称用的值的所以后面可能进不去还原失败。
class Solution {
#define ll long longvectorllans;void add(int l, int r, int v){if(lr)return;ans[l] v;ans[r 1] - v;}
public:vectorlong long countOfPairs(int n, int x, int y){if (xy)swap(x, y);ans vectorll(n 2);// ans[1] n n - 2;// for (int i 2; i n - 1; i)// {// ans[i] -2;// }//for (int k 1; k n; k){int i k,orx x,ory y;add(1, i - 1, 1);add(1, n - i, 1);if (y - x 2)continue;if (k (orx ory 1) / 2){i n 1 - k;x n 1 - ory;y n 1 - orx;}if (i x){//1.jyadd(y - i, n - i,-1);//add(x-i1,x-i1n-y, 1);没有想用“缩短的距离”int dec y - x - 1;//比如 2 3 连完还是1缩短了03-2-1add(y - i - dec, n - i - dec, 1);//2.xjy i x j y//只管能短的即:j-i x-i 1 y-j// 2j xy1// j (xy1)/2//j(xy1)/21int j (x y 1) / 2 1;//j到y-1add(j-i,y-i-1,-1);add(x - i 2, x-i 1 y-j, 1);//3.jx不用管}else if (i (x y) / 2)// x - i - y 与 x - i - - y 都是不起作用不需等于{ //等于的话//y右add(y-i,n-i,-1);int dec y - i - (i - x 1);add(y - i-dec, n - i-dec, 1);//y左//j-ii-x1y-j//2j2i-x1y//j(2i-x1y)/2int j i (- x 1 y) / 2 1;add(j-i,y-1-i,-1);add(i - x 2, i - x y - j 1,1);}if (k (orx ory 1) / 2){x orx;y ory;}}vectorllret(n);ll sum_d 0;for (int i 0; i n; i){sum_d ans[i1];ret[i] sum_d;}return ret;}
};
