写点什么

JavaScript 刷 LeetCode 拿 offer- 位运算

作者:Geek_07a724
  • 2022-11-10
    浙江
  • 本文字数:3995 字

    阅读完需:约 13 分钟

前言

经常会有人问,作为前端,你在实际工作中用到过哪些算法,而我回答一般是,树和位运算;


想想 webpack 上的那些依赖的版本类型,想想 react 源码中的那些 flag 的定义和运算,我觉得还是很有必要去学习一下位运算到底能解决一些什么问题

正文

其实位运算最典型的就运算符号就是,| & ^ 三个,但是运用到具体题目上就很灵活了,基本这个系列也只是复习一下,知道一下如何用二进制的位来存储获取值,而用二进制位这样的数据结构时,位运算就是关联使用的算法了;


其他的,我也不知道啊,就是觉得位运算好酷,有一些特殊的题目,直接用位运算就能几行解决,所以学学可以装个逼,因此这个系列暂时比较少,就两套经典题而已,以后在补充吧;


PS: 其实整理题目至此,已经有 6 组了,最初是为了复习写过的代码,但是越写越觉得自己懂的少,开始疲惫的,但是坚持下去应该会有收获的吧,加油💪

题解

136. 只出现一次的数字

只出现一次的数字 -- 所有题目都是线性时间复杂度,空间复杂度都是常数级复杂度


分析分析 -- 1 个单值,其余是两个


  1. 已知 a ^ a = 0, 0 ^ a = a ,

  2. 所以将 nums 中所有值进行异或处理,出现两次的都会被消除,而最后的结果就是唯一一次出现的那个值

  3. 时间复杂度 O(N),空间复杂度 O(1)


