LeetCode 1195. 多线程 Fizz Buzz
目录
题目描述
题意分析
一个
FizzBuzz对象的四个方法fizz、buzz、fizzbuzz、number会被四个不同的线程各调用一次，四个线程并发运行。要求把所有打印动作拼起来后，整体输出必须和单线程从1数到n依次做 FizzBuzz 判断的结果逐项完全一致：被15整除打印fizzbuzz，只被3整除打印fizz，只被5整除打印buzz，其余打印数字本身。注意四个方法只被调用一次，所以「循环到
n」这件事必须写在每个方法内部，而不是由外部框架反复调用。这意味着每个线程都要自己知道「我这一趟总共该打印几次」，而且这个次数必须和它真正该负责的数字个数分毫不差：多循环一轮就会永久卡在等待上导致整个程序挂死，少循环一轮就会漏输出。约束里
n最大只有50，这个数字小到任何算法层面的优化都毫无意义，等于明说本题的全部考点在并发正确性上：怎样让四个互相不知道对方进度的线程，产出一个严格有序的序列。评测机会反复跑很多次来捕捉偶发的竞态，所以「大部分时候能过」等于错。还有一条隐含要求：不允许忙等空转。让线程反复抢锁看一眼再放开，虽然能出正确结果，但会把 CPU 打满，面试里这属于会被追问到底的写法。
边界上有两处容易被忽略：
n < 3时fizz线程一次都不打印，n < 15时fizzbuzz线程一次都不打印，这些线程必须能正常走完循环并退出，而不是停在等待里；另外n = 1时只有number线程输出一个1，其余三个线程必须立刻结束。
解法：四个信号量协调执行权
核心思路
最朴素的想法是搞一个共享计数器
i和一把锁，四个线程各自while (i <= n)，加锁后看当前的i是不是归自己管，是就打印并i++，不是就解锁重来。这样确实能保证顺序，但瓶颈很明显：不该自己打印的三个线程会疯狂地加锁、判断、解锁，纯粹在烧 CPU，而且谁先抢到锁完全靠操作系统调度，压力大时抖动很厉害。跳出来看会发现一件事：任何时刻，整个系统里只有唯一一个「待打印的数字」，而这个数字该由谁打印，是它自己的数值唯一决定的。既然接下来该谁动手是完全确定的、没有任何竞争可言，那就不该让线程去「抢」，而应该由上一个动作的执行者点名把执行权交给下一个人。这就把「四个线程竞争一把锁」改造成了「一枚令牌在四个线程之间定向传递」。
谁来点名？只有
number线程天然知道当前数字是几（它是唯一从1数到n的线程），所以让它当调度中心：拿到令牌后先判断当前数字属于哪一类，属于自己就直接打印然后把令牌留给自己进入下一个数字，属于别人就把令牌递给那个线程；打印线程干完活后把令牌原样交还给number，让它推进到下一个数字。令牌用四个信号量表示，numberSem初值为1（number先手），其余三个初值为0。这套结构的循环不变量是：任意时刻，四个信号量的许可总数恒等于
1；持有那唯一一个许可的线程，就是当前数字i的合法打印者。number每轮做的是「消耗掉一个许可、再释放出一个许可」，打印线程做的也是「消耗一个、释放一个」，所以总数守恒；而许可的去向永远指向正确的那个线程，输出顺序自然就对了。也正因为总量恒为1，任何两次打印之间都不可能发生重叠。剩下的问题是三个打印线程各自该循环多少次。它们不能靠
number通知，只能自己算：fizzbuzz负责15, 30, 45, ...，直接i += 15循环即可；fizz负责能被3整除但不能被5整除的数，所以在i += 3的循环里要把i % 5 == 0的那些跳过；buzz同理跳过i % 3 == 0。这个跳过不是可有可无的优化，而是正确性要件：number遇到15只会释放fizzbuzzSem，如果fizz也为15准备了一次acquire，它就会永远等下去。
解题步骤
- 建立四个信号量并定好初值：
numberSem初值1，fizzSem、buzzSem、fizzbuzzSem初值0。为什么必须这样：这就是「令牌总量为1且初始在number手里」的直接编码。哪怕给某个打印线程多放一个初始许可，它就会在第1个数字还没打印时抢跑，输出顺序立刻乱掉。number线程从1遍历到n，每轮开头先numberSem.acquire()。为什么放在循环体第一行：acquire是这一轮的入场券，只有拿到它才说明上一个数字已经打印完毕，否则number可能在别人还没打印时就推进到下一个数字。number按15 → 3 → 5 → 其他的顺序做判断。为什么顺序不能变：15的倍数同时满足i % 3 == 0和i % 5 == 0，if-else链是自上而下短路匹配的，把15放在后面会让15被3那一支抢先接走，打印成fizz。- 命中
15/3/5时只做release，不打印。为什么不自己打印：打印动作必须由题目指定的那个线程完成，number只拿到了printNumber这一个回调，物理上也打印不了fizz。释放完这一轮就结束了，number会在下一轮开头的acquire上阻塞，直到打印线程把令牌还回来。- 其余情况由
number自己printNumber.accept(i)后再numberSem.release()。为什么要自己释放：普通数字没有第二个线程会替它归还令牌，如果这里忘了release，下一轮的acquire就会永久阻塞，程序在第一个非3/5倍数上直接挂死。- **三个打印线程各自按自己的步长循环，循环体统一是「
acquire自己的信号量 → 执行打印回调 →releasenumberSem」**。为什么必须归还给numberSem而不是自己：令牌交回调度中心，才能让number推进到下一个数字；还给自己等于把令牌扣下，number` 再也醒不过来。fizz和buzz的循环里跳过15的倍数。为什么：这些数字的令牌会发给fizzbuzz，如果fizz也在这里等，它等到的会是后面某个本该属于自己的数字的令牌，从此每个线程的进度都错位一格，最终必然有线程等不到而死锁。以
n = 15走一遍（用「令牌位置」来跟踪）：
- 起点：令牌在
numberSem。number拿到令牌，i = 1，不被3/5整除，自己打印1，再把令牌放回numberSem。i = 2同上，打印2，令牌回到numberSem。此时另外三个线程都还阻塞在自己的acquire上，没有任何机会插队。i = 3：number拿到令牌，命中i % 3 == 0，把令牌放进fizzSem后本轮结束，随即在下一轮开头的acquire上阻塞。fizz线程被唤醒，打印fizz，把令牌还给numberSem。i = 4：number被唤醒，自己打印4，令牌回到numberSem。i = 5：命中i % 5 == 0，令牌进buzzSem；buzz打印buzz后把令牌还回来。i = 6 .. 14：重复上述模式，6、9、12走fizz，10走buzz，7、8、11、13、14由number自己打印。i = 15：number先撞上i % 15 == 0这一支，令牌进fizzbuzzSem；fizzbuzz打印fizzbuzz，令牌还给numberSem。- 收尾：
number的i变成16超过n，循环结束，此时numberSem里还剩最后一个许可但已无人索取，属于正常残留。fizz的循环走完3, 6, 9, 12（15被i % 5 == 0跳过）后退出，buzz走完5, 10（15被跳过）后退出，fizzbuzz走完15后退出。四个线程全部正常返回。最终输出为
1 2 fizz 4 buzz fizz 7 8 fizz buzz 11 fizz 13 14 fizzbuzz，与单线程结果一致。反过来看，若fizz没有跳过15：它在打印完12后会再做一次fizzSem.acquire()，而number在i = 15时释放的是fizzbuzzSem，之后循环就结束了，再没有人会释放fizzSem，fizz线程永远挂在那里不返回。
代码实现
class FizzBuzz {
private final int n;
private final Semaphore numberSem = new Semaphore(1);
private final Semaphore fizzSem = new Semaphore(0);
private final Semaphore buzzSem = new Semaphore(0);
private final Semaphore fizzbuzzSem = new Semaphore(0);
public FizzBuzz(int n) {
this.n = n;
}
public void fizz(Runnable printFizz) throws InterruptedException {
for (int i = 3; i <= n; i += 3) {
// 15 的倍数归 fizzbuzz 线程，这里不跳过就会多等一次许可而死锁。
if (i % 5 == 0) {
continue;
}
fizzSem.acquire();
printFizz.run();
numberSem.release();
}
}
public void buzz(Runnable printBuzz) throws InterruptedException {
for (int i = 5; i <= n; i += 5) {
if (i % 3 == 0) {
continue;
}
buzzSem.acquire();
printBuzz.run();
numberSem.release();
}
}
public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
for (int i = 15; i <= n; i += 15) {
fizzbuzzSem.acquire();
printFizzBuzz.run();
numberSem.release();
}
}
public void number(IntConsumer printNumber) throws InterruptedException {
for (int i = 1; i <= n; i++) {
numberSem.acquire();
// 15 必须排在 3 和 5 前面，否则会被 fizz 分支抢先接走。
if (i % 15 == 0) {
fizzbuzzSem.release();
} else if (i % 3 == 0) {
fizzSem.release();
} else if (i % 5 == 0) {
buzzSem.release();
} else {
// 普通数字没有别的线程替它归还许可，必须自己释放。
printNumber.accept(i);
numberSem.release();
}
}
}
}
type FizzBuzz struct {
n int
numberSem chan struct{}
fizzSem chan struct{}
buzzSem chan struct{}
fizzbuzzSem chan struct{}
}
func Constructor(n int) FizzBuzz {
fb := FizzBuzz{
n: n,
numberSem: make(chan struct{}, 1),
fizzSem: make(chan struct{}, 1),
buzzSem: make(chan struct{}, 1),
fizzbuzzSem: make(chan struct{}, 1),
}
// 容量为 1 的 channel 就是二元信号量，预先塞一个令牌让 Number 先手。
fb.numberSem <- struct{}{}
return fb
}
func (fb *FizzBuzz) Fizz(printFizz func()) {
for i := 3; i <= fb.n; i += 3 {
// 15 的倍数归 Fizzbuzz 协程，这里不跳过就会多收一次令牌而死锁。
if i%5 == 0 {
continue
}
<-fb.fizzSem
printFizz()
fb.numberSem <- struct{}{}
}
}
func (fb *FizzBuzz) Buzz(printBuzz func()) {
for i := 5; i <= fb.n; i += 5 {
if i%3 == 0 {
continue
}
<-fb.buzzSem
printBuzz()
fb.numberSem <- struct{}{}
}
}
func (fb *FizzBuzz) Fizzbuzz(printFizzBuzz func()) {
for i := 15; i <= fb.n; i += 15 {
<-fb.fizzbuzzSem
printFizzBuzz()
fb.numberSem <- struct{}{}
}
}
func (fb *FizzBuzz) Number(printNumber func(int)) {
for i := 1; i <= fb.n; i++ {
<-fb.numberSem
// 15 必须排在 3 和 5 前面，否则会被 fizz 分支抢先接走。
if i%15 == 0 {
fb.fizzbuzzSem <- struct{}{}
} else if i%3 == 0 {
fb.fizzSem <- struct{}{}
} else if i%5 == 0 {
fb.buzzSem <- struct{}{}
} else {
// 普通数字没有别的协程替它归还令牌，必须自己放回。
printNumber(i)
fb.numberSem <- struct{}{}
}
}
}
复杂度分析
- 时间复杂度：$O(n)$。凭什么：
number线程恰好循环n轮，每个数字触发恰好一次「释放许可 + 一次打印 + 归还许可」的常数次同步操作；三个打印线程的循环轮数加起来也不超过n。没有任何忙等重试，总操作数与n成正比。- 空间复杂度：$O(1)$。凭什么：只有四个信号量对象和几个循环变量，数量固定为常数，不随
n增长。线程数固定为4，也不计入随输入增长的空间。
关键点总结
- 并发题的第一步是判断线程之间是「竞争关系」还是「协作关系」。本题任意时刻只有一个合法执行者且这个执行者可以被提前算出来，属于纯协作，因此正确的模型是定向传递令牌而不是抢锁，这个判断能直接决定你写出的是忙等版还是信号量版。
- 「许可总量守恒且恒为
1」是这类题最好用的自证工具。写完代码逐条检查每个分支是否都做了「消耗一个、释放一个」，任何一条路径上少一次release就是死锁，多一次就是乱序，比反复跑用例靠谱得多。- 让唯一掌握全局状态的线程充当调度中心，是并发编排的通用套路。这里只有
number知道当前数到几，所有判断逻辑就都集中到它一个人身上，其余线程退化成无脑的「等待—打印—归还」三件套，逻辑复杂度被压到最低。- 各个线程自己算出精确的循环次数，是这类「每个方法只被调用一次」的题目的固定要求。步长加跳过条件必须让四个线程的打印次数之和恰好等于
n，多一次死锁、少一次丢输出。- 面试视角：写完后主动说明三件事——为什么不用
synchronized+wait/notify（notifyAll会唤醒全部线程再各自判断，等价于忙等的变体，而信号量是精确唤醒）、为什么初值这样取、以及每个线程的循环次数是怎么算出来的。这三点讲清楚，面试官基本不会再追问。- Go 里容量为
1的chan struct{}就是天然的二元信号量，<-ch对应acquire、ch <- struct{}{}对应release，比引入sync.Cond简洁得多，也是 Go 面试里期望看到的写法。
易错点总结
- 把
if (i % 15 == 0)放在if (i % 3 == 0)后面：n = 15时15会被3那一支接走，输出fizz而不是fizzbuzz；更糟的是fizzbuzz线程永远等不到自己的许可，程序卡死不返回。fizz的循环没跳过i % 5 == 0：n = 15时fizz会为15多做一次acquire，而number把许可给了fizzbuzz，fizz线程永久阻塞在第 5 次acquire上，判题超时。number打印完普通数字后忘记numberSem.release()：n = 1时打印出1后number就永久阻塞，程序连第一个数字之后都走不动。- 打印线程把许可还给自己而不是
numberSem（写成fizzSem.release()）：n = 3时输出完1 2 fizz后，number再也拿不到许可，后续数字全部丢失。numberSem初值写成0：四个线程全部阻塞在各自的acquire上，一个字符都打印不出来，是最典型的「全员死锁」。- 给
fizzSem之类的初值写成1：n = 3时fizz可能在number还没打印1之前就抢先输出fizz，得到fizz 1 2 ...这种乱序；而且这种错误只在特定调度下暴露，本地跑十次可能只错一次。number在命中3/5/15分支时也调用了printNumber.accept(i)：n = 3时输出变成1 2 3 fizz，多打印了一个数字。- 改用
synchronized+ 共享计数器但用if而不是while包裹wait()：虚假唤醒或notifyAll唤醒了不该动的线程时，该线程会跳过条件检查直接打印，n = 15这种长序列跑多次就会偶发乱序。- 三个打印线程写成
for (int i = 1; i <= n; i++)再在循环里判断是否属于自己：循环次数变成n次而acquire只会成功该线程负责的那几次，剩下的acquire全部永久阻塞。- 在
acquire和release之间加了额外的共享变量读写却没有同步：本题的许可传递已经隐含了 happens-before 关系，额外加锁不仅多余，还容易和信号量顺序交织出新的死锁路径。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1114. 按序打印 | 简单 | 最简化的令牌传递，只有一条固定链路，是本题的入门版 |
| 1115. 交替打印 FooBar | 中等 | 两个线程互相唤醒，令牌在双方之间来回摆动，没有调度中心 |
| 1116. 打印零与奇偶数 | 中等 | 三线程且 zero 交替扮演调度中心，与本题的中心化结构最接近 |
| 1188. 设计有限阻塞队列 | 中等 | 计数信号量而非二元信号量，要同时维护空位数和元素数两个计数 |
| 1226. 哲学家进餐 | 中等 | 真正的资源竞争，重点从编排顺序变成破坏死锁的四个必要条件 |
| 1242. 多线程网络爬虫 | 中等 | 无顺序要求但需要线程安全的去重集合与任务分发，考察并发容器的选型 |