Skip to content

Latest commit

 

History

History
227 lines (186 loc) · 6.27 KB

File metadata and controls

227 lines (186 loc) · 6.27 KB
comments difficulty edit_url rating source tags
true
中等
1536
第 52 场双周赛 Q3
数组
双指针
矩阵

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] 只可能是 '#' ,'*' 或者 '.' 。

解法

方法一:队列模拟

我们先将矩阵顺时针旋转 90 度,然后模拟每一列石头的下落过程。

时间复杂度 $O(m \times n)$,空间复杂度 $O(m \times n)$。其中 $m$$n$ 分别是矩阵的行数和列数。

Python3

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

Java

class Solution {
    public char[][] rotateTheBox(char[][] box) {
        int m = box.length, n = box[0].length;
        char[][] ans = new char[n][m];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans[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 (ans[i][j] == '*') {
                    q.clear();
                } else if (ans[i][j] == '.') {
                    q.offer(i);
                } else if (!q.isEmpty()) {
                    ans[q.pollFirst()][j] = '#';
                    ans[i][j] = '.';
                    q.offer(i);
                }
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
        int m = box.size(), n = box[0].size();
        vector<vector<char>> ans(n, vector<char>(m));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans[j][m - i - 1] = box[i][j];
            }
        }
        for (int j = 0; j < m; ++j) {
            queue<int> q;
            for (int i = n - 1; ~i; --i) {
                if (ans[i][j] == '*') {
                    queue<int> t;
                    swap(t, q);
                } else if (ans[i][j] == '.') {
                    q.push(i);
                } else if (!q.empty()) {
                    ans[q.front()][j] = '#';
                    q.pop();
                    ans[i][j] = '.';
                    q.push(i);
                }
            }
        }
        return ans;
    }
};

Go

func rotateTheBox(box [][]byte) [][]byte {
	m, n := len(box), len(box[0])
	ans := make([][]byte, n)
	for i := range ans {
		ans[i] = make([]byte, m)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			ans[j][m-i-1] = box[i][j]
		}
	}
	for j := 0; j < m; j++ {
		q := []int{}
		for i := n - 1; i >= 0; i-- {
			if ans[i][j] == '*' {
				q = []int{}
			} else if ans[i][j] == '.' {
				q = append(q, i)
			} else if len(q) > 0 {
				ans[q[0]][j] = '#'
				q = q[1:]
				ans[i][j] = '.'
				q = append(q, i)
			}
		}
	}
	return ans
}