var singleNumber = function(nums) {    return nums.reduce((prev,cur) => prev ^ cur,0) // 0 和任何值异或都等于任何值,所以以 0 为初始值};
复制代码

137. 只出现一次的数字 II

分析 -- 1 个单值 x ,其余是 3 个 y1,y2...


  1. 将 nums 数组与 [0,31] 的位进行 & 比较,找出在这个位上存在的值的数量 count;

  2. 如果 count 整除 3, 证明这个位上只存在 yi;如果不整除,证明单值 x 在这个位上,那么结果要加上这个位

  3. 注意,由于 num 的取值范围是 [-pow(2,31),pow(2,31)-1], 所以第 31 位 是可以取到的,所以遍历的时候要遍历到第 31 位,取到正负值;

  4. 时间复杂度 O(31∗N),空间复杂度 O(1)


/** * @分析 --- 一个值出现 1 次,其余值出现 3次 -- * 1. 将所有值相加,转成二进制,然后相同的值在同一个位上肯定也是一样的,然后对每一个位进行除 3 取余,得到的值就是唯一一个出现 1 次的值了 */var singleNumber = function (nums) {  let ret = 0;  for (let i = 0; i < 32; i++) {    const temp = 1 << i;    let count = 0;    nums.forEach((num) => {      if (num & temp) count++;    });    // 在 i 这个位上,有 count 这么多个值    if (count % 3) ret |= temp;  }  return ret;};

复制代码

260. 只出现一次的数字 III

只出现一次的数字 -- 所有题目都是线性时间复杂度,空间复杂度都是常数级复杂度

分析

  1. 如果题目看错是只有一个值出现一次,其余都出现两次,那么直接异或就可以得出结果;

  2. 现在是有两个值只出现一次,所以异或和得到的就是这两个值的异或和,所以需要将原数组拆解成两份

  3. 两份里分别存在一个只出现一次的值 x1 和 x2

  4. 相同的两个值要分在同一组

  5. 为了实现 2 中的条件,我们需要找出一个值 temp,让数组中的值和 temp 进行一定的比较分成两组,这时候考虑使用二进制中的位值

  6. 先用异或将所有 nums 中的值进行运算,得到 x1 ^ x2 的值 res,

  7. 对于 res,我们知道他们是由两个值 x1,x2 异或得到,也就是说,对于 res,在某一个位上有值,那么另外一个肯定不在这个位上,不然就相互抵消了

  8. 所以找出第一个存在的位 bite 和对应的值 temp,然后这个时候就变成了,找出唯一一个单值,它存在于位 bite 上

  9. 时间复杂度 O(N),空间复杂度 O(1)


// 260. 只出现一次的数字 III
var singleNumber = function(nums) { // 求出的 res 是 x1 ^ x2 的异或值 const res = nums.reduce((prev,cur) => prev^ cur,0) let bite= 0 // 求出 res 在二进制中的第一个 1 的位置, while((1<<bite) & res === 0 ){ bite++ } // 这个二进制位对应的值,用它可以求出所有存在这个为的值 // x1,x2 有且仅有一个会与 temp 的 & 运算不为 0 const temp = 1<<bite let left = 0,right = 0 nums.forEach(num => { if(num & temp){ left ^= num // 保证 left 是存在 bite 位的值,其他出现两次的值会被异或掉 }else{ right ^= num } }) return [left,right]};

复制代码

78. 子集

分析 -- 数学法


  1. 这里求的组合而不是排列,所以插入顺序与最后的结果是无关的,要保证数组中每一个子集都是唯一即可

  2. 所以对于空的数组 nums,返回的子集只有一个 [[]], 每多加一个元素,那么就是在前一个已有的子集数组基础上,在每一个子集中加上这个元素,形成新的子集

  3. 时间复杂度 2n 其中 n 是 nums 的长度参考视频:传送门


 var subsets = function (nums) {    let ret = [[]] // 默认空数组    for(let num of nums){        ret = [...ret,...ret.map(item => item.concat(num))]    }    return ret}
复制代码


分析 -- 迭代+位运算


  1. 将可能的取值转化成位运算的位,每一个位代表 nums 的下标,如果这个位 i 为 1,则这个数组存在值 nums[i]

  2. 因此我们可以直接得到所有可能的自己的二进制数,他们的值分别是 [0,2^n-1], 其中 n 是 nums 的长度

  3. 然后我们要将这些二进制重新转成数组,然后输出出来。

  4. 时间复杂度 n∗2n 其中 n 是 nums 的长度


var subsets = function (nums) {    const ret = []    const len = nums.length    for(let i = 0;i<(1<<len);i++){        // i 就是其中一个二进制话的自己,所以要将它转成数组        const temp  = []        for(let j=0;j<len;j++){            if(i & (1<<j)){                // i 中存在下标为 j 的数                temp.push(nums[j])            }        }        // 现在 temp 就是 i 转成数组的子集了        ret.push(temp)    }    return ret}
复制代码


分析 -- 迭代


  1. 不需要进行什么位运算,直接用带状态的 dfs 去取,每次都有两个状态,取或者不取,和二叉树贼像,然后当迭代到数组最后一个值的时候,将状态数组收集起来即可

  2. 这种就好像二叉树一样,len 就是二叉树的高度,所以时间复杂度 2n


var subsets = function (nums) {    const ret = []    const len = nums.length;    const dfs = (start,arr) => {        if(start === len){            ret.push(arr)            return        }        dfs(start+1,[...arr])        dfs(start+1,[...arr,nums[start]])    }    dfs(0,[])    return ret}

复制代码

90. 子集 II -- 有重复值

分析


  1. 本题与 78. 子集 比更接近现实,数组 nums 中的值存在重复的,还是求组合而不是排列,所以必须要将相同的值放在一起,所以首先要做的就是排序

  2. 排完序之后,我们再来看上题的三中写法,是否可以复用;

  3. 先说可操作的模拟二叉树迭代法,这里的核心思想就是带参数的自顶向下的遍历,然后每次遍历分两种状态,一种是取值,一种是不取,而这恰好和组合去重匹配;

  4. 如果在某一次的遍历中,当前路径上一次属于没有取值状态 isGet===false, 且当前值 nums[start] 和上一个值 nums[start-1] 相等,那么这一次的遍历有且仅有一个,就是不取值,原因是上一次遍历中的 isGet===true + 它后续子树的 isGet===false 分支会与 isGet===false + 后续子树的isGet===true 重叠,在这里我们把 isGet===false + 后续子树的isGet===true 的分支剪去

  5. 其他状态的分支可以正常遍历,直到 nums 数组遍历结束,最后得到 ret 就是去重后的

  6. 与之对应的第一种数学法没有带状态,比较难复用,第二种迭代+位运算中,是将所有可能性的位运算按照下标与转成了数字,这种情况对于去重,咋看上有点复杂,所以就不考虑了;


var subsetsWithDup = function (nums) {  nums.sort((a, b) => a - b); // 排序  const ret = [];  const len = nums.length;  const dfs = (start, arr, isGet) => {    if (start === len) {      ret.push(arr);      return    }    if(!isGet && nums[start] === nums[start-1]){        // 如果当前值和上一次值相同,且这个遍历上一次是没有取值的;那么必定有一个分支是取值了的,如果这里的临时数组取了值,就会和上边那个分支重叠,所以要剪枝        dfs(start+1,[...arr],false)    }else{        dfs(start+1,[...arr],false)        dfs(start+1,[...arr,nums[start]],true)    }  };  dfs(0,[],true) // 初始化是true,这样就可以避开第一次与前一个值进行比较的判定  return ret};

复制代码

645. 错误的集合

分析


  1. 一般这些有单值,和出现两次的值,第一时间考虑的就是异或,可以将大部分值给筛选掉

  2. 用 [1,len] 和 nums 的中值进行异或,得到的就是丢失值 a 和 重复值 b 的异或值

  3. 需要注意,位运算符号 & | ^ 优先级低于比较匀速符,所以做比较的时候,要注意加上括号

  4. 这个题和 260. 只出现一次的数字 III 十分类似,这里只要将下标[1,2...len] 和 nums 合并,就成了有两个值分别取 1 次和 3 次,其他都取 2 次;

  5. 需要注意的是,哪一个是缺的值,也就是取 1 次的值,哪个是取 3 次,也就是重复的值,所以在得到 left 和 right 后,还需要再遍历一次

  6. 由于希望用 O(1 )


 var findErrorNums = function (nums) {  const res = nums.reduce((prev, cur, index) => prev ^ cur ^ (index + 1), 0);
let temp = 1 // 找出第一个值为 1 的位 while((temp & res) === 0){ temp= temp << 1 } // 所有存在这个位的的 num 和 index 的数量 let left = 0,right = 0 for(let i = 0;i<nums.length;i++){ if(nums[i] & temp) { left ^=nums[i] } if((i+1) & temp) { left ^=(i+1) } if((nums[i] & temp) === 0) { right ^=nums[i] } if(((i+1) & temp) === 0) { right ^=(i+1) } }
for(let num of nums){ if(left === num){ return [left,right] } } return [right,left]
};

复制代码


用户头像

Geek_07a724

关注

还未添加个人签名 2022-09-14 加入

还未添加个人简介

评论

发布
暂无评论
JavaScript刷LeetCode拿offer-位运算_JavaScript_Geek_07a724_InfoQ写作社区