关于leetcode:用javascript分类刷leetcode9位运算图文视频讲解

位运算根底：

程序中所有的数载计算机内存中都是以二进制存储的，位运算就是间接对整数在内存中的二进制进行操作，因为间接在内存中进行操作，不须要转成十进制，因而处理速度十分快

常见位运算

x & 1 === 0 // 判断奇偶
x & (x - 1) // 革除最左边的 1
x & -x // 失去最左边的 1 

191. 位 1 的个数（easy）

编写一个函数，输出是一个无符号整数（以二进制串的模式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明分量）。

提醒：

请留神，在某些语言（如 Java）中，没有无符号整数类型。在这种状况下，输出和输入都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其外部的二进制示意模式都是雷同的。
在 Java 中，编译器应用二进制补码记法来示意有符号整数。因而，在下面的 示例 3 中，输出示意有符号整数 -3。

示例 1：

输出：00000000000000000000000000001011
输入：3
解释：输出的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。
示例 2：

输出：00000000000000000000000010000000
输入：1
解释：输出的二进制串 00000000000000000000000010000000 中，共有一位为 ‘1’。
示例 3：

输出：11111111111111111111111111111101
输入：31
解释：输出的二进制串 11111111111111111111111111111101 中，共有 31 位为 ‘1’。

提醒：

输出必须是长度为 32 的 二进制串。

进阶：

如果屡次调用这个函数，你将如何优化你的算法？

办法 1：循环每个二进制位

• 思路：间接循环二进制中的每一位，判断是否为 1，统计 1 的个数
• 复杂度剖析：工夫复杂度O(k)，k=32。空间复杂度为O(1)

Js:

var hammingWeight = function(n) {
    let ret = 0;
    for (let i = 0; i < 32; i++) {if ((n & (1 << i)) !== 0) {// 让 1 一直左移 判断该位是否为 1
            ret++;
        }
    }
    return ret;
};

办法 2：优化循环的过程

• 思路：巧用二进制公式 x&(x-1) 示意去掉二进制中最左边的第一个 1，减速循环过程
• 复杂度剖析：工夫复杂度为O(k)，k 为二进制中 1 的个数，最坏的状况下所有位都是 1。空间复杂度是O(1)

js:

var hammingWeight = function(n) {
    let ret = 0;
    while (n) {
        n &= n - 1;// 一直消掉最左边的 1
        ret++;
    }
    return ret;
};

268. 失落的数字（easy）

给定一个蕴含 [0, n] 中 n 个数的数组 nums，找出 [0, n] 这个范畴内没有呈现在数组中的那个数。

示例 1：

输出：nums = [3,0,1]
输入：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范畴 [0,3] 内。2 是失落的数字，因为它没有呈现在 nums 中。
示例 2：

输出：nums = [0,1]
输入：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范畴 [0,2] 内。2 是失落的数字，因为它没有呈现在 nums 中。
示例 3：

输出：nums = [9,6,4,2,3,5,7,0,1]
输入：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范畴 [0,9] 内。8 是失落的数字，因为它没有呈现在 nums 中。
示例 4：

输出：nums = [0]
输入：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范畴 [0,1] 内。1 是失落的数字，因为它没有呈现在 nums 中。

提醒：

n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
nums 中的所有数字都 举世无双

进阶：你是否实现线性工夫复杂度、仅应用额定常数空间的算法解决此问题?

办法 1. 排序：在循环数组，看后一个数是不是比前一个大 1

办法 2. 哈希表：将数组中的元素插入哈希表，而后循环 0～nums.length- 1 中的数是不是都在哈希表中

办法 3. 求和：0～nums.length- 1 求和减去 nums 中的和

办法 4 : 位运算

• 思路：雷同的数异或为 0
• 复杂度：工夫复杂度O(n)，空间复杂度O(1)

js:

//nums = [3,0,1]
//index = 0,1,2
var missingNumber = function (nums) {
    let missing = nums.length
    for (let i = 0; i < nums.length; i++) {// 雷同的数异或为 0
        missing = missing ^ nums[i] ^ (i)
    }
    return missing
}

231. 2 的幂（easy）

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true；否则，返回 false。

如果存在一个整数 x 使得 n == 2x，则认为 n 是 2 的幂次方。

示例 1：

输出：n = 1
输入：true
解释：20 = 1
示例 2：

输出：n = 16
输入：true
解释：24 = 16
示例 3：

输出：n = 3
输入：false
示例 4：

输出：n = 4
输入：true
示例 5：

输出：n = 5
输入：false

提醒：

-231 <= n <= 231 – 1

进阶：你可能不应用循环 / 递归解决此问题吗？

办法 1. 二进制

• 思路：一个数是 2 的幂须要满足这个数的二进制中只有一个 1，也就是须要满足这个数 >0，同时打消惟一的一个 1 之后就是 0
• 复杂度：工夫复杂度O(1)。空间复杂度O(1)

Js:

var isPowerOfTwo = function(n) {return n > 0 && (n & (n - 1)) === 0;
};

办法 2. 是否为最大 2 的幂的约数

