1260. 二维网格迁移

地址:

力扣1260. 二维网格迁移https://leetcode-cn.com/problems/shift-2d-grid/

题目:

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

1260. 二维网格迁移

输入:grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出:[[9,1,2],[3,4,5],[6,7,8]]


示例 2:

1260. 二维网格迁移

输入: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;
}

  查看更多刷题笔记

上一篇:grid画表格


下一篇:leetcode64.最小路径和(中等)