二维网格迁移
题目描述
给你一个 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 次迁移操作后最终得到的 二维网格。
输入输出规模
m == grid.length
n == grid[i].length
1
思路
1.简单模拟
最朴素的思路为，按照题目给出的坐标变换公式，执行k次。但根据给出的输入输出规模，发现对于极端输入，操作在10^8次数量级。显然存在更合理的公式去描述进行k次变化后，各个元素的位置。
2.规律公式
- 列的变化：列变化的规律比较简单，迁移k次，就朝右移动k次，考虑到二维网格的周期性，这里需要取膜，即new_col = (ori_col + k) % num_col
- 行的变化：行的行为稍微复杂一些。我们可以发现，当列每迁移num_col次时，行就会向下移动一格。那么我们首先计算，行向下移动的绝对距离：d_row = (ori_col + k) / num_col, 然后将这个值加上原来的行号，再进行取模就得到了k次迁移后的行号：(d_row+ori_row) % num_row
代码
Golang版本
func shiftGrid(grid [][]int, k int) [][]int {
n, m := len(grid), len(grid[0]);
ans := make([][]int, n);
for i := range ans{
ans[i] = make([]int, m);
}
//fill
for i, row := range grid{
for j, item := range row{
new_col, new_row := (j+k) % m, (i+(j+k)/m)%n;
ans[new_row][new_col] = item;
}
}
return ans;
}
Original: https://www.cnblogs.com/xy1997/p/16500366.html
Author: xingyuanyuan
Title: [LC1260]二维网格迁移
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/588094/
转载文章受原作者版权保护。转载请注明原作者出处！