leetcode-48-旋转图像
给定一个 n × n 的二维矩阵 matrix
表示一个图像。请你将图像顺时针旋转 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]]
提示:
n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000
个人解题思路
本题的难点在于想到一个可以用代码实现的旋转方式,我是在看观察矩阵的时候突然想到:
整个矩阵旋转 90 度,相当于每一圈分别旋转 90 度
把每一圈想象成一个正方形,旋转 90 度相当于每条边依次向后换一下
最内圈需要旋转的正方形起始坐标是 (x,x)
, x = Math.floor(n /2 ) - 1
,边长 sideLen = n - 2 * x
从内向外把每一圈都旋转 90 度,就完成了整个矩阵的旋转
代码实现
var rotate = function (matrix) {
const n = matrix.length
const minSquareTopLeftX = Math.floor(n / 2) - 1
for (let min = minSquareTopLeftX; min >= 0; min--) {
const sideLen = n - 2 * min
const max = min + sideLen - 1
let preSideNumList = initPreSideNumList(min, sideLen)
let currentSideNumList = []
for (let step = 1; step <= 4; step++) {
if (step === 1) {
handleRightSide(preSideNumList, currentSideNumList, min, sideLen, max)
}
if (step === 2) {
preSideNumList = currentSideNumList
currentSideNumList = []
handleBottomSide(preSideNumList, currentSideNumList, min, max)
}
if (step === 3) {
preSideNumList = currentSideNumList
currentSideNumList = []
handleLeftSide(preSideNumList, currentSideNumList, min, max)
}
if (step === 4) {
preSideNumList = currentSideNumList
handleTopSide(preSideNumList, min, sideLen, max)
}
}
}
function initPreSideNumList(min, sideLen) {
const result = []
for (let j = min; j < min + sideLen; j++) {
result.push(matrix[min][j])
}
return result
}
function handleRightSide(preSideNumList, currentSideNumList, min, sideLen, max) {
for (let j = min; j < min + sideLen; j++) {
currentSideNumList.push(matrix[j][max])
matrix[j][max] = preSideNumList[j - min]
}
}
function handleBottomSide(preSideNumList, currentSideNumList, min, max) {
for (let j = max; j >= min; j--) {
if (j === max) {
currentSideNumList.push(preSideNumList.at(-1))
} else {
currentSideNumList.push(matrix[max][j])
}
matrix[max][j] = preSideNumList[max - j]
}
}
function handleLeftSide(preSideNumList, currentSideNumList, min, max) {
for (let j = max; j >= min; j--) {
if (j === max) {
currentSideNumList.push(preSideNumList.at(-1))
} else {
currentSideNumList.push(matrix[j][min])
}
matrix[j][min] = preSideNumList[max - j]
}
}
function handleTopSide(preSideNumList, min, sideLen) {
for (let j = min; j < min + sideLen; j++) {
matrix[min][j] = preSideNumList[j - min]
}
}
}
官方解题思路
代码提交后用时表现还可以,但是我这个思路并不取巧,我很好奇官方有什么新奇的旋转方式,于是查看题解发现果然有!它是用翻转替代旋转,过程如下:
- 上下水平轴翻转
- 左上右下对角线翻转
以示例1为例:
代码实现
var rotate = function (matrix) {
const n = matrix.length
// 水平翻转
for (let i = 0; i < Math.floor(n / 2); i++) {
for (let j = 0; j < n; j++) {
[matrix[i][j], matrix[n - i - 1][j]] = [matrix[n - i - 1][j], matrix[i][j]]
}
}
// 对角线翻转
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]
}
}
}
拿下!😀
转载自:https://juejin.cn/post/7203512643239854139