This is the 18th day of my participation in the August Challenge

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.

## 160. Search two-dimensional Matrix II (search-a-2D-matrix-II)

• medium

### The title

Leetcode portal

Write an efficient algorithm to search a target value in m x n matrix matrix. The matrix has the following properties:

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

Example 1

``````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 = 5Output:true
Copy the code``````

Example 2

``````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 = 20Output:false
Copy the code``````

### The basic idea

• The idea is actually very clear, similar to the grid
• We can start at the bottom left, which is the number 18 in this case
• Bigger than it, one step to the right, one step smaller than it and one step up until you find the answer

### Writing implement

``````const searchMatrix = function(matrix, target) {
if (matrix.length === 0 || matrix[0]? .length ===0) {
return false
}
// Calculate the boundary value
let rows = matrix.length, cols = matrix[0]? .length// Initialize the bottom left corner as the starting point, the first column of the last row
let row = matrix.length - 1, col = 0
// Do not go beyond the boundary
while (row >= 0 && col < cols) {
if (matrix[row][col] === target) {
return true
} else if (matrix[row][col] < target) {
/ / right
col++
} else {
/ / go up
row--
}
}
// Go 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 the code``````

## 161. Perfect-squares

• medium
• mathematics

### The title

Leetcode portal

Given a positive integer n, find several perfect squares (e.g. 1, 4, 9, 16…). So that their sum is equal to n. You want to minimize the number of perfect squares that make up the sum.

Given an integer n, return the minimum number of perfect squares that sum to n.

A perfect square is an integer whose value equals the square of another integer; In other words, its value is equal to the product of an integer. For example, 1, 4, 9, and 16 are perfect squares, but 3 and 11 are not.

Example 1

``````Enter n =12Output:3Explanation:12 = 4 + 4 + 4
Copy the code``````

Example 2

``````Enter n =13Output:2Explanation:13 = 4 + 9
Copy the code``````

### The basic idea

Again, our basic 3 steps for dynamic programming.

#### State definition

Our goal is to find the minimum number of perfect squares that sum n numbers

So let dp[I] be the least number of perfect squares that sum the numbers I, so dp[n] is our answer

#### State transition

Let’s start with another j from the beginning, dp[I – j * j] is just dp[I] plus j squared, so it’s going to be plus 1, and the equation is going to be

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

For example, 12 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 have to note that dp[4] = 1, dp[3] = 3 so when we get to the minimum, we can still get to the minimum if we change j.

#### The border

Dp [I] = 1+ 1+ 1+… + 1 (I ones)

### Writing implement

``````const numSquares = function (n) {
let dp = new Array(n + 1).fill(0)
for (let i = 1; i < n + 1; i++) {
I = 1+ 1+ 1+... I 1
dp[i] = i
for (let j = 1; i >= j * j; j++) {
Dp [i-j * j] + 1 = 1
dp[i] = Math.min(dp[i], dp[i - j * j] + 1)}}return dp[n]
}

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

In addition, we recommend this series of articles, very simple, on the front of the advanced students are very effective, wall crack recommended!! Core concepts and algorithm disassembly series