X

LEETCODE 1260. Shift 2D Grid 解题思路分析

题目大意:

二维网格迁移

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

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

  • 位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。
  • 位于 grid[i][m – 1] 的元素将会移动到 grid[i + 1][0]。
  • 位于 grid[n – 1][m – 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]]

提示:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1260

解题思路分析:

本题可以将二维数组变换成一维,将原数组的后K个数放至1维数组的前部,其余按顺序从第K+1位放入数组。最后再将1维数组转化为List返回即可。

这里有一点需要注意一下,k的值是有可能大于数组 总个数的,比如二维数组的大小是3*3,总共9个元素,如果k等于18,其实相当于将所有数字转了2圈后又都回到了原位,因此,精确的k值应该是: k % 数组元素总个数

实现代码:

public List<List<Integer>> shiftGrid(int[][] grid, int k) {
    // 新建一个1维数组,长度为grid的元素个数和
    int[] newGrid = new int[grid.length*grid[0].length];
    // 将k简化
    k=k%newGrid.length;
    int index=0; // grid中当前元素的index
    for(int i=0;i<grid.length;i++){
        for(int j=0;j<grid[0].length;j++){
            // 如果当前元素的index加上k大于了数组长度(是grid的后k个元素)
            if(index+k>=newGrid.length){
                // 将其放入数组前部。
                newGrid[(index+k)-newGrid.length]=grid[i][j];
            }else{
                // 否则将当前index加上k存入数组
                newGrid[index+k]=grid[i][j];
            }
            index++;
        }
    }
    // 将1维数组转为List返回。
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    for(int i=0;i<newGrid.length;i++){
        if(i%grid[0].length==0){
            list = new ArrayList<>();
            res.add(list);
        }
        list.add(newGrid[i]);
    }
    return res;
}

本题解法执行时间为4ms。

Runtime: 4 ms, faster than 99.35% of Java online submissions for Shift 2D Grid.

Memory Usage: 46.5 MB, less than 100.00% of Java online submissions for Shift 2D Grid.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1260-shift-2d-grid-解题思路分析/
Categories: leetcode
kwantong: