一、前言
九日集训第八天
二、题目 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]。
遍历数组，交换两边数字后用异或来反转。
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.a)题目分析：给你一个二维整数数组 m a t r i x matrix matrix， 返回 m a t r i x matrix matrix 的 转置矩阵 。
矩阵的 转置 是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。
新建一个二维数组，将行列互换，之后遍历新数组，交换下标赋值即可。
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<m;i++){
for(int j=0;j<n;j++){
ans[i][j]=matrix[j][i];
}
}
return ans;
}
}
3.a)题目分析：在 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 *** 作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
用面积法计算，如果面积不相等返回原数组，面积相等则遍历数组。
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.a)题目分析：给你一个下标从 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.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<r;i++)
ret[i/n][i%n] = original[i];
return ret;
}
}
5.a)题目分析：给你一个 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 次迁移 *** 作后最终得到的 二维网格。
用余数来计算移动k次后的行和列。
j a v a java java代码
class Solution {
public List<List<Integer>> shiftGrid(int[][] grid, int k) {
int numCols = grid[0].length;
int numRows = grid.length;
List<List<Integer>> newGrid = new ArrayList<>();
for (int row = 0; row < numRows; row++) {
List<Integer> 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.a)题目分析：图像平滑器 是大小为 3 x 3 3 x 3 3x3 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。
每个单元格的 平均灰度 定义为：该单元格自身及其周围的 8 8 8 个单元格的平均值，结果需向下取整。
（即，需要计算蓝色平滑器中 9 9 9 个单元格的平均值）。
如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 4 4 4 个单元格的平均值）。
遍历数组，根据题意构造平滑器。
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.a)题目分析：给你一个 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) 在矩阵内。
运用前缀和。
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.a)题目分析：给定四个整数 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∣。
运用广度优先搜索。
j a v a java java代码
class Solution {
public int[][] allCellsDistOrder(int rowCount, int colCount, int r0, int c0) {
LinkedList<int[]> 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<int[]> 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;
}
}
三、做题记录
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）