LeetCode 1115. 交替打印 FooBar

约 5 分钟
文章信息 7 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 阿里
标签
多线程

题目描述

✅ 1115. 交替打印 FooBar

image-20260928225815091

image-20260928225815093

题意分析

两个线程操作同一个 FooBar 对象，一个调用 foo，另一个调用 bar，各自需要执行打印回调 n 次。无论线程启动和调度顺序如何，整体输出都必须严格交替，并且从 foo 开始。

每次 foo 完成后才能允许本轮 bar，每次 bar 完成后才能开始下一轮 foo。仅仅让两个线程都打印正确次数，还不能保证这个顺序。

解法：信号量交替放行

核心思路

[!blue]

为两方分别设置可等待的执行许可。fooSem 初始有一份许可，barSem 初始为零，因此不管谁先运行，第一次能通过等待的一定是 foo。

每轮 foo 先获取自己的许可，完成回调后把许可交给 bar；bar 也先等待自己的许可，打印完成后再交回 foo。两方都不会把许可直接还给自己，所以每次放行都会把执行权转向另一方。

整个过程只有一份执行权：它可能保存在某个同步对象里，也可能已经被线程取得、正在用于打印。因此正在执行回调时，两个信号量中的可用数量都可能为零。只有打印结束才交接，保证对方无法提前进入下一次输出。

Java 使用信号量的 acquire 与 release，Go 使用容量为一的通道保存或领取一个空值作为许可。通道容量一既能保存启动时的许可，也能接住最后一轮 bar 归还但不再被读取的许可，让两个方法都正常返回。

每轮都重新等待、打印、交接，循环 n 次就会得到恰好 n 对输出，不需要依赖睡眠时间或猜测调度速度。

解题步骤

  1. 初始化 foo 许可为一、bar 许可为零。
  2. foo 每轮等待自己的许可，通过后调用 printFoo，完成后发放一份 bar 许可。
  3. bar 每轮等待自己的许可，通过后调用 printBar，完成后发放一份 foo 许可。
  4. 两个方法分别完成 n 轮后返回；最终归还的 foo 许可留在同步对象中即可。

代码实现

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++) {
            fooSem.acquire();
            printFoo.run();
            // 本次打印完成，把唯一许可交给另一方。
            barSem.release();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            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),
    }
    // 通道保存 foo 的执行许可，容量一也能接住最后一次归还。
    fb.fooSem <- struct{}{}
    return fb
}

func (fb *FooBar) Foo(printFoo func()) {
    for i := 0; i < fb.n; i++ {
        <-fb.fooSem
        printFoo()
        // 本次打印完成，把唯一许可交给另一方。
        fb.barSem <- struct{}{}
    }
}

func (fb *FooBar) Bar(printBar func()) {
    for i := 0; i < fb.n; i++ {
        <-fb.barSem
        printBar()
        // 通道保存 foo 的执行许可，容量一也能接住最后一次归还。
        fb.fooSem <- struct{}{}
    }
}

复杂度分析

  • 时间复杂度：不计回调与调度等待，同步工作 $O(n)$。
  • 空间复杂度：$O(1)$，两个固定同步对象。

关键点总结

[!green]

  • 初始许可决定谁先打印，交给对方的许可决定之后严格交替。
  • 交接必须发生在回调完成之后，而不是刚获得执行权时。
  • Go 的缓冲通道同时承接首次启动和末次归还，避免无人接收时发送阻塞。

易错点总结

[!yellow]

  • 两边都初始化为一，会允许两个回调同时开始；两边都为零，则都无法启动。
  • 打印之前就发放对方许可，对方可能先完成输出，顺序无法保证。
  • 许可还给自己，会让一方连续打印，另一方一直等待。
  • 只在整个循环开始前获取一次许可，后续轮次就失去交替约束。
  • Go 改用无缓冲通道，构造阶段的初始发送以及最后归还都可能找不到接收方而阻塞。

相似题目

题目 难度 关联与区别
1114. 按序打印 简单 从一次顺序约束扩展成n轮交替，需要在每轮完成后把执行许可交给另一线程。
1195. 多线程 Fizz Buzz 中等 同样多个线程按条件接力输出，原题有四种职责，需要根据当前数值选择下一执行者。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/61612197
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！