LeetCode 1116. 打印零与奇偶数

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

题目描述

✅ 1116. 打印零与奇偶数

image-20260928225901778

image-20260928225901779

题意分析

三个线程共享同一个对象，分别负责打印零、奇数和偶数。要求依次在整数 1 到 n 前各打印一个零，所以共有 $2n$ 次 printNumber 调用；两位数及更大的整数仍作为一次完整调用输出。

线程启动和调度顺序无法决定打印顺序，需要显式交接执行许可：零线程打印后只唤醒本轮对应的奇数或偶数线程，数字线程打印完后再唤醒零线程。

解法：信号量同步

核心思路

[!blue]

zero、odd、even 三个信号量分别控制三个线程能否开始下一次打印。初始只有 zero 有一个许可，其余为零，因此无论哪个线程先启动，第一个实际打印的一定是零线程。acquire 取走许可，没有许可就等待；release 把许可交给下一方。

零线程的 num 表示本轮即将输出的非零数字。它先取得零许可并打印零，再按 num 的奇偶只放行对应线程；奇数线程的局部计数依次为奇数，偶数线程的局部计数依次为偶数，因此被放行的一方恰好输出本轮的 num。数字打印结束后才归还零许可，零线程才能开始下一轮。

整个过程只有一枚可用或正在持有的许可，打印期间不会让另一方同时进入。每一轮都严格完成“零、当前数字”后才能进入下一轮，归纳可知最终顺序符合要求，与线程的调度先后无关。

Go 用容量为一的通道保存同样的许可，接收对应等待，发送对应归还。缓冲可以保存构造时放入的初始许可，也能保存最后一个数字归还的许可，即使此时零线程已经结束也不会阻塞。

零线程打印 $n$ 次，奇数和偶数线程分别循环自己的数字个数，恰好消费所有定向许可；最后留在零信号量或通道中的许可无需再消费。n == 1 时偶数线程没有任务，循环直接结束。

解题步骤

  • 仅零线程初始可运行。
  • 零按一到 n 的轮次打印零并定向交接。
  • 奇数从一、偶数从二，以二为步长等待和打印。

代码实现

class ZeroEvenOdd {
    private final int n;
    private final java.util.concurrent.Semaphore zero = new java.util.concurrent.Semaphore(1);
    private final java.util.concurrent.Semaphore odd = new java.util.concurrent.Semaphore(0);
    private final java.util.concurrent.Semaphore even = new java.util.concurrent.Semaphore(0);

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

    public void zero(java.util.function.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(java.util.function.IntConsumer printNumber) throws InterruptedException {
        for (int num = 2; num <= n; num += 2) {
            even.acquire();
            printNumber.accept(num);
            // 数字打印完成再交回；最后的许可可以留在同步对象中。
            zero.release();
        }
    }

    public void odd(java.util.function.IntConsumer printNumber) throws InterruptedException {
        for (int num = 1; num <= n; num += 2) {
            odd.acquire();
            printNumber.accept(num);
            // 数字打印完成再交回；最后的许可可以留在同步对象中。
            zero.release();
        }
    }
}

type ZeroEvenOdd struct {
    n          int
    zeroPermit chan struct{}
    oddPermit  chan struct{}
    evenPermit chan struct{}
}

func Constructor(n int) ZeroEvenOdd {
    zeo := ZeroEvenOdd{
        n:          n,
        zeroPermit: make(chan struct{}, 1),
        oddPermit:  make(chan struct{}, 1),
        evenPermit: make(chan struct{}, 1),
    }
    // 零线程从此通道取得许可，容量一可保存初始与最后归还的许可。
    zeo.zeroPermit <- struct{}{}
    return zeo
}

func (zeo *ZeroEvenOdd) zero(printNumber func(int)) {
    for num := 1; num <= zeo.n; num++ {
        // 每个零都要等待上一个数字打印完成后交回的许可。
        <-zeo.zeroPermit
        printNumber(0)
        // 零打印完成后，只放行负责当前数字奇偶性的线程。
        if num%2 == 1 {
            zeo.oddPermit <- struct{}{}
        } else {
            zeo.evenPermit <- struct{}{}
        }
    }
}

func (zeo *ZeroEvenOdd) even(printNumber func(int)) {
    for num := 2; num <= zeo.n; num += 2 {
        <-zeo.evenPermit
        printNumber(num)
        // 零线程从此通道取得许可，容量一可保存初始与最后归还的许可。
        zeo.zeroPermit <- struct{}{}
    }
}

func (zeo *ZeroEvenOdd) odd(printNumber func(int)) {
    for num := 1; num <= zeo.n; num += 2 {
        <-zeo.oddPermit
        printNumber(num)
        // 零线程从此通道取得许可，容量一可保存初始与最后归还的许可。
        zeo.zeroPermit <- struct{}{}
    }
}

复杂度分析

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

关键点总结

[!green]

  • 打印零的轮次变量表示下一位数字，决定放行哪一方。
  • 最后归还给零线程的许可可留在同步对象中，不需要再消费。
  • 计数为2n次回调；数字达到两位时，不能把它等同于2n个输出字符。

易错点总结

[!yellow]

  • 奇偶目标放反会把许可交给没有本轮任务的线程。
  • 零少循环一次，最后一个数字就永远等不到放行。
  • Go 无缓冲通道沿用构造时塞初始许可，会在构造阶段阻塞。
  • 必须在当前数字打印完成后再归还零许可；先归还再打印，会允许下一轮的零抢先输出。

相似题目

题目 难度 关联与区别
1115. 交替打印 FooBar 中等 交替输出的同步框架相同，本题数字线程还需按奇偶选择接收许可。
1117. H2O 生成 中等 原题按2H与1O的比例成组且组内顺序可变，本题要求0与对应数字严格交替。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/75452796
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！