柚子快報(bào)激活碼778899分享：算法: 位運(yùn)算題目練習(xí)

http://yzkb.51969.com/

文章目錄

位運(yùn)算判定字符是否唯一丟失的數(shù)字兩整數(shù)之和只出現(xiàn)一次的數(shù)字 II消失的兩個(gè)數(shù)字

常見(jiàn)位運(yùn)算總結(jié)

位運(yùn)算

判定字符是否唯一

有很多解法,比如hash表,或者給字符串排個(gè)序,然后遍歷…

寫(xiě)這道題時(shí)沒(méi)注意到如果出現(xiàn)奇數(shù)個(gè)相同字符,此時(shí)就應(yīng)該返回false了. 而不是全部放到位圖中,最后再判斷…

應(yīng)該在放進(jìn)去的時(shí)候就進(jìn)行判斷~

public boolean isUnique(String astr) {

int n = astr.length();

if(n > 26) {

return false;

}

int bit = 0;

for(int i = 0; i < n; i++) {

int m = astr.charAt(i)-'a';

if(((bit >> m) & 1) == 0) {

bit ^= 1 << m;

} else {

return false;

}

}

return true;

}

丟失的數(shù)字

直接秒了~

public int missingNumber(int[] nums) {

int n = nums.length;

int sum = 0;

for (int i = 0; i < n; i++) {

sum ^= i;

sum ^= nums[i];

}

sum ^= n;

return sum;

}

兩整數(shù)之和

看這個(gè)講解看懂了~ 兩整數(shù)之和

public int getSum(int a, int b) {

while(b != 0) {

// 進(jìn)位

int carry = (a & b) << 1;

// 無(wú)符號(hào)相加

a = a ^ b;

// 最終結(jié)果 = carry(進(jìn)位) + a(無(wú)符號(hào)相加結(jié)果)

// 因?yàn)椴荒苁褂?+ ,所以再進(jìn)入循環(huán)

b = carry;

}

return a;

}

只出現(xiàn)一次的數(shù)字 II

這個(gè)解法以前沒(méi)見(jiàn)過(guò),漲知識(shí)了~

這有個(gè)題解: 只出現(xiàn)一次的數(shù)字 II（有限狀態(tài)自動(dòng)機(jī) + 位運(yùn)算，清晰圖解）

public int singleNumber(int[] nums) {

int ret = 0;

for(int i=0;i<32;i++) {

int sum = 0;

for(int j=0;j

sum += (nums[j] >> i) & 1;

}

ret += (sum%3)<

}

return ret;

}

消失的兩個(gè)數(shù)字

這道題跟 只出現(xiàn)一次的數(shù)字 III 差不多.

坑:

找最后的結(jié)果時(shí)不僅要異或數(shù)組,還要異或 1 ~ n+2 的數(shù)字,如果想把這兩個(gè)放到同一個(gè)循環(huán)內(nèi),那么要注意 它們倆的條件不同 !!

public int[] missingTwo(int[] nums) {

int sum = 0;

int n = nums.length;

for (int i = 0; i < n; i++) {

sum ^= nums[i];

sum ^= i + 1;

}

sum ^= n + 1;

sum ^= n + 2;

int p = sum & (-sum);

int ret1 = 0;

for (int i = 0; i < n; i++) {

if ((nums[i] & p) == 0) {

ret1 ^= nums[i];

}

}

for (int i = 1; i <= n + 2; i++) {

if ((i & p) == 0) {

ret1 ^= i;

}

}

int ret2 = sum ^ ret1;

return new int[]{ret1, ret2};

}

我找兩個(gè)數(shù)的二進(jìn)制的不同的那一位用的是 sum & (-sum)

題解用的跟我不一樣,他是一位一位檢查的~

public int[] missingTwo(int[] nums) {

int sum = 0;

int n = nums.length;

for (int i = 0; i < n; i++) {

sum ^= nums[i];

sum ^= i + 1;

}

sum ^= n + 1;

sum ^= n + 2;

int p = 0;

while (true) {

if (((sum >> p) & 1) == 1)

break;

else

p++;

}

int ret1 = 0;

for (int i = 0; i < n; i++) {

if ((nums[i] & (1 << p)) == 0) {

ret1 ^= nums[i];

}

}

for (int i = 1; i <= n + 2; i++) {

if ((i & (1 << p)) == 0) {

ret1 ^= i;

}

}

int ret2 = sum ^ ret1;

return new int[]{ret1, ret2};

}

常見(jiàn)位運(yùn)算總結(jié)

基礎(chǔ)位運(yùn)算

<< 左移>> 右移~ 按位取反. 記憶方法: 0 變 1, 1 變 0.& 按位與. 記憶方法: 有 0 就是 0.| 按位或. 記憶方法: 有 1 就是 1.^ 按位異或. 記憶方法: 相同為0,相異為一. 無(wú)進(jìn)位相加. 給一個(gè)數(shù) n,確定它的二進(jìn)制表示中的第 x 位是 0 還是 1. n = (n >> x) & 1 將一個(gè)數(shù) n 的二進(jìn)制表示中的第 x 位修改成 1. n = n | ( 1 << x ) 將一個(gè)數(shù) n 的二進(jìn)制表示中的第 x 位修改成 0. n = n & ( ~ (1 << x) ) 位圖 提前一個(gè)數(shù) n 的二進(jìn)制表示中的最右側(cè)的 1 n & - n

- n 的含義其實(shí)就是把 n 的二進(jìn)制表示中的最右側(cè)的 1 的左側(cè)區(qū)域全部變成相反. 我們都知道 - n = ~ n + 1

干掉一個(gè)數(shù) n 的二進(jìn)制表示中最右側(cè)的 1 n & (n - 1)

n - 1 其實(shí)是將 n 的二進(jìn)制表示中的最右側(cè)的 1 的右邊區(qū)域(包括1) 全部變成相反

位運(yùn)算的優(yōu)先級(jí)

在使用時(shí)直接加括號(hào),不要背優(yōu)先級(jí)順序 !!

異或(^) 運(yùn)算的運(yùn)算律

a ^ 0 = aa ^ a = 0 (消消樂(lè))a ^ b ^ c = a ^ (b ^ c)

練手題目:

位 1 的個(gè)數(shù)比特位計(jì)數(shù)漢明距離只出現(xiàn)一次的數(shù)字只出現(xiàn)一次的數(shù)字 III

本文到這里就結(jié)束啦~

柚子快報(bào)激活碼778899分享：算法: 位運(yùn)算題目練習(xí)

http://yzkb.51969.com/

推薦閱讀