• 思路：最大的 2 的幂为 2^30 = 1073741824，判断 n 是否是 2^30 的约数即可。
• 复杂度: 工夫复杂度O(1)。空间复杂度O(1)

js:

var isPowerOfTwo = function(n) {
    const MAX = 1 << 30;
    return n > 0 && MAX % n === 0;
};

389. 找不同（easy）

给定两个字符串 s 和 t，它们只蕴含小写字母。

字符串 t 由字符串 s 随机重排，而后在随机地位增加一个字母。

请找出在 t 中被增加的字母。

示例 1：

输出：s = “abcd”, t = “abcde”
输入：”e”
解释：’e’ 是那个被增加的字母。
示例 2：

输出：s = “”, t = “y”
输入：”y”

提醒：

0 <= s.length <= 1000
t.length == s.length + 1
s 和 t 只蕴含小写字母

办法 1. 计数

• 思路：循环字符串 s 统计每个字符的个数，循环字符串 t 每呈现一次 s 中的字符 就让相应字符的数量缩小 1，如果字符缩小到了小于 0 则这个字符就是答案
• 复杂度：工夫复杂度O(n)，n 是字符串的长度。空间复杂度O(k)，k 是字符集的大小

js：

var findTheDifference = function(s, t) {const cnt = new Array(26).fill(0);
    for (const ch of s) {// 循环字符串 s 统计每个字符的个数
        cnt[ch.charCodeAt() - 'a'.charCodeAt()]++;
    }
    for (const ch of t) {// 循环字符串 t 每呈现一次 s 中的字符 就让相应字符的数量缩小 1
        cnt[ch.charCodeAt() - 'a'.charCodeAt()]--;
        if (cnt[ch.charCodeAt() - 'a'.charCodeAt()] < 0) {// 如果字符缩小到了小于 0 则这个字符就是答案
            return ch;
        }
    }
    return ' ';
};

办法 2. 求和

• 思路：统计字符串 s 和 t 中字符 Unicode 的总和，两个和的差 就是不同的字符
• 复杂度：工夫复杂度O(n)。空间复杂度O(1)

js：

var findTheDifference = function(s, t) {
    let as = 0, at = 0;
    for (let i = 0; i < s.length; i++) {// 统计字符串 s 中字符 Unicode 值的总和
        as += s[i].charCodeAt();}
    for (let i = 0; i < t.length; i++) {// 统计字符串 t 中字符 Unicode 值的总和
        at += t[i].charCodeAt();}
    return String.fromCharCode(at - as);// 两个和的差 就是不同的字符
};

方 3. 位运算

• 思路：循环 s 和 t 一直异或 雷同元素异或等于 0 所以惟一不同的字符最初会留下来
• 复杂度：工夫复杂度O(n)。空间复杂度O(1)

js：

//s = "abcd", t = "abcde"
var findTheDifference = function(s, t) {
    let ret = 0;// 循环 s 和 t 一直异或 雷同元素异或等于 0 所以惟一不同的字符最初会留下来
    for (const ch of s) {ret ^= ch.charCodeAt();
    }
    for (const ch of t) {ret ^= ch.charCodeAt();
    }
    return String.fromCharCode(ret);
};

338. 比特位计数 (easy)

给你一个整数 n，对于 0 <= i <= n 中的每个 i，计算其二进制示意中 1 的个数，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

输出：n = 2
输入：[0,1,1]
解释：
0 –> 0
1 –> 1
2 –> 10
示例 2：

输出：n = 5
输入：[0,1,1,2,1,2]
解释：
0 –> 0
1 –> 1
2 –> 10
3 –> 11
4 –> 100
5 –> 101

提醒：

0 <= n <= 105

进阶：

很容易就能实现工夫复杂度为 O(n log n) 的解决方案，你能够在线性工夫复杂度 O(n) 内用一趟扫描解决此问题吗？
你能不应用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount）

办法 1. 循环

• 思路：循环0-n，计算每个数二进制中 1 的个数。
• 复杂度：工夫复杂度O(nk)，k 一个整数统计二进制 1 的复杂度，最坏的状况下是 k =32。空间复杂度是O(1)

js:

var countBits = function(n) {const bits = new Array(n + 1).fill(0);
    for (let i = 0; i <= n; i++) {bits[i] = countOnes(i);
    }
    return bits
};

const countOnes = (x) => {
    let ones = 0;
    while (x > 0) {x &= (x - 1);
        ones++;
    }
    return ones;
}

办法 2. 动静布局

• 思路：bits[i]示意 i 的二进制中 1 的个数，那么 bits[i-1] 就是 bits[i] 拿掉一个 1 之后的值，i & (i - 1)就是去掉最低位的一个 1.

所以状态转移方程就是bits[i] = bits[i & (i - 1)] + 1，一直循环计算出从 1 - n 中每个数二进制中 1 的个数即可

• 复杂度：工夫复杂度O(n)。空间复杂度是O(1)

Js:

var countBits = function(n) {const bits = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {bits[i] = bits[i & (i - 1)] + 1;
    }
    return bits;
};

视频解说：传送门