Go语言题解LeetCode1260二维网格迁移示例详解

题目描述

1260. 二维网格迁移 - 力扣（LeetCode）

给你一个 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：

输入：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

思路分析

• 最笨的方法移动k次

• 第一次优化，对k取模，比如一个3*3的网格，移9次等于没有移

• 第二次优化，由k的值确定向左移简单还是向右移简单：正常情况是向右移，比如一个3*3的网格，要求移8次，相当于左移一次

• 第三次优化，空间换时间，需要多建立长度为k的临时数组，但这样可以把k次移动变成1次移动，除了需要移动到临时数组里的元素，其它元素的移动步长都是k。（这样一来，其实第二次优化的意义不是很大，就省了一点内存而已）

AC 代码

class Solution {
   public List<List<Integer>> shiftGrid(int[][] grid, int k) {
int []yw=new int[grid.length*grid[0].length];
int p=0;
for(int i=0;i<grid.length;i++) {
for(int j=0;j<grid[0].length;j++) {
yw[p++]=grid[i][j];
}
}
k=k％yw.length;
if(k<yw.length/2) {//右移
int []tmp=new int[k];
int pnt=yw.length-k;
for(int i=0;i<k;i++) {
tmp[i]=yw[pnt];
pnt++;
}
for(int i=yw.length-k-1;i>=0;i--) {
yw[i+k]=yw[i];
}
for(int i=0;i<k;i++) {
yw[i]=tmp[i];
}
} else {//左移
           k=yw.length-k;
int []tmp=new int[k];
for(int i=0;i<k;i++) {
tmp[i]=yw[i];
}
for(int i=k;i<yw.length;i++) {
yw[i-k]=yw[i];
}
int pnt=yw.length-k;
for(int i=0;i<k;i++) {
yw[pnt]=tmp[i];
pnt++;
}
}
List<List<Integer>> res=new ArrayList<>();
List<Integer> tp=new ArrayList<>();
p=0;
for(int i=0;i<grid.length;i++) {
for(int j=0;j<grid[0].length;j++) {
tp.add(yw[p++]);
}
res.add(tp);
tp=new ArrayList<>();
}
return res;
}
}

来源：https://juejin.cn/post/7182933754971684923