图像题库
旋转矩阵（旋转图像）
给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
不占用额外内存空间能否做到？
示例1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例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]
]
旋转规律: 对于矩阵中第 i 行的第 j 个元素，在旋转后，它出现在第 j 行倒数第 i 列 位置。
方案A 通过辅助矩阵
思路:
- 关键等式: matrixNew[col][len-row-1] = matrix[row][col]
这样以来，我们使用一个与 matrix 大小相同的辅助数组 matrixNew，临时存储旋转后的结果。我们遍历 matrix 中的每一个元素，根据上述规则将该元素存放到 matrixNew 中对应的位置。在遍历完成之后，再将 matrixNew中的结果 复制到原数组中即可。
:::details 点击查看代码
function createMatrix(array,row,col){
let matrix=[];
for(let i=0;i<row;i++){
matrix[i]=[];
for(let j=0;j<col;j++){
matrix[i][j]=array.shift();
}
}
return matrix
}
function rotateMatrix(matrix){
let row=matrix.length;
let col=matrix[0].length;
let matrixNew=new Array(row).fill(0).map(val=>new Array(col).fill(0))
for(let i=0;i<row;i++){
for(let j=0;j<col;j++){
matrixNew[j][row-i-1]=matrix[i][j];
}
}
for(let i=0;i<row;i++){
for(let j=0;j<col;j++){
matrix[i][j]=matrixNew[i][j];
}
}
return matrix
}
let matrix=createMatrix([1,2,3,4,5,6,7,8,9],3,3);
rotateMatrix(matrix)
console.log(matrix);
:::
性能分析:
时间复杂度：O(N^2)，其中 N 是 matrix 的边长。
空间复杂度：O(N^2) 我们需要使用一个和 matrix 大小相同的辅助数组。
方案B 原地旋转(自外向内)
思路:
-
旋转范围:自外向内 (row/2)*((col+1)/2)
-
原地旋转:
- matrix[row][col] 元素旋转到 matrix[col][len-row-1]
- 即: matrix[col][len-row-1]=matrix[row][col]
- matrix[col][len-row-1] 元素旋转到 :
- 求解旋转目标位置:
- 等式: matrix[col][len-row-1] = matrix[row][col]
- 当前: matrix[?][?] = matrix[col][len-row-1]
- 得出: row = col ; col = len-row-1
- 即: matrix[len-row-1][len-col-1] = matrix[col][len-row-1]
- 求解旋转目标位置:
- matrix[len-row-1][len-col-1] 元素旋转到 :
- 求解旋转目标位置:
- 等式: matrix[col][len-row-1] = matrix[row][col]
- 当前: matrix[?][?] = matrix[len-row-1][len-col-1]
- 得出: row=len-row-1 ; col=len-col-1
- matrix[len-col-1][len-(len-row-1)-1] = matrix[len-row-1][len-col-1]
- 即: matrix[len-col-1][row] = matrix[len-row-1][len-col-1]
- 求解旋转目标位置:
- matrix[len-col-1][row] 元素旋转得到 :
- 求解旋转目标位置:
- 等式: matrix[col][len-row-1] = matrix[row][col]
- 当前: matrix[?][?] = matrix[len-col-1][row]
- 得出: row=len-col-1 ; col = row
- matrix[row][len-(len-col-1)-1]=matrix[len-col-1][row]
- 即: matrix[row][col]=matrix[len-col-1][row]
- 求解旋转目标位置:
- matrix[row][col] 元素旋转到 matrix[col][len-row-1]
-
循环开始通过 temp 临时变量保存当前元素值，依次根据原地旋转操作从下往上赋值即可。
:::details 点击查看代码
function createMatrix(array,row,col){
let matrix=[];
for(let i=0;i<row;i++){
matrix[i]=[];
for(let j=0;j<col;j++){
matrix[i][j]=array.shift();
}
}
return matrix
}
function rotateMatrix(matrix){
let row=matrix.length;
let col=matrix[0].length;
for(let i=0;i<Math.floor(row/2);i++){
for(let j=0;j<Math.floor((col+1)/2);j++){
let temp=matrix[i][j];
matrix[i][j]=matrix[col-j-1][i];
matrix[col-j-1][i]=matrix[row-i-1][col-j-1];
matrix[row-i-1][col-j-1]=matrix[j][row-i-1];
matrix[j][row-i-1]=temp
}
}
return matrix
}
let matrix=createMatrix([1,2,3,4,5,6,7,8,9],3,3);
rotateMatrix(matrix)
console.log(matrix);
:::
性能分析:
时间复杂度：O(N^2)，其中 N 是 matrix 的边长。我们需要枚举的子矩阵大小为 O(⌊n/2⌋×⌊(n+1)/2⌋)= O(N^2)。
空间复杂度：O(1)。为原地旋转。
方案C 用翻转代替旋转(两次翻转)
思路:
- 对矩阵进行水平翻转
- 翻转范围: (row/2)*col
- 翻转操作: matrix[i][j] 与 matrix[row-i-1][j] 互相交换
- 对主对角线翻转
- 翻转范围: row * i
- 翻转操作: matrix[i][j] 与 matrix[j][i] 互相交换
:::details 点击查看代码
function createMatrix(array,row,col){
let matrix=[];
for(let i=0;i<row;i++){
matrix[i]=[];
for(let j=0;j<col;j++){
matrix[i][j]=array.shift();
}
}
return matrix
}
function rotateMatrix(matrix){
let row=matrix.length;
let col=matrix[0].length;
for(let i=0;i<Math.floor(row/2);i++){
for(let j=0;j<col;j++){
[matrix[i][j],matrix[row-i-1][j]]=[matrix[row-i-1][j],matrix[i][j]];
}
}
for(let i=0;i<row;i++){
for(let j=0;j<i;j++){
[matrix[i][j],matrix[j][i]]=[matrix[j][i],matrix[i][j]]
}
}
return matrix
}
let matrix=createMatrix([1,2,3,4,5,6,7,8,9],3,3);
rotateMatrix(matrix)
console.log(matrix);
:::
性能分析:
时间复杂度：O(N^2)，其中 N 是 matrix 的边长。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。
空间复杂度：O(1)。为原地翻转得到的原地旋转。
图像渲染
有一幅以二维整数数组表示的图画 ，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。
给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。
为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。
最后返回经过上色渲染后的图像。
示例1:
输入:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析:
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。
方案A 递归版深度优先遍历
:::details 点击查看代码
var floodFill = function(image, sr, sc, newColor) {
const dfs=(image,x,y,color,newColor)=>{
if(image[x][y]==color){
image[x][y]=newColor;
for(let i=0;i<4;i++){
let mx=x+dx[i];
let my=y+dy[i];
if(mx>=0&&mx<image.length&&my>=0&&my<image[0].length){
dfs(image,mx,my,color,newColor);
}
}
}
}
let dx=[1,0,0,-1];
let dy=[0,1,-1,0];
let currColor=image[sr][sc];
if(currColor!=newColor){
dfs(image,sr,sc,currColor,newColor);
}
return image;
};
:::
方案B 迭代版深度优先遍历
:::details 点击查看代码
:::
方案C 广度优先遍历
思路:
:::details 点击查看代码
function floodFill(image, sr, sc, newColor) {
let dx=[1,0,0,-1];
let dy=[0,1,-1,0];
let currColor=image[sr][sc];
if(currColor==newColor){
return image
}
let n=image.length;
let m=image[0].length;
let queue=[[sr,sc]];
image[sr][sc]=newColor;
while(queue.length){
let item=queue.shift();
let x=item[0];
let y=item[1];
for(let i=0;i<4;i++){
let mx=x+dx[i];
let my=y+dy[i];
if(mx>=0&&mx<n&&my>=0&&my<m&&image[mx][my]==currColor){
queue.push([mx,my]);
image[mx][my]=newColor;
}
}
}
return image;
};
:::