地址:
力扣https://leetcode-cn.com/problems/shift-2d-grid/
题目:
给你一个 m 行 n 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。 每次「迁移」操作将会引发下述活动: 位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。 |
示例 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 |
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shift-2d-grid
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路:
观察移动后的矩阵,我们可以发现
1. 移动次数为 矩阵个数 的倍数时相当于不移动,我们直接输出原矩阵即可
2. 以及移动,一原矩阵 0 号元素作为参考,后续元素的位置是相对不变的
那么我们是否可以考虑用一个一维数组存放移动后的矩阵,最后再拷贝回新矩阵即可
只是,0 号元素应该放到一维数组的那个位置呢?
这个就想到了 (剑指 Offer 58 - II) 左旋转字符串
方法一、一维数组存放移动后的矩阵
int **myMalloc(int r, int c, int *return_r, int **return_c)
{
int **ret = (int **)malloc(sizeof(int *) * r);
*return_r = r;
*return_c =(int *)malloc(sizeof(int) * r);
for(int i=0; i<r; i++)
{
ret[i] = (int *)malloc(sizeof(int) * c);
(*return_c)[i] = c;
}
return ret;
}
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** shiftGrid(int** grid, int gridSize, int* gridColSize, int k, int* returnSize, int** returnColumnSizes){
int r = gridSize;
int c = gridColSize[0];
int i,j,g;
int movenum = k % (r*c);
if(movenum == 0) // same as grid
{
*returnSize = r;
*returnColumnSizes =(int *)malloc(sizeof(int) * r);
for(i=0; i<r; i++)
{
(*returnColumnSizes)[i] = c;
}
return grid;
}
int **ret = myMalloc(r, c, returnSize, returnColumnSizes);
// transfer grid to one-dimensional array first
int arraylen = r*c;
int *array = (int *)malloc(sizeof(int) * arraylen);
for(i=0,g=0; i<r; i++)
{
for(j=0; j<c; j++)
{
array[(g+movenum)%arraylen]=grid[i][j];
g++;
}
}
// copy one-dimensional array from new index:movenum
for(i=0,g=0; i<r; i++)
{
for(j=0; j<c; j++)
{
ret[i][j]=array[g++];
}
}
free(array);
return ret;
}