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.

25. Search for insert position (search-insert-position)

The label

  • Binary search
  • simple

The title

Leetcode portal

Let’s just open leetCode.

Given a sorted array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it will be inserted in order.

It’s basically asking you to find where to insert the target element in the array

You can assume that there are no duplicate elements in the array.

The basic idea

Sorted array again, we can use binary search, refer to this binary search

This is one of the binary search variants we talked about last time:

Finds the last element smaller than Target in the ordered array.

steps

Almost the same variation as binary search in the previous article. See binary search variants, directly to see the implementation.

Writing implement

let searchInsert = (nums, target) = > {
  let [left, right, pivot] = [0, nums.length-1.0]
  while (left <= right) {
    pivot = left + Math.floor((right - left) / 2)
    // Because we are looking for the last element smaller than target, we move the right boundary to the left when it is greater than or equal to target
    if (nums[pivot] >= target) {
      right = pivot - 1
    } else {
      // If the right side is greater than or equal to target, return the last bit
      if ((pivot == nums.length-1) || (nums[pivot+1] >= target)) {
        return pivot + 1
      }
      // If not, move the left boundary right
      left = pivot + 1}}return 0
}

console.log(searchInsert([1.3.5.6].7))
Copy the code

26. Combination-sum

The label

  • DFS
  • back
  • medium

The title

Leetcode portal

Let’s just open leetCode.

You’re given an array of non-repeating positive numbers, and given target, find all the combinations of the sum as target. Elements can be reused, but combinations cannot be repeated, for example [2, 2, 3] and [2, 3, 2] are repeated combinations.

The key analysis

  • This is to find the Path to the legal solution. DFS directly. If you don’t know, check out this depth-first traversal.

  • In order not to create duplicate combinations, we need to limit the starting point of the next round, that is, to add a startIdx, so that the next round does not pick the number to the left of the same layer, and the further we go, the fewer the number of choices. For example, if the candidates = [2,3,6,7] appear to be in ascending order, then the path should be [2,2,3]. The next round starts with the idx of 3. And that guarantees that there are no duplicate solutions.

Writing implement

var combinationSum = function(candidates, target) {
  let res = []
  const dfs = (startIdx, curPath, curSum) = > {
    // This is obviously better than target direct return
    if (curSum > target) {
      return
    }
    // enter the result array when target is equal to
    if (curSum === target) {
      res.push(curPath.slice())
    }
    for (let i = startIdx; i < candidates.length; i++) {
      // Remove the apparently impossible branch
      if (candidates[i] > target) {
        continue;
      }
      // The number candidates[I] selected in this round spell the path
      curPath.push(candidates[i])
      // continue DFS, startIdx = I, the next round will not pick the number to the left of I
      dfs(i, curPath, curSum + candidates[i])
      // Undo the selection, go back to the upper path, and continue to try to select the number to the right of the same level
      curPath.pop()
    }
  }
  Start =0, curPath=[], curSum=0
  dfs(0[],0);
  return res
};

let candidates = [2.3.6.7], target = 7
console.log(combinationSum(candidates, target))
Copy the code

27. Combination-sum-ii

The label

  • DFS
  • back
  • medium

The title

Leetcode portal

Let’s just open leetCode.

Given an array of candidates and a target number target, find all combinations of the candidates that can be the sum of the number and target.

Each number in the candidates must be used only once in each combination.

The difference with the previous problem is that you can’t use the same element multiple times, you can use it an infinite number of times.

The basic idea

So this is basically the same thing as above. Except for the following

  • The candidates array needs to be sorted beforehand
  • If you take the same number in the Path, you jump out of the loop, because it’s sorted, and the same elements are adjacent
  • When DFS recurses, startIdx takes I + 1, so it doesn’t take itself

Writing implement

// Here are only the different parts of the above question, the rest is the same idea
var combinationSum2 = function(candidates, target) {
  let res = []
  // We need to sort the candidates first
  candidates = candidates.sort((a, b) = > a - b)
  const dfs = (startIdx, curPath, curSum) = > {
    if (curSum > target) {
      return
    }
    if (curSum === target) {
      res.push(curPath.slice())
    }
    for (let i = startIdx; i < candidates.length; i++) {
      if (candidates[i] > target) {
        continue;
      }
      // If the number in this cycle is the same, you can jump out of this cycle, because it is sorted and the same elements are adjacent
      if (i > startIdx && candidates[i] === candidates[i-1]) {
        continue;
      }
      curPath.push(candidates[i])
      // continue DFS, startIdx = I + 1, the next round will not select the number including I and left of I
      dfs(i + 1, curPath, curSum + candidates[i])
      curPath.pop()
    }
  }
  dfs(0[],0);
  return res
};

let candidates = [10.1.2.7.6.1.5], target = 8
console.log(combinationSum2(candidates, target))
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