九日集训第八天
二、题目 1）832. 翻转图像1.a)题目分析：给定一个 n ∗ n n * n n∗n 的二进制矩阵 i m a g e image image ，先 水平 翻转图像，然后 反转 图像并返回 结果 。
水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [ 1 , 1 , 0 ] [1,1,0] [1,1,0] 的结果是 [ 0 , 1 , 1 ] [0,1,1] [0,1,1]。
反转图片的意思是图片中的 0 0 0 全部被 1 1 1 替换， 1 1 1 全部被 0 0 0 替换。例如，反转 [ 0 , 1 , 1 ] [0,1,1] [0,1,1] 的结果是 [ 1 , 0 , 0 ] [1,0,0] [1,0,0]。
遍历数组，交换两边数字后用异或来反转。
1.b)代码：j a v a java java代码
class Solution {
public int[][] flipAndInvertImage(int[][] image) {
int n = image.length;
for (int i = 0; i < n; i++) {
int left = 0, right = n - 1;
while (left < right) {
if (image[i][left] == image[i][right]) {
image[i][left] ^= 1;
image[i][right] ^= 1;
}
left++;
right--;
}
if (left == right) {
image[i][left] ^= 1;
}
}
return image;
}
}
2）867. 转置矩阵
2.a)题目分析：给你一个二维整数数组 m a t r i x matrix matrix， 返回 m a t r i x matrix matrix 的 转置矩阵 。矩阵的 转置 是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。
新建一个二维数组，将行列互换，之后遍历新数组，交换下标赋值即可。
2.b)代码：j a v a java java代码
class Solution {
public int[][] transpose(int[][] matrix) {
int n =matrix.length;
int m=matrix[0].length;
int ans[][] =new int [m][n];
for(int i =0;i
3）566. 重塑矩阵
在
M
A
T
L
A
B
MATLAB
MATLAB 中，有一个非常有用的函数
r
e
s
h
a
p
e
reshape
reshape ，它可以将一个
m
x
n
m x n
mxn 矩阵重塑为另一个大小不同
（
r
x
c
）
（r x c）
（rxc）的新矩阵，但保留其原始数据。给你一个由二维数组
m
a
t
mat
mat 表示的
m
x
n
m x n
mxn 矩阵，以及两个正整数
r
r
r 和
c
c
c ，分别表示想要的重构的矩阵的行数和列数。重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。如果具有给定参数的
r
e
s
h
a
p
e
reshape
reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
3.a)题目分析：
用面积法计算，如果面积不相等返回原数组，面积相等则遍历数组。
3.b)代码：
j
a
v
a
java
java代码
class Solution {
public int[][] matrixReshape(int[][] mat, int r, int c) {
int ret[][] =new int [r][c];
int m =mat.length;
int n = mat[0].length;
int id ;
if(m*n!=r*c){
return mat;
}
for (int x = 0; x < m * n; ++x) {
ret[x / c][x % c] = mat[x / n][x % n];
}
return ret;
}
}
4）2022. 将一维数组转变成二维数组
给你一个下标从
0
0
0 开始的一维整数数组
o
r
i
g
i
n
a
l
original
original 和两个整数
m
m
m 和
n
n
n 。你需要使用
o
r
i
g
i
n
a
l
original
original 中 所有 元素创建一个
m
m
m 行
n
n
n 列的二维数组。
o
r
i
g
i
n
a
l
original
original 中下标从
0
0
0 到
n
−
1
n - 1
n−1 （都 包含 ）的元素构成二维数组的第一行，下标从
n
n
n 到
2
∗
n
−
1
2 * n - 1
2∗n−1 （都 包含 ）的元素构成二维数组的第二行，依此类推。请你根据上述过程返回一个
m
∗
n
m * n
m∗n 的二维数组。如果无法构成这样的二维数组，请你返回一个空的二维数组。
4.a)题目分析：
本题跟上题类似，用面积法即可
4.b)代码：
j
a
v
a
java
java代码
class Solution {
public int[][] construct2DArray(int[] original, int m, int n) {
int [][]ret = new int [m][n];
int r =original.length;
if(r!=m*n){
return new int [0][0];
}
for(int i=0;i
5）1260. 二维网格迁移
给你一个
m
m
m 行
n
n
n列的二维网格
g
r
i
d
grid
grid 和一个整数
k
k
k。你需要将
g
r
i
d
grid
grid 迁移
k
k
k 次。
每次「迁移」操作将会引发下述活动：
位于
g
r
i
d
[
i
]
[
j
]
grid[i][j]
grid[i][j] 的元素将会移动到
g
r
i
d
[
i
]
[
j
+
1
]
grid[i][j + 1]
grid[i][j+1]。
位于
g
r
i
d
[
i
]
[
n
−
1
]
grid[i][n - 1]
grid[i][n−1] 的元素将会移动到
g
r
i
d
[
i
+
1
]
[
0
]
grid[i + 1][0]
grid[i+1][0]。
位于
g
r
i
d
[
m
−
1
]
[
n
−
1
]
grid[m - 1][n - 1]
grid[m−1][n−1] 的元素将会移动到
g
r
i
d
[
0
]
[
0
]
grid[0][0]
grid[0][0]。
请你返回
k
k
k 次迁移操作后最终得到的 二维网格。
5.a)题目分析：
用余数来计算移动k次后的行和列。
5.b)代码：
j
a
v
a
java
java代码
class Solution {
public List> shiftGrid(int[][] grid, int k) {
int numCols = grid[0].length;
int numRows = grid.length;
List> newGrid = new ArrayList<>();
for (int row = 0; row < numRows; row++) {
List newRow = new ArrayList<>();
newGrid.add(newRow);
for (int col = 0; col < numCols; col++) {
newRow.add(0);
}
}
for (int row = 0; row < numRows; row++) {
for (int col = 0; col < numCols; col++) {
int newCol = (col + k) % numCols;
int wrapAroundCount = (col + k) / numCols;
int newRow = (row + wrapAroundCount) % numRows;
newGrid.get(newRow).set(newCol, grid[row][col]);
}
}
return newGrid;
}
}
6）661. 图片平滑器
图像平滑器 是大小为
3
x
3
3 x 3
3x3 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。每个单元格的 平均灰度 定义为：该单元格自身及其周围的
8
8
8 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中
9
9
9 个单元格的平均值）。如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中
4
4
4 个单元格的平均值）。
6.a)题目分析：
遍历数组，根据题意构造平滑器。
6.b)代码：
j
a
v
a
java
java代码
class Solution {
public int[][] imageSmoother(int[][] img) {
int m = img.length, n = img[0].length;
int[][] ret = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int num = 0, sum = 0;
for (int x = i - 1; x <= i + 1; x++) {
for (int y = j - 1; y <= j + 1; y++) {
if (x >= 0 && x < m && y >= 0 && y < n) {
num++;
sum += img[x][y];
}
}
}
ret[i][j] = sum / num;
}
}
return ret;
}
}
7）1314. 矩阵区域和
给你一个
m
∗
n
m * n
m∗n 的矩阵
m
a
t
mat
mat和一个整数
k
k
k ，请你返回一个矩阵
a
n
s
w
e
r
answer
answer ，其中每个
a
n
s
w
e
r
[
i
]
[
j
]
answer[i][j]
answer[i][j] 是所有满足下述条件的元素
m
a
t
[
r
]
[
c
]
mat[r][c]
mat[r][c] 的和：
i
−
k
<
=
r
<
=
i
+
k
i - k <= r <= i + k
i−k<=r<=i+k,
j
−
k
<
=
c
<
=
j
+
k
j - k <= c <= j + k
j−k<=c<=j+k 且
(
r
,
c
)
(r, c)
(r,c) 在矩阵内。
7.a)题目分析：
运用前缀和。
7.b)代码：
j
a
v
a
java
java代码
class Solution {
public int[][] matrixBlockSum(int[][] mat, int K) {
int row = mat.length;
int col = mat[0].length;
int[][] res = new int[row][col];
int[][] dp = new int[row + 1][col + 1];
for (int i = 1; i <= row; i++) {
for (int j = 1; j <= col; j++)
dp[i][j] = mat[i - 1][j - 1] + dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1];
}
for (int i = 1; i <= row; i++) {
for (int j = 1; j <= col; j++) {
int x0 = Math.max(i - K - 1, 0);
int x1 = Math.min(i + K, row);
int y0 = Math.max(j - K - 1, 0);
int y1 = Math.min(j + K, col);
res[i - 1][j - 1] = dp[x1][y1] - dp[x1][y0] - dp[x0][y1] + dp[x0][y0];
}
}
return res;
}
}
8）1030. 距离顺序排列矩阵单元格
给定四个整数
r
o
w
,
c
o
l
s
,
r
C
e
n
t
e
r
row , cols , rCenter
row,cols,rCenter 和
c
C
e
n
t
e
r
cCenter
cCenter 。有一个
r
o
w
s
x
c
o
l
s
rows x cols
rowsxcols 的矩阵，你在单元格上的坐标是
(
r
C
e
n
t
e
r
,
c
C
e
n
t
e
r
)
(rCenter, cCenter)
(rCenter,cCenter) 。返回矩阵中的所有单元格的坐标，并按与
(
r
C
e
n
t
e
r
,
c
C
e
n
t
e
r
)
(rCenter, cCenter)
(rCenter,cCenter) 的 距离 从最小到最大的顺序排。你可以按 任何 满足此条件的顺序返回答案。单元格
(
r
1
,
c
1
)
和
(
r
2
,
c
2
)
(r1, c1) 和 (r2, c2)
(r1,c1)和(r2,c2) 之间的距离为
∣
r
1
−
r
2
∣
+
∣
c
1
−
c
2
∣
|r1 - r2| + |c1 - c2|
∣r1−r2∣+∣c1−c2∣。
8.a)题目分析：
运用广度优先搜索。
8.b)代码：
j
a
v
a
java
java代码
class Solution {
public int[][] allCellsDistOrder(int rowCount, int colCount, int r0, int c0) {
linkedList queue = new linkedList<>();
queue.add(new int[] {r0, c0});
boolean[][] visited = new boolean[rowCount][colCount];
visited[r0][c0] = true;
int[][] ansArr = new int[rowCount*colCount][2];
int num = 0;
while (!queue.isEmpty()) {
List nodeList = new ArrayList<>();
while (!queue.isEmpty()) {
int[] node = queue.removeFirst();
ansArr[num++] = node;
nodeList.add(node);
}
for (int[] node : nodeList) {
int row = node[0];
int col = node[1];
// 上
if (row > 0 && !visited[row - 1][col]) {
queue.add(new int[]{row-1, col});
visited[row - 1][col] = true;
}
// 下
if (row < rowCount - 1 && !visited[row + 1][col]) {
queue.add(new int[]{row+1, col});
visited[row + 1][col] = true;
}
// 左
if (col > 0 && !visited[row][col-1]) {
queue.add(new int[]{row, col-1});
visited[row][col-1] = true;
}
// 右
if (col < colCount - 1 && !visited[row][col+1]) {
queue.add(new int[]{row, col+1});
visited[row][col+1] = true;
}
}
}
return ansArr;
}
}
三、做题记录
