按距离统计房屋对数目 I
难度:
标签:
题目描述
You are given three positive integers n, x, and y.
In a city, there exist houses numbered 1 to n connected by n streets. There is a street connecting the house numbered i with the house numbered i + 1 for all 1 <= i <= n - 1 . An additional street connects the house numbered x with the house numbered y.
For each k, such that 1 <= k <= n, you need to find the number of pairs of houses (house1, house2) such that the minimum number of streets that need to be traveled to reach house2 from house1 is k.
Return a 1-indexed array result of length n where result[k] represents the total number of pairs of houses such that the minimum streets required to reach one house from the other is k.
Note that x and y can be equal.
Example 1:
Input: n = 3, x = 1, y = 3 Output: [6,0,0] Explanation: Let's look at each pair of houses: - For the pair (1, 2), we can go from house 1 to house 2 directly. - For the pair (2, 1), we can go from house 2 to house 1 directly. - For the pair (1, 3), we can go from house 1 to house 3 directly. - For the pair (3, 1), we can go from house 3 to house 1 directly. - For the pair (2, 3), we can go from house 2 to house 3 directly. - For the pair (3, 2), we can go from house 3 to house 2 directly.
Example 2:
Input: n = 5, x = 2, y = 4 Output: [10,8,2,0,0] Explanation: For each distance k the pairs are: - For k == 1, the pairs are (1, 2), (2, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3), (4, 5), and (5, 4). - For k == 2, the pairs are (1, 3), (3, 1), (1, 4), (4, 1), (2, 5), (5, 2), (3, 5), and (5, 3). - For k == 3, the pairs are (1, 5), and (5, 1). - For k == 4 and k == 5, there are no pairs.
Example 3:
Input: n = 4, x = 1, y = 1 Output: [6,4,2,0] Explanation: For each distance k the pairs are: - For k == 1, the pairs are (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), and (4, 3). - For k == 2, the pairs are (1, 3), (3, 1), (2, 4), and (4, 2). - For k == 3, the pairs are (1, 4), and (4, 1). - For k == 4, there are no pairs.
Constraints:
2 <= n <= 1001 <= x, y <= n
代码结果
运行时间: 40 ms, 内存: 16.1 MB
/*
* Problem statement:
* Given three positive integers n, x, and y.
* There are houses numbered from 1 to n, connected by n streets.
* Each i (1 <= i < n) has a street connecting house i and house i + 1.
* There is another street connecting house x and house y.
* For each k (1 <= k <= n), find the number of house pairs (house1, house2) such that the shortest street distance between house1 and house2 is k.
* Return an array result where result[k] is the count of such house pairs.
*/
import java.util.stream.IntStream;
public class Solution {
public int[] countPairs(int n, int x, int y) {
int[] result = new int[n];
IntStream.rangeClosed(1, n).forEach(i ->
IntStream.rangeClosed(i + 1, n).forEach(j -> {
int dist = Math.min(j - i, Math.abs(x - i) + 1 + Math.abs(y - j));
result[dist]++;
})
);
return result;
}
}
解释
方法:
时间复杂度:
空间复杂度: