按距离统计房屋对数目 I

100188. 按距离统计房屋对数目 I

给你三个 正整数 n 、x 和 y 。

在城市中，存在编号从 1 到 n 的房屋，由 n 条街道相连。对所有 1 <= i < n ，都存在一条街道连接编号为 i 的房屋与编号为 i + 1 的房屋。另存在一条街道连接编号为 x 的房屋与编号为 y 的房屋。

对于每个 k（1 <= k <= n），你需要找出所有满足要求的 房屋对 [house₁, house₂] ，即从 house₁ 到 house₂ 需要经过的最少街道数为 k 。

返回一个下标从 1 开始且长度为 n 的数组 result ，其中 result[k] 表示所有满足要求的房屋对的数量，即从一个房屋到另一个房屋需要经过的最少街道数为 k 。

注意，x 与 y 可以相等。

示例 1：

输入：n = 3, x = 1, y = 3
输出：[6,0,0]
解释：让我们检视每个房屋对
- 对于房屋对 (1, 2)，可以直接从房屋 1 到房屋 2。
- 对于房屋对 (2, 1)，可以直接从房屋 2 到房屋 1。
- 对于房屋对 (1, 3)，可以直接从房屋 1 到房屋 3。
- 对于房屋对 (3, 1)，可以直接从房屋 3 到房屋 1。
- 对于房屋对 (2, 3)，可以直接从房屋 2 到房屋 3。
- 对于房屋对 (3, 2)，可以直接从房屋 3 到房屋 2。

示例 2：

输入：n = 5, x = 2, y = 4
输出：[10,8,2,0,0]
解释：对于每个距离 k ，满足要求的房屋对如下：
- 对于 k == 1，满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3), (4, 5), 以及 (5, 4)。
- 对于 k == 2，满足要求的房屋对有 (1, 3), (3, 1), (1, 4), (4, 1), (2, 5), (5, 2), (3, 5), 以及 (5, 3)。
- 对于 k == 3，满足要求的房屋对有 (1, 5)，以及 (5, 1) 。
- 对于 k == 4 和 k == 5，不存在满足要求的房屋对。

示例 3：

输入：n = 4, x = 1, y = 1
输出：[6,4,2,0]
解释：对于每个距离 k ，满足要求的房屋对如下：
- 对于 k == 1，满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), 以及 (4, 3)。
- 对于 k == 2，满足要求的房屋对有 (1, 3), (3, 1), (2, 4), 以及 (4, 2)。
- 对于 k == 3，满足要求的房屋对有 (1, 4), 以及 (4, 1)。
- 对于 k == 4，不存在满足要求的房屋对。

提示：

2 <= n <= 100
1 <= x, y <= n

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<int> countOfPairs(int n, int x, int y) { } };

cpp 解法, 执行用时: 3 ms, 内存消耗: 9.5 MB, 提交时间: 2024-01-22 10:33:20

class Solution {
public:
    vector<int> countOfPairs(int n, int x, int y) {
        if (x > y) {
            swap(x, y);
        }

        vector<int> diff(n + 1);

        auto add = [&](int l, int r, int v) {
            if (l > r) return;
            diff[l] += v;
            diff[r + 1] -= v;
        };

        auto update = [&](int i, int x, int y) {
            add(y - i, n - i, -1); // 撤销 [y,n]
            int dec = y - x - 1; // 缩短的距离
            add(y - i - dec, n - i - dec, 1);

            int j = (x + y + 1) / 2 + 1;
            add(j - i, y - 1 - i, -1); // 撤销 [j, y-1]
            add(x - i + 2, x - i + y - j + 1, 1);
        };

        auto update2 = [&](int i, int x, int y) {
            add(y - i, n - i, -1); // 撤销 [y,n]
            int dec = (y - i) - (i - x + 1); // 缩短的距离
            add(y - i - dec, n - i - dec, 1);

            int j = i + (y - x + 1) / 2 + 1;
            add(j - i, y - 1 - i, -1); // 撤销 [j, y-1]
            add(i - x + 2, i - x + y - j + 1, 1);
        };

        for (int i = 1; i <= n; i++) {
            add(1, i - 1, 1);
            add(1, n - i, 1);
            if (x + 1 >= y) {
                continue;
            }
            if (i <= x) {
                update(i, x, y);
            } else if (i >= y) {
                update(n + 1 - i, n + 1 - y, n + 1 - x);
            } else if (i < (x + y) / 2) {
                update2(i, x, y);
            } else if (i > (x + y + 1) / 2) {
                update2(n + 1 - i, n + 1 - y, n + 1 - x);
            }
        }

        vector<int> ans(n);
        long long sum_d = 0;
        for (int i = 0; i < n; i++) {
            sum_d += diff[i + 1];
            ans[i] = sum_d;
        }
        return ans;
    }
};

java 解法, 执行用时: 1 ms, 内存消耗: 43.4 MB, 提交时间: 2024-01-22 10:32:20

