【图论】【分类讨论】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++**实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/520697.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

服务效率飙升!2024最新Zoho Desk功能解析

2024年&#xff0c;立足于服务经济浪潮&#xff0c;如何为您的客户提供优质服务&#xff0c;高效解决客户工单&#xff0c;赢得客户美誉度&#xff0c;是当下各行企业的着力点。 在企业中&#xff0c;与客户发生最直接接触的就是客户服务部门。规范化客服部门业务流程&#xf…

【JavaWeb】Day36.MySQL概述——数据库设计-DDL(三)

查询 关于表结构的查询操作&#xff0c;工作中一般都是直接基于图形化界面操作。 1.查询当前数据库所有表 2.查看指定表结构 3.查询指定表的建表语句 注意&#xff1a;23版的点击导航中的转到DDL 修改 关于表结构的修改操作&#xff0c;一般也是直接基于图形化界面操作。 添…

LeetCode---127双周赛

题目列表 3095. 或值至少 K 的最短子数组 I 3096. 得到更多分数的最少关卡数目 3097. 或值至少为 K 的最短子数组 II 3098. 求出所有子序列的能量和 一、或值至少k的最短子数组I&II 暴力的做法大家都会&#xff0c;这里就不说了&#xff0c;下面我们来看看如何进行优化…

彩虹易支付接口配置

支付通道配置 基本概念 彩虹易支付系统有强大的支付接口扩展能力&#xff0c;首先需要明白以下几个概念。 支付方式&#xff1a; 支付方式用于定义发起支付的调用值&#xff08;在前台开发文档里面显示&#xff09;与支付方式名称。目前系统自带6种支付方式&#xff0c;它们的…

腾讯云最新活动及优惠券领取指南

随着云计算技术的不断发展和普及&#xff0c;越来越多的企业和个人选择将业务迁移到云端。腾讯云作为国内领先的云计算服务提供商&#xff0c;经常推出各种优惠活动&#xff0c;以帮助用户降低成本、提高效率。本文将为大家详细介绍腾讯云的最新活动及优惠券领取指南&#xff0…

猫头虎分享已解决Bug || **Error (通用错误)** 全景剖析

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …

数学杂谈之一:数学的形态

数学杂谈之一&#xff1a;数学的形态 数学的形态可以根据不同的角度和视角进行分类和描述。下面是从数学的发展和应用的不同角度进行的分类&#xff1a; 原始形态&#xff1a;原始形态是指数学的发展和应用起源的形态。它涉及到数学的理论构建、证明和发现过程&#xff0c;是数…

目标追踪StrongSORT——基于DeepSORT重大升级提高多目标跟踪的准确性和鲁棒性

1、概述 1.1 DeepSORT DeepSORT算法是在SORT基础上发展起来的一种多目标跟踪算法。SORT算法结合了目标检测器和跟踪器&#xff0c;其中跟踪器的核心是卡尔曼滤波和匈牙利算法。卡尔曼滤波用于预测目标在下一帧的位置和状态&#xff0c;而匈牙利算法则用于将预测状态与实际检测…

【Linux】Linux C 编程

在 Windows 下编程首先就是安装对应的 IDE &#xff0c;然后在 IDE 里面进行代码编写和编译&#xff0c;但是在 Linux 下&#xff0c;这两个部分是分开的&#xff0c;比如我们可以使用 vim 编辑器编写代码&#xff0c;然后用 gcc 编译器编译代码。Ubuntu 下有一些可以进行编程的…

Azkaban集群模式部署详细教程

序言 Azkaban是一个用于工作流程调度和任务调度的开源工具&#xff0c;它可以帮助用户轻松地管理和监控复杂的工作流程。Azkaban的架构设计旨在提供高度可扩展性和可靠性&#xff0c;同时保持易用性和灵活性。 Azkaban的架构可以分为三个主要组件:Executor、Web Server和db数据…

