二維網格遷移
題目描述
給你一個 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 次遷移操作后最終得到的 二維網格，
LeetCode地址
輸入輸出規模
m == grid.length
n == grid[i].length
1 <= m <= 50
1 <= n <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100
思路
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/499870.html
標籤：其他
上一篇：二分查找