本文解决的问题: 按主题归纳 位运算、矩阵 相关高频题型与通用解法。

适用范围: 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
/**
* 用i=0表示当前位是奇数位,i=1表示当前位是偶数位,并记录对应奇偶数位的结果。
* 当n>0时,如果当前位是1,则增加对应奇偶位的计数,然后反转i并将n作右移位运算。
* 循环以上过程,直到n=0,最后返回结果。
* @param n 输入的整数
* @return 结果数组
*/
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
输入:22 33
输出:5

代码:

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;

// 计算1的个数
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. 矩阵置零示例

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

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) {
// 标记第一行和第一列是否需要置为0
boolean isFirstRowZero = false;
boolean isFirstColZero = false;

// 检查第一列是否有0
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][0] == 0) {
isFirstColZero = true;
break;
}
}

// 检查第一行是否有0
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[0][j] == 0) {
isFirstRowZero = true;
break;
}
}

// 使用第一行和第一列记录每行和每列是否需要置为0
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;
}
}
}

// 根据第一行和第一列的信息,将相应行和列置为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

示例:
2. 螺旋矩阵示例

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

2. 螺旋矩阵示例

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

示例:
3. 旋转图像示例

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

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
/**
* 旋转图像
*
* @param matrix 输入的二维数组
*/
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;
}
}
}

搜索二维矩阵 II

【数组】、【二分查找】、【分治】、【矩阵】

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

提示:
m == matrix.length

n == matrix[i].length

1 <= n, m <= 300

109 <= matrix[i][j] <= 109

每行的所有元素从左到右升序排列

每列的所有元素从上到下升序排列

109 <= target <= 109

示例:
4. 搜索二维矩阵 II示例

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

4. 搜索二维矩阵 II示例

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
/**
* 方法一:
* 在一个二维矩阵中搜索一个特定的目标值
* 矩阵的每一行都被认为是升序排列的
*
* @param matrix 一个二维矩阵,其中每个子数组代表矩阵的一行
* @param target 要搜索的目标值
* @return 如果目标值在矩阵中找到,则返回true;否则返回false
*/
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;
// 如果中间位置的值等于目标值,返回true
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--;
}
}
// 如果没有找到目标值,返回false
return false;
}

/**
* 方法二:
* 在一个二维矩阵中搜索一个特定的目标值
* 该矩阵的特点是每行从左到右递增,每列从上到下递增
* 此方法利用矩阵的排序特性来高效搜索目标值
*
* @param matrix 一个二维整数数组,表示待搜索的矩阵
* @param target 一个整数,表示要搜索的目标值
* @return 如果矩阵中存在该目标值,则返回true;否则返回false
*/
public boolean searchMatrix(int[][] matrix, int target) {
// 初始化搜索的起始位置在矩阵的左下角
int left = 0, bottom = matrix.length - 1;

// 当搜索位置没有越界时,继续搜索
while (left <= matrix[0].length - 1 && bottom >= 0) {
// 如果找到目标值,返回true
if (matrix[bottom][left] == target) {
return true;
}
// 如果当前位置的值大于目标值,说明目标值可能在上方,向上移动一行
if (matrix[bottom][left] > target) {
bottom--;
} else {
// 如果当前位置的值小于目标值,说明目标值可能在右方,向右移动一列
left++;
}
}
// 如果搜索完整个矩阵都没有找到目标值,返回false
return false;
}

参考资料