README_EN.md

1914. Cyclically Rotating a Grid

中文文档

Description

You are given an m x n integer matrix grid​​​, where m and n are both even integers, and an integer k.

The matrix is composed of several layers, which is shown in the below image, where each color is its own layer:

A cyclic rotation of the matrix is done by cyclically rotating each layer in the matrix. To cyclically rotate a layer once, each element in the layer will take the place of the adjacent element in the counter-clockwise direction. An example rotation is shown below:

Return the matrix after applying k cyclic rotations to it.

 

Example 1:

Input: grid = [[40,10],[30,20]], k = 1
Output: [[10,20],[40,30]]
Explanation: The figures above represent the grid at every state.

Example 2:

Input: grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
Output: [[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
Explanation: The figures above represent the grid at every state.

 

Constraints:

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 50
• Both m and n are even integers.
• 1 <= grid[i][j] <= 5000
• 1 <= k <= 109

Solutions

Python3

class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        def rotate(grid, s1, e1, s2, e2, k):
            t = []
            for j in range(e2, e1, -1):
                t.append(grid[s1][j])
            for i in range(s1, s2):
                t.append(grid[i][e1])
            for j in range(e1, e2):
                t.append(grid[s2][j])
            for i in range(s2, s1, -1):
                t.append(grid[i][e2])
            k %= len(t)
            t = t[-k:] +t[:-k]
            k = 0
            for j in range(e2, e1, -1):
                grid[s1][j] = t[k]
                k += 1
            for i in range(s1, s2):
                grid[i][e1] = t[k]
                k += 1
            for j in range(e1, e2):
                grid[s2][j] = t[k]
                k += 1
            for i in range(s2, s1, -1):
                grid[i][e2] = t[k]
                k += 1
        
        m, n = len(grid), len(grid[0])
        s1 = e1 = 0
        s2, e2 = m - 1, n - 1
        while s1 <= s2 and e1 <= e2:
            rotate(grid, s1, e1, s2, e2, k)
            s1 += 1
            e1 += 1
            s2 -= 1
            e2 -= 1
        return grid

Java

class Solution {
    public int[][] rotateGrid(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        int s1 = 0, e1 = 0;
        int s2 = m - 1, e2 = n - 1;
        while (s1 <= s2 && e1 <= e2) {
            rotate(grid, s1++, e1++, s2--, e2--, k);
        }
        return grid;
    }

    private void rotate(int[][] grid, int s1, int e1, int s2, int e2, int k) {
        List<Integer> t = new ArrayList<>();
        for (int j = e2; j > e1; --j) {
            t.add(grid[s1][j]);
        }
        for (int i = s1; i < s2; ++i) {
            t.add(grid[i][e1]);
        }
        for (int j = e1; j < e2; ++j) {
            t.add(grid[s2][j]);
        }
        for (int i = s2; i > s1; --i) {
            t.add(grid[i][e2]);
        }
        int n = t.size();
        k %= n;
        if (k == 0) {
            return;
        }
        k = n - k;
        for (int j = e2; j > e1; --j) {
            grid[s1][j] = t.get(k);
            k = (k + 1) % n;
        }
        for (int i = s1; i < s2; ++i) {
            grid[i][e1] = t.get(k);
            k = (k + 1) % n;
        }
        for (int j = e1; j < e2; ++j) {
            grid[s2][j] = t.get(k);
            k = (k + 1) % n;
        }
        for (int i = s2; i > s1; --i) {
            grid[i][e2] = t.get(k);
            k = (k + 1) % n;
        }
    }
}

...