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

2024-04-07 01:20
文章标签 统计 分类 图论 距离 讨论 数目 房屋 leetcode3017

本文主要是介绍【图论】【分类讨论】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

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

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

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

这篇关于【图论】【分类讨论】LeetCode3017按距离统计房屋对数目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/881312。

相关文章

C#使用DeepSeek API实现自然语言处理,文本分类和情感分析

C#使用DeepSeek API实现自然语言处理,文本分类和情感分析

《C#使用DeepSeekAPI实现自然语言处理,文本分类和情感分析》在C#中使用DeepSeekAPI可以实现多种功能,例如自然语言处理、文本分类、情感分析等,本文主要为大家介绍了具体实现步骤,... 目录准备工作文本生成文本分类问答系统代码生成翻译功能文本摘要文本校对图像描述生成总结在C#中使用Deep
阅读更多...
opencv实现像素统计的示例代码

opencv实现像素统计的示例代码

《opencv实现像素统计的示例代码》本文介绍了OpenCV中统计图像像素信息的常用方法和函数,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 统计像素值的基本信息2. 统计像素值的直方图3. 统计像素值的总和4. 统计非零像素的数量
阅读更多...
如何使用 Bash 脚本中的time命令来统计命令执行时间(中英双语)

如何使用 Bash 脚本中的time命令来统计命令执行时间(中英双语)

《如何使用Bash脚本中的time命令来统计命令执行时间(中英双语)》本文介绍了如何在Bash脚本中使用`time`命令来测量命令执行时间,包括`real`、`user`和`sys`三个时间指标,... 使用 Bash 脚本中的 time 命令来统计命令执行时间在日常的开发和运维过程中，性能监控和优化是不
阅读更多...
基于人工智能的图像分类系统

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务，目标是自动识别图像中的对象类别。通过卷积神经网络（CNN）等深度学习技术，我们可以构建高效的图像分类系统，广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统，包括环境
阅读更多...
hdu1496（用hash思想统计数目）

hdu1496（用hash思想统计数目）

作为一个刚学hash的孩子，感觉这道题目很不错，灵活的运用的数组的下标。 解题步骤：如果用常规方法解，那么时间复杂度为O（n^4）,肯定会超时，然后参考了网上的解题方法，将等式分成两个部分，a*x1^2+b*x2^2和c*x3^2+d*x4^2， 各自作为数组的下标，如果两部分相加为0，则满足等式； 代码如下： #include<iostream>#include<algorithm
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
flume系列之：查看flume系统日志、查看统计flume日志类型、查看flume日志

flume系列之：查看flume系统日志、查看统计flume日志类型、查看flume日志

遍历指定目录下多个文件查找指定内容 服务器系统日志会记录flume相关日志 cat /var/log/messages |grep -i oom 查找系统日志中关于flume的指定日志 import osdef search_string_in_files(directory, search_string):count = 0
阅读更多...
hdu4267区间统计

hdu4267区间统计

题意：给一些数，有两种操作，一种是在[a,b] 区间内，对（i - a）% k == 0 的加value,另一种操作是询问某个位置的值。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import
阅读更多...
hdu4417区间统计

hdu4417区间统计

给你一个数列{An}，然后有m次查询，每次查询一段区间 [l,r] <= h 的值的个数。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamRead
阅读更多...
hdu3333区间统计

hdu3333区间统计

题目大意：求一个区间内不重复数字的和，例如1 1 1 3，区间[1,4]的和为4。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2