全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/od
题目：统计差异值大于相似值二元组个数
知识点：数组进制转换整数范围循环
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
对于任意两个正整数A和B，定义它们之间的差异值和相似值：
差异值：A、B转换成二进制后，对于二进制的每一位，对应位置的bit值不相同则为1，否则为0;
相似值：A、B转换成二进制后，对于二进制的每一位，对应位置的bit值都为1则为1，否则为0;
现在有n个正整数A0 到A(n-1)，问有多少对(i,j)(0 <= i < j < n)，Ai和Aj的差异值大于相似值。
假设A=5,B=3；则A的二进制表示101；B的二进制表示011；则A与B的差异值二进制为110；相似值二进制为001；A与B的差异值十进制等于6，相似值十进制等于1，满足条件。
输入描述：
输入：一个n接下来n个正整数
数据范围：1<=n<=10^5, 1<=A[i]<2^30
输出描述：
输出：满足差异值大于相似值的对数
示例1
输入：
4
4 3 5 2
输出：
4
说明：
样例一解释：
满足条件的分别是(0,1) (0,3) (1,2) (2,3)，共4对
示例2
输入：
5
3 5 2 8 4
输出：
8
说明：
样例二解释：
满足条件的分别是(0,1) (0,3) (0,4) (1,2) (1,3) (2,3) (2,4) (3,4)
解题思路：
比较需要从右向左进行。
例如：
4和3
4:“100”，3：“11”
差异值：7（111），相似值：0（000）
代码实现一：
package com.codernav.demo.hwod.exam;
import java.util.Arrays;
import java.util.Scanner;
/**
* @title 统计差异值大于相似值二元组个数
* @Description 对于任意两个正整数A和B，定义它们之间的差异值和相似值：
* 差异值：A、B转换成二进制后，对于二进制的每一位，对应位置的bit值不相同则为1，否则为0;
* 相似值：A、B转换成二进制后，对于二进制的每一位，对应位置的bit值都为1则为1，否则为0;
* 现在有n个正整数A0 到A(n-1)，问有多少对(i,j)(0 <= i < j < n)，Ai和Aj的差异值大于相似值。
* 假设A=5,B=3；则A的二进制表示101；B的二进制表示011；则A与B的差异值二进制为110；
* 相似值二进制为001；A与B的差异值十进制等于6，相似值十进制等于1，满足条件。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/28
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();
String[] strings = sc.nextLine().split(" ");
int[] ints = Arrays.stream(strings).mapToInt(Integer::parseInt).toArray();
int res = 0;
for (int i = 0; i < ints.length; i++) {
for (int j = i + 1; j < ints.length; j++) {
if (handle(ints[i], ints[j])) {
res++;
}
}
}
System.out.println(res);
}
public static boolean handle(int A, int B) {
String binaryA = Integer.toBinaryString(A); //十进制转二进制
String binaryB = Integer.toBinaryString(B);
int indexA = binaryA.length() - 1; //二进制字符串长度
int indexB = binaryB.length() - 1;
StringBuilder chayi = new StringBuilder(); //差异值字符串
StringBuilder xiangsi = new StringBuilder(); //相似值字符串
while (indexA >= 0 || indexB >= 0) {
char charA = ' ';
char charB = ' ';
if (indexA >= 0) { //索引大于等于0才有值
charA = binaryA.charAt(indexA); //从尾部开始比较
}
if (indexB >= 0) {
charB = binaryB.charAt(indexB);
}
if (charA == charB) {
chayi.append("0");
} else {
chayi.append("1");
}
if (charA == '1' && charB == '1') {
xiangsi.append("1");
} else {
xiangsi.append("0");
}
indexA--;
indexB--;
}
int intChayi = Integer.valueOf(String.valueOf(chayi.reverse()), 2); //因为是从尾部开始比较，需要反转
int intXiangsi = Integer.valueOf(String.valueOf(xiangsi.reverse()), 2);
return intChayi > intXiangsi;
}
}
代码实现二：Java代码满分实现
package com.codernav.demo.hwod.exam;
import java.util.Scanner;
/**
* @title 统计差异值大于相似值二元组个数
* @Description 对于任意两个正整数A和B，定义它们之间的差异值和相似值：
* 差异值：A、B转换成二进制后，对于二进制的每一位，对应位置的bit值不相同则为1，否则为0;
* 相似值：A、B转换成二进制后，对于二进制的每一位，对应位置的bit值都为1则为1，否则为0;
* 现在有n个正整数A0 到A(n-1)，问有多少对(i,j)(0 <= i < j < n)，Ai和Aj的差异值大于相似值。
* 假设A=5,B=3；则A的二进制表示101；B的二进制表示011；则A与B的差异值二进制为110；
* 相似值二进制为001；A与B的差异值十进制等于6，相似值十进制等于1，满足条件。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/28
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] cnt = new int[32];
long ans = 0;
for (int i = 0; i < n; i++) {
int x = sc.nextInt();
int h = 0;
while (x > 0) {
x /= 2;
h++;
}
cnt[h]++;
ans += (i + 1) - cnt[h];
}
System.out.println(ans);
}
}
相关文章
