59. Spiral Matrix II
Posted Updated LeetCode / Mediuma minute read (About 158 words)

59. Spiral Matrix II

Question

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

Read more
54. Spiral Matrix
1572. Matrix Diagonal Sum
Posted Updated LeetCode / Easya minute read (About 132 words)

1572. Matrix Diagonal Sum

Question

Given a square matrix mat, return the sum of the matrix diagonals.

Only include the sum of all the elements on the primary diagonal and all the elements on the secondary diagonal that are not part of the primary diagonal.

Read more
1329. Sort the Matrix Diagonally
Posted Updated LeetCode / Medium2 minutes read (About 234 words)

1329. Sort the Matrix Diagonally

Question

A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix’s end. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2].

Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix.

Solution

分别遍历数组的两条边。
按对角线顺序进行遍历，用列表记录访问过的数字。
排序列表后按对角线填入原数组。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    public int[][] diagonalSort(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        List<Integer> arr = new ArrayList<>();
        
        for(int t = 0; t < m; t++){
            int i = t, j = 0;
            
            while(i < m && j < n){
                arr.add(mat[i][j]);
                i++;
                j++;
            }
            
            Collections.sort(arr);
            
            i = t;
            j = 0;
            
            while(i < m && j < n){
                mat[i][j] = arr.get(j);
                i++;
                j++;
            }
            arr.clear();
        }

        for(int t = 1; t < n; t++){
            int i = 0, j = t;
            
            while(i < m && j < n){
                arr.add(mat[i][j]);
                i++;
                j++;
            }
            
            Collections.sort(arr);
            
            i = 0;
            j = t;
            
            while(i < m && j < n){
                mat[i][j] = arr.get(i);
                i++;
                j++;
            }
            arr.clear();
        }
        return mat;
    }
}
Posted Updated LeetCode / Easya minute read (About 155 words)

2319. Check if Matrix Is X-Matrix

Question

A square matrix is said to be an X-Matrix if both of the following conditions hold:

  1. All the elements in the diagonals of the matrix are non-zero.
  2. All other elements are 0.

Given a 2D integer array grid of size n x n representing a square matrix, return true* if grid is an X-Matrix*. Otherwise, return false.

Solution

遍历，直接判断是否在对角线上，如果在且位置为0，则返回false。
如果不在对角线上，且位置部位0，则返回false。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean checkXMatrix(int[][] grid) {
        int n = grid.length;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i == j || i + j == n - 1){
                    if(grid[i][j] == 0) return false;
                }
                else if(grid[i][j] != 0) return false;
            }
        }
        return true;
    }
}
304. Range Sum Query 2D - Immutable
Posted Updated LeetCode / Medium3 minutes read (About 432 words)

304. Range Sum Query 2D - Immutable

Question

Given a 2D matrix matrix, handle multiple queries of the following type:

  • Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class:

  • NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
  • int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Solution

前缀和/动态规划，用一个dp[][]数组记录到matrix[0][0]到matrix[i][j]区域的和。

计算两个点之间形成的总数只需用外侧的位置的前缀和加上内侧位置的前缀和，然后减去两者交换长宽位置的前缀和即可。

递推公式

计算dp[][]数组时，需要将其上侧与左侧所有数字加和，并加上matrix[][]上该位置对应的元素。
用dp[i][j-1] - dp[i-1][j-1]计算出左侧所有数字之和，dp[i-1][j]则是上侧所有数字之和。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class NumMatrix {
    int[][] dp;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        dp = new int[m+1][n+1];
        
        for(int i = 1; i <= matrix.length; i++){
            for(int j = 1; j <= matrix[0].length; j++){
                dp[i][j] = dp[i][j-1] - dp[i-1][j-1] + dp[i-1][j] + matrix[i-1][j-1];
            }
        };
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row1][col1] + dp[row2+1][col2+1] - dp[row1][col2+1] - dp[row2+1][col1];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

Solution 2

