2024-06-08：用 go 语言，给定三个正整数 n、x 和 y，表示城市中的房屋数量以及编号为 x 和 y 的两个特殊房屋。在这座城市中，房屋通过街道相连。对于每个编号 i（1 ＜= i ＜ n），存在一条

作者：福大大架构师每日一题

2024-06-08
北京
本文字数：1691 字
阅读完需：约 6 分钟

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：

chatgpt

题目来自 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 = 3x = 1y = 3print(count_of_pairs(n, x, y))