网站模板 带数据库,下载网页上的视频,广州网站建设 seo,太原公司注册本文涉及知识点
位运算 数学 哈希映射
LeetCode 2857. 统计距离为 k 的点对
给你一个 二维 整数数组 coordinates 和一个整数 k #xff0c;其中 coordinates[i] [xi, yi] 是第 i 个点在二维平面里的坐标。 我们定义两个点 (x1, y1) 和 (x2, y2) 的 距离 为 (x1 XOR x2) …本文涉及知识点
位运算 数学 哈希映射
LeetCode 2857. 统计距离为 k 的点对
给你一个 二维 整数数组 coordinates 和一个整数 k 其中 coordinates[i] [xi, yi] 是第 i 个点在二维平面里的坐标。 我们定义两个点 (x1, y1) 和 (x2, y2) 的 距离 为 (x1 XOR x2) (y1 XOR y2) XOR 指的是按位异或运算。 请你返回满足 i j 且点 i 和点 j之间距离为 k 的点对数目。 示例 1 输入coordinates [[1,2],[4,2],[1,3],[5,2]], k 5 输出2 解释以下点对距离为 k
(0, 1)(1 XOR 4) (2 XOR 2) 5 。(2, 3)(1 XOR 5) (3 XOR 2) 5 。 示例 2 输入coordinates [[1,3],[1,3],[1,3],[1,3],[1,3]], k 0 输出10 解释任何两个点之间的距离都为 0 所以总共有 10 组点对。
提示 2 coordinates.length 50000 0 xi, yi 106 0 k 100
k 100
由于异或运算的结果非负所以(x1 XOR x2) (y1 XOR y2) 有101种情况 即 (x1 XOR x2) k1 (y1 XOR y2) 100- k1。k1 ∈ \in ∈ [0,100] mPre 记录前面的数及出现次数。对于每个数分别枚举k1。 将x1,y1 压缩成long long 避免写hash 函数。
时间复杂度: o(nk) n 是的coordinates长度。
代码
class Solution {
public:int countPairs(vectorvectorint coordinates, int k) {unordered_maplong long, int mPre;const long long llUnit 10000000;int iRet 0;for (const auto v : coordinates){for (int k1 0; k1 k; k1){long long mask llUnit * (v[0] ^ k1) (v[1] ^ (k - k1));if (mPre.count(mask)){iRet mPre[mask];}}long long tmp llUnit * v[0] v[1];mPre[tmp];}return iRet;}
};扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
