2024-06-05：用go语言，给定三个正整数 n、x 和 y，描述一个城市中由 n 个房屋和 n 条街道连接的情况。城市

福大大架构师每日一题

发布于 2024-06-07 18:34:33

880

发布于 2024-06-07 18:34:33

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

2024-06-05：用go语言，给定三个正整数 n、x 和 y，

描述一个城市中由 n 个房屋和 n 条街道连接的情况。

城市中存在一条额外的街道连接房屋 x 和房屋 y。

需要计算对于每个街道数（从 1 到 n），

有多少房屋对满足从一个房屋到另一个房屋经过的街道数正好为该街道数。

在结果数组中，索引 k 对应的值表示满足此条件的房屋对数量。

输入：n = 3, x = 1, y = 3。

输出：[6,0,0]。

答案2024-06-05：

chatgpt

题目来自leetcode3015。

大体步骤如下：

1.程序开始执行，进入 main 函数。

2.在 main 函数中设定了 n = 3, x = 1, y = 3，并调用 countOfPairs(n, x, y) 函数。

3.进入 countOfPairs 函数，创建一个结果数组 result，长度为 n，用于存储最终的结果。

4.根据 x 和 y 的大小关系，找出较小值和较大值。在这种情况下，x = 1，y = 3，因此 smaller = 1，larger = 3。

5.检查 larger 和 smaller 之间的差值是否小于等于 1，发现是，进入条件分支。

6.使用 for 循环遍历索引 i 从 1 到 n，计算每对房屋的数量并存储在结果数组中。

7.对于给定的 n = 3，在这种情况下，结果数组将变为 [4, 2, 0]。

8.返回结果数组，打印输出 [4, 2, 0]。

时间复杂度分析：

• 计算 diff 数组的过程中有一个 for 循环，时间复杂度为 O(n)。
• 计算前缀和结果的过程中也有一个 for 循环，时间复杂度为 O(n)。

总的时间复杂度为 O(n)。

空间复杂度分析：

• 除了输入参数外，程序额外使用了 result 和 diff 两个数组。
• result 数组的空间复杂度为 O(n)。
• diff 数组的空间复杂度为 O(n+1)，约为 O(n)。

总的额外空间复杂度为 O(n)。

go完整代码如下：

package main

import "fmt"

func countOfPairs(n int, x int, y int) []int {
    result := make([]int, n)
    smaller := min(x, y)
    larger := max(x, y)
    if larger-smaller <= 1 {
        for i := 1; i <= n; i++ {
            result[i-1] = (n-i)*2
        }
        return result
    }
    diff := make([]int, n+1)
    for i := 1; i <= n; i++ {
        if i <= smaller {
            mid := (smaller + larger + 1) / 2
            diff[1]++
            diff[mid-i+1]--
            diff[smaller-i+2]++
            diff[smaller-i+larger-mid+1]--
            diff[smaller-i+1]++
            diff[smaller-i+n-larger+2]--
        } else if i < (smaller+larger)/2 {
            mid := i + (larger-smaller+1)/2
            diff[1]++
            diff[mid-i+1]--
            diff[i-smaller+2]++
            diff[i-smaller+larger-mid+1]--
            diff[i-smaller+1]++
            diff[i-smaller+n-larger+2]--
        } else {
            diff[1]++
            diff[n-i+1]--
        }
    }
    prefixSum := 0
    for i := 1; i <= n; i++ {
        prefixSum += diff[i]
        result[i-1] = prefixSum * 2
    }
    return result
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

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):
    def min(a, b):
        return a if a < b else b

    def max(a, b):
        return a if a > b else b

    result = [0] * n
    smaller = min(x, y)
    larger = max(x, y)

    if larger - smaller <= 1:
        for i in range(1, n+1):
            result[i-1] = (n - i) * 2
        return result

    diff = [0] * (n+1)
    for i in range(1, n+1):
        if i <= smaller:
            mid = (smaller + larger + 1) // 2
            diff[1] += 1
            diff[mid-i+1] -= 1
            diff[smaller-i+2] += 1
            diff[smaller-i+larger-mid+1] -= 1
            diff[smaller-i+1] += 1
            diff[smaller-i+n-larger+2] -= 1
        elif i < (smaller+larger)//2:
            mid = i + (larger-smaller+1)//2
            diff[1] += 1
            diff[mid-i+1] -= 1
            diff[i-smaller+2] += 1
            diff[i-smaller+larger-mid+1] -= 1
            diff[i-smaller+1] += 1
            diff[i-smaller+n-larger+2] -= 1
        else:
            diff[1] += 1
            diff[n-i+1] -= 1

    prefix_sum = 0
    for i in range(1, n+1):
        prefix_sum += diff[i]
        result[i-1] = prefix_sum * 2

    return result

n = 3
x = 1
y = 3
print(count_of_pairs(n, x, y))