二進(jìn)制中 1 的個(gè)數(shù)
輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中 1 的個(gè)數(shù)。
- 知道就知道，不知道沒辦法。
- 題解原話，有一個(gè)性質(zhì)：n&(n?1)，會(huì)將n的二進(jìn)制中最低位由1變成0
public int NumberOf1(int n) {
int cnt = 0;
while (n != 0) {
cnt++;
n &= (n - 1);
}
return cnt;
}
數(shù)組中只出現(xiàn)一次的數(shù)字
一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次，找出這兩個(gè)數(shù)。
- 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>();
//遍歷數(shù)組
for(int i = 0; i < array.length; i++)
//統(tǒng)計(jì)每個(gè)數(shù)出現(xiàn)的頻率
if(!mp.containsKey(array[i]))
mp.put(array[i], 1);
else
mp.put(array[i], mp.get(array[i]) + 1);
//再次遍歷數(shù)組
for(int i = 0; i < array.length; i++)
//找到頻率為1的兩個(gè)數(shù)
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)};
}
}
- 異或
- 個(gè)人不喜歡這個(gè)方法，感覺很難從邏輯上考慮到這層關(guān)系。除非為了用位運(yùn)算而去用位運(yùn)算。
- 兩個(gè)相等的元素異或的結(jié)果為 0，而 0 與任意數(shù) x 異或的結(jié)果都為 x。
- x^x^y^y^z^k = z^k。
- diff = diff & -diff 得到 diff 位級(jí)表示中最右側(cè)為 1 的位,用于區(qū)分兩個(gè)元素。
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;
}
