Skip to content

Latest commit

 

History

History
153 lines (119 loc) · 4.66 KB

README.md

File metadata and controls

153 lines (119 loc) · 4.66 KB
Raw

1861. 旋转盒子

English Version

题目描述

给你一个 m x n 的字符矩阵 box ，它表示一个箱子的侧视图。箱子的每一个格子可能为：

  • '#' 表示石头
  • '*' 表示固定的障碍物
  • '.' 表示空位置

这个箱子被 顺时针旋转 90 度 ，由于重力原因，部分石头的位置会发生改变。每个石头会垂直掉落，直到它遇到障碍物，另一个石头或者箱子的底部。重力 不会 影响障碍物的位置，同时箱子旋转不会产生惯性 ，也就是说石头的水平位置不会发生改变。

题目保证初始时 box 中的石头要么在一个障碍物上，要么在另一个石头上，要么在箱子的底部。

请你返回一个 n x m的矩阵，表示按照上述旋转后，箱子内的结果。

 

示例 1：

输入：box = [["#",".","#"]]
输出：[["."],
      ["#"],
      ["#"]]

示例 2：

输入：box = [["#",".","*","."],
            ["#","#","*","."]]
输出：[["#","."],
      ["#","#"],
      ["*","*"],
      [".","."]]

示例 3：

输入：box = [["#","#","*",".","*","."],
            ["#","#","#","*",".","."],
            ["#","#","#",".","#","."]]
输出：[[".","#","#"],
      [".","#","#"],
      ["#","#","*"],
      ["#","*","."],
      ["#",".","*"],
      ["#",".","."]]

 

提示：

  • m == box.length
  • n == box[i].length
  • 1 <= m, n <= 500
  • box[i][j] 只可能是 '#' ，'*' 或者 '.' 。

解法

先旋转，再挪动箱子。

Python3

class Solution:
    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
        m, n = len(box), len(box[0])
        res = [[None] * m for _ in range(n)]
        for i in range(m):
            for j in range(n):
                res[j][m - i - 1] = box[i][j]
        for j in range(m):
            q = collections.deque()
            for i in range(n - 1, -1, -1):
                if res[i][j] == '*':
                    q.clear()
                    continue
                if res[i][j] == '.':
                    q.append(i)
                else:
                    if not q:
                        continue
                    res[q.popleft()][j] = '#'
                    res[i][j] = '.'
                    q.append(i)
        return res

Java

class Solution {
    public char[][] rotateTheBox(char[][] box) {
        int m = box.length, n = box[0].length;
        char[][] res = new char[n][m];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                res[j][m - i - 1] = box[i][j];
            }
        }
        for (int j = 0; j < m; ++j) {
            Deque<Integer> q = new ArrayDeque<>();
            for (int i = n - 1; i >= 0; --i) {
                if (res[i][j] == '*') {
                    q.clear();
                    continue;
                }
                if (res[i][j] == '.') {
                    q.offer(i);
                } else {
                    if (q.isEmpty()) {
                        continue;
                    }
                    res[q.poll()][j] = '#';
                    res[i][j] = '.';
                    q.offer(i);
                }
            }
        }
        return res;
    }
}

...