class Solution {
    public int[] countOfPairs(int n, int x, int y) {
        if (x > y) {
            int temp = x;
            x = y;
            y = temp;
        }

        diff = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            add(1, i - 1, 1);
            add(1, n - i, 1);
            if (x + 1 >= y) {
                continue;
            }
            if (i <= x) {
                update(i, x, y, n);
            } else if (i >= y) {
                update(n + 1 - i, n + 1 - y, n + 1 - x, n);
            } else if (i < (x + y) / 2) {
                update2(i, x, y, n);
            } else if (i > (x + y + 1) / 2) {
                update2(n + 1 - i, n + 1 - y, n + 1 - x, n);
            }
        }

        int[] ans = new int[n];
        int sumD = 0;
        for (int i = 0; i < n; i++) {
            sumD += diff[i + 1];
            ans[i] = sumD;
        }
        return ans;
    }

    private int[] diff;

    private void add(int l, int r, int v) {
        if (l > r) return;
        diff[l] += v;
        diff[r + 1] -= v;
    }

    private void update(int i, int x, int y, int n) {
        add(y - i, n - i, -1); // 撤销 [y,n]
        int dec = y - x - 1; // 缩短的距离
        add(y - i - dec, n - i - dec, 1);

        int j = (x + y + 1) / 2 + 1;
        add(j - i, y - 1 - i, -1); // 撤销 [j, y-1]
        add(x - i + 2, x - i + y - j + 1, 1);
    }

    private void update2(int i, int x, int y, int n) {
        add(y - i, n - i, -1); // 撤销 [y,n]
        int dec = (y - i) - (i - x + 1); // 缩短的距离
        add(y - i - dec, n - i - dec, 1);

        int j = i + (y - x + 1) / 2 + 1;
        add(j - i, y - 1 - i, -1); // 撤销 [j, y-1]
        add(i - x + 2, i - x + y - j + 1, 1);
    }
}

golang 解法, 执行用时: 3 ms, 内存消耗: 3.1 MB, 提交时间: 2024-01-22 10:31:19

func countOfPairs(n, x, y int) []int {
	if x > y {
		x, y = y, x
	}

	diff := make([]int, n+1)
	add := func(l, r, v int) {
		if l > r {
			return
		}
		diff[l] += v
		diff[r+1] -= v
	}

	update := func(i, x, y int) {
		add(y-i, n-i, -1) // 撤销 [y,n]
		dec := y - x - 1  // 缩短的距离
		add(y-i-dec, n-i-dec, 1)

		j := (x+y+1)/2 + 1
		add(j-i, y-1-i, -1) // 撤销 [j, y-1]
		add(x-i+2, x-i+y-j+1, 1)
	}

	update2 := func(i, x, y int) {
		add(y-i, n-i, -1) // 撤销 [y,n]
		dec := (y - i) - (i - x + 1) // 缩短的距离
		add(y-i-dec, n-i-dec, 1)

		j := i + (y-x+1)/2 + 1
		add(j-i, y-1-i, -1) // 撤销 [j, y-1]
		add(i-x+2, i-x+y-j+1, 1)
	}

	for i := 1; i <= n; i++ {
		add(1, i-1, 1)
		add(1, n-i, 1)
		if x+1 >= y {
			continue
		}
		if i <= x {
			update(i, x, y)
		} else if i >= y {
			update(n+1-i, n+1-y, n+1-x)
		} else if i < (x+y)/2 {
			update2(i, x, y)
		} else if i > (x+y+1)/2 {
			update2(n+1-i, n+1-y, n+1-x)
		}
	}

	ans := make([]int, n)
	sumD := 0
	for i, d := range diff[1:] {
		sumD += d
		ans[i] = sumD
	}
	return ans
}

python3 解法, 执行用时: 63 ms, 内存消耗: 16.6 MB, 提交时间: 2024-01-22 10:29:03

class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        if x > y:
            x, y = y, x

        diff = [0] * (n + 1)

        def add(l: int, r: int, v: int) -> None:
            if l > r: return
            diff[l] += v
            diff[r + 1] -= v

        def update(i: int, x: int, y: int) -> None:
            add(y - i, n - i, -1)  # 撤销 [y,n]
            dec = y - x - 1  # 缩短的距离
            add(y - i - dec, n - i - dec, 1)

            j = (x + y + 1) // 2 + 1
            add(j - i, y - 1 - i, -1)  # 撤销 [j, y-1]
            add(x - i + 2, x - i + y - j + 1, 1)

        def update2(i: int, x: int, y: int) -> None:
            add(y - i, n - i, -1)  # 撤销 [y,n]
            dec = (y - i) - (i - x + 1)  # 缩短的距离
            add(y - i - dec, n - i - dec, 1)

            j = i + (y - x + 1) // 2 + 1
            add(j - i, y - 1 - i, -1)  # 撤销 [j, y-1]
            add(i - x + 2, i - x + y - j + 1, 1)

        for i in range(1, n + 1):
            add(1, i - 1, 1)
            add(1, n - i, 1)
            if x + 1 >= y:
                continue
            if i <= x:
                update(i, x, y)
            elif i >= y:
                update(n + 1 - i, n + 1 - y, n + 1 - x)
            elif i < (x + y) // 2:
                update2(i, x, y)
            elif i > (x + y + 1) // 2:
                update2(n + 1 - i, n + 1 - y, n + 1 - x)

        return list(accumulate(diff))[1:]

上一题

下一题

详情