差分数组图论分类讨论整除以2100213按距离统计房屋对数目

作者推荐

【动态规划】【数学】【C++算法】18赛车

本文涉及知识点

差分数组 图论 分类讨论 整除以2

LeetCode100213按距离统计房屋对数目

给你三个 正整数 n 、x 和 y 。
在城市中,存在编号从 1 到 n 的房屋,由 n 条街道相连。对所有 1 <= i < n ,都存在一条街道连接编号为 i 的房屋与编号为 i + 1 的房屋。另存在一条街道连接编号为 x 的房屋与编号为 y 的房屋。
对于每个 k(1 <= 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

ightarrow

→ j。
二,i

ightarrow

→ x

ightarrow

→ y

ightarrow

→ j。
三,i

ightarrow

→ y

ightarrow

→ x

ightarrow

→ j。这中可能不存在:

{

y

之前已经到达终点

,

j

<

=

y

y

x

y

这段路程是多走的

j

>

y

egin{cases} 到y之前已经到达终点, & j <= y \ y
ightarrow x
ightarrow y这段路程是多走的 & j > y \ end{cases}

{到y之前已经到达终点,y→x→y这段路程是多走的?j<=yj>y?
四, x == i,y == i 结果是0。 x

ightarrow

→ y
五,xi,y不等于j。 x

ightarrow

→ y

ightarrow

→ j
六,x!=i,y等于j。 i

ightarrow

→ x

ightarrow

→ y

第一种可能经过的房屋数(不包括起点终点):j-i-1
第二种情况,x==y,无需做特殊处理,会被淘汰。x < y时。
abs(x-i)+ abs(j-y)

ightarrow

→ 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

egin{cases} 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 & 九 \ end{cases}

?
?
??i?x+j?yi?xi?x+y?jx?i+j?yx?ix?i+y?jj?y0y?j?i>x,j>yi>x,j==yx>i,j<yi<x,j>yi<x,j==yi<x,j<yi==x,j>yi==x,j==yi==x,j<y?一二三四五六七八九?

一,二,七,八 可以合并,合并后 i >=x j >= y 。 四五可以合并,i < x ,j >=y 三九也可以合并。合并i >=x ,j<y

{

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

egin{cases} 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& 六\ end{cases}

?
?
??i?x+j?yi?x+y?jx?i+j?yx?i+y?j?i>=x,j>=yx>=i,j<yi<x,j>=yi<x,j<y?一三四六?

我们枚举i,计算j,故x,y,i可以看做常数,可以求出相等的临界值的j。
情况二一:
i-x + j- y <= j - i -1

ightarrow

→ 2i -x - y <= -1

ightarrow

→ 2i <= x+y-1

ightarrow

{

i

x

y

j

2

?

i

<

=

x

+

y

?

1

i

j

e

l

s

e

egin{cases} i
ightarrow x
ightarrow y
ightarrow j & 2*i <= x+y-1\ i
ightarrow j & else end{cases}

{i→x→y→ji→j?2?i<=x+y?1else?
和j无关

情况二三:
i-x +y-j <= j - i -1

ightarrow

→ 2*(i-j) -x + y <= -1

ightarrow

→ -2j <= x - y - 2i -1注意除以-1,大于会变小于

ightarrow

→ 2j >= y-x+2i+1

ightarrow

→ j >= (y-x)/2 + i +1

{

i

x

y

j

j

>

=

(

y

?

x

)

/

2

+

i

+

1

i

j

e

l

s

e

egin{cases} i
ightarrow x
ightarrow y
ightarrow j & j >= (y-x)/2 + i +1 \ i
ightarrow j & else end{cases}

{i→x→y→ji→j?j>=(y?x)/2+i+1else?
情况二四:
要想通过x,y 必须 x-i + j- y <= j - i -1

ightarrow

→ x-y <= -1

ightarrow

→ x <y,恒成立。

情况二六:
要想通过x,y,必须 x-i+y-j <= j - i -1

ightarrow

→ x+y-2j <= -1

ightarrow

→ -2j <= -x-y-1 注意除以-1,大于会变小于

ightarrow

→ 2j >= x+y+1

ightarrow

→ j>=(x+y+1+1)/2

{

i

x

y

j

>

=

(

x

+

y

+

1

+

1

)

/

2

i

j

e

l

s

e

egin{cases} i
ightarrow x
ightarrow y
ightarrow & j>=(x+y+1+1)/2 \ i
ightarrow j & else end{cases}

{i→x→y→i→j?j>=(x+y+1+1)/2else?

y >= 0 整除2的逆运算

2x >= y ,如果y是偶数 等效与 x >= y/2 。如果y是奇数,等效与 x >= (y+1)/2 。两者可以统一为: x >=(y+1)/2 。
2
x > y 如果y是偶数 等效与 x > y/2 。如果y是奇数,等效与 x > y/2。两者统一为x > y/2。
2x <= y 可以统一为 x <=y/2。
2
x < y 可以统一为:x < ( y+1)/2

代码

核心代码

class Solution {
public:
	vector<long long> countOfPairs(int n, int x, int y) {		
		vector<long 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);
		};
		vector<long long> vDiff(n);
		auto Add = [&](int left, int len)
		{
			if (len <= 0)
			{
				return;
			}
			vDiff[left] += 2 ;
			vDiff[left+len] -= 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-j
				Add(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 cur=0;
		for (int i = 0; i < n; i++)
		{
			cur += vDiff[i];
			vRet[i] = cur;
		}
		return vRet;
	}
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& 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, vector<long long>{ 12, 14, 4, 0, 0, 0 });
	}

	{
		Solution sln;
		n = 3, x = 2, y = 2;
		auto res = sln.countOfPairs(n, x, y);
		Assert(res, vector<long long>{4, 2, 0});
	}

	{
		Solution sln;
		n = 4, x = 1, y = 1;
		auto res = sln.countOfPairs(n, x, y);
		Assert(res, vector<long long>{6, 4, 2, 0});
	}
	{
		Solution sln;
		n = 5, x = 2, y = 4;
		auto res = sln.countOfPairs(n, x, y);
		Assert(res, vector<long long>{10, 8, 2, 0, 0});
	}
	
	
	{
		Solution sln;
		n = 3, x = 1, y = 3;		
		auto res = sln.countOfPairs(n,x,y);
		Assert(res, vector<long long>{6, 0, 0});
	}		
	
	{
		Solution sln;
		n = 2, x = 2, y = 2;
		auto res = sln.countOfPairs(n, x, y);
		Assert(res, vector<long 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 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。