LeetCode 2147. 分隔长廊的方案数
LeetCode 2147. 分隔长廊的方案数
Michael阿明
发布于 2022-03-10 18:15:10
发布于 2022-03-10 18:15:10
文章目录
1. 题目
在一个图书馆的长廊里，有一些座位和装饰植物排成一列。 给你一个下标从 0 开始，长度为 n 的字符串 corridor ，它包含字母 ‘S’ 和 ‘P’ ，其中每个 ‘S’ 表示一个座位，每个 ‘P’ 表示一株植物。
在下标 0 的左边和下标 n - 1 的右边 已经 分别各放了一个屏风。 你还需要额外放置一些屏风。 每一个位置 i - 1 和 i 之间（1 <= i <= n - 1），至多能放一个屏风。
请你将走廊用屏风划分为若干段，且每一段内都 恰好有两个座位 ，而每一段内植物的数目没有要求。 可能有多种划分方案，如果两个方案中有任何一个屏风的位置不同，那么它们被视为 不同 方案。
请你返回划分走廊的方案数。 由于答案可能很大，请你返回它对 10^9 + 7 取余 的结果。 如果没有任何方案，请返回 0 。
示例 1：
在这里插入图片描述
输入：corridor = "SSPPSPS"
输出：3
解释：总共有 3 种不同分隔走廊的方案。
上图中黑色的竖线表示已经放置好的屏风。
上图每种方案中，每一段都恰好有 两个 座位。示例 2：
在这里插入图片描述
输入：corridor = "PPSPSP"
输出：1
解释：只有 1 种分隔走廊的方案，就是不放置任何屏风。
放置任何的屏风都会导致有一段无法恰好有 2 个座位。示例 3：
在这里插入图片描述
输入：corridor = "S"
输出：0
解释：没有任何方案，因为总是有一段无法恰好有 2 个座位。
提示：
n == corridor.length
1 <= n <= 10^5
corridor[i] 要么是 'S' ，要么是 'P' 。来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-of-ways-to-divide-a-long-corridor 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 记录每两个座位之间的 植物数量+1（可摆放的方案数）
- 所有的方案数连乘即可
class Solution {
public:
int numberOfWays(string corridor) {
int s = 0, p = 0, mod = 1e9+7;
vector<int> puts;
puts.reserve(corridor.size());
for(auto c : corridor)
{
if(c=='S'){
if(s>0 && s%2==0){
puts.push_back(p+1);
p = 0;
}
s++;
if(s==2) p = 0;
}
else if (s%2==0) p++;
}
if(s%2==1 || s==0) return 0;
long long ans = 1;
for(int i = 0; i < puts.size(); ++i)
ans = (ans*puts[i])%mod;
return ans;
}
};104 ms 38 MB C++
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录