LeetCode 1116. 打印零与奇偶数

2024-10-22 HGNULB 约 12 分钟

文章信息 7 个分类 1 个标签

分类

题目描述

✅ 1116. 打印零与奇偶数

题意分析

同一个 ZeroEvenOdd 实例会被三个线程分别调用 zero、even、odd 三个方法。zero 负责打印 n 个 0，odd 负责打印 1 到 n 之间的所有奇数，even 负责打印所有偶数，最终标准输出必须严格是 0102030405...，也就是每个数字前面必须紧跟一个 0。三个方法各自跑在独立线程里，调度顺序完全由操作系统决定，我们无法假设谁先启动。

从要求里能读出的信号很明确。第一，输出序列是完全确定的，没有任何自由度，这意味着三个线程之间是严格的轮转关系而不是竞争关系——任何时刻只有一个线程「有资格」执行，其余两个必须阻塞等待。第二，每个方法内部的循环次数是固定可算的：zero 跑 n 轮，odd 跑 ⌈n/2⌉ 轮，even 跑 ⌊n/2⌋ 轮，三者加起来正好是 2n 次打印。第三，printNumber 是外部传进来的回调，我们不知道它耗时多久，也不能假设它是原子的，因此必须保证调用它的时候当前线程是唯一活跃的那个。

边界要照顾几处：n = 1 时 even 的循环体一次都不执行，它必须能干净退出而不是卡在等待上；n 为偶数时最后一个打印的是偶数，n 为奇数时最后一个是奇数，也就是说轮转的终止点会随奇偶性变化，三个线程各自靠自己的循环条件结束，谁也不该等待一个永远不会到来的信号；全部打印完成后不能有线程遗留在阻塞态，否则判题会判超时。

解法：信号量同步

核心思路

最先想到的往往是「共享一个计数器加 synchronized 加忙等」：三个线程都去抢锁，抢到后看当前该不该自己打印，不该就放锁重试。这能跑通，但问题很大——线程在不该自己的时候疯狂空转抢锁，CPU 全浪费在无效唤醒上，而且什么时候轮到自己完全靠碰运气，最坏情况下延迟不可控。退一步用 wait/notifyAll 能避免忙等，但 notifyAll 会把两个等待者都叫醒，其中一个发现不是自己又睡回去，仍然有一半的唤醒是无效的，而且必须写在 while 循环里防虚假唤醒，代码噪音不小。

瓶颈在于：我们用了一个「大家共享的条件」去表达一件本质上是「点对点」的事。观察输出序列 0,1,0,2,0,3,... 可以发现，执行权的传递是完全确定的一条链——zero 打完 0 之后，下一个该谁执行是当场就能算出来的（看这一轮的数字是奇是偶），数字线程打完之后下一个一定是 zero。既然交接对象是确定的，就不该广播唤醒，而应该定向放行。

于是用三个信号量各自代表一个线程的「执行许可」，不变量可以显式写出来：任意时刻，三个信号量的许可总数恒为 1，持有那唯一许可的线程就是当前唯一有资格打印的线程。初始状态把这枚许可给 zero（因为输出必须以 0 开头）；zero 每轮消耗许可、打印 0、然后按当前数字的奇偶把许可交给 odd 或 even；数字线程消耗许可、打印数字、再把许可还给 zero。这条「总量恒为 1」的不变量既保证了互斥（不会有两个线程同时打印），又保证了顺序（许可的流向就是输出的顺序），还顺带保证了无死锁（许可永远在某个尚未跑完循环的线程手里）。

解题步骤

第一步是初始化三个信号量：zero 初始许可为 1，odd 和 even 初始为 0。这个初值分配直接编码了「第一个动作必须是打印 0」这条规则，如果三个都给 0 就无人可动，如果给两个就破坏了总量恒为 1 的不变量。Go 版本用容量为 1 的 channel 模拟信号量，构造时往 zero 里塞一个空结构体，语义完全对应。

第二步写 zero 方法的循环。循环变量 num 从 1 到 n，代表「这一轮打完 0 之后即将被打印的那个数字」。之所以让 zero 也维护这个数字，是因为交接对象取决于它的奇偶性——zero 必须自己算出来才知道该放行谁。每轮先 acquire 拿到许可，再调用 printNumber(0)，最后根据 num % 2 把许可 release 给 odd 或 even。释放动作必须放在打印之后，否则接棒线程可能在 0 还没打出来时就打印了数字。

第三步写 odd 和 even。它们的循环变量直接从各自的起点按步长 2 递增：odd 从 1 开始，even 从 2 开始，这样循环变量本身就是要打印的值，不需要额外计算。每轮先 acquire 自己的许可，打印，然后 release 给 zero，把执行权交还。注意它们不需要判断奇偶，因为循环步长已经保证了它们只会碰到属于自己的数字。

