用 javascript 分类刷 leetcode9. 位运算 (图文视频讲解)

位运算基础：

程序中所有的数载计算机内存中都是以二进制存储的，位运算就是直接对整数在内存中的二进制进行操作，由于直接在内存中进行操作，不需要转成十进制，因此处理速度非常快

常见位运算

x & 1 === 0 //判断奇偶x & (x - 1) //清除最右边的1x & -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.length1 <= n <= 1040 <= nums[i] <= nnums 中的所有数字都 独一无二 

进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

方法 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,2var 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 <= 1000t.length == s.length + 1s 和 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 --> 01 --> 12 --> 10 示例 2：

输入：n = 5 输出：[0,1,1,2,1,2]解释：0 --> 01 --> 12 --> 103 --> 114 --> 1005 --> 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;};

视频讲解：传送门