攻城獅
Not a programmer 不工程的攻城獅

Follow

Not a programmer 不工程的攻城獅

Follow
LeetCode Solution, Easy, 1260. Shift 2D Grid

LeetCode Solution, Easy, 1260. Shift 2D Grid

移動 2D 矩陣

攻城獅's photo
攻城獅
·Apr 11, 2022·
Play this article

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:

e1.png

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:

e2.png

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
  }
}

Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this