Leetcode 48 rotating image (horizontal + main diagonal), leetcode 221 maximum square (dynamic programming DP indicates the answer value with ij as the lower right corner), leetcode 240 searching two-d

Top1：Leetcode 48 Rotated image （ level + The main diagonal ）

And leetcode Interview questions 01.07 It's a question https://leetcode.cn/problems/rotate-matrix-lcci/
Title Description ：
Given a n × n Two dimensional matrix of matrix Represents an image . Please rotate the image clockwise 90 degree .

You must be there. In situ Rotated image , This means that you need to modify the input two-dimensional matrix directly . Please do not Use another matrix to rotate the image .

One 、 Flip horizontal i: Subscript 0 To n/2【 middle +firstEnd】,j:0 To col In exchange for ij And n-i-1,j+ Main diagonal flip i： Subscript 0 To rows,j：0 To <i In exchange for ij

The main diagonal is diagonally downward to the right

• Time complexity ：O（1）. among N yes matrix The length of . For each flip operation , We all need to enumerate half the elements in the matrix .
• Spatial complexity ：O（1）. In situ inversion constant level complexity .

You can use the complete code ：

public void rotate(int[][] matrix) {
    
    int n = matrix.length;
    //  Flip horizontal 
    for (int i = 0; i < n / 2; i++) {
       //  Subscript  【 middle 】  and  【 The first half end】
        for (int j = 0; j < n; j++) {
    
            int tem = matrix[i][j];
            matrix[i][j] = matrix[n - i - 1][j];   //  Subscript to -1, Just think about it and you can write it 
            matrix[n - i - 1][j] = tem;
        }
    }
    //  Main diagonal flip 
    for (int i = 0; i < n; i++) {
       //  The lower half of the main diagonal , When i=1,j Can only 0;i=2,j Can only 0,1
        for (int j = 0; j < i; j++) {
    
            int tem = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tem;
        }
    }
}

Top2：Leetcode 221 The largest square （ Dynamic programming dp Said to ij Is the answer value in the lower right corner ）

Official explanation ：https://leetcode.cn/problems/maximal-square/solution/zui-da-zheng-fang-xing-by-leetcode-solution/
Title Description ：
In a ‘0’ and ‘1’ In the two-dimensional matrix , Found contains only ‘1’ The largest square of , And return its area .

One 、dp[i][j] Said to ij For the lower right corner , And only 1 Is the maximum side length of the square .

Two 、 If dp[i][j]=='1’ Just initialize i=0 || j=0 The location of =1, Otherwise, it defaults to 0. next ij The position is equal to upper 、 left side 、 upper left The minimum value of .

• Time complexity ：O（mn）. among m and n Is the number of rows and columns of the matrix . You need to traverse each element of the source real matrix to calculate dp value .
• Spatial complexity ：O（mn）. We created a matrix of the same size as the original matrix dp.
• Pay attention to space complexity optimization ： Due to the dp(i,j) From above 、 Three adjacent positions on the left and upper left dp Values determine , Therefore, two one-dimensional arrays can be used for state transition , Space complexity is optimized to O(n).

You can use the complete code ：

public int maximalSquare(char[][] matrix) {
    
    int ans = 0;
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return ans;
    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;
                }
                ans = Math.max(ans, dp[i][j]);
            }
        }
    }
    return ans * ans;
}

Top3：Leetcode 240 Search for a two-dimensional matrix II（ Exclude row and column method ）

Official explanation ：https://leetcode.cn/problems/search-a-2d-matrix-ii/solution/sou-suo-er-wei-ju-zhen-ii-by-leetcode-so-9hcx/
Title Description ：
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：

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

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 = 20
Output ：false

One 、 Initial subscript x=0,y=length-1.while Loop traversal （x<m&&y>=0） When matrix[x][y] > target When it's time to explain y This column is better than matrix[x][y] Big ,y– Exclude a column and narrow the range ; When else It means matrix[x][y] < target It means that this line is better than matrix[x][y] Small ,x++ Exclude the previous line .

Finally, the Boolean value is returned

• Time complexity ：O（m+n）. In the process of searching , If we don't find target, Then we'll either y Reduce 11, Either x increase 11. because (x,y) The initial values of are (0,n−1), therefore y Can be reduced at most n Time ,x Can be increased up to m Time , The total number of searches is m+n.
• Spatial complexity ：O（1）. Constant space complexity .

You can use the complete code ：

public boolean searchMatrix(int[][] matrix, int target) {
    
    int m = matrix.length, n = matrix[0].length;
    int x = 0, y = n - 1;
    while (x < m && y >= 0) {
    
        if (matrix[x][y] == target) return true;
        if (matrix[x][y] > target) y--;   //  All elements in this column are >target, Ignore this column 
        else x++;   //  All elements in this line are < target, Ignore this line 
    }
    return false;
}