华为OD机试 - 统计差异值大于相似值二元组个数 - 二进制（Java 新系统 200分）

华为OD机试 新系统 题库疯狂收录中刷题点这里专栏导读本专栏收录于《华为OD机试JAVA真题》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。一、题目描述对于任意两个正整数A和B定义它们之间的 差异值和相似值差异值A、B转换成二进制后对于二进制的每一位对应位置的bit 值不相同则为1否则为0相似值A、B转换成二进制后对于二进制的每一位对应位置的bit值都为1则为1否则为0现在有n个正整数A0到An-1问有多少(i, j) (0ijn)Ai 和Aj的差异值大于相似值。假设A5B3则A的二进制表示101B的二进制表示011则A与B的差异值二进制为110相似值二进制为001A与B的差异值十进制等于6相似值十进制等于1满足条件。二、输入描述一个n接下来n个正整数数据范围1n1051A[i]230三、输出描述满足差异值大于相似值的对数四、测试用例测试用例11、输入44 3 5 22、输出43、说明二进制长度分别为4 - 100长度 33 - 11长度 25 - 101长度 32 - 10长度 2长度分组长度 22 个长度 32 个总对数4 * 3 / 2 6同长度对数C(2,2) C(2,2) 1 1 2答案6 - 2 4测试用例21、输入53 5 2 8 42、输出83、说明二进制长度分别为3 - 25 - 32 - 28 - 44 - 3分组长度 22 个长度 32 个长度 41 个总对数C(5,2)10同长度对数C(2,2)C(2,2)112答案10-28五、解题思路对于两个正整数 A、B若 A 和 B 的二进制最高位所在位置不同也就是二进制长度不同那么一定有A ^ B A B若 A 和 B 的二进制最高位所在位置相同也就是二进制长度相同那么一定有A ^ B A B情况1二进制长度不同例如A 8 - 1000B 3 - 0011最高位位置不同那么在更高的那一位上A ^ B 1A B 0而更高位已经决定了大小关系所以A ^ B A B情况2二进制长度相同例如A 5 - 101B 6 - 110它们最高位都在第 3 位从左往右看因此最高位上A ^ B 0A B 1最高位就已经决定A ^ B A B六、Java算法源码publicclassOdTest{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);// 读取元素个数 nintnsc.nextInt();// cnt[len] 表示二进制长度为 len 的数字出现的次数// 题目中 A[i] 2^30因此二进制长度最大为 30long[]cntnewlong[31];// 读取每个数并统计它的二进制长度for(inti0;in;i){intxsc.nextInt();// 计算 x 的二进制长度intlen0;while(x0){len;x1;}// 记录该长度的数量cnt[len];}// 先计算总对数C(n, 2)longtotalPairs(long)n*(n-1)/2;// 统计二进制长度相同的数对数量longsameLenPairs0;for(intlen1;len30;len){sameLenPairscnt[len]*(cnt[len]-1)/2;}// 满足条件的数对 总对数 - 二进制长度相同的数对longanstotalPairs-sameLenPairs;// 按题意输出结果不添加任何多余提示System.out.print(ans);sc.close();}}七、效果展示1、输入41 2 4 82、输出63、说明二进制长度分别为1 - 12 - 24 - 38 - 4四个数长度都不同所以任意两两都满足条件下一篇华为OD机试 - 简易内存池 - 逻辑分析Java 新系统 200分本专栏收录于《华为OD机试JAVA真题》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。