北京市建设网站,阿里快速建站,中国建设银行e路通网站,wordpress官方主题下载作者推荐
【动态规划】【数学】【C算法】18赛车
本文涉及知识点
差分数组 图论 分类讨论 整除以2
LeetCode100213按距离统计房屋对数目
给你三个 正整数 n 、x 和 y 。 在城市中#xff0c;存在编号从 1 到 n 的房屋#xff0c;由 n 条街道相连。对所有 1 i n…作者推荐
【动态规划】【数学】【C算法】18赛车
本文涉及知识点
差分数组 图论 分类讨论 整除以2
LeetCode100213按距离统计房屋对数目
给你三个 正整数 n 、x 和 y 。 在城市中存在编号从 1 到 n 的房屋由 n 条街道相连。对所有 1 i n 都存在一条街道连接编号为 i 的房屋与编号为 i 1 的房屋。另存在一条街道连接编号为 x 的房屋与编号为 y 的房屋。 对于每个 k1 k n你需要找出所有满足要求的 房屋对 [house1, house2] 即从 house1 到 house2 需要经过的 最少 街道数为 k 。 返回一个下标从 1 开始且长度为 n 的数组 result 其中 result[k] 表示所有满足要求的房屋对的数量即从一个房屋到另一个房屋需要经过的 最少 街道数为 k 。 注意x 与 y 可以 相等 。 示例 1 输入n 3, x 1, y 3 输出[6,0,0] 解释让我们检视每个房屋对
对于房屋对 (1, 2)可以直接从房屋 1 到房屋 2。对于房屋对 (2, 1)可以直接从房屋 2 到房屋 1。对于房屋对 (1, 3)可以直接从房屋 1 到房屋 3。对于房屋对 (3, 1)可以直接从房屋 3 到房屋 1。对于房屋对 (2, 3)可以直接从房屋 2 到房屋 3。对于房屋对 (3, 2)可以直接从房屋 3 到房屋 2。 示例 2 输入n 5, x 2, y 4 输出[10,8,2,0,0] 解释对于每个距离 k 满足要求的房屋对如下对于 k 1满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3), (4, 5), 以及 (5, 4)。对于 k 2满足要求的房屋对有 (1, 3), (3, 1), (1, 4), (4, 1), (2, 5), (5, 2), (3, 5), 以及 (5, 3)。对于 k 3满足要求的房屋对有 (1, 5)以及 (5, 1) 。对于 k 4 和 k 5不存在满足要求的房屋对。 示例 3 输入n 4, x 1, y 1 输出[6,4,2,0] 解释对于每个距离 k 满足要求的房屋对如下对于 k 1满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), 以及 (4, 3)。对于 k 2满足要求的房屋对有 (1, 3), (3, 1), (2, 4), 以及 (4, 2)。对于 k 3满足要求的房屋对有 (1, 4), 以及 (4, 1)。对于 k 4不存在满足要求的房屋对。
分类讨论
x,y从1开始x–,y–让其从0开始。如果x y交换x和y。 如果xy直接处理{(n-1)*2,(n-2)2…} 题目要计算的是除了起点和终点外经过的房屋数。 起点i和终点j相同不统计。 起点和终点互换需要统计。可以只统计起点终点最后将结果2。 整个路径可以四个节点i,x,y,j表示。 一各节点最多出现1次否则有环将环删除。 二i,j 必定出现1次x和y要么都出现1次要么不出现。 三第一个节点必定是i,最后一个节点必定是j。 理论上有六种可能实际上只有五种 一i → \rightarrow → j。 二i → \rightarrow → x → \rightarrow → y → \rightarrow → j。 三i → \rightarrow → y → \rightarrow → x → \rightarrow → j。这中可能不存在 { 到 y 之前已经到达终点 , j y y → x → y 这段路程是多走的 j y \begin{cases} 到y之前已经到达终点, j y \\ y \rightarrow x \rightarrow y这段路程是多走的 j y \\ \end{cases} {到y之前已经到达终点,y→x→y这段路程是多走的jyjy 四, x i,y i 结果是0。 x → \rightarrow → y 五xi,y不等于j。 x → \rightarrow → y → \rightarrow → j 六x!i,y等于j。 i → \rightarrow → x → \rightarrow → y
第一种可能经过的房屋数不包括起点终点j-i-1 第二种情况xy无需做特殊处理会被淘汰。x y时。 abs(x-i) abs(j-y) → \rightarrow → abs(x-i)abx(j-y) { i − x j − y i x , j y 一 i − x i x , j y 二 i − x y − j x i , j y 三 x − i j − y i x , j y 四 x − i i x , j y 五 x − i y − j i x , j y 六 j − y i x , j y 七 0 i x , j y 八 y − j i x , j y 九 \begin{cases} i-x j- y i x ,jy 一\\ i-x i x, j y 二\\ i-x y-j x i ,j y 三\\ x-i j- y i x,j y 四\\ x-i i x,j y 五\\ x-iy-j i x,j y 六\\ j - y i x ,j y 七 \\ 0 i x ,j y 八\\ y - j ix,j y 九 \\ \end{cases} ⎩ ⎨ ⎧i−xj−yi−xi−xy−jx−ij−yx−ix−iy−jj−y0y−jix,jyix,jyxi,jyix,jyix,jyix,jyix,jyix,jyix,jy一二三四五六七八九
一二七八 可以合并合并后 i x j y 。 四五可以合并i x ,j y 三九也可以合并。合并i x ,jy { i − x j − y i x , j y 一 i − x y − j x i , j y 三 x − i j − y i x , j y 四 x − i y − j i x , j y 六 \begin{cases} i-x j- y i x ,jy 一\\ i-x y-j x i ,j y 三\\ x-i j- y i x, j y 四\\ x-iy-j i x,j y 六\\ \end{cases} ⎩ ⎨ ⎧i−xj−yi−xy−jx−ij−yx−iy−jix,jyxi,jyix,jyix,jy一三四六
我们枚举i计算j故x,y,i可以看做常数可以求出相等的临界值的j。 情况二一 i-x j- y j - i -1 → \rightarrow → 2i -x - y -1 → \rightarrow → 2i xy-1 → \rightarrow → { i → x → y → j 2 ∗ i x y − 1 i → j e l s e \begin{cases} i \rightarrow x \rightarrow y \rightarrow j 2*i xy-1\\ i \rightarrow j else \end{cases} {i→x→y→ji→j2∗ixy−1else 和j无关
情况二三 i-x y-j j - i -1 → \rightarrow → 2*(i-j) -x y -1 → \rightarrow → -2j x - y - 2i -1注意除以-1大于会变小于。 → \rightarrow → 2j y-x2i1 → \rightarrow → j (y-x)/2 i 1 { i → x → y → j j ( y − x ) / 2 i 1 i → j e l s e \begin{cases} i \rightarrow x \rightarrow y \rightarrow j j (y-x)/2 i 1 \\ i \rightarrow j else \end{cases} {i→x→y→ji→jj(y−x)/2i1else 情况二四 要想通过x,y 必须 x-i j- y j - i -1 → \rightarrow → x-y -1 → \rightarrow → x y恒成立。
情况二六 要想通过x,y必须 x-iy-j j - i -1 → \rightarrow → xy-2j -1 → \rightarrow → -2j -x-y-1 注意除以-1大于会变小于。 → \rightarrow → 2j xy1 → \rightarrow → j(xy11)/2 { i → x → y → j ( x y 1 1 ) / 2 i → j e l s e \begin{cases} i \rightarrow x \rightarrow y \rightarrow j(xy11)/2 \\ i \rightarrow j else \end{cases} {i→x→y→i→jj(xy11)/2else
y 0 整除2的逆运算
2x y 如果y是偶数 等效与 x y/2 。如果y是奇数等效与 x (y1)/2 。两者可以统一为: x (y1)/2 。 2x y 如果y是偶数 等效与 x y/2 。如果y是奇数等效与 x y/2。两者统一为x y/2。 2x y 可以统一为 x y/2。 2x y 可以统一为x ( y1)/2
代码
核心代码
class Solution {
public:vectorlong long countOfPairs(int n, int x, int y) { vectorlong long vRet(n);if (x y){vRet.clear();for (int i n - 1; i 0; i--){vRet.emplace_back(i * 2);}return vRet;}if (x y ){swap(x, y);}x--;y--;int i 0;
#define Path1(j) (j - i -1 )auto Path2 [i,x,y]( const int j){return abs(i - x) abs(j - y);};vectorlong long vDiff(n);auto Add [](int left, int len){if (len 0){return;}vDiff[left] 2 ;vDiff[leftlen] - 2 ;};for (; i x; i){//j 在[y,n)const int iy max(i 1, y);if (n - iy 0){Add(Path2(iy), n - iy);} //j在(i,y)if( y - i -1 0 ){//i-x-y-j [j0,y)const int j0 (x y 2) / 2; Add(Path2(y-1), y - j0);//(i,j0)Add(0, j0 - i - 1);}}for (; i n; i){//j在(max(y-1,i),n)if (2*i x y-1){//i-x-y-jAdd(Path2(max(y-1, i) 1), n - max(y-1, i) -1);}else{Add(Path1(max(y-1, i) 1), n - max(y-1, i) -1);}//j在(i,y)if (y - i - 1 0){int j0 min(y,(2 * i y - x 2) / 2);j0 max(j0, i 1);//if (y - j0 0){//j在[j0,y) i-x-y-j Add(Path2(y - 1), y - j0);//j在(i,j0)Add(0, j0 - i - 1);}}}long long cur0;for (int i 0; i n; i){cur vDiff[i];vRet[i] cur;}return vRet;}
};测试用例
templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}}int main()
{ int n, x, y;{Solution sln;n 6, x 1, y 5;auto res sln.countOfPairs(n, x, y);Assert(res, vectorlong long{ 12, 14, 4, 0, 0, 0 });}{Solution sln;n 3, x 2, y 2;auto res sln.countOfPairs(n, x, y);Assert(res, vectorlong long{4, 2, 0});}{Solution sln;n 4, x 1, y 1;auto res sln.countOfPairs(n, x, y);Assert(res, vectorlong long{6, 4, 2, 0});}{Solution sln;n 5, x 2, y 4;auto res sln.countOfPairs(n, x, y);Assert(res, vectorlong long{10, 8, 2, 0, 0});}{Solution sln;n 3, x 1, y 3; auto res sln.countOfPairs(n,x,y);Assert(res, vectorlong long{6, 0, 0});} {Solution sln;n 2, x 2, y 2;auto res sln.countOfPairs(n, x, y);Assert(res, vectorlong long{2, 0});}}扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
