二进制中 1 的个数
输入一个整数，输出该数二进制表示中 1 的个数。
- 知道就知道，不知道没办法。
- 题解原话，有一个性质：n&(n−1)，会将n的二进制中最低位由1变成0
public int NumberOf1(int n) {
int cnt = 0;
while (n != 0) {
cnt++;
n &= (n - 1);
}
return cnt;
}
数组中只出现一次的数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次，找出这两个数。
- hash表
import java.util.*;
public class Solution {
public int[] FindNumsAppearOnce (int[] array) {
HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
ArrayList<Integer> res = new ArrayList<Integer>();
//遍历数组
for(int i = 0; i < array.length; i++)
//统计每个数出现的频率
if(!mp.containsKey(array[i]))
mp.put(array[i], 1);
else
mp.put(array[i], mp.get(array[i]) + 1);
//再次遍历数组
for(int i = 0; i < array.length; i++)
//找到频率为1的两个数
if(mp.get(array[i]) == 1)
res.add(array[i]);
//整理次序
if(res.get(0) < res.get(1))
return new int[] {res.get(0), res.get(1)};
else
return new int[] {res.get(1), res.get(0)};
}
}
- 异或
- 个人不喜欢这个方法，感觉很难从逻辑上考虑到这层关系。除非为了用位运算而去用位运算。
- 两个相等的元素异或的结果为 0，而 0 与任意数 x 异或的结果都为 x。
- x^x^y^y^z^k = z^k。
- diff = diff & -diff 得到 diff 位级表示中最右侧为 1 的位,用于区分两个元素。
public int[] FindNumsAppearOnce (int[] nums) {
int[] res = new int[2];
int diff = 0;
for (int num : nums)
diff ^= num;
diff &= -diff;
for (int num : nums) {
if ((num & diff) == 0)
res[0] ^= num;
else
res[1] ^= num;
}
if (res[0] > res[1]) {
swap(res);
}
return res;
}
private void swap(int[] nums) {
int t = nums[0];
nums[0] = nums[1];
nums[1] = t;
}
