lintcode 3605 · 二维网格偏移 【数组相关，模拟即可】

题目

https://www.lintcode.com/problem/3605

给定一个 m 行 n 列的二维网格 grid 和一个整数 k，需要将 grid 偏移 k 次，偏移规则如下：

位于 grid[i][j] 的元素移动到 grid[i][j + 1]
位于 grid[i][n - 1] 的元素移动到 grid[i + 1][0]
位于 grid[m - 1][n - 1] 的元素移动到 grid[0][0]
偏移操作为一次性完成，以上三个规则不会造成数据覆盖，返回偏移 k 次之后的二维网格。


样例
样例1：
3605_1.png

输入：grid = [[1,2,3],[4,5,6],[7,8,9]]  k = 1
输出：[[9,1,2],[3,4,5],[6,7,8]]
样例2：
3605_2.png

输入：grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]  k = 2
输出：[[11,12,1,2],[3,4,5,6],[7,8,9,10]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

思路

其实就是数组中的每个数依次往后移动k个位置，
最后的k个数填充到数组开头，倒数第k个放数组第一个，
倒数第k-1个放第二个位置，以此类推
1
2
3

参考答案

public class Solution {
    /**
     * @param grid: m*n matrix
     * @param k: Number of shifts
     * @return: m*n matrix after shift
     */
    public int[][] shiftGrid(int[][] grid, int k) {
         //根据题意，每一次移动，
        // 其实就是把每一行的最后一个数移动到下一行的第一个数的位置
        //最后一个数移动到开数组头位置
        //那么：移动k次，就是每个数依次往后移动k个位置，结尾的数，移动到开头
        int n= grid.length,m= grid[0].length;
        int len = n*m;
        int[][] ans = new int[n][m];


        for (int i = 0; i <len-k ; i++) {  //先填充k到n*m之间的单元格
            int x = i/m;
            int y = i -x*m;


            int index = i+k;
            int x1 = index/m;
            int y1 = index-x1*m;
            ans[x1][y1] = grid[x][y];
        }

        int end = k-1;
        for (int i =len-1 ; i >len-k-1 ; i--) { //最后的k个数要移动到开头
            int x = i/m;
            int y = i -x*m;

            int x1 = end/m;
            int y1 = end-x1*m;
            end--;
            ans[x1][y1] = grid[x][y];
        }

        return ans;
    }
}
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
40
41