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.

21. Next permutation

The label

  • The language understanding
  • medium

The title

Leetcode portal

Let’s just open leetCode.

To implement a function that gets the next permutation, the algorithm rearranges the given sequence of numbers into the next larger permutation in the lexicographical order. If no next larger permutation exists, the numbers are rearranged into the smallest permutation (that is, ascending). You must modify in place, allowing only extra constant space.

The next permutation is simply the number of integers that you get when you combine these numbers. For example, [1, 2, 3] has permutations

[1, 2, 3] < < [1, 3, 2], [2, 1, 3] < [2, 3, 1) < < [3, 1, 2] [3, 2, 1] 123 < 132 < 213 < 231 < 312 < 321Copy the code

The next permutation is going to be in this order and the next permutation is going to be in that order, and if it’s already the largest it goes back to the head of the queue and becomes the smallest.

The basic idea

  1. We want the next number to be bigger than the current number, so that it satisfies the definition of the next permutation. So you just swap the big number with the decimal number, and you get a bigger number. For example, 213, if you swap 1 and 3 you get a bigger number 231.

  2. We also want the next number to increase as little as possible, and in order to do that, we need to swap as far to the right as possible, and we need to look backwards and swap as small a large number as possible with the decimal number ahead. For example, 1243, the next permutation would swap 3 and 2 instead of 4 and 2. After switching the large number to the front, you need to reset all the numbers following the large number to the ascending order, which is the smallest order.

  3. It’s already the largest, it’s a descending order (the largest), and it inverts directly to the ascending order (the smallest).

steps

  1. Find the first pair of adjacent ascending elements (I, j) from back to forward, satisfyingA[i] < A[j]. At this time[j,end)It must be in descending order. If no matching pair of adjacent elements can be found, the current is indicated[begin, end)Is a descending order, then jump directly to Step 4
  2. At [j,end) look forward from backThe first onemeetA[i] < A[k] 的 k.A [I], A [k]The difference is the above mentionedThe decimal,Large number of
  3. willA[i] 与 A[k]exchange
  4. You can say that at this point[j, end)It has to be in descending order, inverse[j, end)In ascending order

Writing implement

/ * * *@param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
  let len = nums.length
  if (len <= 1) {
    return nums
  }
  let [i, j, k] = [len - 2, len - 1, len - 1]
  // Find the first group of adjacent ascending order
  while (i >= 0 && nums[i] >= nums[j]) {
    i--;
    j--;
  }
  // Not the last permutation, find k such that A[I]
  if (i >= 0) {
    while (nums[i] >= nums[k]) {
      k--;
    }
    A[k] = A[k];
    [nums[i], nums[k]] = [nums[k], nums[i]]
  } 
  // [j, end]
  for (i = j, j = len - 1; i < j; i++, j--) {
    [nums[i], nums[j]] = [nums[j], nums[i]]
  }
  // console.log(nums)
};

console.log(nextPermutation([3.2.1]))
Copy the code

22. Binary search

The label

  • Basic search
  • simple

The title

Leetcode portal

Let’s just open leetCode.

Binary lookup is a textbook algorithm based on comparing a target value to the middle element of an array.

The basic idea

  1. If the target value is equal to the intermediate element, the target value is found.
  2. If the target value is small, continue searching to the left.
  3. If the target value is large, continue searching on the right.

So notice that the premise is that the array is ordered. Eliminate the wrong answers half at a time.

steps

  1. Initialization pointerleft = 0, right = n - 1.
  2. whenleft <= right 时
    1. Compare intermediate elementsnums[pivot]And the targettarget 。
    2. iftarget === nums[pivot], return to Pivot.
    3. iftarget < nums[pivot], continue the search on the leftright = pivot - 1.
    4. iftarget > nums[pivot], continue the search on the rightleft = pivot + 1.

Writing implement

var binarySearch = function(nums, target) {
  // Set the left and right Pointers and the middle bit baseline
  let [left, right, pivot] = [0, nums.length - 1.0]
  while (left <= right) {
    pivot = left + Math.floor((right - left) / 2)
    if (nums[pivot] === target) {
      return pivot
    } else if (target < nums[pivot]) {
      right = pivot - 1
    } else {
      left = pivot + 1}}return -1
};

console.log(binarySearch([-1.0.3.5.9.12].9))
Copy the code

23. Search for a Sorted array with search-in-Rotation-array

The label

  • Binary search
  • medium

The title

Leetcode portal

Let’s just open leetCode.

Suppose the array sorted in ascending order is rotated at some previously unknown point. For example, the array [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]. Searches for a given target value, returning its index if it exists in the array, or -1 otherwise. You can assume that there are no duplicate elements in the array. (Each value in the array is unique)

What rotation means is that there is a break point in an otherwise ordered sequence. The next random sequence is placed in front of the array, thus forming two ordered sequences.

The relevant knowledge

Binary search above is the foreshadowing of this problem, this problem is a slight variation of binary search.

The basic idea

Because the array is basically ordered, although there is a “break point” in the middle, it can be implemented using binary search algorithm.

Right numerical interval [big] | [4, 5, 6, 7, 0, 1, 2] | | numerical interval [small] left pviotCopy the code

In fact, this sequence is divided into two sections, one is a small numerical interval, one is a large numerical interval.

  • Nums [pviot] > nums[left], nums[pviot] > nums[right]

  • Nums [pviot] < nums[left], nums[pviot] < nums[right], as shown below.

Right numerical interval [big] | [6, 7, 0, 1, 2, 4, 5] | | small numerical interval left pviotCopy the code

After determining which interval to fall in, judge the relationship between the benchmark and target, and then adjust the left and right boundaries to deal with the problem with dichotomy.

Writing implement

var search = function(nums, target) {
  let [len, left, right, pivot] = [nums.length, 0, nums.length - 1.0]
  if (len === 0) {
    return -1
  }
  while (left <= right) {
    pivot = left + Math.floor((right - left) / 2)
    if (nums[pivot] === target) {
      return pivot
    } else if (nums[pivot] >= nums[left]) {
      // Adjust the left and right boundaries when the value is large
      if (nums[left] <= target && target < nums[pivot]) {
        right = pivot - 1
      } else {
        left = pivot + 1}}else if (nums[pivot] <= nums[right]) {
      // Adjust the left and right boundaries in a small part of the interval
      if (nums[pivot] < target && target <= nums[right]) {
        left = pivot + 1
      } else {
        right = pivot - 1}}}return -1
};

let nums = [4.5.6.7.0.1.2], target = 1
console.log(search(nums, 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 reiver 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

reference

  • Leetcode-cn.com/problems/ne…