第四步是终止的正确性。三个线程都靠自己的循环上界自然退出，没有任何一方需要等待终止信号。当最后一个数字被打印后，许可被还给 zero，而 zero 的循环此时已经走完，它不会再来 acquire，这枚多余的许可就静静留在信号量里无人认领——这不是泄漏，方法返回后对象被回收即可。反过来，odd 和 even 在自己循环跑完后也绝不会再 acquire，所以不存在谁被永久阻塞。

以 n = 3 走一遍。初始 zero=1, odd=0, even=0。假设 odd 线程先被调度，它 acquire(odd) 立刻阻塞；even 同理阻塞；zero 线程进来，num=1，acquire(zero) 成功（许可归零），打印 0，num % 2 == 1 于是 release(odd)。odd 被唤醒，num=1，打印 1，release(zero)；zero 第二轮 num=2，acquire 成功，打印 0，偶数于是 release(even)。even 醒来，num=2，打印 2，release(zero)；zero 第三轮 num=3，打印 0，奇数于是 release(odd)。odd 第二轮 num=3，打印 3，release(zero)。此时 zero 的循环 num 已到 4 超过 n 退出，odd 下一轮 num=5 超过 n 退出，even 下一轮 num=4 超过 n 退出。最终输出 0102030……准确地说是 0,1,0,2,0,3，完全符合要求，且三个线程全部正常返回。注意整个过程中无论操作系统先调度谁，被调度的线程若没有许可就会立刻阻塞，实际执行顺序被信号量强行拉回到唯一的正确序列上。

代码实现

class ZeroEvenOdd {
    // 打印 0 之后要根据下一次数字的奇偶性唤醒 odd 或 even，数字线程打印完再唤醒 zero。
    private final int n;
    private final Semaphore zero = new Semaphore(1);
    private final Semaphore odd = new Semaphore(0);
    private final Semaphore even = new Semaphore(0);

    public ZeroEvenOdd(int n) {
        this.n = n;
    }

    public void zero(IntConsumer printNumber) throws InterruptedException {
        for (int num = 1; num <= n; num++) {
            zero.acquire();
            printNumber.accept(0);
            if (num % 2 == 1) {
                odd.release();
            } else {
                even.release();
            }
        }
    }

    public void even(IntConsumer printNumber) throws InterruptedException {
        for (int num = 2; num <= n; num += 2) {
            even.acquire();
            printNumber.accept(num);
            zero.release();
        }
    }

    public void odd(IntConsumer printNumber) throws InterruptedException {
        for (int num = 1; num <= n; num += 2) {
            odd.acquire();
            printNumber.accept(num);
            zero.release();
        }
    }
}

type ZeroEvenOdd struct {
    // 打印 0 之后要根据下一次数字的奇偶性唤醒 odd 或 even，数字线程打印完再唤醒 zero。
    n    int
    zero chan struct{}
    odd  chan struct{}
    even chan struct{}
}

func Constructor(n int) ZeroEvenOdd {
    zeo := ZeroEvenOdd{
        n:    n,
        zero: make(chan struct{}, 1),
        odd:  make(chan struct{}, 1),
        even: make(chan struct{}, 1),
    }
    zeo.zero <- struct{}{}
    return zeo
}

func (zeo *ZeroEvenOdd) zero(printNumber func(int)) {
    for num := 1; num <= zeo.n; num++ {
        <-zeo.zero
        printNumber(0)
        if num%2 == 1 {
            zeo.odd <- struct{}{}
        } else {
            zeo.even <- struct{}{}
        }
    }
}

func (zeo *ZeroEvenOdd) even(printNumber func(int)) {
    for num := 2; num <= zeo.n; num += 2 {
        <-zeo.even
        printNumber(num)
        zeo.zero <- struct{}{}
    }
}

func (zeo *ZeroEvenOdd) odd(printNumber func(int)) {
    for num := 1; num <= zeo.n; num += 2 {
        <-zeo.odd
        printNumber(num)
        zeo.zero <- struct{}{}
    }
}

复杂度分析

时间复杂度：$O(n)$，其中 n 表示需要打印的正整数数量。总共发生 2n 次打印，对应 2n 次许可获取和 2n 次释放，每次都是常数级操作，没有任何忙等或重试，因此总工作量与 n 成正比。

空间复杂度：$O(1)$，只维护三个信号量（Go 版是三个容量为 1 的 channel）和每个线程各自的循环变量，与 n 无关。

关键点总结

多线程顺序打印类问题的通用解法是「许可接力」：为每个角色配一个初值为 0 的信号量，只给第一个该执行的角色 1 个许可，然后让每个角色执行完毕后精确地把许可交给下一棒。识别出这个模式，1114、1115、1195 这类题都能一套模板打完。

显式写出「许可总数恒为 1」这条不变量，是论证正确性的最短路径。它一次性覆盖了互斥、顺序和无死锁三件事，面试时用这一句话就能把三个追问全部答掉，远胜逐条举例说明。

