current position:Home>Front end algorithm must brush question series [88]

Front end algorithm must brush question series [88]

2021-08-27 00:15:43 Wen bin Da Niao

This is my participation 8 The fourth of the yuegengwen challenge 18 God , Check out the activity details :8 Yuegengwen challenge

There's nothing in this series , It's pure leetcode Topic analysis , Don't seek to use a coquettish line or niche solution , But with clear code and simple enough ideas to help you clear up the topic . Let you no longer be afraid of the written test in the interview .

160. Search for a two-dimensional matrix II (search-a-2d-matrix-ii)

label

  • secondary

subject

leetcode Portal

Write an efficient algorithm to search  m x n  matrix matrix One of the goals in target . The matrix has the following characteristics :

The elements of each row are arranged in ascending order from left to right . The elements of each column are arranged in ascending order from top to bottom .

Example 1

image.png

 Input :matrix = [
[1,4,7,11,15],
[2,5,8,12,19],
[3,6,9,16,22],
[10,13,14,17,24],
[18,21,23,26,30]], target = 5
 Output :true
 Copy code 

Example 2

image.png

 Input :matrix = [
[1,4,7,11,15],
[2,5,8,12,19],
[3,6,9,16,22],
[10,13,14,17,24],
[18,21,23,26,30]], target = 20
 Output :false
 Copy code 

The basic idea

  • The idea is actually very clear , It's like walking in a grid
  • We can start at the bottom left , In this case 18 The number of
  • Bigger than it , Take a step to the right , Smaller than it, take a step up until you find the answer

The writing method realizes

const searchMatrix = function(matrix, target) {
  if (matrix.length === 0 || matrix[0]?.length === 0) {
    return false
  }
  //  Boundary value calculation 
  let rows = matrix.length, cols = matrix[0]?.length
  //  Initialize the lower left corner as the starting point ,  The first column of the last row 
  let row = matrix.length - 1, col = 0
  //  You can't go beyond the boundary 
  while (row >= 0 && col < cols) {
    if (matrix[row][col] === target) {
      return true
    } else if (matrix[row][col] < target) {
      //  turn right 
      col++
    } else {
      //  Go up 
      row--
    }
  }
  //  Beyond the boundary 
  return false
}

let matrix = [
[1,4,7,11,15],
[2,5,8,12,19],
[3,6,9,16,22],
[10,13,14,17,24],
[18,21,23,26,30]], target = 22

console.log(searchMatrix(matrix, target))
 Copy code 

161. Complete square (perfect-squares)

label

  • secondary
  • mathematics

subject

leetcode Portal

Given a positive integer  n, Find some perfect squares ( such as  1, 4, 9, 16, ...) Make their sum equal to n. You need to minimize the number of complete squares that make up the sum .

Give you an integer n , Return and for n Of the complete square of Minimum quantity .

Complete square It's an integer , Its value is equal to the square of another integer ; let me put it another way , Its value is equal to the product of the self multiplication of an integer . for example ,1、4、9 and 16 They're all perfect squares , and 3 and 11 No .

Example 1

 Input : n = 12
 Output : 3 
 explain : 12 = 4 + 4 + 4
 Copy code 

Example 2

 Input : n = 13
 Output : 2
 explain : 13 = 4 + 9
 Copy code 

The basic idea

It's still our basic dynamic programming 3 Step train of thought .

State definition

our The goal is Is to seek With n The number is and Of The least number of complete squares

Then set dp[i] That is to say i The number is the minimum number of the complete square of the sum , that dp[n] That's our answer to this question

State shift

Let's start another j from the beginning , see dp[i - j * j] Actually Namely dp[i] Plus j The square of , So add... To the quantity 1, The equation is

dp[i] = Math.min(dp[i], dp[i - j * j] + 1)

Does anyone say this will not happen , such as 12 Count to 12 = 9 + 3 => dp[12] = dp[3] + 1

12 = 4 + 4 + 4 => dp[12] = dp[8] + 1 = dp[4] + 1 + 1 = 1 + 1 + 1

We need to pay attention dp[4] = 1 , dp[3] = 3 So when we calculate the minimum , j The minimum value can still be calculated after the change .

The border

dp[i] The greatest satisfaction is actually all Split into 1 Add up , i = 1 + 1 + 1+ ... + 1 (i individual 1)

The writing method realizes

const numSquares = function (n) {
  let dp = new Array(n + 1).fill(0)
  for (let i = 1; i < n + 1; i++) {
    //  This is a  i  Maximum case  i = 1 + 1 + 1+ ... i  individual  1
    dp[i] = i
    for (let j = 1; i >= j * j; j++) {
      //  Follow again  dp[i - j * j] + 1  The biggest one   At present  j  Round up the next smallest bit 
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1)
    }
  }
  return dp[n]
}

let n = 12
console.log(numSquares(n))
 Copy code 

In addition, I would like to recommend this series of articles to you , It's very simple , It is very useful for advanced students , Wall crack recommendation !!! Core concepts and algorithms

That's all for today , If you want to brush the topic with me, you can add my wechat Click here to make a friend Or Search my wechat infinity_9368, You can chat and say Add my code " Heavenly King Gedi tiger " The next sentence is english , Please send me the verification message presious tower shock the rever monster, I see it through , After that, I'll do my best to help you , But pay attention to the way you ask questions , I suggest you read this article first : The wisdom of asking questions

Reference resources

copyright notice
author[Wen bin Da Niao],Please bring the original link to reprint, thank you.
https://en.qdmana.com/2021/08/20210827001541488u.html

Random recommended