leetcode演算法之位運算

今天來盤一盤 **位運算 ** 這類題目

使用python刷題分類整理的筆記,請參考: //github.com/lxztju/leetcode-algorithm/tree/v1

位運算

  • 461 漢明距離 (Easy)
  • 136 只出現一次的數字 (Easy)
  • 268 丟失的數字 (Easy)
  • 260 只出現一次的數字 III (Medium)
  • 190 顛倒二進位位 (Easy)
  • 231 2的冪 (Easy)
  • 342 4的冪 (Easy)
  • 693 交替位二進位數 (Easy)
  • 476 數字的補數 (Easy)
  • 371 兩整數之和 (Easy)
  • 318 最大單詞長度乘積 (Medium)
  • 338 比特位計數 (Medium)

461 漢明距離 (Easy)

class Solution {
public:
    int hammingDistance(int x, int y) {
    // 統計不同的位數
        auto sx = bitTransfer(x);
        auto sy = bitTransfer(y);
        int cnt = 0;
        for ( int i = 0; i< 32; i++){
            if (sy[i] != sx[i])
                cnt++;
        }
        return cnt;

    }
    string bitTransfer(int x){
        // 將轉換為01的二進位字元串
        string s(32, '0');
        if (x == 0) return s;
        int i = 31;
        while ( x > 0){
            int res = x % 2;
            s[i] = (res + '0');
            x /= 2;
            i--;
        }
        return s;
    }
};
  • 異或操作
class Solution {
public:
    int hammingDistance(int x, int y) {
    // 利用異或操作，不同的為1， 然後統計1的個數
        int res = x ^ y;
        int cnt = 0;
        while ( res > 0){
            cnt += (res & 1);
            res >>= 1;
        }
        return cnt;

    }

};

136 只出現一次的數字 (Easy)

  • 相同元素的異或值為0
  • 0與任何元素的異或值為其自身
  • 因此整個序列所有元素的異或值即為僅僅出現一次的元素
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (auto num:nums){
            res ^= num;
        }
        return res;
    }
};

  • 這個題也可以排序，然後查找僅僅出現一次的元素

  • 也可以利用哈希表來查找。

268 丟失的數字 (Easy)

  • 方法1： 排序

  • 方法2： 哈希表

  • 方法3： 位運算

    • 與上一題的處理方法類似，新構建一個0-n的數組6與原來的數組結合形成大數組，缺失的數字就是在新數組中及你進出現一次的數字
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0;
        for ( int i=0; i< nums.size(); i++){
            res ^= (nums[i] ^ i);
        }
        return res ^ nums.size();
    }
};

260 只出現一次的數字 III (Medium)

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        // 整個數組進行異或操作，得到兩個單獨出現的字元的異或值
        int numXor = 0;
        for (auto num: nums)
            numXor ^= num;

        // 按照這個異或者，將原始數組分為兩部分，每個單獨出現的數字分別位於其中的一部分。
        int split = 1;
        while ((numXor & split) == 0){
            split <<= 1;
        }
        vector<int> res(2, 0);
        for (auto num : nums){
            if (num & split)
                res[0] ^= num;
            else
                res[1] ^= num;
        }
        return res;
    }
};

190 顛倒二進位位 (Easy)

  • 直接顛倒
class Solution {
  public:
  uint32_t reverseBits(uint32_t n) {
    uint32_t res = 0, power = 31;
    while (n != 0) {
      res += (n & 1) << power;
      n >>= 1;
      power -= 1;
    }
    return res;
  }
};

231 2的冪 (Easy)

class Solution {
public:
    bool isPowerOfTwo(int n) {
        int res = 0;
        int cnt = 0;
        if ( n < 0) return false;
        while ( n != 0){
            if ((n & 1) == 1)
                cnt++;
            n >>= 1;
        }
        return cnt == 1;
    }
};

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return ( n > 0 && (( n & (n - 1) )== 0) );
    }
};

342 4的冪 (Easy)

class Solution {
public:
    bool isPowerOfFour(int num) {
    	// 2的冪
        if (num > 0 && (num & ( num - 1 )) == 0)
        	// 判斷是否是4的冪
            return (num & 0x55555555) == num;
        return false;
    }
};

693 交替位二進位數 (Easy)

  • 直接模擬整個交替過程，判斷是否交替。
class Solution {
public:
    bool hasAlternatingBits(int n) {
        int tmp1 = n & 1;
        n >>= 1;
        while ( n != 0){
            int tmp2 = n & 1;
            n >>= 1;
            if (tmp1 == tmp2)
                return false;
            tmp1 = tmp2;
        }
        return true;
    }
};

476 數字的補數 (Easy)

  • 101(5)的補數為111(7)減101
class Solution {
public:
    int findComplement(int num) {
        long tmp = 1;
        while( tmp <= num){
            tmp <<= 1;
        }
        return tmp - 1 - num;
    }
};

371 兩整數之和 (Easy)

class Solution {
public:
    int getSum(int a, int b) {
        return a + b;
    }
};
  • 題目要求不使用+ -符號
  • 使用在數字電子電路中，加法電路的設計方式
  • 針對二進位位，進位位為採用兩個二進位的與運算， 和為兩個二進位的異或運算的結果。
class Solution {
public:
    int getSum(int a, int b) {

        while (b){
            auto carry = (static_cast<unsigned int> (a & b) )<< 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
};

318 最大單詞長度乘積 (Medium)

  • 使用位運算作為編碼來統計出現字母的種類數。
class Solution {
public:
    int maxProduct(vector<string>& words) {
        // 使用一個整形數字來表每個單詞所含有字母的種類。，這個整形數字的後26位，如果某一位為1，說明出現這個字母
        int n = words.size();
        vector<int> code(n, 0);
        for (int i = 0; i < n; i++){
            for (int j=0; j < words[i].size(); j++){
                code[i] |= 1 << (words[i][j] - 'a');
            }
        }
        int res = 0;
        for ( int i = 0; i < n-1; i++){
            for ( int j = i+1; j < n; j++){
                if ((code[i] & code[j]) == 0){
                    int tmp = (words[i].size()) * (words[j].size());
                    res = max(res, tmp);
                }
            }
        }
        return res;
    }
};

338 比特位計數 (Medium)

  • 直接統計
class Solution {
public:
    vector<int> countBits(int num) {
        // 直接統計
        vector<int> res;
        for (int i = 0; i<=num; i++){
            int tmp = 0;
            int tmp1 = i;
            while (tmp1 != 0){
                tmp += (tmp1 & 1);
                tmp1 >>= 1;
            }
            res.push_back(tmp);
        }
        return res;
    }
};

更多分類刷題資料

Tags:

VirMach 便宜 VPS