跳转至

4052. 行列循环移位

难度简单

题目描述

给你一个整数 n、一个大小为 n x n 的二维整数数组 grid，以及两个长度均为 n 的整数数组 rowShift 和 colShift，其中：

  • rowShift[i] 表示将 grid 的第 i 行向左 循环移位 的位数。
  • colShift[j] 表示将 grid 的第 j 列向上 循环移位 的位数。

首先按照 rowShift 对每一行进行循环移位，然后按照 colShift 对每一列进行循环移位。

返回完成所有移位操作后的网格。

将第 i 行向左 循环移位 k 位时，只移动该行。原本位于第 j 列的元素会移动到第 (j - k + n) % n 列，其余各行保持不变。

将第 j 列向上 循环移位 k 位时，只移动该列。原本位于第 i 行的元素会移动到第 (i - k + n) % n 行，其余各列保持不变。

 

示例 1：

输入： n = 2, grid = [[1,2],[3,4]], rowShift = [1,0], colShift = [0,1]

输出： [[2,4],[3,1]]

解释：

grid 的变化过程如下：

示例 2：

输入： n = 3, grid = [[1,2,3],[4,5,6],[7,8,9]], rowShift = [1,2,0], colShift = [2,2,1]

输出： [[7,8,5],[2,3,9],[6,4,1]]

解释：

grid 的变化过程如下：

 

提示：

  • 1 <= n == grid.length == grid[i].length <= 10
  • 1 <= grid[i][j] <= 100
  • rowShift.length == colShift.length == n
  • 0 <= rowShift[i], colShift[i] < n

解法

方法一：模拟

思考

\(n \le 10\)，按题意做两遍移位即可通过，不必先把映射压成一次下标计算。

必须先整行左移，再按新的列下标做上移。列循环用的是行移位之后的列，不能拿原来的 \(j\) 去套 \(\textit{colShift}\)。

因此先用中间网格记下每一行的左移结果，再写到答案网格。

题目要求先按 \(\textit{rowShift}\) 对每一行做循环左移，再按 \(\textit{colShift}\) 对每一列做循环上移。

创建中间矩阵 \(t\)。原网格中的 \(\textit{grid}[i][j]\) 向左循环 \(\textit{rowShift}[i]\) 位后，落到

\[ t[i][(j - \textit{rowShift}[i] + n) \bmod n] \]

再创建答案矩阵 \(\textit{ans}\)。\(t[i][j]\) 向上循环 \(\textit{colShift}[j]\) 位后，落到

\[ \textit{ans}[(i - \textit{colShift}[j] + n) \bmod n][j] \]

时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n^2)\)。其中 \(n\) 是网格的边长。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def cyclicShift(
        self, n: int, grid: list[list[int]], rowShift: list[int], colShift: list[int]
    ) -> list[list[int]]:
        t = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                t[i][(j - rowShift[i] + n) % n] = grid[i][j]
        ans = [[0] * n for _ in range(n)]
        for j in range(n):
            for i in range(n):
                ans[(i - colShift[j] + n) % n][j] = t[i][j]
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int[][] cyclicShift(int n, int[][] grid, int[] rowShift, int[] colShift) {
        int[][] t = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                t[i][(j - rowShift[i] + n) % n] = grid[i][j];
            }
        }
        int[][] ans = new int[n][n];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                ans[(i - colShift[j] + n) % n][j] = t[i][j];
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> cyclicShift(int n, vector<vector<int>>& grid, vector<int>& rowShift, vector<int>& colShift) {
        vector<vector<int>> t(n, vector<int>(n));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                t[i][(j - rowShift[i] + n) % n] = grid[i][j];
            }
        }
        vector<vector<int>> ans(n, vector<int>(n));
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                ans[(i - colShift[j] + n) % n][j] = t[i][j];
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func cyclicShift(n int, grid [][]int, rowShift []int, colShift []int) [][]int {
    t := make([][]int, n)
    for i := range t {
        t[i] = make([]int, n)
    }
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            t[i][(j-rowShift[i]+n)%n] = grid[i][j]
        }
    }
    ans := make([][]int, n)
    for i := range ans {
        ans[i] = make([]int, n)
    }
    for j := 0; j < n; j++ {
        for i := 0; i < n; i++ {
            ans[(i-colShift[j]+n)%n][j] = t[i][j]
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function cyclicShift(
    n: number,
    grid: number[][],
    rowShift: number[],
    colShift: number[],
): number[][] {
    const t = Array.from({ length: n }, () => Array(n).fill(0));
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            t[i][(j - rowShift[i] + n) % n] = grid[i][j];
        }
    }
    const ans = Array.from({ length: n }, () => Array(n).fill(0));
    for (let j = 0; j < n; j++) {
        for (let i = 0; i < n; i++) {
            ans[(i - colShift[j] + n) % n][j] = t[i][j];
        }
    }
    return ans;
}

评论