Python-VBA编程500例-033(入门级)

角色定位(Role Positioning)在编程中的实际应用场景主要体现在以下几个方面&#xff1a; 1、权限管理&#xff1a;在开发企业级应用或复杂的系统时&#xff0c;角色定位用于定义和管理用户的权限。例如&#xff0c;一个系统可能有管理员、普通用户、访客等不同角色&#xff0c…

Linux网络管理类命令

ping -c&#xff1a;指定次数 -i n&#xff1a;指定发送频率 n 秒 -t&#xff1a;指定 TTL 值 -s&#xff1a;指定发送包的大小 ifconfig iproute netstat -anltp ss ssh 主机名 SCP wget nmap -A: 全面扫描 -p &#xff1a;端口 80 22-80 80,25,443 -sP &#xf…

利用native的方式实现跨线程调用

简介 在OpenHarmony应用开发实践中&#xff0c;经常会遇到一些耗时的任务&#xff0c;如I/O操作、域名解析以及复杂计算等。这些任务如果直接在主线程中执行&#xff0c;将会严重阻塞主线程&#xff0c;影响后续任务的正常流程&#xff0c;进而导致用户界面响应延迟甚至卡顿。…

【学习笔记】Elsevier的Latex模板文件(附网址)

注&#xff1a;这是一篇没有技术含量的水文&#xff0c;主要是看有人下载下来&#xff0c;居然当成资源需要积分才能下载。我觉得不行&#xff0c;故提供原始下载地址供查阅使用。 链接: 上述图片所示网址&#xff1a;链接直达

Redis(性能管理、主从复制、哨兵模式)概述及部署

目录 一、性能管理 1、查看Redis内存使用 2、内存碎片率 3、跟踪内存碎片率 4、内存使用率 5、内回收key 二、Redis集群有三种模式 三、Redis主从复制 1、主从复制的概念 2、主从复制的作用 3、主从复制的流程 4、搭建Redis主从复制 1.环境准备 2.安装Redis&#…

在团队管理过程中,怎样能够让员工更容易接受和执行反馈呢?

让员工更容易接受和执行反馈&#xff0c;关键在于建立一种开放、积极且互相尊重的沟通氛围。 确保反馈的针对性和具体性是关键。 员工需要清楚了解他们的表现如何&#xff0c;以及他们需要改进的地方在哪里。因此&#xff0c;反馈内容应具体明确&#xff0c;避免模糊或笼统的表…

Python零基础到精通

Python入门指南 欢迎进入 Python 领域。作为程序员&#xff0c;我们总是在寻找能提高效率、编写优雅的代码的工具&#xff0c;而 Python 正是其中之一。你即将探索一种强大而灵活的编程语言&#xff0c;它被广泛应用于各种领域&#xff0c;从网站开发到数据科学&#xff0c;再到…

基础总结篇:Activity生命周期

private int param 1; //Activity创建时被调用 Override public void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); Log.i(TAG, “onCreate called.”); setContentView(R.layout.lifecycle); Button btn (Button) findViewById(R.id.…

【开源语音项目OpenVoice](一)——实操演示

目录 一、前菜 1、Python选择 2、pip源切换 3、ffmpeg配置问题 4、VSCode添加Jupyter扩展 二、配置虚拟环境 1、下载源码 方法一 直接下载源码压缩包 方法二 使用git 1&#xff09;git加入鼠标右键 2&#xff09;git clone源码 2、VSCode出场 1&#xff09;创建pyth…

VC++ 错误 Compiler Error C2018 unknown character ‘hexnumber‘

如下图&#xff0c;不能识别的字符0xa1&#xff0c; 这是代码中出现了全角空格&#xff0c;如下图标识的一行&#xff0c;等号前面出现了全角空格&#xff1b;改为半角空格&#xff1b; 如果是未知字符0xa3&#xff0c;则是程序中有中文符号&#xff0c;如程序中的引号&#xf…