怎么建网站卖东西,提示网站有风险,注册公司网上核名网站,WordPress前端发布文章文章目录1. 题目2. 解题1. 题目
在一个图书馆的长廊里#xff0c;有一些座位和装饰植物排成一列。 给你一个下标从 0 开始#xff0c;长度为 n 的字符串 corridor #xff0c;它包含字母 ‘S’ 和 ‘P’ #xff0c;其中每个 ‘S’ 表示一个座位#xff0c;每个 ‘P’ 表…
文章目录1. 题目2. 解题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 1e97;vectorint puts;puts.reserve(corridor.size());for(auto c : corridor){if(cS){if(s0 s%20){puts.push_back(p1);p 0;}s;if(s2) p 0;}else if (s%20) p;}if(s%21 || s0) 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 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
