2024-06-08：用go语言，给定三个正整数 n、x和y， 表示城市中的房屋数量以及编号
1 / 0 / 创建于 10个月前
moonfdd 的个人博客
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 完整代码如下：#
package main
import "fmt"
func countOfPairs(n, x, y int) []int64 {
if x > y {
x, y = y, x
}
ans := make([]int64, n)
if x+1 >= y {
for i := 1; i < n; i++ {
ans[i-1] = int64(n-i) * 2
}
return ans
}
diff := make([]int, n+1)
add := func(l, r int) {
diff[l]++
diff[r+1]--
}
for i := 1; i < n; i++ {
if i <= x {
k := (x + y + 1) / 2
add(1, k-i)
add(x-i+2, x-i+y-k)
add(x-i+1, x-i+1+n-y)
} else if i < (x+y)/2 {
k := i + (y-x+1)/2
add(1, k-i)
add(i-x+2, i-x+y-k)
add(i-x+1, i-x+1+n-y)
} else {
add(1, n-i)
}
}
sumD := int64(0)
for i, d := range diff[1:] {
sumD += int64(d)
ans[i] = sumD * 2
}
return ans
}
func main() {
n := 3
x := 1
y := 3
fmt.Println(countOfPairs(n, x, y))
}
Python 完整代码如下：#
# -*-coding:utf-8-*-
def count_of_pairs(n, x, y):
if x > y:
x, y = y, x
ans = [0] * n
if x + 1 >= y:
for i in range(1, n):
ans[i - 1] = (n - i) * 2
return ans
diff = [0] * (n + 1)
def add(l, r):
diff[l] += 1
diff[r + 1] -= 1
for i in range(1, n):
if i <= x:
k = (x + y + 1) // 2
add(1, k - i)
add(x - i + 2, x - i + y - k)
add(x - i + 1, x - i + 1 + n - y)
elif i < (x + y) // 2:
k = i + (y - x + 1) // 2
add(1, k - i)
add(i - x + 2, i - x + y - k)
add(i - x + 1, i - x + 1 + n - y)
else:
add(1, n - i)
sum_d = 0
for i, d in enumerate(diff[1:], start=1):
sum_d += d
ans[i - 1] = sum_d * 2
return ans
n = 3
x = 1
y = 3
print(count_of_pairs(n, x, y))
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：