LeetCode 1861. 旋转盒子（前缀和）

Michael阿明

发布于 2021-09-06 11:03:22

2360

发布于 2021-09-06 11:03:22

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

1. 题目

给你一个 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] 只可能是 '#' ，'*' 或者 '.' 。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/rotating-the-box 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

建立每行的前缀和，从底部开始检查

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)
        {
            int sum = 0;
            vector<int> presum(n,0);
            for(int j = 0; j < n; ++j)
            {
                if(box[i][j] == '#')
                    sum++;
                else if(box[i][j] == '*')
                {
                    sum = 0;
                    ans[j][m-1-i] = '*';//障碍物填上
                }
                presum[j] = sum;
            }
            int s = -1;
            for(int j = n-1; j >= 0; --j)//从底部开始摆
            {
                if(presum[j] > 0 && s == -1)
                    s = presum[j];
                else if(presum[j] == 0)
                    s = -1;
                if(s > 0)//有剩余的石头可摆
                {
                    ans[j][m-1-i] = '#';
                    s--;
                }
            }
        }
        return ans;
    }
};

292 ms 57.1 MB C++

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/05/16 ，如有侵权请联系 cloudcommunity@tencent.com 删除

https