本文涉及的知识点
图论 分类讨论
本题同解
【差分数组】【图论】【分类讨论】【整除以2】3017按距离统计房屋对数目
LeetCode3017按距离统计房屋对数目
给你三个 正整数 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
不失一般性,令x < y。
则x
↔
\leftrightarrow
↔ y ,是环。房屋z1和z2,令z1 < z2 分类如下:
分类一,z1 < x ,z2 < x 。则两者经过的街道数为z2-z1。
分类二,z1,z2
∈
\in
∈[x,y] 。min(z2-z1,y-z2+z1-x+1)。
分类三:z1,z2 > y。和分类一类似。
分类四:z1 < x ,z2
∈
\in
∈[x,y]。 min(z2-z1,y-z2+1+(x-z1))
分类五:z1 < x ,z2 > y 。则两者经过的街道数为(z1-x)+1+(z2-y)。通过x,y中中转多花 x+1-y ,由于y > x,故多化的<=0,更优。
分类六:z1
∈
\in
∈[x,y],z2 > y。 min(z2-z1,z1-x+1+(z2-y))
总结后的分类
新分类一:[z3,z4] 都不通过x
↔
\leftrightarrow
↔y 中转。包括分类一,分类五,及x==y。
距离为1的数量为:z4-z3。
距离为2的数量为:z4-z3-1
⋮
\vdots
⋮
新分类二:两个点都在环上,环的长度为len。则两点的合法距离只能
∈
\in
∈[1,len/2] 原分类二。
如果len是偶数,距离len/2的点对数量为len/2,z5
→
\rightarrow
→z6 就是 z6
→
\rightarrow
→z5。
其它情况点对数量为:len。
新分类三:两个点分别在环两侧。分类五。
长度为3的点对:1。
长度为4的点对:2。
长度为5的点对:3 。
令环左侧的点数为len1,环右侧的点数为len2。计算距离为d的数量:
minl = max(0,d-3-(len2-1))
maxl = min(len1-1,d-3)
距离为d的点对数量:maxl - minl +1 。
新分类四:环上一点,一侧一点。原分类四六。
把环拆成两个,就和新分类三基本一致。
拆分成{2,1,4}和{5,6},同时拆分成{3,4} {5,6}
交点4 被计算了两次,要扣掉。
代码
核心代码
class Solution {
public:
vector<long long> countOfPairs(int n, int x, int y) {
m_vRet.resize(n);
if (x == y) {
Do1(1, n);
return m_vRet;
}
if (x > y) {
swap(x, y);
}
Do1(1, x - 1);
const int iCycLen = y - x + 1;
Do2(iCycLen);
Do1(y + 1, n);
Do4(iCycLen, x - 1);
Do3(x - 1, 3, n - y);
Do4(iCycLen, n - y);
return m_vRet;
}
void Do1(int left, int r)
{
for (int d = 1; d <= r - left; d++) {
update(d, r - left + 1 - d);
}
}
void Do2(int iCycLen)
{
for (int d = 1; d <= iCycLen / 2; d++)
{
const int cnt = ((0 == iCycLen % 2) && (iCycLen / 2 == d)) ? iCycLen / 2 : iCycLen;
update(d, cnt);
}
}
void Do3(int len1, int iMidDis, int len2)
{
for (int d = 0; d <= len1 + len2 - 2; d++)
{
const int minl = max(0, d - (len2 - 1));
const int maxl = min(len1 - 1, d);
update(d + iMidDis, maxl - minl + 1);
}
}
void Do4(int iCycLen, int len)
{
Do3((iCycLen+1) / 2 , 1, len);
Do3(iCycLen / 2 + 1, 1, len);
for (int d = 1; d <= len; d++) {
update(d, -1);
}
}
inline void update(int d, int cnt)
{
m_vRet[d - 1] += cnt*2;
}
vector<long long> m_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++**实现。