【图论】【分类讨论】LeetCode3017按距离统计房屋对数目-阿里云开发者社区

【图论】【分类讨论】LeetCode3017按距离统计房屋对数目

2024-04-10 27

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【图论】【分类讨论】LeetCode3017按距离统计房屋对数目

本文涉及的知识点

图论分类讨论

本题同解

【差分数组】【图论】【分类讨论】【整除以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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。