Every day a Leetcode
题目来源:3017. 按距离统计房屋对数目 II
解法1:暴力
暴力枚举每一个房屋对 (i, j) 的 3 种路径:
- i->j:长度为 len1 = j-i;
- i->x->y->j:长度为 len2 = abs(i - x) + 1 + abs(j - y);
- i->y->x->j:长度为 len3 = abs(i - y) + 1 + abs(j - x)。
取这 3 种路径的最小值作为房屋对 (i, j) 的路径,路径长度 len = min({len1, len2, len3}),因为路径是双向的,在答案数组 ans 中 ans[len - 1] += 2。
最后返回 ans 数组。
代码:
/*
* @lc app=leetcode.cn id=3017 lang=cpp
*
* [3017] 按距离统计房屋对数目 II
*/
// @lc code=start
class Solution
{
public:
vector<long long> countOfPairs(int n, int x, int y)
{
vector<long long> ans(n, 0);
for (int i = 1; i < n; i++)
for (int j = i + 1; j <= n; j++)
{
int len1 = j - i; // i->j
int len2 = abs(i - x) + 1 + abs(j - y); // i->x->y->j
int len3 = abs(i - y) + 1 + abs(j - x); // i->y->x->j
// 取最短距离作为路径
int len = min({
len1, len2, len3});
ans[len - 1] += 2; // 路径是双向的
}
return ans;
}
};
// @lc code=end
结果:
复杂度分析:
时间复杂度:O(n2),其中 n 是房屋数量。
空间复杂度:O(n),其中 n 是房屋数量。
解法2:差分数组
题解:两种分类讨论思路(Python/Java/C++/Go)
代码:
/*
* @lc app=leetcode.cn id=3017 lang=cpp
*
* [3017] 按距离统计房屋对数目 II
*/
// @lc code=start
class Solution
{
public:
vector<long long> 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<long long> 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;
}
};
// @lc code=end
结果:
复杂度分析:
时间复杂度:O(n),其中 n 是房屋数量。
空间复杂度:O(n),其中 n 是房屋数量。