LeetCode 1115. 交替打印 FooBar
目录
题目描述
题意分析
同一个对象上会有两个线程并发跑起来，一个只负责调用
printFoo，另一个只负责调用printBar，各自调用n次。要求不管操作系统怎么调度，最终拼出来的输出永远是foobar重复n次。关键约束信号是「两个方法体互不相干，却必须产生一个全局有序的输出」。这说明输出顺序不可能由各自循环的计数决定，只能由两段代码谁先跑到打印那一行决定。
还有一个隐含约束：两个方法被启动的先后是不确定的，
bar的线程完全可能先被调度。所以初始状态必须自带方向性，让抢先跑起来的bar也只能停下来等。边界上
n至少为1，不存在一次都不打印的情况；结束时两个线程都必须能正常退出，不能有任何一方永远卡在等待里。
解法：信号量交替放行
核心思路
最直觉的写法是加一个共享布尔量
fooTurn，两边都写while (!fooTurn) {}这样的自旋等待。逻辑上说得通，但瓶颈很明显：忙等会把 CPU 烧满，而且如果这个变量不是volatile的，另一个线程可能永远读到过期的缓存值，直接死循环。沿着这个思路再想一步：忙等之所以出现，是因为「等待」这件事被表达成了「反复查看」。如果换成一种能让线程真正睡下去、并由对方主动叫醒的机制，就既省 CPU 又天然保证了可见性。
观察真正需要维护的东西：任意时刻，只有一个线程被允许推进到打印那一行。把这个「允许」做成一枚可以被交出去的令牌，问题就变成令牌在两个线程之间来回传递。
于是引入两个计数信号：
fooSem表示foo手上有几张通行证，barSem同理。不变量是fooSem + barSem ≡ 1，即整个生命周期里通行证总数恒为1，永远只有一边能走。初始把这唯一一张给foo，方向性就有了；每次打印完把它交给对方，交替就自动成立了。
解题步骤
- 构造对象时保存
n。因为两个方法都要靠它决定循环次数，且它在并发期间只读不写，不需要额外保护。- 把
fooSem初始化为1、barSem初始化为0。这一步就是把唯一的通行证预先发给foo，从而钉死第一个输出是foo，与线程启动顺序无关。foo()循环n次：先fooSem.acquire()，拿不到就阻塞挂起；拿到后执行printFoo.run()；最后barSem.release()把通行证交给对方。释放必须放在打印之后，否则对方可能在自己打印完成前就插进来。bar()循环n次：先barSem.acquire()，打印，再fooSem.release()。这样通行证又回到foo手里，开启下一轮。- 两个循环次数都是
n，保证第n轮bar打印完后，foo虽然收到了最后一张通行证但循环已经结束，两个线程都干净退出，不会残留阻塞。以
n = 2走一遍：初始fooSem = 1、barSem = 0。假设调度器先让bar跑，bar执行barSem.acquire()时barSem = 0，立即阻塞。foo跑起来，acquire成功，fooSem变0，输出foo，然后barSem.release()使barSem = 1，此时fooSem + barSem = 1仍然成立。被唤醒的bar拿走许可，barSem回到0，输出bar，再fooSem.release()使fooSem = 1。第二轮同理：foo拿到许可打印foo，fooSem = 0、barSem = 1；bar打印bar，barSem = 0、fooSem = 1。两个循环各走满两次退出，最终输出foobarfoobar，末尾fooSem里剩下的那张许可无人认领，也不影响退出。
代码实现
class FooBar {
private final int n;
private final java.util.concurrent.Semaphore fooSem = new java.util.concurrent.Semaphore(1);
private final java.util.concurrent.Semaphore barSem = new java.util.concurrent.Semaphore(0);
public FooBar(int n) {
this.n = n;
}
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
// foo 打印后把执行权交给 bar。
fooSem.acquire();
printFoo.run();
barSem.release();
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
// bar 打印后把执行权交回下一轮 foo。
barSem.acquire();
printBar.run();
fooSem.release();
}
}
}
type FooBar struct {
n int
fooSem chan struct{}
barSem chan struct{}
}
func Constructor(n int) FooBar {
fb := FooBar{
n: n,
fooSem: make(chan struct{}, 1),
barSem: make(chan struct{}, 1),
}
fb.fooSem <- struct{}{}
return fb
}
func (fb *FooBar) Foo(printFoo func()) {
for i := 0; i < fb.n; i++ {
// foo 打印后把执行权交给 bar。
<-fb.fooSem
printFoo()
fb.barSem <- struct{}{}
}
}
func (fb *FooBar) Bar(printBar func()) {
for i := 0; i < fb.n; i++ {
// bar 打印后把执行权交回下一轮 foo。
<-fb.barSem
printBar()
fb.fooSem <- struct{}{}
}
}
复杂度分析
- 时间复杂度：$O(n)$，两个方法各自循环
n次，每次只做一对常数时间的获取与释放，没有任何重试或轮询。- 空间复杂度：$O(1)$，只额外持有两个信号量对象，占用与
n无关。
关键点总结
- 并发题的核心是先写出不变量再写代码。这里的不变量「通行证总数恒为
1」一旦确定，初始值、获取顺序、释放位置就全被推导出来了，不需要靠试。- 初始状态承担了「谁先跑」的定序职责。凡是要求固定首个输出的交替问题，都要把初始许可只发给指定的一方。
- 释放对方的信号量必须是临界区的最后一步，把打印夹在获取和释放之间，才能保证输出不交错。
- 面试视角：面试官通常会追问「为什么不用
synchronized加wait/notify」。可以答：能实现，但两线程场景下notify唤醒的一定是对方线程所以恰好安全，扩展到三线程就必须换notifyAll并配合状态变量重新检查，而信号量把这个状态显式化了，更不容易写错。- 面试视角：还要能主动说明「忙等 + 非
volatile变量」的写法为什么错，这一点比写出正确答案更能体现对内存可见性的理解。
易错点总结
- 错误写法：
barSem也初始化为1。用例n = 1→bar线程可能先拿到许可，输出变成barfoo，交替顺序从第一轮就崩了。- 错误写法：把
printFoo.run()写在barSem.release()之后。用例n = 2→bar可能在foo真正打印前就完成打印，出现barfoo这类乱序。- 错误写法：
foo里释放的是fooSem。用例n = 1→foo反复拿回自己的许可连打n个foo，bar永远阻塞，程序超时。- 错误写法：用一个共享的普通
boolean字段自旋等待，不加volatile。用例任意n→ 另一线程可能一直读到旧值，形成活锁式死循环，同时 CPU 被打满。- 错误写法：
bar的循环写成n - 1次或用i <= n。用例n = 3→ 少打印一个bar或多阻塞一轮，输出长度不对甚至挂死。- 错误写法：把
acquire放在循环外，只获取一次。用例n = 2→ 第二轮不再等待对方，两个线程各自连续打印，输出退化成foofoobarbar。- 错误写法：Go 版本忘记在构造函数里往
fooSem里塞初始值。用例任意n→ 两个 goroutine 都在接收操作上阻塞，直接死锁。- 错误写法：Go 版本把通道建成无缓冲的，同时保留「先接收后发送」的结构。用例任意
n→ 发送方要等接收方就位，foo打印完发往barSem时若bar尚未到达接收点就会被挂住，配合初始塞值的逻辑就无处安放，容易写出死锁。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1114. 按序打印 | 简单 | 三个线程一次性定序，无需循环回传 |
| 1116. 打印零与奇偶数 | 中等 | 三线程按 0x0y 模式轮转，令牌分支更多 |
| 1195. 多线程 Fizz Buzz | 中等 | 放行对象由数字整除关系动态决定 |
| 1226. 哲学家进餐 | 中等 | 多资源竞争下的死锁避免 |
| 1242. 多线程网络爬虫 | 中等 | 线程池与共享去重集合的并发安全 |