1260. Two dimensional grid migration: simple construction simulation problem

Title Description

This is a LeetCode Upper 1260. Two dimensional grid migration , The difficulty is Simple .

Tag : 「 simulation 」、「 structure 」

To give you one m That's ok n  Two dimensional grid of columns  grid  And an integer  k. You need to  grid  transfer  k  Time .

Every time 「 transfer 」 The operation will trigger the following activities ：

• be located grid[i][j]  The element will be moved to   grid[i][j + 1]
• be located   grid[i][n - 1] The element will be moved to   grid[i + 1][0]
• be located grid[m - 1][n - 1]  The element will be moved to   grid[0][0]
• Please return   k The final result after the migration operation Two dimensional meshes

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

Tips ：

simulation

For convenience , We make grid by g, Make n and m Respectively g The number of rows and columns .

Because the migration process has obvious regularity , So we can directly regard as The subscript of the final column of each column tcol = (i + k) % m（ among i Subscript the original column ）, meanwhile regard as The row subscript of the first row element of the current column in the new column trow = ((i + k) / m) % n, Then it is a simple traversal assignment operation .

Java Code ：

class Solution {
    public List<List<Integer>> shiftGrid(int[][] g, int k) {
        int n = g.length, m = g[0].length;
        int[][] mat = new int[n][m];
        for (int i = 0; i < m; i++) {
            int tcol = (i + k) % m, trow = ((i + k) / m) % n, idx = 0;
            while (idx != n) {
                mat[trow++][tcol] = g[idx++][i];
                if (trow == n) trow = 0;
            }
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<Integer> alist = new ArrayList<>();
            for (int j = 0; j < m; j++) alist.add(mat[i][j]);
            ans.add(alist);
        }
        return ans;
    }
}

TypeScript Code ：

function shiftGrid(g: number[][], k: number): number[][] {
    const n = g.length, m = g[0].length
    const ans: number[][] = new Array<Array<number>>()
    for (let i = 0; i < n; i++) ans[i] = new Array<number>(m).fill(0)
    for (let i = 0; i < m; i++) {
        let tcol = (i + k) % m, trow = Math.floor(((i + k) / m)) % n, idx = 0
        while (idx != n) {
            ans[trow++][tcol] = g[idx++][i]
            if (trow == n) trow = 0
        }
    }
    return ans
};

• Time complexity ：
• Spatial complexity ：

Last

This is us. 「 Brush through LeetCode」 The first of the series No.1260 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .