LeetCode 1195. 多线程 Fizz Buzz

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

题目描述

✅ 1195. 多线程 Fizz Buzz

image-20260928230307761

image-20260928230307762

题意分析

四个线程分别负责输出 fizz、buzz、fizzbuzz 和普通数字，整体仍要按整数 1 到 n 的顺序输出每一项。

同时被 3 和 5 整除时输出 fizzbuzz；只被 3 整除时输出 fizz，只被 5 整除时输出 buzz，其余输出整数本身。线程调度可以任意交错，但每个数必须恰好由对应线程输出一次，后一个数不能抢到前面。

解法：四个信号量协调执行权

核心思路

[!blue]

让 number 线程负责按数值递增顺序分派任务，其他三个线程等待自己负责的类别。设置四个执行许可，只有 numberSem 初始为一，其余为零，保证先由调度线程决定第一项交给谁。

number 每轮先获取许可。当前是普通数字时，自己打印并归还 numberSem；当前需要特殊文本时，把许可交给对应线程。下一轮开始前仍要获取 numberSem，所以会等上一项真正完成打印后才能继续。

专用线程获得自己的许可后只执行相应回调，打印结束才把许可归还 number。执行权始终只有一份，可能在同步对象中等待，也可能被某个回调的执行线程持有，因而不会出现两个数同时争抢输出顺序。

分派时先判断 15 的倍数，再判断 3、5。专用线程的循环次数也必须一致：fizz 跳过 15 的倍数，buzz 同样跳过，fizzbuzz 只等待这些共同倍数。它们的循环变量用于数清自己有多少次任务，全局次序仍由 number 控制。

最后一个特殊任务可能在 number 方法返回后才完成，因此整个调用要以四个方法全部完成为准。Java 信号量和 Go 容量为一的通道都能保存最后归还的许可，专用线程不会因为调度者不再领取而卡住，不需要额外结束消息。

解题步骤

  1. 创建四个同步对象，只有数字调度者初始持有一份许可。
  2. number 从 1 遍历到 n，每轮先等待调度许可。
  3. 依次按 15、3、5 的整除关系选择专用线程；普通数则自己打印并归还许可。
  4. 三个专用线程按各自实际负责的次数，反复等待、打印、归还调度许可。
  5. 全部数都输出完后，各线程完成规定次数并返回。

代码实现

class FizzBuzz {
    private final int n;
    private final java.util.concurrent.Semaphore numberSem = new java.util.concurrent.Semaphore(1);
    private final java.util.concurrent.Semaphore fizzSem = new java.util.concurrent.Semaphore(0);
    private final java.util.concurrent.Semaphore buzzSem = new java.util.concurrent.Semaphore(0);
    private final java.util.concurrent.Semaphore fizzbuzzSem =
            new java.util.concurrent.Semaphore(0);

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

    public void fizz(Runnable printFizz) throws InterruptedException {
        for (int i = 3; i <= n; i += 3) {
            // 十五的倍数交给专用线程，不为它多等待许可。
            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(java.util.function.IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i++) {
            numberSem.acquire();

            // 先判断共同倍数，避免被单独三或五的分支截走。
            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),
    }
    // 调度线程从此通道获取执行许可，每次最多保留一枚。
    fb.numberSem <- struct{}{}
    return fb
}

func (fb *FizzBuzz) Fizz(printFizz func()) {
    for i := 3; i <= fb.n; i += 3 {
        // 十五的倍数交给专用线程，不为它多等待许可。
        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
        // 先判断共同倍数，避免被单独三或五的分支截走。
        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)$。
  • 空间复杂度：$O(1)$，四个固定同步对象。

关键点总结

[!green]

  • 调度线程决定类别与顺序，专用线程完成对应回调，执行权通过许可交接。
  • 打印完成才归还，保证下一数字的放行不会先于当前输出。
  • 每个专用线程等待次数必须等于派发次数，避免漏输出或结束后仍阻塞。

易错点总结

[!yellow]

  • 先判断被 3 或 5 整除，会把共同倍数提前分配给单一类别，漏掉 fizzbuzz。
  • fizz、buzz 循环仍为共同倍数等待一次，会多等一个永远不会到来的许可。
  • 普通数字打印后忘记归还许可，调度者下一轮也会把自己阻塞。
  • 专用线程在回调之前就归还许可，下一项可能抢先输出。
  • Go 的通道改成无缓冲，初始放入许可或最后一次归还都可能阻塞。
  • 只等待 number 返回就认为全部完成，可能漏等最后一个仍在执行的专用回调。

相似题目

题目 难度 关联与区别
412. Fizz Buzz 简单 输出规则相同，本题重点是让不同职责线程按同一个数值顺序同步输出。
1116. 打印零与奇偶数 中等 同样由当前数值条件决定交给哪个线程，本题按3和5的整除规则分派。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/21474916
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！