暴力搜索，直接计算从row1, col1到row2, col2的元素加和。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class NumMatrix {
    int[][] mat;
    public NumMatrix(int[][] matrix) {
        mat = matrix;
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for(int i = row1; i <= row2; i++){
            for(int j = col1; j <= col2; j++){
                sum += mat[i][j];
            }
        }
        return sum;
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */
867. Transpose Matrix
Posted Updated LeetCode / Easya few seconds read (About 107 words)

867. Transpose Matrix

Question

Given a 2D integer array matrix, return the transpose of matrix.

The transpose of a matrix is the matrix flipped over its main diagonal, switching the matrix’s row and column indices.

Solution

记录一个新数组res[][]。

双重循环，交换下标将matrix[i][j]复制到res[j][i]，最后返回。

Code

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int[][] transpose(int[][] matrix) {
        int[][] res = new int[matrix[0].length][matrix.length];
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                res[j][i] = matrix[i][j];
            }
        }
        return res;
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 519 words)

1091. Shortest Path in Binary Matrix

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

All the visited cells of the path are 0.
All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).
The length of a clear path is the number of visited cells of this path.

由于不能重复搜索，且需要在搜索时将搜索过的位置改变，因此需要采用BFS逐一层级的搜索。
逐层级搜索并记录层级。最后返回层级+1即可。
（还有更快的优化算法A*）

整体没有改变太多，基本还是方法二那种。启发式函数改为切比雪夫距离距离。
距离计算方法有很多，常用启发式函数有这几种。选择合适的启发式函数有利于速度的提升。这题可以用好几种启发式函数，初学都可以试着都写一下。

曼哈顿距离（Manhattan Distance）
一般只能在四个方向上移动时用（右、左、上、下）

对角线距离（Diagonal Distance）：
当我们只允许向八个方向移动时用（国际象棋中的王移动方式那种）

欧几里得距离（Euclidean Distance）：
不受限制，允许向任何方向移动时。

切比雪夫距离（Chebyshev Distance）：
可参考：[https://leetcode-cn.com/problems/minimum-time-visiting-all-points/solution/fang-wen-suo-you-dian-de-zui-xiao-shi-jian-by-le-2/](LeetCode 1266)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid[0].length;
        int m = grid.length;
        
        Queue<Integer> q = new LinkedList<>();
        int count = 0;
        q.add(0);
        int size = q.size();
        
        while(!q.isEmpty()){
            for(int k = 0; k < size; k++){
                int curr = q.poll();
                int i = curr / n;
                int j = curr % n;

                if(grid[i][j] ==1) continue;                
                if(i == m-1 && j == n-1 && grid[i][j] == 0) return count+1;
            
                if(grid[i][j] == 0){
                    grid[i][j] = 1;
                    if(i+1<n && j+1<n) q.add((i+1) * n + (j+1));
                    if(i+1<n && j-1>=0) q.add((i+1) * n + (j-1));
                    if(i+1<n) q.add((i+1) * n + j);
                    if(i-1>=0 && j-1>=0) q.add((i-1) * n + (j-1));
                    if(i-1>=0 && j+1<n) q.add((i-1) * n + (j+1));
                    if(j+1<n) q.add(i * n + (j+1));
                    if(j-1>=0) q.add(i * n + (j-1));
                    if(i-1>=0) q.add((i-1) * n + j);
                }
            }
            size = q.size();
            count++;
        }
        return -1;
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 194 words)

547. Number of Provinces

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

DFS搜索，当map[i][i] = 1时加入搜索。
搜索时将map[i][i]设为0。遍历并递归其数列。
当map[i][i]等于0时，返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    int[][] map;
    public int findCircleNum(int[][] isConnected) {
        map = isConnected;
        int count = 0;
        
        for(int i = 0; i < isConnected.length; i++){
            if(map[i][i] == 1){
                count++;
                dfs(i);
            }
        }
        return count;
    }
    
    private void dfs(int i){
        if(map[i][i] == 0){
            return;
        }
        map[i][i] = 0;
        for(int j = 0; j < map[0].length; j++){
            if(map[i][j] == 1){
                dfs(j);
            }
        }
    }
}
200. Number of Islands
Posted Updated LeetCode / Medium2 minutes read (About 309 words)

200. Number of Islands

Question

Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Solution

