本文解决的问题: 按主题归纳 位运算、矩阵 相关高频题型与通用解法。
适用范围: LeetCode 中文站题目,示例主要使用 Java。
阅读建议: 先识别数据结构与不变量,再结合题目约束选择算法,不要只记忆代码。
位运算
给你一个 正 整数 n 。
用 even 表示在 n 的二进制形式(下标从 0 开始)中值为 1 的偶数下标的个数。
用 odd 表示在 n 的二进制形式(下标从 0 开始)中值为 1 的奇数下标的个数。
请注意,在数字的二进制表示中,位下标的顺序 从右到左。
返回整数数组 answer,其中 answer = [even, odd]。
提示:
1 <= n <= 1000
示例:
1 2 3 4 5 6 7 8 9 10 11
| 输入:n = 50 输出:[1,2] 解释: 50 的二进制表示是 110010。 在下标 1,4,5 对应的值为 1。
输入:n = 2 输出:[0,1] 解释: 2 的二进制表示是 10。 只有下标 1 对应的值为 1。
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
|
public int[] evenOddBit(int n) { int[] res = new int[2]; int i = 0; while (n > 0) { res[i] += n & 1; n >>= 1; i ^= 1; } return res; }
|
二进制不同位
输入两个整数,求两个整数二进制格式有多少个位不同
示例:
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| public int countDifferentBits(int a, int b) { int xorResult = a ^ b; int count = 0; while (xorResult != 0) { count += xorResult & 1; xorResult >>>= 1; } return count; }
|
矩阵
【数组】,【哈希表】,【矩阵】
给定一个 *m* x *n* 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用原地算法。
进阶:
- 一个直观的解决方案是使用
O(*mn*) 的额外空间,但这并不是一个好的解决方案。
- 一个简单的改进方案是使用
O(*m* + *n*) 的额外空间,但这仍然不是最好的解决方案。
- 你能想出一个仅使用常量空间的解决方案吗?
提示:
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
231 <= matrix[i][j] <= 231 - 1
示例:

1 2
| 输入:matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出:[[1,0,1],[0,0,0],[1,0,1]]
|

1 2
| 输入:matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出:[[0,0,0,0],[0,4,5,0],[0,3,1,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 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
| public void setZeroes(int[][] matrix) { boolean isFirstRowZero = false; boolean isFirstColZero = false; for (int i = 0; i < matrix.length; i++) { if (matrix[i][0] == 0) { isFirstColZero = true; break; } } for (int j = 0; j < matrix[0].length; j++) { if (matrix[0][j] == 0) { isFirstRowZero = true; break; } } for (int i = 1; i < matrix.length; i++) { for (int j = 1; j < matrix[i].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) { Arrays.fill(matrix[i], 0); } } for (int j = 1; j < matrix[0].length; j++) { if (matrix[0][j] == 0) { for (int i = 0; i < matrix.length; i++) { matrix[i][j] = 0; } } } if (isFirstRowZero) { Arrays.fill(matrix[0], 0); } if (isFirstColZero) { for (int i = 0; i < matrix.length; i++) { matrix[i][0] = 0; } } }
|
【数组】,【矩阵】,【模拟】
给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。
提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
100 <= matrix[i][j] <= 100
示例:

1 2
| 输入:matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出:[1,2,3,6,9,8,7,4,5]
|

1 2
| 输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出:[1,2,3,4,8,12,11,10,9,5,6,7]
|
代码:
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
| public List<Integer> spiralOrder(int[][] matrix) { List<Integer> res = new ArrayList<>(); if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return res; } int rows = matrix.length; int cols = matrix[0].length; int top = 0, bottom = rows - 1, left = 0, right = cols - 1; while (top <= bottom && left <= right) { for (int i = left; i <= right; i++) { res.add(matrix[top][i]); } top++; for (int i = top; i <= bottom; i++) { res.add(matrix[i][right]); } right--; if (top <= bottom) { for (int i = right; i >= left; i--) { res.add(matrix[bottom][i]); } bottom--; } if (left <= right) { for (int i = bottom; i >= top; i--) { res.add(matrix[i][left]); } left++; } } return res; }
|
【数组】,【数学】,【矩阵】
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须原地旋转图像,这意味着需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
提示:
n == matrix.length == matrix[i].length
1 <= n <= 20
1000 <= matrix[i][j] <= 1000
示例:

1 2
| 输入:matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出:[[7,4,1],[8,5,2],[9,6,3]]
|

1 2
| 输入:matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] 输出:[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
|
代码:
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
|
public void rotate(int[][] matrix) { int n = matrix.length; for (int i = 0; i < n / 2; i++) { for (int j = 0; j < (n + 1) / 2; j++) { int tmp = matrix[i][j]; matrix[i][j] = matrix[n - 1 - j][i]; matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]; matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]; matrix[j][n - 1 - i] = tmp; } } }
|
【数组】、【二分查找】、【分治】、【矩阵】
编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
提示:
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
109 <= matrix[i][j] <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
109 <= target <= 109
示例:

1 2
| 输入: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 输出:true
|

1 2
| 输入: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 输出:false
|
代码:
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
|
public boolean searchMatrix(int[][] matrix, int target) { int top = 0, bottom = matrix.length - 1; while (top <= bottom) { int left = 0, right = matrix[0].length - 1; while (left <= right && matrix[top][right] >= target) { int mid = (left + right) / 2; if (matrix[top][mid] == target) { return true; } else if (matrix[top][mid] > target) { right = mid - 1; } else { left = mid + 1; } } top++; if (matrix[bottom][0] > target) { bottom--; } } return false; }
public boolean searchMatrix(int[][] matrix, int target) { int left = 0, bottom = matrix.length - 1; while (left <= matrix[0].length - 1 && bottom >= 0) { if (matrix[bottom][left] == target) { return true; } if (matrix[bottom][left] > target) { bottom--; } else { left++; } } return false; }
|
参考资料