This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

28. The missing first positive number (first-missing-positive)

The label

  • hash map
  • difficult

The title

Leetcode portal

Let’s just open leetCode.

Find the first missing positive integer.

Basic knowledge of

Use hashMap to trade space for time. See here for a simple use of Map

  • Use the Map 1
  • Use the Map 2

The basic idea

To reduce the time complexity, we can put all the input arrays into the map, and then the j loop, starting from 1, checks for the presence of J in the map, and returns the result immediately if there is no J.

steps

  1. Put all the input arrays into the map to form a mapping table
  2. Since we want a positive integer, we start with 1 to see if there is any j in the map, and return the result immediately if there is no j.
  3. If it is [] or [1], return it directlylen + 1

Writing implement

/ * * *@param {number[]} nums
 * @return {number}* /
var firstMissingPositive = function(nums) {
  let numMap = new Map(), 
  len = nums.length
  // add nums to map
  for (let i = 0; i < len; i++) {
    numMap.set(nums[i], nums[i])
  }
  // Start at 1 and return the index if the first one does not match
  for (let j = 1; j < len + 1; j++) {
    if(numMap.get(j) ! == j) {return j
    }
  }
  return len + 1
};

console.log(firstMissingPositive([1]))
Copy the code

29. Permutations

The label

  • DFS
  • back
  • medium

The title

Leetcode portal

Let’s just open leetCode.

Given a sequence without repeating digits, return all possible permutations.

Input: [1,2,3] output:

31 [[1, 2, 3], [1], [2,1,3],,3,1 [2], [3,1,2], [3, 2, 1]]Copy the code

The basic idea

Classic problem. The essence is DFS + backtracking

Same idea as this passage

Writing implement

/ * * *@param {number[]} nums
 * @return {number[][]}* /
var permute = function(nums) {
  let [res, len] = [[], nums.length]
  let dfs = (curPath) = > {
    if (curPath.length === len) {
      res.push(curPath.slice())
      return
    }
    for (let i = 0; i < len; i++) {
      if(! curPath.includes(nums[i])) { curPath.push(nums[i]) dfs(curPath) curPath.pop() } } } dfs([])return res
};

console.log(permute([1.2.3]))
Copy the code

This can be improved by swapping space for time and using a currently used object to record used objects instead of array.prototype.includes

var permute = function(nums) {
  let [res, len, curUsed] = [[], nums.length, {}]
  let dfs = (curPath) = > {
    if (curPath.length === len) {
      res.push(curPath.slice())
      return
    }
    for (let i = 0; i < len; i++) {
      // Direct skip has been used
      if (curUsed[nums[i]]) {
        continue;
      }
      curPath.push(nums[i])
      curUsed[nums[i]] = true
      dfs(curPath)
      curPath.pop()
      curUsed[nums[i]] = false
    }
  }
  dfs([])
  return res
};

console.log(permute([1.2.3]))
Copy the code

In addition, I would like to recommend the article of the eldest brother to you. It is very simple and profound. It is very effective for the students who advance in the front end. Core concepts and algorithm disassembly series

That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me presious tower shock the rever monster, I see it through, the code is not on the ha, add after I will do my best to help you, but pay attention to the way of asking questions, suggest reading this article first: the wisdom of asking questions