2024-06-08：用go语言，给定三个正整数 n、x和y，表示城市中的房屋数量以及编号为x和y的两个特殊房屋。在这座城市

福大大架构师每日一题

发布于 2024-08-16 16:33:41

720

发布于 2024-08-16 16:33:41

文章被收录于专栏：福大大架构师每日一题

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