1260. Shift 2D Grid

題目敘述

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.length
• n == grid[i].length
• 1 <= m <= 50
• 1 <= n <= 50
• -1000 <= grid[i][j] <= 1000
• 0 <= 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

/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number[][]}
 */
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
{

    /**
     * @param Integer[][] $grid
     * @param Integer $k
     * @return Integer[][]
     */
    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
  }
}