位運(yùn)算的慣用套路，都在這兒！（算法 NO.2）
本文所列題目來自 LeetCode 中國網(wǎng)站，屬于算法面試中關(guān)于位運(yùn)算的經(jīng)典高頻考題。題解由 Doocs 開源社區(qū) leetcode 項目維護(hù)者提供。
目前已經(jīng)有超過 50 位開發(fā)者參與了此項目，期待你的加入！
項目地址：https://github.com/doocs/leetcode
題目1
題目描述
一個整型數(shù)組?nums?里除兩個數(shù)字之外，其他數(shù)字都出現(xiàn)了兩次。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。要求時間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)。
示例 1：
輸入：nums = [4,1,4,6]輸出：[1,6] 或 [6,1]
示例 2：
輸入：nums = [1,2,10,4,1,4,3,3]輸出：[2,10] 或 [10,2]
限制：
?2 <= nums <= 10000
解法
異或運(yùn)算求解。
首先明確，兩個相同的數(shù)異或之后的結(jié)果為 0。對該數(shù)組所有元素進(jìn)行異或運(yùn)算，結(jié)果就是兩個只出現(xiàn)一次的數(shù)字異或的結(jié)果。找出這個結(jié)果中某個二進(jìn)制位為 1 的位置，之后對數(shù)組所有元素進(jìn)行分類，二進(jìn)制位為 0 的異或到 a，二進(jìn)制位為 1 的異或到 b，結(jié)果就是 a，b。
Python3
class Solution:def singleNumbers(self, nums: List[int]) -> List[int]:xor_res = 0for num in nums:xor_res ^= numpos = 0while (xor_res & 1) == 0:pos += 1xor_res >>= 1a = b = 0for num in nums:t = num >> posif (t & 1) == 0:a ^= numelse:b ^= numreturn [a, b]
Java
class Solution {public int[] singleNumbers(int[] nums) {int xor = 0;for (int num : nums) {xor ^= num;}int pos = 0;while ((xor & 1) == 0) {++pos;xor >>= 1;}int a = 0, b = 0;for (int num : nums) {int t = num >> pos;if ((t & 1) == 0) {a ^= num;} else {b ^= num;}}return new int[] {a, b};}}
題目2
題目描述
在一個數(shù)組?nums?中除一個數(shù)字只出現(xiàn)一次之外，其他數(shù)字都出現(xiàn)了三次。請找出那個只出現(xiàn)一次的數(shù)字。
示例 1：
輸入：nums = [3,4,3,3]輸出：4
示例 2：
輸入：nums = [9,1,7,9,7,9,7]輸出：1
限制：
?1 <= nums.length <= 10000?1 <= nums[i] < 2^31
解法
統(tǒng)計所有數(shù)字每個位中 1 出現(xiàn)的次數(shù)，對于某個位，1 出現(xiàn)的次數(shù)一定是 3 的倍數(shù) +1 或 0。對這個數(shù) %3 得到的結(jié)果就是那個出現(xiàn)一次的數(shù)字在該位上的值。
Python3
class Solution:def singleNumber(self, nums: List[int]) -> int:bits = [0 for _ in range(32)]for num in nums:for i in range(32):bits[i] += (num & 1)num >>= 1res = 0for i in range(32):if bits[i] % 3 == 1:res += (1 << i)return res
Java
class Solution {public int singleNumber(int[] nums) {int[] bits = new int[32];for (int num : nums) {for (int i = 0; i < 32; ++i) {bits[i] += (num & 1);num >>= 1;}}int res = 0;for (int i = 0; i < 32; ++i) {if (bits[i] % 3 == 1) {res += (1 << i);}}return res;}}
題目3
題目描述
集合?S?包含從1到?n?的整數(shù)。不幸的是，因為數(shù)據(jù)錯誤，導(dǎo)致集合里面某一個元素復(fù)制了成了集合里面的另外一個元素的值，導(dǎo)致集合丟失了一個整數(shù)并且有一個元素重復(fù)。
給定一個數(shù)組?nums?代表了集合?S?發(fā)生錯誤后的結(jié)果。你的任務(wù)是首先尋找到重復(fù)出現(xiàn)的整數(shù)，再找到丟失的整數(shù)，將它們以數(shù)組的形式返回。
示例 1:
輸入: nums = [1,2,2,4]輸出: [2,3]
注意:
1.給定數(shù)組的長度范圍是[2, 10000]。2.給定的數(shù)組是無序的。
解法
首先使用 1 到 n 的所有數(shù)字做異或運(yùn)算，然后再與數(shù)組中的所有數(shù)字異或，得到的值就是缺失數(shù)字與重復(fù)的數(shù)字異或的結(jié)果。
接著計算中這個值中其中一個非零的位 pos。然后 pos 位是否為 1，將 nums 數(shù)組的元素分成兩部分，分別異或；接著將?1~n?的元素也分成兩部分，分別異或。得到的兩部分結(jié)果分別為 a,b，即是缺失數(shù)字與重復(fù)數(shù)字。
最后判斷數(shù)組中是否存在 a 或 b，若存在 a，說明重復(fù)數(shù)字是 a，返回?[a,b]，否則返回?[b,a]。
Python3
class Solution:def findErrorNums(self, nums: List[int]) -> List[int]:res = 0for num in nums:res ^= numfor i in range(1, len(nums) + 1):res ^= ipos = 0while (res & 1) == 0:res >>= 1pos += 1a = b = 0for num in nums:if ((num >> pos) & 1) == 0:a ^= numelse:b ^= numfor i in range(1, len(nums) + 1):if ((i >> pos) & 1) == 0:a ^= ielse:b ^= ifor num in nums:if num == a:return [a, b]return [b, a]
Java
class Solution {public int[] findErrorNums(int[] nums) {int res = 0;for (int num : nums) {res ^= num;}for (int i = 1, n = nums.length; i < n + 1; ++i) {res ^= i;}int pos = 0;while ((res & 1) == 0) {res >>= 1;++pos;}int a = 0, b = 0;for (int num : nums) {if (((num >> pos) & 1) == 0) {a ^= num;} else {b ^= num;}}for (int i = 1, n = nums.length; i < n + 1; ++i) {if (((i >> pos) & 1) == 0) {a ^= i;} else {b ^= i;}}for (int num : nums) {if (num == a) {return new int[]{a, b};}}return new int[]{b, a};}}
題目4
題目描述
請實現(xiàn)一個函數(shù)，輸入一個整數(shù)，輸出該數(shù)二進(jìn)制表示中 1 的個數(shù)。例如，把 9?表示成二進(jìn)制是 1001，有 2 位是 1。因此，如果輸入 9，則該函數(shù)輸出 2。
示例 1：
輸入：00000000000000000000000000001011輸出：3解釋：輸入的二進(jìn)制串 00000000000000000000000000001011?中，共有三位為 '1'。
示例 2：
輸入：00000000000000000000000010000000輸出：1解釋：輸入的二進(jìn)制串 00000000000000000000000010000000?中，共有一位為 '1'。
示例 3：
輸入：11111111111111111111111111111101輸出：31解釋：輸入的二進(jìn)制串 11111111111111111111111111111101 中，共有 31 位為 '1'。
解法
n & (n - 1)?會消除 n 中最后一位中的 1。
Python3
class Solution:def hammingWeight(self, n: int) -> int:res = 0while n:n &= (n - 1)res += 1return res
Java
public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {int res = 0;while (n != 0) {n &= (n - 1);++res;}return res;}}
長按識別下圖二維碼，關(guān)注公眾號「Doocs開源社區(qū)」，第一時間跟你們分享好玩、實用的技術(shù)文章與業(yè)內(nèi)最新資訊。