遍历所有点，如果等于1则对其进行DFS搜索。
在搜索的同时将1设为0。
如果等于0则递归返回。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    char[][] area;
    public int numIslands(char[][] grid) {
        area = grid;
        int count = 0;
        
        for(int i = 0; i < area.length; i++){
            for(int j = 0; j < area[0].length; j++){
                if(area[i][j] == '1'){
                    dfs(i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private void dfs(int i, int j){
        if(area[i][j] == '0'){
            return;
        }
        area[i][j] = '0';
        
        if( i+1 < area.length ){
            dfs(i+1, j);
        }
        if( i-1 >= 0 ){
            dfs(i-1, j);
        }
        if( j+1 < area[0].length ){
            dfs(i, j+1);
        }
        if( j-1 >= 0 ){
            dfs(i, j-1);
        }
    }
}

Solution 2

同样是dfs搜索遍历每个位置，然而这个方法使用visited[][]数组来记录点是否被访问过。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    int[][] visited;
    char[][] map;
    int[][] operations;
    public int numIslands(char[][] grid) {
        visited = new int[grid.length][grid[0].length];
        map = grid;
        int count = 0;
        operations = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(visited[i][j] == 1 || map[i][j] == '0') continue;
                dfs(i, j);
                count++;
            }
        }
        return count;
    }
    
    private void dfs(int x, int y){
        if(x < 0 || x >= map.length || y < 0 || y >= map[0].length ) return;
        if(visited[x][y] == 1 || map[x][y] == '0') return;
        visited[x][y] = 1;
        for(int[] operation : operations){
            int m = x + operation[0];
            int n = y + operation[1];
            dfs(m, n);
        }
        
    }
}
240. Search a 2D Matrix II
Posted Updated LeetCode / Medium / 复习a minute read (About 137 words)

240. Search a 2D Matrix II

Question

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

Solution

将起始点设置为第一行的最后一列。
如果搜寻目标大于该点则向下搜索。
如果搜寻目标小于该点则向左搜索。

Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0, j = matrix[0].length - 1;
        
        while(i < matrix.length && j >= 0){
            if(matrix[i][j] == target) return true;
            else if(matrix[i][j] > target) j--;
            else i++;
        }
        return false;
    }
}
48. Rotate Image
Posted Updated LeetCode / Medium / 复习3 minutes read (About 505 words)

48. Rotate Image

Question

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Solution 1

此方法是in-place算法。

visited[][]数组记录访问情况，遍历所有位置，如果已访问则跳过。
循环替换矩阵上的每一个位置，如果已经访问过则break。
如果未访问则将要替换位置的值保存，并且在visited[][]数组上记录。
然后继续遍历替换过的位置。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public void rotate(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] visited = new int[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(visited[i][j] == 1) continue;
                int x = i, y = j;
                int value = matrix[i][j];
                while(true){
                    int s = n-1-x, t = y;
                    if(visited[t][s] == 1) break;
                    int temp = matrix[t][s];
                    matrix[t][s] = value;
                    value = temp;
                    visited[t][s] = 1;
                    x = t;
                    y = s;
                }
            }
        }
    }
}

Solution 2

此方法类似Solution 1，但是并非原地算法。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public void rotate(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] mat = new int[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int s = n-1-i, t = j;
                mat[t][s] = matrix[i][j];
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                matrix[i][j] = mat[i][j];
            }
        }
    }
}

Solution 3

辅助方法getPixel计算旋转后的像素位置。
旋转时候矩阵内的四个分区的像素会互相替换。
因此需要将需要旋转的初始位置记录进入队列。
旋转图像时根据getPixel方法计算出需要替换的位置。
然后依次替换像素。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        Queue<Integer> queue = new LinkedList();
        for (int p = 0; p < n/2; p++){
            for(int q = 0; q < (n+1)/2; q++){
                queue.offer(p * n + q);
            }
        }

        while(!queue.isEmpty()){
            int i = queue.poll();
            int INDEX = i;
            boolean flag = true;
            int temp = matrix[i/n][i%n];
            while(i != INDEX || flag ){
                flag = false;
                int j = getPixel(n, i);
                int swap = matrix[j / n][j % n];
                matrix[j / n][j % n] = temp; 
                temp = swap;
                i = j;
            }
        }     
    }
    
    private int getPixel(int n, int o){
        int row = o / n;
        int col = o % n;
        int newRow = col;
        int newCol = n - (row + 1);
        return (newRow * n) + newCol;
    }
}
Posted Updated LeetCode / Mediuma minute read (About 140 words)

