分隔长廊的方案数

2147. 分隔长廊的方案数

在一个图书馆的长廊里，有一些座位和装饰植物排成一列。给你一个下标从 0 开始，长度为 n 的字符串 corridor ，它包含字母 'S' 和 'P' ，其中每个 'S' 表示一个座位，每个 'P' 表示一株植物。

在下标 0 的左边和下标 n - 1 的右边已经分别各放了一个屏风。你还需要额外放置一些屏风。每一个位置 i - 1 和 i 之间（1 <= i <= n - 1），至多能放一个屏风。

请你将走廊用屏风划分为若干段，且每一段内都 恰好有两个座位 ，而每一段内植物的数目没有要求。可能有多种划分方案，如果两个方案中有任何一个屏风的位置不同，那么它们被视为不同方案。

请你返回划分走廊的方案数。由于答案可能很大，请你返回它对 10⁹ + 7 取余的结果。如果没有任何方案，请返回 0 。

示例 1：

输入：corridor = "SSPPSPS"
输出：3
解释：总共有 3 种不同分隔走廊的方案。
上图中黑色的竖线表示已经放置好的屏风。
上图每种方案中，每一段都恰好有 两个 座位。

示例 2：

输入：corridor = "PPSPSP"
输出：1
解释：只有 1 种分隔走廊的方案，就是不放置任何屏风。
放置任何的屏风都会导致有一段无法恰好有 2 个座位。

示例 3：

输入：corridor = "S"
输出：0
解释：没有任何方案，因为总是有一段无法恰好有 2 个座位。

提示：

n == corridor.length
1 <= n <= 10⁵
corridor[i] 要么是 'S' ，要么是 'P' 。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int numberOfWays(string corridor) { } };

golang 解法, 执行用时: 40 ms, 内存消耗: 6.8 MB, 提交时间: 2023-10-10 23:43:03

func numberOfWays(corridor string) int {
	ans, cntS, pre := 1, 0, 0
	for i, ch := range corridor {
		if ch == 'S' {
			// 对第 3,5,7,... 个座位，可以在其到其左侧最近座位之间的任意一个位置放置屏风
			cntS++
			if cntS >= 3 && cntS%2 == 1 {
				ans = ans * (i - pre) % (1e9 + 7)
			}
			pre = i // 记录上一个座位的位置
		}
	}
	if cntS == 0 || cntS%2 == 1 { // 座位个数不能为 0 或奇数
		return 0
	}
	return ans
}

cpp 解法, 执行用时: 112 ms, 内存消耗: 30.2 MB, 提交时间: 2023-10-10 23:42:51

class Solution {
public:
    int numberOfWays(string corridor) {
        int ans = 1, cnt_s = 0, pre = 0;
        for (int i = 0; i < corridor.length(); ++i) {
            if (corridor[i] == 'S') {
                // 对第 3,5,7,... 个座位，可以在其到其左侧最近座位之间的任意一个位置放置屏风
                ++cnt_s;
                if (cnt_s >= 3 && cnt_s % 2) {
                    ans = (long) ans * (i - pre) % 1000000007;
                }
                pre = i; // 记录上一个座位的位置
            }
        }
        return cnt_s && cnt_s % 2 == 0 ? ans : 0; // 座位个数必须为正偶数
    }
};

java 解法, 执行用时: 25 ms, 内存消耗: 43.1 MB, 提交时间: 2023-10-10 23:42:37

class Solution {
    public int numberOfWays(String corridor) {
        var ans = 1L;
        var cntS = 0;
        var pre = 0;
        for (var i = 0; i < corridor.length(); ++i) {
            if (corridor.charAt(i) == 'S') {
                // 对第 3,5,7,... 个座位，可以在其到其左侧最近座位之间的任意一个位置放置屏风
                ++cntS;
                if (cntS >= 3 && cntS % 2 == 1) {
                    ans = ans * (i - pre) % 1000000007;
                }
                pre = i; // 记录上一个座位的位置 
            }
        }
        return cntS > 0 && cntS % 2 == 0 ? (int) ans : 0; // 座位个数必须为正偶数
    }
}

python3 解法, 执行用时: 392 ms, 内存消耗: 16.7 MB, 提交时间: 2023-10-10 23:42:24

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        ans, cnt_s, pre = 1, 0, 0
        for i, ch in enumerate(corridor):
            if ch == 'S':
                # 对第 3,5,7,... 个座位，可以在其到其左侧最近座位之间的任意一个位置放置屏风
                cnt_s += 1
                if cnt_s >= 3 and cnt_s % 2:
                    ans = ans * (i - pre) % 1000000007
                pre = i  # 记录上一个座位的位置
        return ans if cnt_s and cnt_s % 2 == 0 else 0  # 座位个数必须为正偶数

上一题

下一题

详情