{"id":5867,"date":"2019-11-26T12:55:11","date_gmt":"2019-11-26T20:55:11","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5867"},"modified":"2019-11-26T15:25:18","modified_gmt":"2019-11-26T23:25:18","slug":"leetcode-1260-shift-2d-grid","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-1260-shift-2d-grid\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1260. Shift 2D Grid"},"content":{"rendered":"\n<p>Given a 2D&nbsp;<code>grid<\/code>&nbsp;of size&nbsp;<code>n<\/code>&nbsp;*&nbsp;<code>m<\/code>&nbsp;and an integer&nbsp;<code>k<\/code>. You need to shift the&nbsp;<code>grid<\/code>&nbsp;<code>k<\/code>&nbsp;times.<\/p>\n\n\n\n<p>In one shift operation:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Element at&nbsp;<code>grid[i][j]<\/code>&nbsp;becomes at&nbsp;<code>grid[i][j + 1]<\/code>.<\/li><li>Element at&nbsp;<code>grid[i][m - 1]<\/code>&nbsp;becomes at&nbsp;<code>grid[i + 1][0]<\/code>.<\/li><li>Element at&nbsp;<code>grid[n - 1][m - 1]<\/code>&nbsp;becomes at&nbsp;<code>grid[0][0]<\/code>.<\/li><\/ul>\n\n\n\n<p>Return the&nbsp;<em>2D grid<\/em>&nbsp;after applying shift operation&nbsp;<code>k<\/code>&nbsp;times.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/11\/05\/e1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> <code>grid<\/code> = [[1,2,3],[4,5,6],[7,8,9]], k = 1\n<strong>Output:<\/strong> [[9,1,2],[3,4,5],[6,7,8]]\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/11\/05\/e2.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> <code>grid<\/code> = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4\n<strong>Output:<\/strong> [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> <code>grid<\/code> = [[1,2,3],[4,5,6],[7,8,9]], k = 9\n<strong>Output:<\/strong> [[1,2,3],[4,5,6],[7,8,9]]\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= grid.length &lt;= 50<\/code><\/li><li><code>1 &lt;= grid[i].length &lt;= 50<\/code><\/li><li><code>-1000 &lt;= grid[i][j] &lt;= 1000<\/code><\/li><li><code>0 &lt;= k &lt;= 100<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Simulation<\/strong><\/h2>\n\n\n\n<p>Simulate the shift process for k times.<\/p>\n\n\n\n<p>Time complexity: O(k*n*m)<br>Space complexity: O(1) in-place<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 80ms, 13.5 MB\nclass Solution {\npublic:\n  vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {\n    const int n = grid.size();\n    const int m = grid[0].size();\n    while (k--) {\n      int last = grid[n - 1][m - 1];\n      for (int i = n - 1; i >= 0; --i)\n        for (int j = m - 1; j >= 0; --j) {          \n          if (i == 0 && j == 0) \n            grid[i][j] = last;\n          else if (j == 0)\n            grid[i][j] = grid[i - 1][m - 1];\n          else\n            grid[i][j] = grid[i][j - 1];\n        }\n      }\n    return grid;\n    }    \n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Rotate<\/strong><\/h2>\n\n\n\n<p>Shift k times is equivalent to flatten the matrix and rotate by -k or (m*n &#8211; k % (m * n)).<\/p>\n\n\n\n<p>Time complexity: O(m*n)<br>Space complexity: O(m*n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 68 ms, 14.4 MB\nclass Solution {\npublic:\n  vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {  \n    const int n = grid.size();\n    const int m = grid[0].size();\n    k = m * n - k % (m*n);\n    vector<int> g;\n    for (int i = 0; i < n; ++i) \n      g.insert(end(g), begin(grid[i]), end(grid[i]));\n    rotate(begin(g), begin(g) + k, end(g));\n    auto it = begin(g);\n    for (int i = 0; i < n; ++i)\n      for (int j = 0; j < m; ++j)\n        grid[i][j] = *it++;\n    return grid;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p>O(1) space in-place rotation<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\uff0c 68 ms, 13.6 MB\nclass MatrixIterator { \n public:\n  MatrixIterator(vector<vector<int>>& data, int index = 0) :\n    data_(data),\n    index_(index) {}\n  \n  MatrixIterator& operator++() {\n    ++index_;\n    return *this;\n  }  \n  \n  MatrixIterator& operator--() {\n    --index_;\n    return *this;\n  }\n  \n  MatrixIterator operator +(int dis) const {\n    return MatrixIterator(data_, index_ + dis);\n  }\n  \n  MatrixIterator operator -(int dis) const {\n    return MatrixIterator(data_, index_ - dis);\n  }\n  \n  bool operator==(const MatrixIterator& o) const {\n    return data_ == o.data_ && index_ == o.index_;\n  }    \n  \n  bool operator!=(const MatrixIterator& o) const {\n    return data_ != o.data_ || index_ != o.index_;\n  }\n  \n  ptrdiff_t operator-(const MatrixIterator& o) const {\n    return index_ - o.index_;\n  }\n  \n  MatrixIterator& operator=(const MatrixIterator& o) {\n    data_ = o.data_;\n    index_ = o.index_;\n    return *this;\n  }\n  \n  int& operator*() {\n    if (index_ <= 0) {\n      return data_[0][0];\n    } else if (index_ >= m() * n()) {\n      return data_.back().back();\n    } else {\n      return data_[index_ \/ m()][index_ % m()];\n    }\n  }\n  \n private:\n  int n() const { return data_.size(); }\n  int m() const { return n() == 0 ? 0 : data_[0].size(); }  \n  vector<vector<int>>& data_;\n  int index_;\n};\n\nnamespace std {\n  template<>\n  struct iterator_traits<MatrixIterator> {\n    typedef ptrdiff_t                  difference_type;\n    typedef int                        value_type;\n    typedef int*                       pointer;\n    typedef int&                       reference;\n    typedef random_access_iterator_tag iterator_category;\n  };\n}\n\nclass Solution {\npublic:\n  vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {  \n    const int n = grid.size();\n    const int m = grid[0].size();\n    k = m * n - k % (m*n);\n    MatrixIterator it(grid);\n    rotate(it, it + k, it + m * n);\n    return grid;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a 2D&nbsp;grid&nbsp;of size&nbsp;n&nbsp;*&nbsp;m&nbsp;and an integer&nbsp;k. You need to shift the&nbsp;grid&nbsp;k&nbsp;times. In one shift operation: Element at&nbsp;grid[i][j]&nbsp;becomes at&nbsp;grid[i][j + 1]. Element at&nbsp;grid[i][m &#8211; 1]&nbsp;becomes at&nbsp;grid[i&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[179],"class_list":["post-5867","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5867","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5867"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5867\/revisions"}],"predecessor-version":[{"id":5871,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5867\/revisions\/5871"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5867"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5867"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5867"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}