LeetCode.1260. 二维网格迁移____原地暴力 / 降维+循环数组直接定位

1260. 二维网格迁移

给你一个 m 行 n 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。

每次「迁移」操作将会引发下述活动：

1. 位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。
2. 位于 grid[i][n - 1] 的元素将会移动到 grid[i + 1][0]。
3. 位于 grid[m - 1][n - 1] 的元素将会移动到 grid[0][0]。

请你返回 k 次迁移操作后最终得到的 二维网格。

示例 1：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[9,1,2],[3,4,5],[6,7,8]]

示例 2：

输入：grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
输出：[[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]

示例 3：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
输出：[[1,2,3],[4,5,6],[7,8,9]]

提示：

m == grid.length
n == grid[i].length
1 <= m <= 50
1 <= n <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100

Solution1(原地暴力):

• 我们可以直接原地暴力模拟迁移即可；

Code1:

/* 原地暴力 */
class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        List<List<Integer>> res = new ArrayList<>();
        if(k == 0){
            for(int i=0;i<m;i++){
                List<Integer> list = new ArrayList<>();
                for(int j=0;j<n;j++){
                    list.add(grid[i][j]);
                }
                res.add(list);
            }
            return res;
        }
        int count = 0;
        while(count != k){
            int temp = grid[m - 1][n - 1];
            for(int i=0;i<m;i++){
                List<Integer> list = null;
                if(count == k - 1)
                    list = new ArrayList<>();
                for(int j=0;j<n;j++){
                    int t_temp = temp;
                    temp = grid[i][j];
                    grid[i][j] = t_temp;
                    if(count == k - 1)
                        list.add(t_temp);
                }
                if(count == k - 1)
                    res.add(list);
            }
            count++;
        }
        
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

Solution2(降维+循环数组直接定位):

• 对于矩阵转移类似的题目，我们要先多多观察，我们发现这里其实很像一个一维循环数组移动元素的问题，即尾部再往后面走就跑到了头部，且能降维就降维，因此我们可以把此二维转一维；
• 接着我们发现，我们没必要枚举k次迁移操作，我们发现迁移k次其实对于一维循环数组来说就是每个元素向后面移动k次即可，因此我们可以直接根据数学关系定位每个元素的位置；

Code2:

/* 二维转一维 + 循环数组直接定位 */
class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        List<List<Integer>> res = new ArrayList<>();
        int len = m * n;
        int[] aux = new int[len];
        int index = 0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                aux[index++] = grid[i][j]; 
            }
        }

        int[] mock = new int[len];
        for(int i=0;i<len;i++){
            mock[(i + k) % len] = aux[i];
        }

        List<Integer> list = null;
        for(int i=0;i<len;i++){
            if(i % n == 0)
                list = new ArrayList<>();
            list.add(mock[i]);
            if((i + 1) % n == 0)
                res.add(list);
        }

        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32