# 1260. 二維網格遷移 ## 題目地址（1260. 二維網格遷移） <https://leetcode-cn.com/problems/shift-2d-grid/description/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個 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 ``` ``` ## 前置知識 - [數組](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) - 數學 ## 暴力法 ## 公司 - 字節 ### 思路 我們直接翻譯題目，沒有任何 hack 的做法。 ### 代碼 ``` <pre class="calibre18">``` <span class="hljs-keyword">from</span> copy <span class="hljs-keyword">import</span> deepcopy <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">shiftGrid</span><span class="hljs-params">(self, grid: List[List[int]], k: int)</span> -> List[List[int]]:</span> n = len(grid) m = len(grid[<span class="hljs-params">0</span>]) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(k): old = deepcopy(grid) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(m): <span class="hljs-keyword">if</span> j == m - <span class="hljs-params">1</span>: grid[(i + <span class="hljs-params">1</span>) % n][<span class="hljs-params">0</span>] = old[i][j] <span class="hljs-keyword">elif</span> i == n - <span class="hljs-params">1</span> <span class="hljs-keyword">and</span> j == m - <span class="hljs-params">1</span>: grid[<span class="hljs-params">0</span>][<span class="hljs-params">0</span>] = old[i][j] <span class="hljs-keyword">else</span>: grid[i][j + <span class="hljs-params">1</span>] = old[i][j] <span class="hljs-keyword">return</span> grid ``` ``` 由于是 easy，上述做法勉強可以過，我們考慮優化。 ## 數學分析 ### 思路 我們仔細觀察矩陣會發現，其實這樣的矩陣遷移是有規律的。 如圖：  因此這個問題就轉化為我們一直的一維矩陣轉移問題，LeetCode 也有原題[189. 旋轉數組](https://leetcode-cn.com/problems/rotate-array/)，同時我也寫了一篇文章[文科生都能看懂的循環移位算法](https://lucifer.ren/blog/2019/12/11/rotate-list/)專門討論這個，最終我們使用的是三次旋轉法，相關數學證明也有寫，很詳細，這里不再贅述。 LeetCode 真的是喜歡換湯不換藥呀 ?? ### 代碼 Python 代碼： ``` <pre class="calibre18">``` <span class="hljs-title">#</span> <span class="hljs-title"># @lc app=leetcode.cn id=1260 lang=python3</span> <span class="hljs-title">#</span> <span class="hljs-title"># [1260] 二維網格遷移</span> <span class="hljs-title">#</span> <span class="hljs-title"># @lc code=start</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">shiftGrid</span><span class="hljs-params">(self, grid: List[List[int]], k: int)</span> -> List[List[int]]:</span> n = len(grid) m = len(grid[<span class="hljs-params">0</span>]) <span class="hljs-title"># 二維到一維</span> arr = [grid[i][j] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n) <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(m)] <span class="hljs-title"># 取模，縮小k的范圍，避免無意義的運算</span> k %= m * n res = [] <span class="hljs-title"># 首尾交換法</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">reverse</span><span class="hljs-params">(l, r)</span>:</span> <span class="hljs-keyword">while</span> l < r: t = arr[l] arr[l] = arr[r] arr[r] = t l += <span class="hljs-params">1</span> r -= <span class="hljs-params">1</span> <span class="hljs-title"># 三次旋轉</span> reverse(<span class="hljs-params">0</span>, m * n - k - <span class="hljs-params">1</span>) reverse(m * n - k, m * n - <span class="hljs-params">1</span>) reverse(<span class="hljs-params">0</span>, m * n - <span class="hljs-params">1</span>) <span class="hljs-title"># 一維到二維</span> row = [] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(m * n): <span class="hljs-keyword">if</span> i > <span class="hljs-params">0</span> <span class="hljs-keyword">and</span> i % m == <span class="hljs-params">0</span>: res.append(row) row = [] row.append(arr[i]) res.append(row) <span class="hljs-keyword">return</span> res <span class="hljs-title"># @lc code=end</span> ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) ## 相關題目 - [189. 旋轉數組](https://leetcode-cn.com/problems/rotate-array/) ## 參考 - [文科生都能看懂的循環移位算法](https://lucifer.ren/blog/2019/12/11/rotate-list/) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經37K star啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。