59. Spiral Matrix II

问题
Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

循环，创建一个上界和一个下界。
当达到界限时，改变方向。
更新上界和下界的数值。
当上界小于下界时返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        int upperBound = n;
        int lowerBound = 0;
        int i = 0;
        int j = 0;
        int count = 1;
        ans[0][0] = 1;
 
        while ( lowerBound < upperBound ){
            while ( j < upperBound-1 ){
                j++;
                count++; 
                ans[i][j] = count;           
            }
            while ( i < upperBound-1 ){
                i++;
                count++;
                ans[i][j] = count;
            }
            while ( j > lowerBound ){
                j--;
                count++;
                ans[i][j] = count;
            }
            upperBound--;
            lowerBound++;
            while ( i > lowerBound ){
                i--;
                count++;
                ans[i][j] = count;
            }
        }
        return ans;
    }
}
Posted Updated LeetCode / Medium3 minutes read (About 381 words)

289. Game of Life

问题
According to Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

  1. Any live cell with fewer than two live neighbors dies as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by over-population.
  4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.

辅助方法，计算每个位置四周有生命的总和。
根据规则填写到新数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    public void gameOfLife(int[][] board) {
        int[][] ans = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[0].length; j++){
                int neighbors = countNeighbors(board, i, j);
                if ( neighbors < 2 && board[i][j] == 1 ){
                    ans[i][j] = 0;
                }
                else if( neighbors <= 3 && board[i][j] == 1 ){
                    ans[i][j] = 1;
                }
                else if( neighbors > 3 && board[i][j] == 1 ){
                    ans[i][j] = 0;
                }
                else if( neighbors == 3 && board[i][j] == 0){
                    ans[i][j] = 1;
                }
                
            }
        }
        
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[0].length; j++){
                board[i][j] = ans[i][j];
            }
        }
    }
    
    
    private int countNeighbors(int[][] board, int r, int c){
        int neighbors = 0;
        int row = board.length;
        int col = board[0].length;
        
        if(r + 1 < row && board[r+1][c] == 1){ neighbors++; }
        if(r - 1 >= 0 && board[r-1][c] == 1){ neighbors++; }
        if(c + 1 < col && board[r][c+1] == 1){ neighbors++; }
        if(c - 1 >= 0 && board[r][c-1] == 1){ neighbors++; }
        
        if(r + 1 < row && c + 1 < col && board[r+1][c+1] == 1){ neighbors++; }
        if(r + 1 < row && c - 1 >= 0 && board[r+1][c-1] == 1 ){ neighbors++; }
        if(r - 1 >= 0 && c + 1 < col && board[r-1][c+1] == 1 ){ neighbors++; }
        if(r - 1 >= 0 && c - 1 >= 0 && board[r-1][c-1] == 1 ){ neighbors++; }
        
        return neighbors;
    }
}
Posted Updated LeetCode / Easya minute read (About 176 words)

1260. Shift 2D Grid

问题
Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.

In one shift operation:

Element at grid[i][j] moves to grid[i][j + 1].
Element at grid[i][n - 1] moves to grid[i + 1][0].
Element at grid[m - 1][n - 1] moves to grid[0][0].
Return the 2D grid after applying shift operation k times.

遍历整个数组，将索引值加上移动的次数，得到新的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        int row = grid.length;
        int col = grid[0].length;
        int size = row * col;
        Integer[][] mat = new Integer[row][col];
        
        for (int i = 0; i < size; i++){
            int j = i + k;
            if ( j > size - 1){
                j %= size;
            }
            int nr = j / col;
            int nc = j % col;
            int or = i / col;
            int oc = i % col;
            
            mat[nr][nc] = grid[or][oc];
        }
        
        for (int i = 0; i < row; i++){
            List<Integer> nums = Arrays.asList(mat[i]);
            ans.add(nums);
        }
        
        return ans;
    }
}
Follow

Recents

Archives

Links

×