leetcode
题目名
- 汉明距离总和
题面
两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。
计算一个数组中，任意两个数之间汉明距离的总和。
示例:
输入: 4, 14, 2
输出: 6
解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。（这样表示是为了体现后四位之间关系）
所以答案为：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
注意:
数组中元素的范围为从 0到 10^9。
数组的长度不超过 10^4。
分析
一开始想两层for循环暴力枚举一下所有数对。数组长度给的范围很微妙，只有两层for循环不会TLE，但是汉明距离的计算做不到O（1），gg。
后来一想只要求和，只要统计一下所有数各个对应二进制位上1和0的数目，将这两个数目相乘（根据元素范围，二进制位数31即可），就是这一位最终的结果（这一位对总和的贡献），再将各个位的结果相加就能得到最终总和。
代码
class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
int yi[31]={0},li[31]={0},res=0;
for(int i=0;i<nums.size();i++)
{
for(int j=0;j<30;j++)
if((nums[i]>>j&1)==1)
yi[j]++;
else
li[j]++;
}
for(int i=0;i<30;i++)
res+=yi[i]*li[i];
return res;
}
};
小小总结一下，就像该题讨论区一位老哥所讲：位运算的题往往需要一个31次（int范围内）的for循环，”仅包含字母“的题目往往需要写一个 26 次（26个小写英文字母嘛）的 for 循环（话说回来，我这两天做的题还真就都遇到了位运算和仅含字母，还挺巧……不过仅含字母或者字符串中各字符类型一致也有可能是trie树。ORZ）。
acwing
题目名
- 整数配对
题面
给定 n 个整数 a1,a2,…,an，n 为偶数。
现在要将它们两两配对，组成 n2 个数对。
ai 和 aj 能够配对，当且仅当 ai=aj。
每次增加操作可以使其中的任意一个数 ai 加一。
请问，要使得 n 个整数能够成功组成 n2 个数对，至少要进行多少次增加操作。
输入格式
第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
一个整数，表示所需最少操作次数。
数据范围
1≤n≤105,
1≤ai≤104
输入样例1：
6
5 10 2 3 14 5
输出样例1：
5
输入样例2：
2
1 100
输出样例2：
99
分析
挺好想的，排序，两两作差再将结果相加即得最少操作次数。
代码
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n,a[100005];
long long res=0;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
for(int i=1;i<n;i+=2)
res +=a[i]-a[i-1];
cout<<res<<endl;
return 0;
}