Skip to content

Latest commit

 

History

History
167 lines (112 loc) · 4.18 KB

1260.shift-2d-grid.md

File metadata and controls

167 lines (112 loc) · 4.18 KB
Raw

题目地址（1260. 二维网格迁移）

https://leetcode-cn.com/problems/shift-2d-grid/description/

题目描述


给你一个 n 行 m 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。

每次「迁移」操作将会引发下述活动：

位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。
位于 grid[i][m - 1] 的元素将会移动到 grid[i + 1][0]。
位于 grid[n - 1][m - 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]]
 

提示：

1 <= grid.length <= 50
1 <= grid[i].length <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100

前置知识

公司

  • 字节

模拟法

思路

我们直接翻译题目，没有任何 hack 的做法。

代码

from copy import deepcopy

class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        n = len(grid)
        m = len(grid[0])
        for _ in range(k):
            old = deepcopy(grid)
            for i in range(n):
                for j in range(m):
                    if j == m - 1:
                            grid[(i + 1) % n][0] = old[i][j]
                    elif i == n - 1 and j == m - 1:
                        grid[0][0] = old[i][j]
                    else:
                        grid[i][j + 1] = old[i][j]
        return grid

由于是 easy，上述做法勉强可以过，我们考虑优化。

数学分析

思路

我们仔细观察矩阵会发现，其实这样的矩阵迁移是有规律的。 如图： image

因此这个问题就转化为我们一直的一维矩阵转移问题，LeetCode 也有原题189. 旋转数组，同时我也写了一篇文章文科生都能看懂的循环移位算法专门讨论这个，最终我们使用的是三次旋转法，相关数学证明也有写，很详细，这里不再赘述。

LeetCode 真的是喜欢换汤不换药呀 😂

代码

Python 代码：

#
# @lc app=leetcode.cn id=1260 lang=python3
#
# [1260] 二维网格迁移
#

# @lc code=start


class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        n = len(grid)
        m = len(grid[0])
        # 二维到一维
        arr = [grid[i][j] for i in range(n) for j in range(m)]
        # 取模，缩小k的范围，避免无意义的运算
        k %= m * n
        res = []
        # 首尾交换法

        def reverse(l, r):
            while l < r:
                t = arr[l]
                arr[l] = arr[r]
                arr[r] = t
                l += 1
                r -= 1
        # 三次旋转
        reverse(0, m * n - k - 1)
        reverse(m * n - k, m * n - 1)
        reverse(0, m * n - 1)
        # 一维到二维
        row = []
        for i in range(m * n):
            if i > 0 and i % m == 0:
                res.append(row)
                row = []
            row.append(arr[i])
        res.append(row)

        return res

# @lc code=end

复杂度分析

  • 时间复杂度：$$O(N)$$
  • 空间复杂度：$$O(1)$$

相关题目

参考

更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经37K star啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。