题目描述：
给你一个 二维 整数数组 coordinates 和一个整数 k ，其中 coordinates[i] = [xi, yi] 是第 i 个点在二维平面里的坐标。
我们定义两个点 (x1, y1) 和 (x2, y2) 的 距离 为 (x1 XOR x2) + (y1 XOR y2) ，XOR 指的是按位异或运算。
请你返回满足 i < j 且点 i 和点 j之间距离为 k 的点对数目。
数据范围：
$2\le coord.len \le 5\times 10 ^ 4; 0\le x_i, y_i \le 10^6; 0\le k \le 100$
题解：
首先注意到 $k$ 的范围很小，可以考虑对每一个 $(x_1, y_1)$ ，枚举 $k$ 的两个和数，也就是 $x1 \oplus x_2 = i, y_1 \oplus y_2 = k - i$ 。可以通过枚举 $i$ 得到 $x_2,y_2$ . $x_2 = i \oplus x_1, y_2 = (k - i) \oplus y_1$ 。然后就需要看 $x_2,y_2$ 在 $x_1,y_1$ 点对的前面出现了多少次，可以使用前缀和的方式统计。主要难点是在怎么hash点对。
我是用的位运算，发现 $x_i,y_i$ 的数据范围肯定小于int，那么直接用x<<32|y 得到hash值。好像不能使用x^y ，因为会出现 $(y,x)$ 也被统计进去。
也可以写一个仿函数
1
2
3
4
5
6
7
8
9
| struct pair_hash
{
template <class T1, class T2>
std::size_t operator() (const std::pair<T1, T2> &pair) const
{
return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
}
};
unordered_map<pair<int, int>, int, pair_hash> mp;
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
long long hash(long long x, long long y)
{
x <<= 32;
return x | y;
}
int countPairs(vector<vector<int>> &coordinates, int k)
{
int n = coordinates.size();
unordered_map<long long, int> mp;
int ans = 0;
for (auto &xy : coordinates)
{
int x = xy[0];
int y = xy[1];
for (int i = 0; i <= k; ++i)
{
int j = k - i;
int x2 = i ^ x;
int y2 = j ^ y;
if (mp.count(hash(x2, y2)))
{
ans += mp[hash(x2, y2)];
}
}
mp[hash(x, y)]++;
}
return ans;
}
};
|