DeepSeek LeetCode 2147.分割长廊的方案数 public int numberOfWays(String corridor)
这道题的意思是:在一条走廊(字符串)中,'S' 表示座位,'P' 表示植物。我们需要用隔板把走廊分成若干段,使得每段恰好包含 2 个座位。问有多少种不同的分割方案。
---
思路分析
1. 预处理座位数
如果总座位数 totalSeats 不是偶数,直接返回 0。
如果总座位数为 0,也没有任何分割方式,返回 0(题目要求每段必须有 2 个座位,没法分)。
2. 识别每对座位之间的植物
将走廊按座位顺序分组,假设座位位置下标为 p1, p2, ..., pn(n 为偶数)。
我们要在每对座位 (p2, p3) 之间放隔板吗? 不是。
而是:
· 第 1 段:从第 1 个座位到第 2 个座位为止(包含它们)。
· 然后第 2 个座位到第 3 个座位之间如果不放隔板,就会让第 1 段包含 3 个座位,不行。
· 实际上,我们把每 连续 2 个座位 划分成一个“块”。
· 块 1:座位 1 和座位 2
· 块 2:座位 3 和座位 4
· …
· 在块与块之间放置隔板,位置是在前一个块的最后座位与后一个块的最前座位之间的 植物区 随意选择隔板数(可以不放,但最终必须有隔板,因为要分成不同段)。
3. 关键转化
对于 (座位1, 座位2) 与 (座位3, 座位4) 之间的一段(即从座位2+1到座位3-1 这些字符),假设这段长度为 len(全是植物),那么我们可以选择在这 len 个位置中放若干个隔板吗? 不对——我们只能放一个隔板? 不,题意的分割方式是在植物之间切开,隔板可以放多个吗?
仔细理解:一个分割方案是在某些位置放且只放一个隔板,最终让走廊被分成若干段,每段恰 2 个座位。
所以两个相邻块(比如座位 2 与座位 3 之间)至少要有一个隔板来分开它们。
隔板只能放在两个座位之间(不允许放在座位之前或之后),也就是说在 index2+1 与 index3-1 之间的缝隙(植物之间的缝隙)可以任意选择一个或多个? 不,如果选多个隔板,会多出空段(全植物)是不可能的。因此:
· 实际上,两个块之间的植物区有 m 个植物,就有 m+1 个可选放隔板的位置(缝隙)。我们只能放恰好一个隔板来隔开它们,所以方案数 = m+1。
推导:
设块 1 的最后一个座位是 pos2,块 2 的第一个座位是 pos3。
它们之间植物区长度 = pos3 - pos2 - 1 个字符。
放隔板的缝隙数 = 植物区长度 + 1。(因为隔板可以放在植物前、植物间、植物后)
这些缝隙任选 1 个放置隔板,所以乘上 (植物区长度 + 1)。
4. 举例
"SSPPSPS"
座位位置:0,1,4,6。
块1: (0,1)
块2: (4,6)
之间植物区 = 从 2 到 3("PP")长度 2,缝隙 = 3,所以 3 种放法。
5. 最后
将所有相邻块间的 缝隙数 相乘,再取模 1e9+7。
---
算法步骤
1. 遍历 corridor,记录所有 'S' 的下标到数组 seats。
2. 如果 seats 长度是 0 或奇数,直接返回 0。
3. 初始化 ways = 1。
4. 对 i 从 1 到 seats.length/2 - 1(相邻块之间):
· 块 i 的最后座位 index = seats[2i - 1]
块 i+1 的第一个座位 index = seats[2i]
植物数 = seats[2i] - seats[2i - 1] - 1
缝隙数 = 植物数 + 1
ways = (ways * 缝隙数) % MOD
5. 返回 ways。
---
代码实现
```java
class Solution {
private static final int MOD = 1_000_000_007;
public int numberOfWays(String corridor) {
int n = corridor.length();
List<Integer> seats = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (corridor.charAt(i) == 'S') {
seats.add(i);
}
}
int seatCount = seats.size();
if (seatCount == 0 || seatCount % 2 != 0) {
return 0;
}
long ways = 1;
// pair index: 从第一对到最后一对之间
for (int i = 2; i < seatCount; i += 2) {
int gapPlants = seats.get(i) - seats.get(i - 1) - 1;
ways = (ways * (gapPlants + 1)) % MOD;
}
return (int) ways;
}
}
```
更多推荐




所有评论(0)