6.16号刷题

发表于 | 分类于 | 0 comments

第一题 54. Spiral Matrix

题目描述

给定一个二维矩阵，将二维矩阵按照螺旋的方式进行读取。

算法

利用一个direction指示当前方向和需要截止的大小，然后按照螺旋的方式进行读取。

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
public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix.length == 0) return res;
        int m = matrix.length, n = matrix[0].length;
        int total = m * n, count = 0, direction = 1;
        int i = 0, j = 0;
        while (count < total) {
            int extra = direction / 4;
            if (direction % 4 == 1) {
                while (j < n - extra) {
                    res.add(matrix[i][j]);
                    j++;
                    count++;
                }
                j--;
                direction++;
                i++;
            } else if (direction % 4 == 2) {
                while (i < m - extra) {
                    res.add(matrix[i][j]);
                    i++;
                    count++;
                }
                i--;
                direction++;
                j--;
            } else if (direction % 4 == 3) {
                while (j >= extra) {
                    res.add(matrix[i][j]);
                    j--;
                    count++;
                }
                j++;
                direction++;
                i--;
            } else if (direction % 4 == 0) {
                while (i >= extra) {
                    res.add(matrix[i][j]);
                    i--;
                    count++;
                }
                i++;
                direction++;
                j++;
            }
        }
        
        return res;        
    }
}

第二题 59. Spiral Matrix II

题目描述

现在给定一个整数n， 需要产生一个n * n的矩阵，其中矩阵中的每个位置的值有 [1, n^2]按照螺旋的方式排列

算法

方法与之前的相同

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
public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        if (n < 1) return res;
        int count = 1, i = 0, j = 0, direction = 1;
        while (count <= n * n) {
            int extra = direction / 4;
            
            if (direction % 4 == 1) {
                while (j < n - extra) {
                    res[i][j] = count;
                    count++;
                    j++;
                }
                j--;
                direction++;
                i++;
            } else if (direction % 4 == 2) {
                while (i < n - extra) {
                    res[i][j] = count;
                    count++;
                    i++;
                }
                i--;
                direction++;
                j--;
            } else if (direction % 4 == 3) {
                while (j >= extra) {
                    res[i][j] = count;
                    count++;
                    j--;
                }
                j++;
                direction++;
                i--;
            } else if (direction % 4 == 0) {
                while (i >= extra) {
                    res[i][j] = count;
                    count++;
                    i--;
                }
                i++;
                direction++;
                j++;
            }
        }
        return res;        
    }
}

第三题 562. Longest Line of Consecutive One in Matrix

题目描述

给定01矩阵M，计算矩阵中一条线上连续1的最大长度。一条线可以为横向、纵向、主对角线、反对角线。

提示：给定矩阵元素个数不超过10,000

算法

从头开始检查每个数是否为1，如果是1的话进行查看，为了缩减重复的运算，我们如果发现这个数的前一个数是1的话，就跳过。自己代码比较繁琐，但是能beat 90%

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
public class Solution {
    public int longestLine(int[][] M) {
        if (M.length == 0) return 0;
        int max  = 0 , m = M.length, n = M[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int num = M[i][j];
                if (num == 1) {
                    int count = 1;
                    // 1. Horizontal
                    if (j == 0) {
                        count = 1;
                        int temp = j + 1;
                        while(temp < n && M[i][temp] == 1) {
                            count++;
                            temp++;
                        }
                    } else if (M[i][j - 1] != 1) {
                        count = 1;
                        int temp = j + 1;
                        while(temp < n && M[i][temp] == 1) {
                            count++;
                            temp++;
                        }
                    }
                    max = Math.max(count, max);
                    // 2. Vertical
                    if (i == 0) {
                        count = 1;
                        int temp = i + 1;
                        while (temp < m && M[temp][j] == 1) {
                            count++;
                            temp++;
                        }
                    } else if (M[i - 1][j] != 1) {
                        count = 1;
                        int temp = i + 1;
                        while (temp < m && M[temp][j] == 1) {
                            count++;
                            temp++;
                        }
                    }
                    max = Math.max(count, max);
                    // 3. diagonal
                    if (i == 0 || j == 0) {
                        count = 1;
                        int tempI = i + 1, tempJ = j + 1;
                        while(tempI < m && tempJ < n && M[tempI][tempJ] == 1) {
                            count++;
                            tempI++;
                            tempJ++;
                        }
                    } else if (M[i - 1][j - 1] != 1) {
                        count = 1;
                        int tempI = i + 1, tempJ = j + 1;
                        while(tempI < m && tempJ < n && M[tempI][tempJ] == 1) {
                            count++;
                            tempI++;
                            tempJ++;
                        }
                    }
                    max = Math.max(count, max);
                    // 4. anti-diagonal
                    if (i == 0 || j == n - 1) {
                        count = 1;
                        int tempI = i + 1, tempJ = j - 1;
                        while (tempJ >= 0 && tempI < m && M[tempI][tempJ] == 1) {
                            count++;
                            tempI++;
                            tempJ--;
                        }
                    } else if (M[i - 1][j + 1] != 1) {
                        count = 1;
                        int tempI = i + 1, tempJ = j - 1;
                        while (tempJ >= 0 && tempI < m && M[tempI][tempJ] == 1) {
                            count++;
                            tempI++;
                            tempJ--;
                        }
                    }
                    max = Math.max(count, max);
                }
            }
        }
        
        return max;        
    }
}

第四题 64. Minimum Path Sum

题目描述

现在又一个m * n的int型矩阵，要求从(0，0)这个点走到(m - 1, n - 1)这个点，求怎么走的sum值最小。

算法

动态规划，与求机器人有几条路径的方法相似

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
public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid.length == 0) return 0;
        int m = grid.length, n = grid[0].length;
        int[][] presum = new int[m][n];
        
        // Initial
        presum[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            presum[i][0] = presum[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            presum[0][j] = presum[0][j - 1] + grid[0][j];
        }
        
        //DP calculate
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                int min = Math.min(presum[i - 1][j], presum[i][j - 1]);
                presum[i][j] = grid[i][j] + min;
            }
        }
        return presum[m - 1][n - 1];        
    }
}