“This is the 14th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”
takeaway
Fat friends in order to better help new students adapt to the algorithm and questions, recently we began a special assault step by step. We’re going to start with one of the most frustrating types of algorithms, dynamic programming and we’re going to do a 21-day incubation program. What are you waiting for? Come and join us for 21 days of dynamic programming challenge!!
21 Days Dynamic Planning Introduction
Given an M x N grid with non-negative integers, find a path from the top left to the bottom right that minimizes the sum of the numbers along the path.
Note: you can only move one step down or right at a time.
The sample1Input: grid = [[1.3.1], [1.5.1], [4.2.1]] output:7Explanation: Because the path1-3-1-1-1The sum of.Copy the codeThe sample2Input: grid = [[1.2.3], [4.5.6]] output:12
Copy the codeDue to the direction of the path is down or to the right, so the grid of the first line of each element can't get to, starting from the elements of the upper left corner to the right of the grid in the first column of each element can't get to, from the top left corner elements began to move down the path is the only at this time, so that each element corresponding to the minimum path and the sum of the Numbers on the corresponding path. For element not in the first row and first column, you can move a step down from the adjacent elements above to arrive, or from one step to the right to the left adjacent element, element corresponding to the minimum path and the adjacent elements with the left adjacent elements is equal to the top of the corresponding minimum path and the minimum value and the value of the current element. Since the minimum path of each element is related to the minimum path sum of its adjacent elements, dynamic programming can be used to solve the problem. Create a two-dimensional array \ Textit {dp}dp, the same size as the original grid, \ Textit {dp}[I][j]dp[I][j] represents the minimum sum of paths from the top left corner to (I,j)(I,j). Obviously, \ textit {dp} [0] [0]=\textit{grid}[0] [0]dp[0] [0]=grid[0] [0]. For the remaining elements in \textit{dp}dp, the element values are calculated using the following state transition equation. When I > 0 I >0And j = 0 j =0When \ textit {dp} [I] [0]=\textit{dp}[i-1] [0]+\textit{grid}[i][0]dp[i][0[I] = dp -1] [0]+grid[i][0]. When I = I = 00And j > 0 j >0When \ textit {dp} [0][j]=\textit{dp}[0][j-1]+\textit{grid}[0][j]dp[0][j]=dp[0[j] -1]+grid[0] [j]. When I > 0 I >0And j > 0 j >0When \ textit {dp} [j] = \ [I] min (\ textit {dp} [I -1][j],\textit{dp}[i][j-1\]) + textit {grid} [I] [j] dp [I] [j] = min (dp [I -1] [j], dp [I] [j -1]) + grid [I] [j]. Finally, we get \textit{dp}[m-1][n-1[m] dp -1[n] -1] is the minimum path sum from the upper-left corner of the grid to the lower-right corner of the grid.class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length, columns = grid[0].length;
int[][] dp = new int[rows][columns];
dp[0] [0] = grid[0] [0];
for (int i = 1; i < rows; i++) {
dp[i][0] = dp[i - 1] [0] + grid[i][0];
}
for (int j = 1; j < columns; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < columns; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; }}return dp[rows - 1][columns - 1]; }}Copy the codeIn a two-dimensional matrix of ‘0’ and ‘1’, find the largest square containing only ‘1’ and return its area.
The sample1Input: matrix = [["1"."0"."1"."0"."0"], ["1"."0"."1"."1"."1"], ["1"."1"."1"."1"."1"], ["1"."0"."0"."1"."0"]] output:4
Copy the code
The sample2Input: matrix = [["0"."1"], ["1"."0"]] output:1
Copy the codeThe sample3Input: matrix = [["0"]] output:0
Copy the codeDynamic programming can be used to reduce time complexity. We use \textit{dp}(I,j) dp(I,j) to indicate that (I,j) (I,j) (I,j) is the bottom right corner, and only contains11The maximum side length of a square. If we can calculate all \textit{dp}(I,j) dp(I,j), then the maximum value is that the matrix contains only11Square is the area of the largest square. So how do we evaluate each element in \textit{dp}dp? For each position (I,j) (I,j), check the value of that position in the matrix: if the value of that position is00, \textit{dp}(I,j)= 0dp(I,j)=0, because the current position cannot be in by11Of a square; If the value of that position is zero11, then \ Textit {dp}(I,j) dp(I,j) is determined by the three adjacent positions \textit{dp}dp 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 plus11, the state transition equation is as follows: dp(I, j)=min(dp(I −1, j), dp (I -1, j -1) and dp (I, j -1)) +1Dp (I, j) = min (dp (I -1, j), dp (I -1, j -1) and dp (I, j -1)) +1
class Solution {
public int maximalSquare(char[][] matrix) {
int maxSide = 0;
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return maxSide;
}
int rows = matrix.length, columns = matrix[0].length;
int[][] dp = new int[rows][columns];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (matrix[i][j] == '1') {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; } maxSide = Math.max(maxSide, dp[i][j]); }}}int maxSquare = maxSide * maxSide;
returnmaxSquare; }}Copy the codeThe interview questions
This time, I’m going to talk about the essential knowledge of binary tree interview; Construct a Node object:
public class node {
public int val;
public node left;/ / the left child
public node right;/ / right child
public node(a) {}public node(int val,node left,node right) {
this.val=val;
this.left=left;
this.right=right;
}
public node(int val, node left) {
super(a);this.val = val;
this.left = left; }}Copy the code Find the minimum depth of the binary tree
public class minDepth {
public static int depth(node root) {
if(root==null)return 0;
return getMin(root);
}
public static int getMin(node root) {
if(root==null)return Integer.MAX_VALUE;// The maximum value of the int type
if(root.left==null&& root.right==null) {return 1;
}
return Math.min(getMin(root.left), getMin(root.right))+1; }}Copy the code