題目敘述
Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.
In one shift operation:
- Element at
grid[i][j] moves to grid[i][j + 1].
- Element at
grid[i][n - 1] moves to grid[i + 1][0].
- Element at
grid[m - 1][n - 1] moves to grid[0][0].
Return the 2D grid after applying shift operation k times.
Example 1:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]
Example 2:
Input: grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output: [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]
Example 3:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]
Constraints:
m == grid.lengthn == grid[i].length1 <= m <= 501 <= n <= 50-1000 <= grid[i][j] <= 10000 <= k <= 100
Hint 1:
Simulate step by step. move grid[i][j] to grid[i][j+1]. handle last column of the grid.
Hint 2:
Put the matrix row by row to a vector. take k % vector.length and move last k of the vector to the beginning. put the vector to the matrix back the same way.
題目翻譯
這題會給一個 m x n 的二維矩陣，和一個整數 k。需要將此矩陣的內容移動 k 的位置。如範例的圖示。
解法解析
這題有幾種解法，但最主要的重點就在於怎麼去計算索引。
第一種解法概念，類似於 189. Rotate Array，將二維矩陣視為一維的陣列。挪移位置後再重新拆回矩陣。Kotlin 的解法就是類似這個方式處理。
第二種解法概念，就是直接找出索引的計算規則，以下的程式範例就是使用此種方式
解法範例
Go
func shiftGrid(grid [][]int, k int) [][]int {
numRows := len(grid)
numCols := len(grid[0])
var newGrid [][]int
for row := 0; row < numRows; row++ {
var newRow []int
for col := 0; col < numCols; col++ {
idx := row*numCols + col - k
for idx < 0 {
idx += numCols * numRows
}
newRow = append(newRow, grid[idx/numCols][idx%numCols])
}
newGrid = append(newGrid, newRow)
}
return newGrid
}
JavaScript
var shiftGrid = function (grid, k) {
const numRows = grid.length,
numCols = grid[0].length;
const newGrid = [];
for (let i = 0; i < numRows; i++) {
newGrid[i] = new Array(numCols).fill(0);
}
for (let row = 0; row < numRows; row++) {
for (let col = 0; col < numCols; col++) {
const newCol = (col + k) % numCols;
const newRow = (row + Math.floor((col + k) / numCols)) % numRows;
newGrid[newRow][newCol] = grid[row][col];
}
}
return newGrid;
};
Kotlin
class Solution {
fun shiftGrid(grid: Array<IntArray>, k: Int): List<List<Int>> {
val newGrid = mutableListOf<MutableList<Int>>()
val numRows = grid.size
val numCols = grid[0].size
val total = numRows * numCols
val sub = k % total
for (b in 0..numRows - 1) newGrid.add(mutableListOf<Int>())
for (a in 0..total - 1) {
val idx = (a - sub + total) % total
newGrid.get(a / numCols).add(grid[idx / numCols][idx % numCols])
}
return newGrid
}
}
PHP
class Solution
{
function shiftGrid($grid, $k)
{
$numRows = count($grid);
$numCols = count($grid[0]);
$newGrid = array_fill(0, $numRows, array_fill(0, $numCols, 0));
for ($row = 0; $row < $numRows; $row++) {
for ($col = 0; $col < $numCols; $col++) {
$newCol = ($col + $k) % $numCols;
$newRow = ($row + floor(($col + $k) / $numCols)) % $numRows;
$newGrid[$newRow][$newCol] = $grid[$row][$col];
}
}
return $newGrid;
}
}
Python
class Solution:
def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
num_rows, num_cols = len(grid), len(grid[0])
new_grid = [[0] * num_cols for _ in range(num_rows)]
for row in range(num_rows):
for col in range(num_cols):
new_col = (col + k) % num_cols
new_row = (row + (col + k) // num_cols) % num_rows
new_grid[new_row][new_col] = grid[row][col]
return new_grid
Rust
Swift
class Solution {
func shiftGrid(_ grid: [[Int]], _ k: Int) -> [[Int]] {
let numRows = grid.count
let numCols = grid[0].count
var newGrid = [[Int]](repeating: [Int](repeating: 0, count: numCols), count: numRows)
for row in 0..<numRows {
for col in 0..<numCols {
let newCol = (col + k) % numCols
let newRow = (row + ((col + k) / numCols)) % numRows
newGrid[newRow][newCol] = grid[row][col]
}
}
return newGrid
}
}
