Algorithms & Data Structures : Bit Operations Problems

Problem

LeetCode 78. Subsets
[bit operation]

LeetCode 2135. Count Words Obtained After Adding a Letter
[bit operation]

LeetCode 201. Bitwise AND of Numbers Range
[bit operation][math]

LeetCode : 477. Total Hamming Distance
[bit operation][math]

LeetCode : 393. UTF-8 Validation
[Bit Operation][Array]

LeetCode : 2433. Find The Original Array of Prefix Xor
[Bit Operation]

LeetCode 78. Subsets

每一個 bit 都代表著 nums 上的一個數字，所以我們需要遍尋 0…00 ~ 1…11
想要遍尋每一種 bit ， 例如我們想要遍尋三個 bit ， 那我們只需要遍尋數字 0 ~ 2³ — 1 就可以了，所以就用一個 for 迴圈去遍尋 0 ~ 7。

最後再將該 bitmask 轉換成陣列。

class Solution {
public: 
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        int p = pow(2, nums.size());
        for(int i = 0;i < p;i++) {
            vector<int> tmp;
            int bitmask = 1;
            for(int j = 0;j < nums.size();j++) {
                if(i & bitmask) {
                    tmp.push_back(nums[j]);
                }
                bitmask = bitmask << 1;
            }
            res.push_back(tmp);
        } 
        return res;
    }
};

LeetCode 2135. Count Words Obtained After Adding a Letter

為 startWords 製作好 bit mask ，並放到 hash table 內。
接著遍尋 targetWords，每個字串都拔掉一個字母，看看能不能符合 hash table 內的 bit mask。

class Solution {
public:
    int wordCount(vector<string>& startWords, vector<string>& targetWords) {
        unordered_map<bitset<32>, bool> um;
        int res = 0;
        for(int i = 0;i < startWords.size();i++) {
            bitset<32> bs;
            for(int j = 0;j < startWords[i].size();j++) {
                bs[startWords[i][j] - 'a'] = true;
            }
            um[bs] = true;
        }
        
        for(int i = 0;i < targetWords.size();i++) {
            bitset<32> bs;
            for(int j = 0;j < targetWords[i].size();j++) {
                bs[targetWords[i][j] - 'a'] = true;
            }
            
            for(int j = 0;j < 26;j++) {
                if(false == bs[j]) {
                    continue;
                }
                bs[j] = false;
                
                if(um.find(bs) != um.end()) {
                    res++;
                    break;
                }
                
                bs[j] = true;
            }
        }
return res;
    }
};

LeetCode 201. Bitwise AND of Numbers Range

// TODO 選一個不用 long long 的解法
#define LL long long
class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int ans = 0;
        
        LL base  = 1;
        LL basei = 0;
        while(base <= left) {
            LL mask = 0;
            for(int i = basei + 1;i < 32;i++) {
                mask |= (1 << i);
            }
            
            // 將 left 視為 2 進制，找尋到 left 非 0 的部位
            // 加上這個部位後，把這個部位後面的部位通通變成 0，看看是否還在範圍內
            // 若在範圍內，表示範圍內有個數可以將這個部位變成 0
            // 若不在範圍內，表示範圍內沒有數可以將這個部位變成 0，於是可以計入 ans
            //
            // "加上這個部位後，把這個部位後面的部位通通變成 0"，意指該部位為 0 且大於 left 的最小值。
            if(0 != (left & base) && ((left + base) & mask) > right) {
                ans |= base;
            }
            
            base *= 2;
            basei++;
        }
        
        return ans;
    }
};

LeetCode : 477. Total Hamming Distance

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int ans = 0;
        
        vector<int> bc = vector<int>(32, 0); // bit count
        vector<int> zc = vector<int>(32, 0); // zero count
        
        for(int i = 0;i < nums.size();i++) {
            int base = 1;
            
            for(int j = 0;j < 30;j++) {
                if(nums[i] & base) {
                    ans += zc[j];
                } else {
                    ans += bc[j];
                }
                base *= 2;
            }
            
            base = 1;
            for(int j = 0;j < 30;j++) {
                if(nums[i] & base) {
                    bc[j]++;
                } else {
                    zc[j]++;
                }
                base *= 2;
            }
        }
        
        return ans;
    }
};

LeetCode : 393. UTF-8 Validation

// TODO : 效能太差
// DFS
class Solution {
public:
    
    bool is1BytesUTF(int nowi, vector<int> &d) {
        if(nowi + 1 <= d.size()) {
            return (0 == (d[nowi] & (1 << 7)));
        }
        return false;
    }
    
    bool is2BytesUTF(int nowi, vector<int> &d) {
        if(nowi + 2 <= d.size()) {
            return (6 == (d[nowi] >> 5)) &&
                   (2 == (d[nowi + 1] >> 6));
        }
        return false;
    }
    
    bool is3BytesUTF(int nowi, vector<int> &d) {
        if(nowi + 3 <= d.size()) {
            return (14 == (d[nowi] >> 4)) &&
                   (2  == (d[nowi + 1] >> 6)) &&
                   (2  == (d[nowi + 2] >> 6));
        }
        return false;
    }
    
    bool is4BytesUTF(int nowi, vector<int> &d) {
        if(nowi + 4 <= d.size()) {
            return (30 == (d[nowi] >> 3)) &&
                   (2  == (d[nowi + 1] >> 6)) &&
                   (2  == (d[nowi + 2] >> 6)) &&
                   (2  == (d[nowi + 3] >> 6));
        }
        return false;
    }
    
    bool dfs(int nowi, vector<int> &d) {
        if(nowi == d.size()) {
            return true;    
        }
        
        bool result = false;
        if(is1BytesUTF(nowi, d)) {
            result = dfs(nowi + 1, d);
        }
        if(result) {
            return true;
        }
        
        if(is2BytesUTF(nowi, d)) {
            result = dfs(nowi + 2, d);
        }
        if(result) {
            return true;
        }
        
        if(is3BytesUTF(nowi, d)) {
            result = dfs(nowi + 3, d);
        }
        if(result) {
            return true;
        }
        
        if(is4BytesUTF(nowi, d)) {
            result = dfs(nowi + 4, d);
        }
        if(result) {
            return true;
        }
        
        return false;
    }
    
    bool validUtf8(vector<int>& data) {
        return dfs(0, data);
    }
};

LeetCode : 2433. Find The Original Array of Prefix Xor

class Solution {
public:
    vector<int> findArray(vector<int>& pref) {
        vector<int> ans = vector<int>(pref.size());
        
        ans[0] = pref[0];
        for(int i = 1;i < pref.size();i++) {
            ans[i] = pref[i - 1] ^ pref[i];
        }
        
        return ans;
    }
};