柚子快報激活碼778899分享：算法: 位運算題目練習

http://yzkb.51969.com/

文章目錄

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

常見位運算總結(jié)

位運算

判定字符是否唯一

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

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

應該在放進去的時候就進行判斷~

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ù)之和

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

public int getSum(int a, int b) {

while(b != 0) {

// 進位

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

// 無符號相加

a = a ^ b;

// 最終結(jié)果 = carry(進位) + a(無符號相加結(jié)果)

// 因為不能使用 + ,所以再進入循環(huán)

b = carry;

}

return a;

}

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

這個解法以前沒見過,漲知識了~

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

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;

}

消失的兩個數(shù)字

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

坑:

找最后的結(jié)果時不僅要異或數(shù)組,還要異或 1 ~ n+2 的數(shù)字,如果想把這兩個放到同一個循環(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};

}

我找兩個數(shù)的二進制的不同的那一位用的是 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é)

基礎位運算

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

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

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

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

位運算的優(yōu)先級

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

異或(^) 運算的運算律

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

練手題目:

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

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

柚子快報激活碼778899分享：算法: 位運算題目練習

http://yzkb.51969.com/

推薦閱讀