1. Maximum area of the island
Given a grid, a non-empty two-dimensional array containing some zeros and ones.
An island is a combination of adjacent ones (land) that must be either horizontal or vertical. You can assume that all four edges of the grid are surrounded by zeros (for water).
Find the largest island area in the given two-dimensional array. (If there are no islands, the return area is 0.)
Example 1:
[[0.0.1.0.0.0.0.1.0.0.0.0.0].
[0.0.0.0.0.0.0.1.1.1.0.0.0].
[0.1.1.0.1.0.0.0.0.0.0.0.0].
[0.1.0.0.1.1.0.0.1.0.1.0.0].
[0.1.0.0.1.1.0.0.1.1.1.0.0].
[0.0.0.0.0.0.0.0.0.0.1.0.0].
[0.0.0.0.0.0.0.1.1.1.0.0.0].
[0.0.0.0.0.0.0.1.1.0.0.0.0]]
Copy the codeI should return 6 for the given matrix above. Note that the answer should not be 11, as islands can only contain 1’s in four directions, horizontal or vertical.
Example 2:
[[0,0,0,0,0,0,0,0]]
Copy the codeFor the given matrix above, return 0.
Note: The given matrix grid is not more than 50 in length or width.
Analysis:
We want to know the area of each connected shape in the grid and take the maximum. On a piece of land, explore each piece of land connected to it (and land connected to it) in four directions, and the total amount of land explored will be the area of the connected shape. To ensure that each piece of land is visited no more than once, we set the value of that piece of land to 0 each time we pass it. So we don’t visit the same land many times.
- 1. Traverse the grid to get the maximum island area for each location, and return one
maxArea - 2. Search function – Recursive implementation of DFS function
- 3. Determine the boundary, if not inside the boundary, return 0; Otherwise, it is 1. Recursively calculate whether the upper, lower and left sides are 1 and calculate the island area;
- Grid [I][j]=0
Realization solution:
var maxAreaOfIsland = function (grid) {
var maxArea = 0; // Record holder
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === 1) {
maxArea = Math.max(maxArea, dfs(grid, i, j)); // Update the record
}
}
}
function dfs(grid, i, j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === 0) {
return 0; // Recursive exit boundary
}
grid[i][j] = 0; // Avoid double counting, sink island strategy
var area = 1;
area += dfs(grid, i + 1, j); // The top 1
area += dfs(grid, i - 1, j); // The following 1
area += dfs(grid, i, j + 1); // 1 on the left
area += dfs(grid, i, j - 1); // 1 on the right
return area
}
return maxArea // Return the maximum area
};
Copy the code2. Maximum square area
Find the largest square containing only 1 in a two-dimensional matrix of 0 and 1 and return its area.
Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output:4
Copy the codeDynamic programming analysis:
We use dp(I,j)dp(I,j)dp(I,j) to represent the maximum side length of a square with (I,j)(I,j)(I,j) as the bottom right corner and containing only 111. If we can calculate the values of all dp(I,j)dp(I,j)dp(I,j), then the maximum value is the maximum side length of the matrix containing only 111 squares, whose square is the area of the largest square.
If the value of this position is 000, then dp(I,j)=0dp(I,j)=0dp(I,j)=0, because the current position cannot be in a square of 111;
If the value of this position is 111, then dp(I,j) DP (I,j)dp(I,j) is determined by the DPDPDP values of the three adjacent positions above, to the left, and to the upper left. Specifically, the value of the element at the current position is equal to the minimum of the elements at the three adjacent positions plus 111, and the state transition equation is as follows:
Dp (I, j) = min (dp (I – 1, j), dp (I – 1, j – 1), dp (I, j) – 1) + 1 dp (I, j) = min (dp (I – 1, j), dp (I – 1, j – 1), dp (I, J – 1) + 1 dp (I, j) = min (dp (I – 1, j), dp (I – 1, j – 1), dp (I, j) – 1) + 1
Js solution:
/ * *
* @param {character[][]} matrix
* @return {number}
* /
var maximalSquare = function (matrix) {
if(! matrix.length || ! matrix[0].length) return 0
var maxSlideLen = 0.// Record the longest edge
dp = Array(matrix.length); // Build the dp array
for (var i = 0; i < matrix.length; i++) {
dp[i] = Array(matrix[0].length).fill(0); // Fill each bit with 0
for (let j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] === 1) {
if (i === 0 || j === 0) {
dp[i][j] = 1; // The first column and the first row have a dp value of 1
} else {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 // Check whether there are 0's in the upper left, lower left, and upper right
}
maxSlideLen = Math.max(maxSlideLen, dp[i][j]) // Update the maximum edge length
}
}
}
return maxSlideLen ** 2 // Find the maximum side length area
};
Copy the code3. Count all primes less than the non-negative integer n.
Count the number of primes less than the non-negative integer n.
Example:
Input:10
Output:4
Explanation: less than10The primes of phi have a total of4Student: Yes, they are2.3.5.7 。
Copy the codeViolent solution:
/ * *
* @param {number} n
* @return {number}
* /
var countPrimes = function(n) {
var count = 0;
function isPrime(num){
for(var i=2; i<=Math.sqrt(num); i++){
if(num%i===0) return false
}
return true
}
for(var j=2; j<n; j++){
if(isPrime(j)){
count++
}
}
return count
};
Copy the codeEratosthenes sieve method
/ * *
* @param {number} n
* @return {number}
* /
var countPrimes = function(n) {
var count = 0;
var times = Array(n).fill(0);
for(var i =2; i<times.length; i++){
if(! times[i- 1]) {
count++;
for(varj=i*i; j<=n; j+=i){
times[j- 1] =true
}
}
}
return count
};
Copy the code