preface

People often ask, what algorithms do you actually use as a front end, and I usually say, trees and bits;

Think about the dependencies on webPack and the react source code for flag definitions and operations. I think it’s important to learn what bitwise operations can solve

Drainage of the

Brush these 20 dichotomy questions, may still tear the big factory interview

Brush these a few pile of questions, or may not tear the big factory interview

Brush these 30 tree questions, may still tear the big factory interview

Brush these 20 linked list questions, may still tear the big factory interview

Brush these 15 DP questions, can only chance the topic into dachang

The body of the

Actually bit operations is the most typical of computing symbols, | & ^ 3, but apply to a specific topic is very flexible, to review your base this series is just know how to use the binary bits to store values, and use the data structure, the binary bit operations is associated with the use of algorithm;

Others, I don’t know ah, just think bitwise operation is cool, there are some special problems, directly use bitwise operation can be solved in a few lines, so learn to learn to install force, so this series is relatively small for the time being, just two sets of classic problems, later supplement it;

PS: In fact, sorting out the topic so far, there have been 6 groups, the original is to review the code written, but the more I feel that I understand less, began to tired, but stick to it should have a harvest, come on 💪

The title list

  • 136. A number that appears only once
  • 137. The number II that occurs only once
  • 260. The number III that occurs only once
  • 78. The subset
  • 90. Subset II — has duplicate values
  • 645. A collection of errors

Answer key

136. A number that appears only once

Numbers that occur only once — all problems are linear in time and constant in space

Analysis analysis – 1 single value, the rest are two

  1. We know that a to the a is equal to 0, 0 to the a is equal to a,
  2. So if you xor all the values in NUMS, those that occur twice are eliminated, and you end up with the only value that occurs once
  3. Time complexity O(N){O(N)}O(N), space complexity O(1){O(1)}O(1)
var singleNumber = function(nums) {
    return nums.reduce((prev,cur) = > prev ^ cur,0) // 0 and any value are xor equal to any value, so 0 is the initial value
};
Copy the code

137. The number II that occurs only once

Analysis — 1 single value x, the rest are 3 y1,y2…

  1. Compare the nums array & with the bits of [0,31] to find the number of values that exist at that bit count;
  2. If count goes into 3, then there’s only yi there; If I don’t divide it exactly, if I prove that the single-valued x is in this bit, then I’m going to add this bit to it
  3. [-pow(2,31),pow(2,31)-1] [-pow(2,31) -1] [-pow(2,31) -1]
  4. 31 ∗ time complexity O (N) (31 * N)} {O O 31 ∗ (N), space complexity O (1) (1)} {O O (1)
/** * @ analysis -- one value occurs 1 times, other values occur 3 times -- * 1. Add all the values, convert them to binary, then the same value must be the same in the same bit, then divide each bit by 3 mod, the result is the only value that occurs once */
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++;
    });
    // Count is the number of values in the I bit
    if (count % 3) ret |= temp;
  }
  return ret;
};

Copy the code

260. The number III that occurs only once

Numbers that occur only once — all problems are linear in time and constant in space

Analysis of the

  1. If only one value occurs once and all the others occur twice, then xor gives the answer;
  2. Now there are two values that only appear once, so the xor sum is the xor sum of those two values, so we need to split the array into two pieces
    • There are values x1 and x2 that occur only once in each copy
    • The same two values should be placed in the same group
  3. To implement the condition in 2, we need to find a value temp and compare the values in the array with temp into two groupsA value
  4. Perform xor on all the values in nums to get the x1 ^ x2 value res,
  5. For res, we know that they are xor from two values x1 and x2, that is, for res, if it has a value in one place, then the other one must not be in that place, or they cancel out
  6. So find the first bit bite that exists and the corresponding value temp, and then at this point it becomes, find the only single value that exists on bit BITE
  7. Time complexity O(N){O(N)}O(N), space complexity O(1){O(1)}O(1)
// 260. The number III occurs only once

var singleNumber = function(nums) {
    // The resulting res is xor of x1 ^ x2
    const res = nums.reduce((prev,cur) = > prev^ cur,0)
    let bite= 0
    // Find the position of the first 1 in the binary,
    while((1<<bite) & res === 0 ){
        bite++
    }
    // The value of this bit, which can be used to find all values of this value
    // there is one and only one ampersand with temp that is not 0
    const temp = 1<<bite
    let left = 0,right = 0
    nums.forEach(num= > {
        if(num & temp){
            left ^= num // Make sure left is the bite bit value, other values that occur twice will be xor removed
        }else{
            right ^= num
        }
    })
    return [left,right]
};

