LeetCode刷题总结-数组篇（中）
- 2019 年 11 月 6 日
- 笔记
本文接着上一篇文章《LeetCode刷题总结-数组篇(上)》，继续讲第二个常考问题：矩阵问题。
矩阵也可以称为二维数组。在LeetCode相关习题中，作者总结发现主要考点有：矩阵元素的遍历、矩阵位置的旋转、矩阵行或列次序的交换、空间复杂度为O(1)等。本期共12道题，2道简单题，8道中等题，2道困难题。
- 例1是杨辉三角的一个延申题，是一道非常经典的矩阵习题，本题理想解法是动态规划，但是也可以采用递归来求解。
- 例2是一道顺时针访问矩阵元素的习题，在不少面试题中有见到。
- 例3、例4和例5则强调如果利用矩阵本身的空间，来变换矩阵中的元素，即空间复杂度为O(1)。用到了元素间交换和位运算策略，其中相关解法很巧妙。
- 例6是一道如何移动矩阵的问题。
- 例7和例8则是考察我们快速理解题意，并在较短时间内完成较高质量代码的能力。即编写的代码争取一次性通过。
- 例9考察我们如何把二分查找的应用场景由一维数组转换到二维数组。
- 例10是一道动态规划结合矩阵的经典习题，并且还可以延申出求最短路径的问题。
- 例11则很有意思，该题是上篇例6中《和为K的子数组》的一个升级版，把一维数组的场景变换成了二维的场景，并结合了动态思想，因此题目难度由中等变成了困难。
- 例12是一道困难级别的习题，该题主要考察如何我们的数学分析能力，如何灵活变换矩阵的行和列，以及细节处理能力。
例1 杨辉三角 II
题号：119，难度：简单（可参考 杨辉三角，题号：118，难度：简单）
题目描述：
解题思路：
依据杨辉三角的规律，当前行的数据和上一行的数据有着递推关系：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。依据该递推公式可以写一个较为清晰的动态规划解法，其空间复杂度为O(k)。但是，也可以采用递归的思想来解决。此处提供一个应用递归思想来解决该问题的代码。
具体代码：
class Solution { public List<Integer> getRow(int rowIndex) { List<Integer> result = new ArrayList<>(); if(rowIndex + 1 <= 0) return result; dfs(result, rowIndex+1); return result; } public void dfs(List<Integer> result, int rowIndex) { if(rowIndex == 1) { result.add(1); return; } dfs(result, rowIndex - 1); int len = result.size(); int temp = 1; for(int i = 1;i < len;i++) { int t = result.get(i); result.set(i, temp+result.get(i)); temp = t; } result.add(1); } }
执行结果：
例2 螺旋矩阵
题号：54，难度：中等
题目描述：
解题思路：
这题只需要不停的往内顺时针旋转访问即可。但是，在实现代码时需要注意边界的问题。另外，依据LeetCode上评论的解答思路，可以给访问过的元素做一个标记，或者统计当前已经访问的元素个数，这样更加有利于判断访问结束的时间节点。
具体代码：
class Solution { public List<Integer> spiralOrder(int[][] matrix) { if(matrix.length == 0) return new ArrayList<Integer>(); List<Integer> result = new ArrayList<>(); int start_x = 0, start_y = 0; int max_x = matrix.length, max_y = matrix[0].length; int len = matrix.length * matrix[0].length; while(result.size() < len) { int x = start_x, y = start_y; for(;y < max_y && result.size() < len;y++) result.add(matrix[x][y]); // 向右 y = y -1; for(x = x + 1;x < max_x && result.size() < len;x++) result.add(matrix[x][y]); // 向下 x = x - 1; for(y = y -1;y >= start_y && result.size() < len;y--) result.add(matrix[x][y]); // 向左 y = y + 1; for(x = x - 1;x > start_x && result.size() < len;x--) result.add(matrix[x][y]); // 向上 max_x--; max_y--; start_x++; start_y++; } return result; } }
执行结果：
例3 旋转图像
题号：48，难度：中等
题目描述：
解题思路：
这题可以理解为是例2的一个演化版。题目意思说明为n*n的矩阵，所以不用考虑长方形矩阵的情形。下面代码给出的解答思路为依据正方形矩阵不停往内进行旋转转圈，每次转动的步数为边长长度减去1的大小，每往内旋转一步，正方形边长减2。另外，看到LeetCode评论的解答思路，有一个很有意思：把矩阵翻转两次，第一次沿着主对角线翻转，第二次沿着垂直中线翻转。
具体代码：
class Solution { public void rotate(int[][] matrix) { for(int i = 0;i < matrix.length;i++) { int len = matrix.length - i * 2; while(--len > 0) { int temp = matrix[i][i]; // 左移 for(int j = i + 1;j < matrix.length - i;j++) temp = swap(matrix, i, j, temp); // 下移 for(int j = i + 1;j < matrix.length - i;j++) temp = swap(matrix, j, matrix.length - i -1, temp); } // 右移 for(int j = matrix.length - i - 2;j >= i;j--) temp = swap(matrix, matrix.length - i -1, j, temp); // 上移 for(int j = matrix.length - i - 2;j >= i;j--) temp = swap(matrix, j, i, temp); } } } public int swap(int[][] matrix, int i, int j, int temp) { int t = matrix[i][j]; matrix[i][j] = temp; return t; } }
执行结果：
例4 矩阵置零
题号：73，难度：中等
题目描述：
解题思路：
先说一下空间复杂度为O(m+n)的思路（PS：该思路不符合题意的原地算法要求）。申请两个一维数组，一个表示矩阵行，一个表示矩阵列。然后，遍历矩阵中所有元素，一旦出现零，把该零对应行和对应列的一维数组的值标记为常数1。最后，分别按行和按列给原始矩阵赋值零。
现在参考LeetCode上一个评论的思路，空间复杂度为O(2)。申请两个布尔变量cow和col，分别记录原矩阵第0行和第0列中是否存在零，如果存在标记为True，否则标记为False。然后，接下来的思路就是上面O(m+n)的解决思路，唯一不同的是此时的空间是采用原始矩阵的空间。
具体代码：
class Solution { public void setZeroes(int[][] matrix) { boolean row = false, col = false; for(int i = 0;i < matrix.length;i++) { if(matrix[i][0] == 0) { row = true; break; } } for(int j = 0;j < matrix[0].length;j++) { if(matrix[0][j] == 0) { col = true; break; } } for(int i = 1;i < matrix.length;i++) { for(int j = 1;j < matrix[0].length;j++) { if(matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } for(int i = 1;i < matrix.length;i++) { if(matrix[i][0] == 0) { for(int j = 1;j < matrix[0].length;j++) matrix[i][j] = 0; } } for(int j = 1;j < matrix[0].length;j++) { if(matrix[0][j] == 0) { for(int i = 1;i < matrix.length;i++) matrix[i][j] = 0; } } if(row) { for(int i = 0;i < matrix.length;i++) matrix[i][0] = 0; } if(col) { for(int j = 0;j < matrix[0].length;j++) matrix[0][j] = 0; } } }
执行结果：
例5 生命游戏
题号：289，难度：中等
题目描述：
解题思路：
此题在要求采用原地算法，即不能应用额外的空间来更新原始的矩阵元素。此题的解决方案需要使用位运算来解决。
先观察题目对活细胞和死细胞的定义，然后把它们转化为二进制表示。
活细胞：1变换为二进制01，如果活细胞变为死细胞，只需要把01变为11，即1变为3，其最后一位依然可以识别为活细胞。
死细胞：0变换为二进制00，如果死细胞变为活细胞，只需要把00变为10，即0变为2，其最后一位依然可以识别为死细胞。
最后，采用board[i][j]&1进行位运算的法则来求取一个细胞周围的活细胞数量，并更新当前细胞的状态。
具体代码：
class Solution { public void gameOfLife(int[][] board) { // 01表示活细胞，01——>11变为死细胞，即由1变为3 // 00表示死细胞，00——>10变为活细胞，即由0变为2 for(int i = 0;i < board.length;i++) { for(int j = 0;j < board[0].length;j++) { int count = countLive(board, i, j); if((board[i][j] & 1) == 1) { if(count < 2 || count > 3) board[i][j] = 3; } else { if(count == 3) board[i][j] = 2; } } } for(int i = 0;i < board.length;i++) { for(int j = 0;j < board[0].length;j++) { if(board[i][j] == 3) board[i][j] = 0; if(board[i][j] == 2) board[i][j] = 1; } } } public int countLive(int[][] board, int x, int y) { int[][] step = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}; int count = 0; for(int i = 0;i < step.length;i++) { int temp_x = x + step[i][0]; int temp_y = y + step[i][1]; if(temp_x >= 0 && temp_x < board.length && temp_y >= 0 && temp_y < board[0].length) { if((board[temp_x][temp_y] & 1) == 1) count++; } } return count; } }
执行结果：
例6 图像重叠
题号：835，难度：中等
题目描述：
解题思路：
此题注意如何处理矩阵的移动，使得移动后两个矩阵进行匹配。直接采用两个for循环表示其中一个矩阵移动后的位置。具体变换形式参考代码。
具体代码：
class Solution { public int largestOverlap(int[][] A, int[][] B) { int result = 0, len = A.length; for(int i = 0;i < len;i++) { for(int j = 0;j < len;j++) { int count1 = 0, count2 = 0; for(int m = 0;m < len - i;m++) { for(int n = 0;n < len - j;n++) { count1 += (A[m][n] & B[m+i][n+j]); count2 += (B[m][n] & A[m+i][n+j]); } } result = Math.max(result, count1); result = Math.max(result, count2); } } return result; } }
执行结果：
例7 车的可用捕获量
题号：999，难度：简单
题目描述：
解题思路：
本题较为简单，直接遍历矩阵找到车的位置，然后在车能行走的四个方向依次遍历即可。（放入此题的意图，题目比较长，读懂题意需要耗费一些时间，另外编写代码需要注意边界问题）
具体代码：
class Solution { public int numRookCaptures(char[][] board) { for(int i = 0;i < board.length;i++) { for(int j = 0;j < board[0].length;j++) { if(board[i][j] == 'R') return getResult(board, i, j); } } return 0; } public int getResult(char[][] board, int x, int y) { int count = 0; int tempX = x, tempY = y; //向上 while(--tempX >= 0) { if(board[tempX][y] == 'B') break; else if(board[tempX][y] == 'p') { count++; break; } } tempX = x; //向下 while(++tempX < board.length) { if(board[tempX][y] == 'B') break; else if(board[tempX][y] == 'p') { count++; break; } } //向左 while(--tempY >= 0) { if(board[x][tempY] == 'B') break; else if(board[x][tempY] == 'p') { count++; break; } } tempY = y; //向右 while(++tempY < board[0].length) { if(board[x][tempY] == 'B') break; else if(board[x][tempY] == 'p') { count++; break; } } return count; } }
执行结果：
例8 可以攻击国王的皇后
题号：1222，难度：中等
题目描述：
解题思路：
此题是例7的一个小小的升级版，重点还是处理边界问题，以及快速编写代码和一次通过的能力。
具体代码：
class Solution { private int[][] used; public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) { used = new int[8][8]; used[king[0]][king[1]] = 2; for(int i = 0;i < queens.length;i++) used[queens[i][0]][queens[i][1]] = 1; List<List<Integer>> result = new ArrayList<>(); for(int i = 0;i < queens.length;i++) { if(judgeQ(queens[i][0], queens[i][1])) { List<Integer> temp = new ArrayList<>(); temp.add(queens[i][0]); temp.add(queens[i][1]); result.add(temp); } } return result; } public boolean judgeQ(int x, int y) { int x1 = x; while(--x1 >= 0) { if(used[x1][y] == 2) return true; if(used[x1][y] == 1) break; } int x2 = x; while(++x2 < 8) { if(used[x2][y] == 2) return true; if(used[x2][y] == 1) break; } int y1 = y; while(--y1 >= 0) { if(used[x][y1] == 2) return true; if(used[x][y1] == 1) break; } int y2 = y; while(++y2 < 8) { if(used[x][y2] == 2) return true; if(used[x][y2] == 1) break; } int x3 = x, y3 = y; while(--x3 >= 0 && --y3 >= 0) { if(used[x3][y3] == 2) return true; if(used[x3][y3] == 1) break; } int x4 = x, y4 = y; while(++x4 < 8 && ++y4 < 8) { if(used[x4][y4] == 2) return true; if(used[x4][y4] == 1) break; } int x5 = x, y5 = y; while(--x5 >= 0 && ++y5 < 8) { if(used[x5][y5] == 2) return true; if(used[x5][y5] == 1) break; } int x6 = x, y6 = y; while(++x6 < 8 && --y6 >= 0) { if(used[x6][y6] == 2) return true; if(used[x6][y6] == 1) break; } return false; } }
执行结果：
例9 搜索二维矩阵
题号：74，难度：中等
题目描述：
解题思路：
正常的想法是把矩阵想象成一个一维数组，然后采用二分查找的思路来实现。但是，这种方法可能需要处理（1，m）和（m，1）这两种特殊的二维矩阵边界问题（PS：在LeetCode上看到过直接应用二分查找很快解决的代码）。因为矩阵按照行是有序的，不妨采用每行最后一个值作为边界与目标值进行比较大小，每次增加一行或者减少一列的数据，具体实现可参考代码。
具体代码：
class Solution { /* 二分查找的代码 public boolean searchMatrix(int[][] matrix, int target) { if (matrix.length == 0 || matrix[0].length == 0) return false; int begin, mid, end; begin = mid = 0; int len1 = matrix.length, len2 = matrix[0].length; end = len1 * len2 - 1; while (begin < end) { mid = (begin + end) / 2; if (matrix[mid / len2][mid % len2] < target) begin = mid + 1; else end = mid; } return matrix[begin / len2][begin % len2] == target; } */ public boolean searchMatrix(int[][] matrix, int target) { if(matrix.length == 0) return false; int row = 0, col = matrix[0].length-1; while(row < matrix.length && col >= 0){ if(matrix[row][col] < target) row++; else if(matrix[row][col] > target) col--; else return true; } return false; } }
执行结果：
例10 最小路径和
题号：64，难度：中等
题目描述：
解题思路：
此题最直接的思路是采用递归进行深度搜索遍历来解决，但是提交代码后发现会出现超时的问题。此时，需要考虑应用动态规划的思想来解题。动态规划的转换方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]，另外需要考虑矩阵边界的问题。
具体代码：
class Solution { public int minPathSum(int[][] grid) { int[][] dp = new int[grid.length + 1][grid[0].length + 1]; for(int i = 1;i < dp.length;i++) { for(int j = 1;j < dp[0].length;j++) { if(i == 1) dp[i][j] = dp[i][j-1] + grid[i-1][j-1]; else if(j == 1) dp[i][j] = dp[i-1][j] + grid[i-1][j-1]; else dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]; } } return dp[grid.length][grid[0].length]; } }
执行结果：
例11 元素和为目标值的子矩阵数量
题号：1074，难度：困难
题目描述：
解题思路：
这道题其实是《和为K的子数组，题号：560，难度：中等》的一个升级版，560题是一维数组，本题是二维数组，其和变成了一个子矩阵的形式。此处我们可以采用把矩阵每行的元素变换成从该行开始道当前元素的和，另外单独选两列求矩阵和，这样就把二维数组变成了列形式的一维数组求和。此时，解题思路就和560题一样。
具体代码：
class Solution { public int numSubmatrixSumTarget(int[][] matrix, int target) { for(int i = 0;i < matrix.length;i++) for(int j = 1;j < matrix[0].length;j++) matrix[i][j] += matrix[i][j-1]; int result = 0; for(int j1 = 0;j1 < matrix[0].length;j1++) { for(int j2 = j1;j2 < matrix[0].length;j2++) { Map<Integer, Integer> map = new HashMap<>(); map.put(0,1); int pre = 0; for(int i = 0;i < matrix.length;i++) { int val = pre + (j1 == 0 ? matrix[i][j2] : matrix[i][j2] - matrix[i][j1-1]); result += map.getOrDefault(val - target, 0); map.put(val, map.getOrDefault(val, 0)+1); pre = val; } } } return result; } }
执行结果：
例12 变为棋盘
题号：782，难度：困难
题目描述：
解题思路：
本题分析一下01出现的规律，可知如果n为偶数，那么每行每列中0和1的个数必然相等；如果n为奇数，那么0和1个数差的绝对值为1。由于矩阵只能交换行和列，结果要出现0和1不断相间排列，那么所有行中只能出现两种模式的01排列方式，并且这两种排列方式互补。例如，n=4, 第一行排序：1001，那么其他行要不等于1001，要么等于0110，否则就不可能转换为棋盘，直接输出-1即可。对于列的情况，和行一样。（PS：此题需要处理最小变换次数的边界问题，分奇偶讨论行或者列的最小交换次数）
具体代码：
class Solution { public int movesToChessboard(int[][] board) { if(check(board)) { int row = 0, start = board[0][0]; for(int i = 1;i < board.length;i++) { if(board[i][0] == start) row++; start = 1 - start; } int col = 0; start = board[0][0]; for(int j = 1;j < board[0].length;j++) { if(board[0][j] == start) col++; start = 1 - start; } if(board.length % 2 == 0) { // 分奇数偶数讨论行和列最小交换次数 row = Math.min(board.length-row, row); col = Math.min(board.length-col, col); } else { if(row % 2 == 1) row = board.length-row; if(col % 2 == 1) col = board.length-col; } return row / 2 + col / 2; } return -1; } public boolean judgeEqual(int[][] board, int i, int j) { for(int k = 0;k < board[0].length;k++) { if(board[i][k] != board[j][k]) return false; } return true; } public boolean judgeNotEqual(int[][] board, int i, int j) { for(int k = 0;k < board[0].length;k++) { if(board[i][k] == board[j][k]) return false; } return true; } public boolean check(int[][] board) { int row_0 = 0, row_1 = 0, col_0 = 0, col_1 = 0; for(int i = 0;i < board[0].length;i++) { if(board[0][i] == 0) row_0++; else if(board[0][i] == 1) row_1++; if(board[i][0] == 0) col_0++; else if(board[i][0] == 1) col_1++; } if(Math.abs(row_0 - row_1) > 1 || row_0+row_1 != board[0].length) return false; if(Math.abs(col_0 - col_1) > 1 || col_0+col_1 != board.length) return false; row_0 = 0; row_1 = 0; for(int j = 1;j < board[0].length;j++) { if(judgeEqual(board, 0, j)) row_0++; else if(judgeNotEqual(board, 0, j)) row_1++; else return false; } return true; } }
执行结果：
