Cyclically Rotating a Grid
You are given an m x n integer matrix grid, where m and n are both even integers, and an integer k.
The matrix is composed of several layers, which is shown in the below image, where each color is its own layer:
A cyclic rotation of the matrix is done by cyclically rotating each layer in the matrix. To cyclically rotate a layer once, each element in the layer will take the place of the adjacent element in the counter-clockwise direction. An example rotation is shown below:
Return the matrix after applying k cyclic rotations to it.
Example 1:
Input: grid = [[40,10],[30,20]], k = 1
Output: [[10,20],[40,30]]
Explanation: The figures above represent the grid at every state.
Example 2:
Input: grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
Output: [[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
Explanation: The figures above represent the grid at every state.
Constraints:
- m == grid.length
- n == grid[i].length
- 2 <= m, n <= 50
- Both m and n are even integers.
- 1 <= grid[i][j] <= 5000
- 1 <= k <= \(10^9\)
Approach 1
class Solution {
fun rotateGrid(grid: Array<IntArray>, k: Int): Array<IntArray> {
val row = grid.size
val col = grid.first().size
val layer = min(row, col).shr(1)
for (i in 0..<layer) {
val list = mutableListOf<Int>()
repeat(col - 2 * i - 1) { list += grid[i][i + it] }
repeat(row - 2 * i - 1) { list += grid[i + it][col - 1 - i] }
repeat(col - 2 * i - 1) { list += grid[row - 1 - i][col - 1 - i - it] }
repeat(row - 2 * i - 1) { list += grid[row - 1 - i - it][i] }
val size = list.size
var index = k % size
repeat(col - 2 * i - 1) { grid[i][i + it] = list[(index++) % size] }
repeat(row - 2 * i - 1) { grid[i + it][col - 1 - i] = list[(index++) % size] }
repeat(col - 2 * i - 1) { grid[row - 1 - i][col - 1 - i - it] = list[(index++) % size] }
repeat(row - 2 * i - 1) { grid[row - 1 - i - it][i] = list[(index++) % size] }
}
return grid
}
}
Approach 2
class Solution {
fun rotateGrid(grid: Array<IntArray>, k: Int): Array<IntArray> {
val row = grid.size
val col = grid.first().size
val cycle = min(row, col).shr(1)
for (i in 0..<cycle) {
val list = mutableListOf<Int>()
traversalLayer(row, col, i) { r, c -> list += grid[r][c] }
val size = list.size
var index = k % size
traversalLayer(row, col, i) { r, c -> grid[r][c] = list[(index++) % size] }
}
return grid
}
private fun traversalLayer(
row: Int,
col: Int,
layer: Int,
onEach: (r: Int, c: Int) -> Unit = { _, _ -> }
) {
val forwardH = col - 2 * layer - 1
val forwardV = row - 2 * layer - 1
val forwards = IntArray(4) { if (it % 2 == 0) forwardH else forwardV }
var x = layer
var y = layer
var dx = 0
var dy = 1
var turnRight = 0
repeat(2 * (forwardH + forwardV)) {
onEach(x, y)
x += dx
y += dy
if (--forwards[turnRight] == 0) {
turnRight++
// 等价于 dx = dy.also { dy = -dx }
dy = dx + dy
dx = dy - dx
dy = dx - dy
}
}
}
}
如果是逆时针遍历：
private fun traversalLayer(
row: Int,
col: Int,
layer: Int,
onEach: (r: Int, c: Int) -> Unit = { _, _ -> }
) {
val forwardH = col - 2 * layer - 1
val forwardV = row - 2 * layer - 1
val forwards = IntArray(4) { if (it % 2 == 0) forwardH else forwardV }
var x = layer
var y = layer
var dx = 1
var dy = 0
var turnLeft = 0
repeat(2 * (forwardH + forwardV)) {
onEach(x, y)
x += dx
y += dy
if (--forwards[turnLeft] == 0) {
turnLeft++
// 等价于 dx = -dy.also { dy = dx }
dx = dx + dy
dy = dx - dy
dx = dy - dx
}
}
}