Copy the code

78. The subset

Analysis — mathematical method

  1. We’re doing combinations, not permutations, so the order of insertion doesn’t matter, just make sure that every subset of the array is unique
  2. Therefore, for an empty array nums, only one subset [[]] is returned, and each additional element is added to each subset to form a new subset based on the previous array of subsets
  3. Time complexity 2n{2^n}2n where n is the length of NUMs

* /


 var subsets = function (nums) {
    let ret = [[]] // Default empty array
    for(let num of nums){
        ret = [...ret,...ret.map(item= > item.concat(num))]
    }
    return ret
}
Copy the code

Analysis – iteration + bit operation

  1. Convert the possible values into bits of the bitoperation. Each bit represents the subscript of nums. If the bit I is 1, then the array has the value nums[I].
  2. Thus we can directly obtain all possible binary numbers of our own, with values of [0,2^n-1], where n is the length of nums
  3. And then we’re going to convert those binaries back into arrays and print them out.
  4. Time complexity n∗2n{n * 2^n}n∗2n where n is the length of NUMs
var subsets = function (nums) {
    const ret = []
    const len = nums.length
    for(let i = 0; i<(1<<len); i++){// I is the self of one of the binary words, so convert it to an array
        const temp  = []
        for(let j=0; j<len; j++){if(i & (1<<j)){
                // there are numbers with subscript j in I
                temp.push(nums[j])
            }
        }
        // Temp is now a subset of the array I is converted to
        ret.push(temp)
    }
    return ret
}
Copy the code

Analysis — iteration

  1. You don’t need to do any bit operations, you just use DFS with state, you have two states at a time, get or not get, and binary tree, and then when you get to the last value of the array, you collect the state array, okay
  2. This is like a binary tree, len is the height of the binary tree, so the time is 2n{2^n}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
}

Copy the code

90. Subset II — has duplicate values

Analysis of the

  1. 78. The first thing you need to do is sort the values of the array nums
  2. After sorting, let’s see if we can reuse the three ways of writing the previous problem;
  3. Let’s start with the actionableSimulated binary tree iterative method, the core idea here is the top-down traversal with parameters, and then each traversal is divided into two states, one is the value, the other is not taken, and this happens to be re-matched with the combination;
  4. If the current path is in no value state last time during a traversalisGet===false, and the current value nums[start] is the same as the previous value nums[start-1], then the current traversal has one and only one value, but no value, because the last traversalisGet===true+ of its subsequent subtreesisGet===falseBranches withisGet===false+ of subsequent subtreesisGet===trueOverlap, and here we haveisGet===false+ of subsequent subtreesisGet===trueCut off the branches
  5. The branches of the other states can be traversed normally until the numS array traversal is complete, and the ret is finally obtained after recasting
  6. Corresponding to it, the first numerical method has no state, which is difficult to reuse. In the second iterative + bit operation, all the possible bit operations are converted into numbers according to the subscript and. This situation is a little complicated for deduplication, so it will not be considered.

var subsetsWithDup = function (nums) {
  nums.sort((a, b) = > a - b); / / sorting
  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]) {// If the current value is the same as the last value, and the last time this traversal did not have a value; So there must be a branch that takes a value, and if this temporary array takes a value, it's going to overlap that branch, so I'm going to prune it
        dfs(start+1,[...arr],false)}else{
        dfs(start+1,[...arr],false)
        dfs(start+1,[...arr,nums[start]],true)}}; dfs(0[],true) // The initialization is true to avoid the first comparison with the previous value
  return ret
};

Copy the code

645. A collection of errors

Analysis of the

  1. In general, if you have a single value or a value that occurs twice, the first thing to consider is xOR, and you can filter out most of the values
  2. Xor with the median of [1,len] and NUMs yields the xor of the missing value A and the repeated value B
  3. Need to pay attention to, a sign of operation & | ^ priority is lower than the relatively uniform, so compare, attention should be paid to add parentheses
  4. Nums = len (1,2…len); len (1,2…len); len (1,2…len); len (1,2…len); len (1,2…len); len (1,2…len); len (1,2…len)
  5. And the thing to notice is, which one is missing, which one is taking one, and which one is taking three, which is repeating, so once you have left and right, you have to go through it again
  6. Because I want to use order one.
 var findErrorNums = function (nums) {
  const res = nums.reduce((prev, cur, index) = > prev ^ cur ^ (index + 1), 0);

  let temp = 1
  // Find the first bit with the value 1
  while((temp & res) === 0){
    temp= temp << 1
  }
  // The number of num and index bits that exist in this bit
  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]

};

Copy the code