Skip to content

Latest commit

 

History

History

c

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
c.go
c.go
 
 
c.txt
c.txt
 
 
c_test.go
c_test.go
 
 

README.md

视频讲解 第三题。

突破口：$0\le k\le 100$。

由于异或和都是非负数，所以等式 ( x 1 ⊕ x 2 ) + ( y 1 ⊕ y 2 ) = k 暗含着：

  • 0 ≤ x 1 ⊕ x 2 ≤ k
  • 0 ≤ y 1 ⊕ y 2 ≤ k

如果 x 1 ⊕ x 2 = i ，我们可以得到 y 1 ⊕ y 2 = k − i 。

异或运算类似加法，我们可以把 x 2 和 y 2 移到等式右侧。

枚举 ( x 2 , y 2 ) ，则 x 1 = x 2 ⊕ i 且 y 1 = y 2 ⊕ ( k − i ) 。

用哈希表统计遍历过的点的个数，把哈希表中的 ( x 2 ⊕ i , y 2 ⊕ ( k − i ) ) 的个数加入答案。

如果不方便在哈希表中插入 pair，可以把 ( x , y ) 压缩成一个整数，例如 2000000 x + y 。

class Solution:
    def countPairs(self, coordinates: List[List[int]], k: int) -> int:
        ans = 0
        cnt = Counter()
        for x, y in coordinates:
            for i in range(k + 1):
                ans += cnt[x ^ i, y ^ (k - i)]  # tuple 的括号可以省略
            cnt[x, y] += 1  # tuple 的括号可以省略
        return ans
class Solution {
    public int countPairs(List<List<Integer>> coordinates, int k) {
        int ans = 0;
        var cnt = new HashMap<Long, Integer>();
        for (var p : coordinates) {
            int x = p.get(0), y = p.get(1);
            for (int i = 0; i <= k; i++) {
                ans += cnt.getOrDefault((x ^ i) * 2000000L + (y ^ (k - i)), 0);
            }
            cnt.merge(x * 2000000L + y, 1, Integer::sum);
        }
        return ans;
    }
}
class Solution {
public:
    int countPairs(vector<vector<int>> &coordinates, int k) {
        int ans = 0;
        unordered_map<long long, int> cnt;
        for (auto &p: coordinates) {
            for (int i = 0; i <= k; i++) {
                // 直接 ans += cnt[...] 会插入不存在的点
                auto it = cnt.find((p[0] ^ i) * 2000000LL + (p[1] ^ (k - i)));
                if (it != cnt.end()) {
                    ans += it->second;
                }
            }
            cnt[p[0] * 2000000LL + p[1]]++;
        }
        return ans;
    }
};
func countPairs(coordinates [][]int, k int) (ans int) {
	type pair struct{ x, y int }
	cnt := map[pair]int{}
	for _, p := range coordinates {
		x, y := p[0], p[1]
		for i := 0; i <= k; i++ {
			ans += cnt[pair{x ^ i, y ^ (k - i)}]
		}
		cnt[pair{x, y}]++
	}
	return
}
var countPairs = function (coordinates, k) {
    let ans = 0;
    const cnt = new Map();
    for (const [x, y] of coordinates) {
        for (let i = 0; i <= k; i++) {
            ans += cnt.get((x ^ i) * 2000000 + (y ^ (k - i))) ?? 0;
        }
        const key = x * 2000000 + y;
        cnt.set(key, (cnt.get(key) ?? 0) + 1);
    }
    return ans;
};

复杂度分析

  • 时间复杂度：$\mathcal{O}(nk)$，其中 n 为 nums 的长度。
  • 空间复杂度：$\mathcal{O}(n)$。