位运算(跟着英雄学算法)

位运算(跟着英雄学算法),第1张

位运算(跟着英雄学算法)

位运算肯定先转二进制,我的快速记忆是都是1反1否则反0

比如 2&1就为10与01进行位运算就为0,3&1就为 11与01进行位运算结果为1

位1的个数

https://leetcode-cn.com/problems/number-of-1-bits/submissions/

思路
每次进行消1运算,消一次记录一次

代码

js

    var hammingWeight = function (n) {
        let res = 0
        while (n) {
            n &= (n - 1)
            res++
        }
        return res
    };

c

    int hammingWeight(uint32_t n) {
        int res = 0;
        while(n){
            n &= n-1;
            res++;
        }
        return res;
    }
数字范围按位与

https://leetcode-cn.com/problems/bitwise-and-of-numbers-range/

思路因区间在[left, right],要提取出left与right的公共前缀,思路就是对right进行消一 *** 作当right不再比left大时直接返回right即可

代码

js

	        var rangeBitwiseAnd = function(left, right) {
	            while(left 
    - c
	      int rangeBitwiseAnd(int left, int right){
	            while(right > left){
	                right &= right-1;
	            }
	            return right;
	        }
数组中数字出现的次数 II

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/

思路
因为数字有32位,循环32次,每次左移一位,然后每次都与数组的数进行位与 *** 作,看i位是否为1如果为1,计数一次js

var singleNumber = function (nums) {
    let res = 0;
    for (let i = 0; i < 32; i++) {
        let cnt = 0;
        let bit = 1 << i;
        for (let j = 0; j < nums.length; j++) {
            if (nums[j] & bit) cnt++;
        }
        //找到某一位为1的数,并左移,为了将这一位循环结束后移至原位
        if (cnt % 3 != 0) res |= bit;
    }
    return res;
};

c

int singleNumber(int* nums, int numsSize){
    int res = 0;
    for(int i = 0; i < 32; i++){
        int cnt = 0;
        int bit = 1 << i;
        for(int j = 0; j < numsSize;j++){
        //将数右移,并求出最后一位为 1 的个数
            if((nums[j] >> i & 1) == 1) cnt++;
        }
        if(cnt % 3 != 0)res |= bit;
    }
    return res;
}
318. 最大单词长度乘积

https://leetcode-cn.com/problems/maximum-product-of-word-lengths/

思路
先将所有字符的bitMask预计算出来,避免重复计算然后判断两个字符串是否重复并取出最大乘积

js

var maxProduct = function (words) {
    let n = words.length
    let masks = []
    for (let i = 0; i < n; i++) {
        let bitMask = 0
        for (let c of words[i]) {
            // 这段代码主要是给字符记位如出现a就标记为1,b标记为10...97为a的字符编码
            bitMask |= (1 << c.charCodeAt() - 97)
        }
        masks[i] = bitMask
    }
    let ans = 0
    for (let i = 0; i < words.length; i++) {
        let word1 = words[i]
        for (let j = i + 1; j < words.length; j++) {
            let word2 = words[j]
            // 取得对应的预计算的结果进行位与操作判断是否有重复的字符,并得到最大的单词长度乘积
            if ((masks[i] & masks[j]) == 0) ans = Math.max(ans, word1.length * word2.length)
        }
    }
    return ans
}

c

int max(num1,num2){
    return num1>num2?num1:num2;
}
int maxProduct(char ** words, int wordsSize){
    int masks[wordsSize];
    for(int i = 0; i < wordsSize; i++){
        int bitMask = 0;
        for(int k = 0;  k < strlen(words[i]); k++){
            if(words[i][k])
            if(words[i][k])
            bitMask |= (1 << words[i][k] - 'a');
        }
        masks[i] = bitMask;
    }
    int ans = 0;
    for(int i = 0; i < wordsSize; i++){
        int word1 = strlen(words[i]);
        for(int j = 0; j < wordsSize; j++){
            int word2 = strlen(words[j]);
            int num = word1 * word2;
            if((masks[i] & masks[j]) == 0) {
                ans = max(ans,num);
            }
        }
    }
    return ans;
}
1318. 或运算的最小翻转次数

https://leetcode-cn.com/problems/minimum-flips-to-make-a-or-b-equal-to-c/

思路
设a、b和c二进制表示的第i位分别为bit_a、bit_b 和 bit_c若bit_c的值为0,那么bit_a和bit_b必须都为0,需要翻转次数为bit_a+bit_b若bit_c的值为1,那么bit_a和bit_b中至少有一个为1,只有当它们都为0时,才需要1次翻转将每一位的翻转次数进行累加,在枚举完所有位之后,就得到了最小翻转次数

var minFlips = function (a, b, c) {
    let ans = 0
    for (let i = 0; i < 31; ++i) {
        let [bit_a, bit_b, bit_c] = [(a >> i) & 1, (b >> i) & 1, (c >> i) & 1]
        if (bit_c == 0) {
            ans += bit_a + bit_b
        } else {
            ans += (bit_a + bit_b == 0)
        }
    }
    return ans
};

c

int minFlips(int a, int b, int c){
    int result=0;
    for(int i = 0; i < 31; i++){
        int bit_a = (a >> i) & 1;
        int bit_b = (b >> i) & 1;
        int bit_c = (c >> i) & 1;
        if(bit_c == 0){
            result += bit_a + bit_b;
        }else{
            result += (bit_a + bit_b == 0);
        }
    }
     return result;
}
461. 汉明距离

https://leetcode-cn.com/problems/hamming-distance/

思路

先进行异或 *** 作,然后消一计数

js

 var hammingWeight = function (n) {
    let res = 0
    while (n) {
        n &= (n - 1)
        res++
    }
    return res
};
var hammingDistance = function(x, y) {
   let num = y^x;
   return hammingWeight(num)
};

c

int hammingWeight(n) {
    int res = 0;
    while (n) {
        n &= (n - 1);
        res++;
    }
    return res;
};
int hammingDistance(int x, int y){
    int num = y ^ x;
    return hammingWeight(num);
}
136. 只出现一次的数字

https://leetcode-cn.com/problems/single-number/

思路

直接异或最后剩的数就是只出现一次数字的

var singleNumber = function (nums) {
    let res = 0;
    for (let i = 0; i < nums.length; i++) {
        res ^= nums[i];
    }
    return res;
};
int singleNumber(int* nums, int numsSize){
    int s = 0,i;
    for(i=0;i 
1486. 数组异或 *** 作 

https://leetcode-cn.com/problems/xor-operation-in-an-array/

思路
start为循环开始条件,用一个变量来计数,每次循环+=2,并记一次数,当计数为n时循环结束

js

var xorOperation = function (n, start) {
    let sum = 0,res = 0;
    for (let i = start; sum != n; i += 2, sum++) {
        res ^= i
    }
    return res
};

c

int xorOperation(int n, int start){
    int sum = 0,res = 0;
    for (int i = start; sum != n; i += 2, sum++) {
        res ^= i;
    }
    return res;
}
1720. 解码异或后的数组

https://leetcode-cn.com/problems/decode-xored-array/

思路

创建一个数组,长度为encoded的长度+1,将第1位为first,再将其他几位做异或 *** 作得到最终数组

js

 */
var decode = function(encoded, first) {
    let arr = [first]
    for(let [index,item] of encoded.entries()){
        arr[index+1] = arr[index] ^ item
    }
    return arr
};

c

int* decode(int* encoded, int encodedSize, int first, int* returnSize){
    int* arr= malloc(sizeof(int) * (encodedSize + 1));
    arr[0] = first;
    for(int i = 0; i < encodedSize; i++){
        arr[i+1] = encoded[i] ^ arr[i];
    }
    *returnSize = encodedSize + 1;
    return arr;
}
1310. 子数组异或查询

https://leetcode-cn.com/problems/xor-queries-of-a-subarray/

思路
首先计数前缀异或数组,然后计算每个的查询结果,第i个就为前缀和异或数组[queries[i][0]]异或前缀和数组[queries[i][1]+1]

js

var xorQueries = function(arr, queries) {
    const n = arr.length;
    const xors = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        xors[i + 1] = xors[i] ^ arr[i];
    }
    const m = queries.length;
    const ans = new Array(m).fill(0);
    for (let i = 0; i < m; i++) {
        ans[i] = xors[queries[i][0]] ^ xors[queries[i][1] + 1];
    }
    return ans;
};

c

int* xorQueries(int* arr, int arrSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    int n = arrSize;
    int xors[n + 1];
    xors[0] = 0;
    for (int i = 0; i < n; i++) {
        xors[i + 1] = xors[i] ^ arr[i];
    }
    int m = queriesSize;
    int* ans = malloc(sizeof(int) * m);
    *returnSize = m;
    for (int i = 0; i < m; i++) {
        ans[i] = xors[queries[i][0]] ^ xors[queries[i][1] + 1];
    }
    return ans;
}

面试题 05.01. 插入

https://leetcode-cn.com/problems/insert-into-bits-lcci/

思路先将i - j位归0,然后将M左移i位进行位或 *** 作

js

var insertBits = function(N, M, i, j) {
    let k
    for(k = i;k <= j; ++k){
        N &= ~(1 << k)
    }
    return N | (M << i)
};

c

int insertBits(int N, int M, int i, int j){
    int k;
    for(k = i;k <= j; ++k){
        N &= ~((long long)1 << k);
    }
    return N | (M << i);
}
翻转数位

https://leetcode-cn.com/problems/reverse-bits-lcci/

思路
维护一个窗口,窗口内的0的个数<=1时,窗口大小可以计入结果,取长度的最大值
当窗口内0的个数>1的时候收缩窗口,直到满足<=1
窗口边界的取值范围为[0,31]

js<<

var reverseBits = function (num) {
    let s = 0, c = 0, res = -1;
    for (let i = 0; i < 32; i++) {
        if ((num & (1 << i)) === 0) c += 1;
        while (c > 1) {
            if ((num & (1 << s)) === 0) c -= 1
            s += 1
        }
        res = Math.max(res, i - s + 1)
    }
    return res
};
交替位二进制数

https://leetcode-cn.com/problems/binary-number-with-alternating-bits/

思路
判断相邻的两位是否相同,不同就是true,所以从低到高不断位与3判断相邻两位的模式,如果循环结束没有这种模式就返回true

js

var hasAlternatingBits = function(n) {
    while(n){
        if((n&3) == 3 || (n&3) == 0){
            return false
        }
        n >>= 1;
    }
    return true
};

c

bool hasAlternatingBits(int n){
    while(n){
        if((n&3) == 3 || (n & 3) == 0){
            return false;
        }
        n >>= 1;
    }
    return true;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5711434.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-18

发表评论

登录后才能评论

评论列表(0条)

保存