信号量优于 wait/notifyAll 的地方在于定向唤醒：notifyAll 会叫醒所有等待者，无效唤醒率随线程数上升；信号量的 release 只针对特定对象，被唤醒的线程一定是该执行的那个，也就不需要用 while 循环防虚假唤醒。

释放许可必须写在打印动作之后。同步原语的作用是划定临界区，一旦提前释放，接棒线程就可能与当前线程的打印语句交叠，输出顺序被破坏——这条「先做事、再交棒」的顺序在所有接力式同步里都成立。

让每个线程用自己的循环上界自然退出，不要引入额外的终止标志或毒丸消息。当每个角色的执行次数在编译期就能算清楚时，这是最简单也最不易出错的收尾方式，而多出来的那枚无人认领的许可不会造成任何问题。

Go 里用带缓冲 channel 模拟信号量是惯用法：容量 1 的 channel 收发一个空结构体，<-ch 对应 acquire，ch <- struct{}{} 对应 release，空结构体不占内存。面试写 Go 时能主动说出这个对应关系，比硬套 sync.Cond 更显熟练。

易错点总结

错误写法：三个信号量初值全给 0。用例 n = 1 → 三个线程都在 acquire 上阻塞，没有任何一枚许可可以流动，程序永久死锁，判题超时。

错误写法：zero 的初值给 1，同时 odd 的初值也给 1。用例 n = 2 → zero 和 odd 可能同时进入打印，输出可能变成 10 开头，且总量恒为 1 的不变量被破坏，后续顺序全乱。

错误写法：zero 里先 release 再 printNumber.accept(0)。用例 n = 1 → odd 被提前放行，可能在 0 打印之前就打印了 1，输出成 10 而非 01。

错误写法：zero 里用 if (num % 2 == 0) odd.release(); else even.release(); 把奇偶判断写反。用例 n = 1 → 许可被交给 even，而 even 在 n=1 时循环体一次都不执行，许可无人消费，odd 永远等不到自己的许可，死锁。

错误写法：odd 和 even 打印完后 release 的是自己而不是 zero。用例 n = 2 → odd 打印 1 后把许可还给自己，下一轮 num=3 已超上界不再 acquire，许可滞留，zero 永远拿不到许可，输出停在 01 后死锁。

错误写法：even 的循环写成 for (int num = 1; num <= n; num += 2)。用例 n = 4 → even 打印的是 1 和 3，odd 也打印 1 和 3，输出里全是奇数，偶数从未出现。

错误写法：zero 的循环上界写成 num < n。用例 n = 3 → 只打印 2 个 0 就退出，最后一个数字 3 的许可没人发放，odd 卡在第二轮 acquire 上永久阻塞。

错误写法：用一个共享 volatile int 计数器加忙等循环 while (cur % 2 != 0) {} 代替信号量。用例 n 较大时 → 虽然可能通过，但三个线程持续空转吃满 CPU，且没有任何内存屏障保护 printNumber 的调用时机，面试中会被直接判为不合格方案。

错误写法：Go 里三个 channel 都用无缓冲的 make(chan struct{})。用例 n = 1 → 构造函数里的 zeo.zero <- struct{}{} 在没有接收方时立刻阻塞，实例根本构造不出来，程序卡死在初始化阶段。

错误写法：Go 版把方法接收者写成值类型 func (zeo ZeroEvenOdd) zero(...)。用例任意 n → 虽然 channel 是引用语义仍能工作，但每次调用都复制整个结构体，若后续加入 sync.Mutex 等字段会被一并复制而失效，是隐患极大的写法。

错误写法：认为 zero 需要在结束时额外 release 一次来「唤醒」其他线程收尾。用例 n = 2 → 多放出的许可让 odd 或 even 的循环条件之外多消费一次，实际上它们早已退出，这枚许可只是浪费，但若误加在循环内则会导致多打印一个数字。

相似题目

题目	难度	考察点
1114. 按序打印	简单	只需一次性的三段顺序，没有循环轮转，是许可接力的最简形态
1115. 交替打印 FooBar	中等	两个角色的乒乓交替，交接对象固定，不需要按奇偶动态选择下一棒
1195. 多线程 Fizz Buzz	中等	四个角色且分派规则是整除条件，调度线程的分支判断更复杂
1226. 哲学家进餐	中等	从顺序控制转为资源竞争，重点是打破循环等待避免死锁而非定序
1188. 设计有限阻塞队列	中等	经典生产者消费者，用两个计数信号量表示空位与元素数，许可可大于 1
1242. 多线程网络爬虫	中等	考并发任务分发与去重，需要线程池和并发容器而非固定轮转
146. LRU 缓存	中等	单线程数据结构设计，面试常追问「如何改造成线程安全版本」
622. 设计循环队列	中等	环形缓冲区的边界判定，是实现阻塞队列前必须先掌握的底层结构
232. 用栈实现队列	简单	摊还分析与状态迁移，考察用受限原语拼出目标语义的思路
225. 用队列实现栈	简单	上题的对偶形式，训练「用已有同步/容器原语组合出新语义」的直觉