假设我们有一个大小为mx n的2D网格。我们还有另一个变量k。我们必须将网格移动k次。移位操作如下
网格G [i,j]上的元素移到G [i,j + 1]
网格G [i,n – 1]的元素移到G [i + 1,0]
网格G [m-1,n-1]上的元素移到G [0,0]
所以如果网格像-
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
输出将是-
9 | 1 | 2 |
3 | 4 | 5 |
6 | 7 | 8 |
为了解决这个问题,我们将遵循以下步骤-
移位操作将矩阵作为输入
n =行数,m:=列数,x:=右下元素
对于i:= n – 1,降低到0
如果j = 0且i> 0,则G [i,j]:= G [i – 1,m-1]
否则,如果j> 0,则G [i,j]:= G [i,j – 1]
对于j:= m – 1降至0
G [0,0]:= x
通过以下规则调用shift操作-
当k不为0时
移格G
将k减1
返回网格G
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; void print_vector(vector<vector<int> > v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << "["; for(int j = 0; j <v[i].size(); j++){ cout << v[i][j] <<", "; } cout << "],"; } cout << "]"<<endl; } class Solution { public: void shift(vector<vector<int>>& grid){ int n = grid.size(); int m = grid[0].size(); int x = grid[n-1][m-1]; for(int i = n-1; i>=0; i--){ for(int j = m-1;j>=0;j--){ if(j == 0 && i>0){ grid[i][j] = grid[i-1][m-1]; } else if(j>0){ grid[i][j] = grid[i][j-1]; } } } grid[0][0] = x; } vector<vector<int>> shiftGrid(vector<vector<int>>& g, int k) { while(k--){ shift(g); } return g; } }; main(){ Solution ob; vector<vector<int>> mat = {{1,2,3},{4,5,6},{7,8,9}}; print_vector(ob.shiftGrid(mat, 1)); }
{{1,2,3},{4,5,6},{7,8,9}} 1
输出结果
[[9, 1, 2, ],[3, 4, 5, ],[6, 7, 8, ],]