2024-06-08:用 go 语言,给定三个正整数 n、x 和 y, 表示城市中的房屋数量以及编号为 x 和 y 的两个特殊房屋。 在这座城市中,房屋通过街道相连。对于每个编号 i(1 <= i < n), 存在一条
2024-06-08:用 go 语言,给定三个正整数 n、x 和 y,
表示城市中的房屋数量以及编号为 x 和 y 的两个特殊房屋。
在这座城市中,房屋通过街道相连。对于每个编号 i(1 <= i < n),
存在一条连接第 i 个房屋与第(i+1)个房屋的街道。
此外,还有一条特殊街道连接编号为 x 的房屋与编号为 y 的房屋。
对于每个 k(1 <= k <= n),
需要找出所有满足以下条件的房屋对[house1, house2]:从 house1 到 house2 需要经过最少 k 条街道。
请返回一个长度为 n 且从下标 1 开始的数组 result,
其中 result[k]表示满足上述条件的房屋对数量,
即从一个房屋到另一个房屋需要经过最少 k 条街道。
注意:x 和 y 可以相等。
输入:n = 3, x = 1, y = 3。
输出:[6,0,0]。
答案 2024-06-08:
题目来自 leetcode3017。
大体步骤如下:
1.快速检查 x 和 y 的大小关系,确保 x <= y,若不满足则交换它们的值,以便后续计算更简单。
2.初始化一个长度为 n 的空整型数组 ans,用于存储结果。
3.检查特殊情况:当 x 和 y 之间只隔一个房屋时,快速计算出 ans 数组的值。在这种情况下,循环遍历房屋序号,填充 ans 数组。
4.对于一般情况,初始化一个长度为 n+1 的整型数组 diff,用于记录每个房屋对应的路径数量的变化。
5.定义一个匿名函数 add(l, r),用于更新 diff 数组中的元素。该函数增加索引 l 到 r 之间的元素值。
6.使用循环遍历房屋,根据不同条件来更新 diff 数组中的值。具体处理逻辑如下:
对于小于等于 x 的房屋,根据特定计算方式更新 diff 数组。
对于大于 x 小于(y+x)/2 的房屋,采用不同计算方式更新 diff 数组。
其他房屋直接更新 diff 数组。
7.计算出所有房屋对应路径数量的变化,并填充结果数组 ans。
8.返回计算结果 ans。
总的时间复杂度:这段代码中的最主要操作是循环遍历房屋,即(O(n))。在每次循环中,对于不同条件,进行一些简单的数学计算和更新数组操作。因此,总的时间复杂度可以近似看作(O(n))。
总的空间复杂度:除了输入参数外,主要使用了 ans、diff 这两个数组来存储结果和中间计算数据,它们的长度均为 n。因此,空间复杂度为(O(n))。
Go 完整代码如下:
![](https://static001.geekbang.org/infoq/04/04b5520bb57622e884fabe30cacdeff3.png)
Python 完整代码如下:
![](https://static001.geekbang.org/infoq/ac/ac2169f5b3ca1d66ed1c9d1f3258e54c.png)
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/ee7918622b7fe06d71d873b95】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论