LeetCode Go · 并发（1）

返回题库与筛选 · 收录范围与使用说明

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 9 题 · 点击题目展开，先独立思考，再查看解法。

1114. 按序打印

简单1 种解法

标签：多线程

题目、示例与约束

给你一个类：

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

三个不同的线程 A、B、C 将会共用一个 Foo 实例。

• 线程 A 将会调用 first() 方法
• 线程 B 将会调用 second() 方法
• 线程 C 将会调用 third() 方法

请设计修改程序，以确保 second() 方法在 first() 方法之后被执行，third() 方法在 second() 方法之后被执行。

提示：

• 尽管输入中的数字似乎暗示了顺序，但是我们并不保证线程在操作系统中的调度顺序。
• 你看到的输入格式主要是为了确保测试的全面性。

 

示例 1：

输入：nums = [1,2,3]
输出："firstsecondthird"
解释：
有三个线程会被异步启动。输入 [1,2,3] 表示线程 A 将会调用 first() 方法，线程 B 将会调用 second() 方法，线程 C 将会调用 third() 方法。正确的输出是 "firstsecondthird"。

示例 2：

输入：nums = [1,3,2]
输出："firstsecondthird"
解释：
输入 [1,3,2] 表示线程 A 将会调用 first() 方法，线程 B 将会调用 third() 方法，线程 C 将会调用 second() 方法。正确的输出是 "firstsecondthird"。

 

提示：

• nums 是 [1, 2, 3] 的一组排列

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

基于 Doocs 参考改写：按 Python 两个完成许可的依赖链实现。First 输出后关闭 firstDone；Second 等待该通道关闭，输出后关闭 secondDone；Third 等待 secondDone。关闭与接收建立先行发生关系，不依赖 goroutine 的启动顺序。

变量与复杂度：两个通道分别代表前两步完成，三个方法各执行一次；时间、空间均 O(1)。

平台接口：Constructor() Foo；共享对象的 First、Second、Third 方法均接收 func() 打印回调，各由一条线程调用一次。并发对象应只构造一次，由所有 goroutine 共享，开始使用后不能复制。回调按题意假定会正常返回且不重入对象；复杂度不包含等待其他线程和回调自身的耗时。

出处与许可：基于 Doocs 原题及参考资料，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；Go 代码及本说明按 CC BY-SA 4.0 共享。

// 依据 Doocs/leetcode 题目与参考资料进行 Go 改写/整理。
// 来源：https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/1100-1199/1114.Print%20in%20Order/README.md
// 许可：CC BY-SA 4.0，https://creativecommons.org/licenses/by-sa/4.0/

type Foo struct{ firstDone, secondDone chan struct{} }

func Constructor() Foo                   { return Foo{make(chan struct{}), make(chan struct{})} }
func (f *Foo) First(printFirst func())   { printFirst(); close(f.firstDone) }
func (f *Foo) Second(printSecond func()) { <-f.firstDone; printSecond(); close(f.secondDone) }
func (f *Foo) Third(printThird func())   { <-f.secondDone; printThird() }

力扣原题 · Doocs 题解来源

1115. 交替打印 FooBar

中等1 种解法

标签：多线程

题目、示例与约束

给你一个类：

class FooBar {
  public void foo() {
    for (int i = 0; i < n; i++) {
      print("foo");
    }
  }

  public void bar() {
    for (int i = 0; i < n; i++) {
      print("bar");
    }
  }
}

两个不同的线程将会共用一个 FooBar 实例：

• 线程 A 将会调用 foo() 方法，而
• 线程 B 将会调用 bar() 方法

请设计修改程序，以确保 "foobar" 被输出 n 次。

 

示例 1：

输入：n = 1
输出："foobar"
解释：这里有两个线程被异步启动。其中一个调用 foo() 方法, 另一个调用 bar() 方法，"foobar" 将被输出一次。

示例 2：

输入：n = 2
输出："foobarfoobar"
解释："foobar" 将被输出两次。

 

提示：

• 1 <= n <= 1000

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

基于 Doocs 参考改写：将 Python 的两个信号量改写为容量为 1 的许可通道。foo 初始持有许可，输出后交给 bar，bar 输出后交还 foo；每条线程循环 n 次。最后一次交还许可仍可写入缓冲区，不会因对方退出而阻塞。

变量与复杂度：n 为重复次数，fooTurn、barTurn 表示下一步许可。总时间 O(n)，辅助空间 O(1)。

平台接口：Constructor(n int) FooBar，Foo(printFoo func())、Bar(printBar func()) 分别由两个 goroutine 各调用一次。并发对象应只构造一次，由所有 goroutine 共享，开始使用后不能复制。回调按题意假定会正常返回且不重入对象；复杂度不包含等待其他线程和回调自身的耗时。

出处与许可：基于 Doocs 原题及参考资料，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；Go 代码及本说明按 CC BY-SA 4.0 共享。

// 依据 Doocs/leetcode 题目与参考资料进行 Go 改写/整理。
// 来源：https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/1100-1199/1115.Print%20FooBar%20Alternately/README.md
// 许可：CC BY-SA 4.0，https://creativecommons.org/licenses/by-sa/4.0/

type FooBar struct {
	n                int
	fooTurn, barTurn chan struct{}
}

func Constructor(n int) FooBar {
	f := FooBar{n, make(chan struct{}, 1), make(chan struct{}, 1)}
	f.fooTurn <- struct{}{}
	return f
}
func (f *FooBar) Foo(printFoo func()) {
	for i := 0; i < f.n; i++ {
		<-f.fooTurn
		printFoo()
		f.barTurn <- struct{}{}
	}
}
func (f *FooBar) Bar(printBar func()) {
	for i := 0; i < f.n; i++ {
		<-f.barTurn
		printBar()
		f.fooTurn <- struct{}{}
	}
}

力扣原题 · Doocs 题解来源

1116. 打印零与奇偶数

中等1 种解法

标签：多线程

题目、示例与约束

现有函数 printNumber 可以用一个整数参数调用，并输出该整数到控制台。

• 例如，调用 printNumber(7) 将会输出 7 到控制台。

给你类 ZeroEvenOdd 的一个实例，该类中有三个函数：zero、even 和 odd 。ZeroEvenOdd 的相同实例将会传递给三个不同线程：

• 线程 A：调用 zero() ，只输出 0
• 线程 B：调用 even() ，只输出偶数
• 线程 C：调用 odd() ，只输出奇数

修改给出的类，以输出序列 "010203040506..." ，其中序列的长度必须为 2n 。

实现 ZeroEvenOdd 类：

• ZeroEvenOdd(int n) 用数字 n 初始化对象，表示需要输出的数。
• void zero(printNumber) 调用 printNumber 以输出一个 0 。
• void even(printNumber) 调用printNumber 以输出偶数。
• void odd(printNumber) 调用 printNumber 以输出奇数。

 

示例 1：

输入：n = 2
输出："0102"
解释：三条线程异步执行，其中一个调用 zero()，另一个线程调用 even()，最后一个线程调用odd()。正确的输出为 "0102"。

示例 2：

输入：n = 5
输出："0102030405"

 

提示：

• 1 <= n <= 1000

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

基于 Doocs 参考改写：把 Python 三个信号量改写为容量 1 的通道。Zero 每次输出零后，按下一个整数的奇偶选择 oddTurn 或 evenTurn；对应线程输出数字再交回 zeroTurn。只由 Zero 决定次序，奇数与偶数线程不竞争同一许可。

变量与复杂度：n 为最大输出整数，三条许可通道控制相应步骤。共输出 2n 次，时间 O(n)，空间 O(1)。

平台接口：Constructor(n int) ZeroEvenOdd；Zero、Even、Odd 均接受 func(int)，由三条 goroutine 各调用一次。并发对象应只构造一次，由所有 goroutine 共享，开始使用后不能复制。回调按题意假定会正常返回且不重入对象；复杂度不包含等待其他线程和回调自身的耗时。

出处与许可：基于 Doocs 原题及参考资料，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；Go 代码及本说明按 CC BY-SA 4.0 共享。

// 依据 Doocs/leetcode 题目与参考资料进行 Go 改写/整理。
// 来源：https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/1100-1199/1116.Print%20Zero%20Even%20Odd/README.md
// 许可：CC BY-SA 4.0，https://creativecommons.org/licenses/by-sa/4.0/

type ZeroEvenOdd struct {
	n                           int
	zeroTurn, evenTurn, oddTurn chan struct{}
}

func Constructor(n int) ZeroEvenOdd {
	z := ZeroEvenOdd{n, make(chan struct{}, 1), make(chan struct{}, 1), make(chan struct{}, 1)}
	z.zeroTurn <- struct{}{}
	return z
}
func (z *ZeroEvenOdd) Zero(printNumber func(int)) {
	for i := 1; i <= z.n; i++ {
		<-z.zeroTurn
		printNumber(0)
		if i%2 == 0 {
			z.evenTurn <- struct{}{}
		} else {
			z.oddTurn <- struct{}{}
		}
	}
}
func (z *ZeroEvenOdd) Even(printNumber func(int)) {
	for i := 2; i <= z.n; i += 2 {
		<-z.evenTurn
		printNumber(i)
		z.zeroTurn <- struct{}{}
	}
}
func (z *ZeroEvenOdd) Odd(printNumber func(int)) {
	for i := 1; i <= z.n; i += 2 {
		<-z.oddTurn
		printNumber(i)
		z.zeroTurn <- struct{}{}
	}
}

力扣原题 · Doocs 题解来源

1117. H2O 生成

中等1 种解法

标签：多线程

题目、示例与约束

现在有两种线程，氧 oxygen 和氢 hydrogen，你的目标是组织这两种线程来产生水分子。

存在一个屏障（barrier）使得每个线程必须等候直到一个完整水分子能够被产生出来。

氢和氧线程会被分别给予 releaseHydrogen 和 releaseOxygen 方法来允许它们突破屏障。

这些线程应该三三成组突破屏障并能立即组合产生一个水分子。

你必须保证产生一个水分子所需线程的结合必须发生在下一个水分子产生之前。

换句话说:

• 如果一个氧线程到达屏障时没有氢线程到达，它必须等候直到两个氢线程到达。
• 如果一个氢线程到达屏障时没有其它线程到达，它必须等候直到一个氧线程和另一个氢线程到达。

书写满足这些限制条件的氢、氧线程同步代码。

 

示例 1:

输入: water = "HOH"
输出: "HHO"
解释: "HOH" 和 "OHH" 依然都是有效解。

示例 2:

输入: water = "OOHHHH"
输出: "HHOHHO"
解释: "HOHHHO", "OHHHHO", "HHOHOH", "HOHHOH", "OHHHOH", "HHOOHH", "HOHOHH" 和 "OHHOHH" 依然都是有效解。

 

提示：

• 3 * n == water.length
• 1 <= n <= 20
• water[i] == 'O' or 'H'
• 输入字符串 water 中的 'H' 总数将会是 2 * n 。
• 输入字符串 water 中的 'O' 总数将会是 n 。

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

基于 Doocs 参考改写：沿用参考解每轮两个氢、一个氧的分组规则，使用互斥锁与条件变量显式实现可复用屏障，避免读取信号量内部计数或无锁累加。线程先占本轮对应元素名额；未凑齐 2H+1O 时等待。凑齐后在锁内逐个执行回调，三个回调都完成才重置名额，下一轮才能加入，因此未凑齐的分子不会提前释放，两个分子的输出也不会交错。

变量与复杂度：h、o 为本轮到达数量，released 为已执行回调数；n 为分子数。有效回调与计数更新共 O(n)，对象空间 O(1)；Broadcast 会唤醒等待者，调度/唤醒开销随竞争线程数变化，不计入固定操作数。

平台接口：Constructor() *H2O 返回指针，避免复制已关联条件变量的锁。Hydrogen(releaseHydrogen func()) 与 Oxygen(releaseOxygen func()) 每个原子线程调用一次。并发对象应只构造一次，由所有 goroutine 共享，开始使用后不能复制。回调按题意假定会正常返回且不重入对象；复杂度不包含等待其他线程和回调自身的耗时。

出处与许可：基于 Doocs 原题及参考资料，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；Go 代码及本说明按 CC BY-SA 4.0 共享。

// 依据 Doocs/leetcode 题目与参考资料进行 Go 改写/整理。
// 来源：https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/1100-1199/1117.Building%20H2O/README.md
// 许可：CC BY-SA 4.0，https://creativecommons.org/licenses/by-sa/4.0/

import "sync"

type H2O struct {
	mu             sync.Mutex
	changed        *sync.Cond
	h, o, released int
}

func Constructor() *H2O                        { w := &H2O{}; w.changed = sync.NewCond(&w.mu); return w }
func (w *H2O) Hydrogen(releaseHydrogen func()) { w.arrive(true, releaseHydrogen) }
func (w *H2O) Oxygen(releaseOxygen func())     { w.arrive(false, releaseOxygen) }
func (w *H2O) arrive(hydrogen bool, release func()) {
	w.mu.Lock()
	defer w.mu.Unlock()
	for (hydrogen && w.h == 2) || (!hydrogen && w.o == 1) {
		w.changed.Wait()
	}
	if hydrogen {
		w.h++
	} else {
		w.o++
	}
	if w.h == 2 && w.o == 1 {
		w.changed.Broadcast()
	}
	for w.h < 2 || w.o < 1 {
		w.changed.Wait()
	}
	release()
	w.released++
	if w.released == 3 {
		w.h, w.o, w.released = 0, 0, 0
		w.changed.Broadcast()
	}
}

力扣原题 · Doocs 题解来源

1188. 设计有限阻塞队列 🔒

中等1 种解法

标签：多线程

题目、示例与约束

实现一个拥有如下方法的线程安全有限阻塞队列：

• BoundedBlockingQueue(int capacity) 构造方法初始化队列，其中capacity代表队列长度上限。
• void enqueue(int element) 在队首增加一个element. 如果队列满，调用线程被阻塞直到队列非满。
• int dequeue() 返回队尾元素并从队列中将其删除. 如果队列为空，调用线程被阻塞直到队列非空。
• int size() 返回当前队列元素个数。

你的实现将会被多线程同时访问进行测试。每一个线程要么是一个只调用enqueue方法的生产者线程，要么是一个只调用dequeue方法的消费者线程。size方法将会在每一个测试用例之后进行调用。

请不要使用内置的有限阻塞队列实现，否则面试将不会通过。

 

示例 1:

输入:
1
1
["BoundedBlockingQueue","enqueue","dequeue","dequeue","enqueue","enqueue","enqueue","enqueue","dequeue"]
[[2],[1],[],[],[0],[2],[3],[4],[]]

输出:
[1,0,2,2]

解释:
生产者线程数目 = 1
消费者线程数目 = 1

BoundedBlockingQueue queue = new BoundedBlockingQueue(2);   // 使用capacity = 2初始化队列。

queue.enqueue(1);   // 生产者线程将 1 插入队列。
queue.dequeue();    // 消费者线程调用 dequeue 并返回 1 。
queue.dequeue();    // 由于队列为空，消费者线程被阻塞。
queue.enqueue(0);   // 生产者线程将 0 插入队列。消费者线程被解除阻塞同时将 0 弹出队列并返回。
queue.enqueue(2);   // 生产者线程将 2 插入队列。
queue.enqueue(3);   // 生产者线程将 3 插入队列。
queue.enqueue(4);   // 生产者线程由于队列长度已达到上限 2 而被阻塞。
queue.dequeue();    // 消费者线程将 2 从队列弹出并返回。生产者线程解除阻塞同时将4插入队列。
queue.size();       // 队列中还有 2 个元素。size()方法在每组测试用例最后调用。

 

示例 2:

输入:
3
4
["BoundedBlockingQueue","enqueue","enqueue","enqueue","dequeue","dequeue","dequeue","enqueue"]
[[3],[1],[0],[2],[],[],[],[3]]

输出:
[1,0,2,1]

解释:
生产者线程数目 = 3
消费者线程数目 = 4

BoundedBlockingQueue queue = new BoundedBlockingQueue(3);   // 使用capacity = 3初始化队列。

queue.enqueue(1);   // 生产者线程 P1 将 1 插入队列。
queue.enqueue(0);   // 生产者线程 P2 将 0 插入队列。
queue.enqueue(2);   // 生产者线程 P3 将2插入队列。
queue.dequeue();    // 消费者线程 C1 调用 dequeue。
queue.dequeue();    // 消费者线程 C2 调用 dequeue。
queue.dequeue();    // 消费者线程 C3 调用 dequeue。
queue.enqueue(3);   // 其中一个生产者线程将3插入队列。
queue.size();       // 队列中还有 1 个元素。

由于生产者/消费者线程的数目可能大于 1 ，我们并不知道线程如何被操作系统调度，即使输入看上去隐含了顺序。因此任意一种输出[1,0,2]或[1,2,0]或[0,1,2]或[0,2,1]或[2,0,1]或[2,1,0]都可被接受。

 

提示:

• 1 <= Number of Prdoucers <= 8
• 1 <= Number of Consumers <= 8
• 1 <= size <= 30
• 0 <= element <= 20
•  enqueue的调用次数 大于等于  dequeue 的调用次数。
•  enque, deque 和 size 最多被调用 40 次

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

基于 Doocs 参考改写：沿用空位/元素许可控制有界 FIFO 的参考思路，但 Go 中底层队列也必须互斥，不能照抄参考代码的无锁容器操作。使用固定容量环形切片、互斥锁、notEmpty/notFull 条件变量；入队遇满、出队遇空时循环等待，改变数量后唤醒另一方。Size 也加锁读取。未使用内置阻塞队列，元素存储不是 channel。

变量与复杂度：capacity 为容量，head 为最旧元素下标，count 为当前数量，尾部位置为 (head+count)%capacity。单次入队、出队、Size 的有效操作 O(1)，空间 O(capacity)，等待时间取决于生产者/消费者。

平台接口：Constructor(capacity int) *BoundedBlockingQueue；Enqueue(element int)、Dequeue() int、Size() int。返回指针以稳定条件变量所用锁地址。并发对象应只构造一次，由所有 goroutine 共享，开始使用后不能复制。回调按题意假定会正常返回且不重入对象；复杂度不包含等待其他线程和回调自身的耗时。

出处与许可：基于 Doocs 原题及参考资料，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；Go 代码及本说明按 CC BY-SA 4.0 共享。

// 依据 Doocs/leetcode 题目与参考资料进行 Go 改写/整理。
// 来源：https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/1100-1199/1188.Design%20Bounded%20Blocking%20Queue/README.md
// 许可：CC BY-SA 4.0，https://creativecommons.org/licenses/by-sa/4.0/

import "sync"

type BoundedBlockingQueue struct {
	mu                sync.Mutex
	notEmpty, notFull *sync.Cond
	data              []int
	head, count       int
}

func Constructor(capacity int) *BoundedBlockingQueue {
	q := &BoundedBlockingQueue{data: make([]int, capacity)}
	q.notEmpty = sync.NewCond(&q.mu)
	q.notFull = sync.NewCond(&q.mu)
	return q
}
func (q *BoundedBlockingQueue) Enqueue(element int) {
	q.mu.Lock()
	defer q.mu.Unlock()
	for q.count == len(q.data) {
		q.notFull.Wait()
	}
	q.data[(q.head+q.count)%len(q.data)] = element
	q.count++
	q.notEmpty.Signal()
}
func (q *BoundedBlockingQueue) Dequeue() int {
	q.mu.Lock()
	defer q.mu.Unlock()
	for q.count == 0 {
		q.notEmpty.Wait()
	}
	value := q.data[q.head]
	q.head = (q.head + 1) % len(q.data)
	q.count--
	q.notFull.Signal()
	return value
}
func (q *BoundedBlockingQueue) Size() int { q.mu.Lock(); defer q.mu.Unlock(); return q.count }

力扣原题 · Doocs 题解来源

1195. 多线程 Fizz Buzz

中等1 种解法

标签：多线程

题目、示例与约束

编写一个可以从 1 到 n 输出代表这个数字的字符串的程序，但是：

• 如果这个数字可以被 3 整除，输出 "fizz"。
• 如果这个数字可以被 5 整除，输出 "buzz"。
• 如果这个数字可以同时被 3 和 5 整除，输出 "fizzbuzz"。

例如，当 n = 15，输出： 1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz。

假设有这么一个类：

class FizzBuzz {
  public FizzBuzz(int n) { ... }               // constructor
  public void fizz(printFizz) { ... }          // only output "fizz"
  public void buzz(printBuzz) { ... }          // only output "buzz"
  public void fizzbuzz(printFizzBuzz) { ... }  // only output "fizzbuzz"
  public void number(printNumber) { ... }      // only output the numbers
}

请你实现一个有四个线程的多线程版  FizzBuzz， 同一个 FizzBuzz 实例会被如下四个线程使用：

1. 线程A将调用 fizz() 来判断是否能被 3 整除，如果可以，则输出 fizz。
2. 线程B将调用 buzz() 来判断是否能被 5 整除，如果可以，则输出 buzz。
3. 线程C将调用 fizzbuzz() 来判断是否同时能被 3 和 5 整除，如果可以，则输出 fizzbuzz。
4. 线程D将调用 number() 来实现输出既不能被 3 整除也不能被 5 整除的数字。

 

提示：

• 本题已经提供了打印字符串的相关方法，如 printFizz() 等，具体方法名请参考答题模板中的注释部分。

 

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

基于 Doocs 参考改写：采用源 Java 的四信号量方案，Go 用容量 1 的通道表示许可。Number 顺序处理 1..n，遇到 3/5/15 的倍数时交给对应线程；对应回调完成后交还 numberTurn。其他数字由 Number 自己输出并交还许可。每条线程预先知道自己的工作次数，因此无需忙等或额外终止消息。

变量与复杂度：n 为终点，numberTurn 是主许可，fizzTurn、buzzTurn、bothTurn 对应特殊输出。总时间 O(n)，空间 O(1)。

平台接口：Constructor(n int) FizzBuzz；Fizz、Buzz、Fizzbuzz 接收 func()，Number 接收 func(int)，四条 goroutine 各调用一个方法一次。并发对象应只构造一次，由所有 goroutine 共享，开始使用后不能复制。回调按题意假定会正常返回且不重入对象；复杂度不包含等待其他线程和回调自身的耗时。

出处与许可：基于 Doocs 原题及参考资料，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；Go 代码及本说明按 CC BY-SA 4.0 共享。

// 依据 Doocs/leetcode 题目与参考资料进行 Go 改写/整理。
// 来源：https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/1100-1199/1195.Fizz%20Buzz%20Multithreaded/README.md
// 许可：CC BY-SA 4.0，https://creativecommons.org/licenses/by-sa/4.0/

type FizzBuzz struct {
	n                                        int
	numberTurn, fizzTurn, buzzTurn, bothTurn chan struct{}
}

func Constructor(n int) FizzBuzz {
	f := FizzBuzz{n, make(chan struct{}, 1), make(chan struct{}, 1), make(chan struct{}, 1), make(chan struct{}, 1)}
	f.numberTurn <- struct{}{}
	return f
}
func (f *FizzBuzz) Fizz(printFizz func()) {
	for i := 3; i <= f.n; i += 3 {
		if i%5 != 0 {
			<-f.fizzTurn
			printFizz()
			f.numberTurn <- struct{}{}
		}
	}
}
func (f *FizzBuzz) Buzz(printBuzz func()) {
	for i := 5; i <= f.n; i += 5 {
		if i%3 != 0 {
			<-f.buzzTurn
			printBuzz()
			f.numberTurn <- struct{}{}
		}
	}
}
func (f *FizzBuzz) Fizzbuzz(printFizzBuzz func()) {
	for i := 15; i <= f.n; i += 15 {
		<-f.bothTurn
		printFizzBuzz()
		f.numberTurn <- struct{}{}
	}
}
func (f *FizzBuzz) Number(printNumber func(int)) {
	for i := 1; i <= f.n; i++ {
		<-f.numberTurn
		switch {
		case i%15 == 0:
			f.bothTurn <- struct{}{}
		case i%3 == 0:
			f.fizzTurn <- struct{}{}
		case i%5 == 0:
			f.buzzTurn <- struct{}{}
		default:
			printNumber(i)
			f.numberTurn <- struct{}{}
		}
	}
}

力扣原题 · Doocs 题解来源

1226. 哲学家进餐

中等1 种解法

标签：多线程

题目、示例与约束

5 个沉默寡言的哲学家围坐在圆桌前，每人面前一盘意面。叉子放在哲学家之间的桌面上。（5 个哲学家，5 根叉子）

所有的哲学家都只会在思考和进餐两种行为间交替。哲学家只有同时拿到左边和右边的叉子才能吃到面，而同一根叉子在同一时间只能被一个哲学家使用。每个哲学家吃完面后都需要把叉子放回桌面以供其他哲学家吃面。只要条件允许，哲学家可以拿起左边或者右边的叉子，但在没有同时拿到左右叉子时不能进食。

假设面的数量没有限制，哲学家也能随便吃，不需要考虑吃不吃得下。

设计一个进餐规则（并行算法）使得每个哲学家都不会挨饿；也就是说，在没有人知道别人什么时候想吃东西或思考的情况下，每个哲学家都可以在吃饭和思考之间一直交替下去。

问题描述和图片来自维基百科 wikipedia.org

 

哲学家从 0 到 4 按 顺时针 编号。请实现函数 void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)：

• philosopher 哲学家的编号。
• pickLeftFork 和 pickRightFork 表示拿起左边或右边的叉子。
• eat 表示吃面。
• putLeftFork 和 putRightFork 表示放下左边或右边的叉子。
• 由于哲学家不是在吃面就是在想着啥时候吃面，所以思考这个方法没有对应的回调。

给你 5 个线程，每个都代表一个哲学家，请你使用类的同一个对象来模拟这个过程。在最后一次调用结束之前，可能会为同一个哲学家多次调用该函数。

 

示例：

输入：n = 1
输出：[[3,2,1],[3,1,1],[3,0,3],[3,1,2],[3,2,2],[4,2,1],[4,1,1],[2,2,1],[2,1,1],[1,2,1],[2,0,3],[2,1,2],[2,2,2],[4,0,3],[4,1,2],[4,2,2],[1,1,1],[1,0,3],[1,1,2],[1,2,2],[0,1,1],[0,2,1],[0,0,3],[0,1,2],[0,2,2]]
解释:
n 表示每个哲学家需要进餐的次数。
输出数组描述了叉子的控制和进餐的调用，它的格式如下：
output[i] = [a, b, c] (3个整数)
- a 哲学家编号。
- b 指定叉子：{1 : 左边, 2 : 右边}.
- c 指定行为：{1 : 拿起, 2 : 放下, 3 : 吃面}。
如 [4,2,1] 表示 4 号哲学家拿起了右边的叉子。

 

提示：

• 1 <= n <= 60

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

基于 Doocs 参考改写：保留 C++ 参考的核心规则：就餐期间独占本人的两把叉，拿叉、吃饭、放叉回调都在占有期内。Go 用互斥锁下的叉子占用表和条件变量原子取得两把叉，不发生各拿一把的循环等待；额外以递增票号按到达顺序准入，防止后来的请求持续抢先。已准入者执行回调时不占管理锁，因此不相邻的哲学家仍可同时进餐。有限回调与正常调度假设下，每个票号最终会获准。

变量与复杂度：busy[5] 为叉子占用状态，next 为下个票号，serving 为当前可准入票号；哲学家 p 使用叉子 p 和 (p+1)%5。每次就餐的有效操作 O(1)，对象空间 O(1)，不计条件等待和广播唤醒开销。票号顺序可能产生队首等待，但题目最多 5 位哲学家、每位 60 次，避免忙等。

平台接口：Constructor() *DiningPhilosophers；WantsToEat(philosopher int, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork func())。并发对象应只构造一次，由所有 goroutine 共享，开始使用后不能复制。回调按题意假定会正常返回且不重入对象；复杂度不包含等待其他线程和回调自身的耗时。

出处与许可：基于 Doocs 原题及参考资料，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；Go 代码及本说明按 CC BY-SA 4.0 共享。

// 依据 Doocs/leetcode 题目与参考资料进行 Go 改写/整理。
// 来源：https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/1200-1299/1226.The%20Dining%20Philosophers/README.md
// 许可：CC BY-SA 4.0，https://creativecommons.org/licenses/by-sa/4.0/

import "sync"

type DiningPhilosophers struct {
	mu            sync.Mutex
	changed       *sync.Cond
	busy          [5]bool
	next, serving uint64
}

func Constructor() *DiningPhilosophers {
	d := &DiningPhilosophers{}
	d.changed = sync.NewCond(&d.mu)
	return d
}
func (d *DiningPhilosophers) WantsToEat(philosopher int, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork func()) {
	left, right := philosopher, (philosopher+1)%5
	d.mu.Lock()
	ticket := d.next
	d.next++
	for ticket != d.serving || d.busy[left] || d.busy[right] {
		d.changed.Wait()
	}
	d.busy[left], d.busy[right] = true, true
	d.serving++
	d.changed.Broadcast()
	d.mu.Unlock()
	pickLeftFork()
	pickRightFork()
	eat()
	putLeftFork()
	putRightFork()
	d.mu.Lock()
	d.busy[left], d.busy[right] = false, false
	d.changed.Broadcast()
	d.mu.Unlock()
}

力扣原题 · Doocs 题解来源

1242. 多线程网络爬虫 🔒

中等1 种解法

标签：深度优先搜索、广度优先搜索、多线程

题目、示例与约束

给你一个初始地址 startUrl 和一个 HTML 解析器接口 HtmlParser，请你实现一个 多线程的网页爬虫，用于获取与 startUrl 有 相同域名 的所有链接。 

以 任意 顺序返回爬虫获取的路径。

爬虫应该遵循：

• 从 startUrl 开始
• 调用 HtmlParser.getUrls(url) 从指定网页路径获得的所有路径。
• 不要抓取相同的链接两次。
• 仅浏览与 startUrl 相同域名 的链接。

如上图所示，域名是 example.org 。简单起见，你可以假设所有链接都采用 http 协议，并且没有指定 端口号。举个例子，链接 http://leetcode.com/problems 和链接 http://leetcode.com/contest 属于同一个 域名， 而 http://example.org/test 与 http://example.com/abc 并不属于同一个 域名。

HtmlParser 的接口定义如下：

interface HtmlParser {
  // Return a list of all urls from a webpage of given url.
  // This is a blocking call, that means it will do HTTP request and return when this request is finished.
  public List<String> getUrls(String url);
}

注意一点，getUrls(String url) 模拟执行一个HTTP的请求。 你可以将它当做一个阻塞式的方法，直到请求结束。 getUrls(String url) 保证会在 15ms 内返回所有的路径。 单线程的方案会超过时间限制，你能用多线程方案做的更好吗？

对于问题所需的功能，下面提供了两个例子。为了方便自定义测试，你可以声明三个变量 urls，edges 和 startUrl。但要注意你只能在代码中访问 startUrl，并不能直接访问 urls 和 edges。

 

拓展问题：

1. 假设我们要要抓取 10000 个节点和 10 亿个路径。并且在每个节点部署相同的的软件。软件可以发现所有的节点。我们必须尽可能减少机器之间的通讯，并确保每个节点负载均衡。你将如何设计这个网页爬虫？
2. 如果有一个节点发生故障不工作该怎么办？
3. 如何确认爬虫任务已经完成？

 

示例 1：

输入：
urls = [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.google.com",
  "http://news.yahoo.com/us"
]
edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl = "http://news.yahoo.com/news/topics/"
输出：[
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.yahoo.com/us"
]

示例 2：

输入：
urls = [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.google.com"
]
edges = [[0,2],[2,1],[3,2],[3,1],[3,0]]
startUrl = "http://news.google.com"
输出：["http://news.google.com"]
解释：startUrl 链接与其他页面不共享一个域名。

 

提示：

• 1 <= urls.length <= 1000
• 1 <= urls[i].length <= 300
• startUrl 是 urls 中的一个。
• 域名的长度必须为 1 到 63 个字符（包括点 . 在内），只能包含从 “a” 到 “z” 的 ASCII 字母和 “0” 到 “9” 的数字，以及中划线 “-”。
• 域名开头和结尾不能是中划线 “-”。
• 参考资料：https://en.wikipedia.org/wiki/Hostname#Restrictions_on_valid_hostnames
• 你可以假设路径都是不重复的。

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

根据题意整理：本地 Doocs 实现围栏为空。按其思考中的并发抓取、同主机过滤和去重原则实现：8 个工作 goroutine 只调用平台解析器；调度 goroutine 独占 seen、待处理队列和正在抓取数，避免集合数据竞争。通过 select 同时分发任务、接收结果，不让工作线程因向满任务队列回填而死锁。完整比较 URL 的 Hostname，不能用字符串前缀判断域名。队列为空且运行数为零才结束，并等待工作 goroutine 退出。

变量与复杂度：V 为可达同域网页数，E 为这些页面返回的链接总数，L 为链接最大长度，P=8 为并发上限。调度和解析时间 O((V+E)L)，网络模拟等待由最多 P 个任务分摊；总辅助空间 O((V+E)L)，包括去重集合、队列和在途返回值。每页只解析一次。

平台接口：crawl(startUrl string, htmlParser HtmlParser) []string；平台提供 HtmlParser 及 GetUrls(url string) []string。解析器须允许从多个 goroutine 调用；其内部可以串行处理，只要每次调用正常返回，调度器就不会依赖回调同时执行。测试另有串行解析器用例。源码本身不发网络请求，测试提供线程安全的本地 mock；返回顺序不限。

出处与许可：基于 Doocs 原题及参考资料，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；Go 代码及本说明按 CC BY-SA 4.0 共享。

// 依据 Doocs/leetcode 题目与参考资料进行 Go 改写/整理。
// 来源：https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/1200-1299/1242.Web%20Crawler%20Multithreaded/README.md
// 许可：CC BY-SA 4.0，https://creativecommons.org/licenses/by-sa/4.0/

import (
	"net/url"
	"sync"
)

func crawl(startUrl string, htmlParser HtmlParser) []string {
	start, _ := url.Parse(startUrl)
	jobs := make(chan string)
	results := make(chan []string, 8)
	var workers sync.WaitGroup
	for i := 0; i < 8; i++ {
		workers.Add(1)
		go func() {
			defer workers.Done()
			for page := range jobs {
				results <- htmlParser.GetUrls(page)
			}
		}()
	}
	seen := map[string]bool{startUrl: true}
	pending := []string{startUrl}
	answer := []string{startUrl}
	active := 0
	for len(pending) > 0 || active > 0 {
		var output chan string
		next := ""
		if len(pending) > 0 {
			output = jobs
			next = pending[0]
		}
		select {
		case output <- next:
			pending = pending[1:]
			active++
		case links := <-results:
			active--
			for _, link := range links {
				parsed, err := url.Parse(link)
				if err != nil || parsed.Hostname() != start.Hostname() || seen[link] {
					continue
				}
				seen[link] = true
				pending = append(pending, link)
				answer = append(answer, link)
			}
		}
	}
	close(jobs)
	workers.Wait()
	return answer
}

力扣原题 · Doocs 题解来源

1279. 红绿灯路口 🔒

简单1 种解法

标签：多线程

题目、示例与约束

这是两条路的交叉路口。第一条路是 A 路，车辆可沿 1 号方向由北向南行驶，也可沿 2 号方向由南向北行驶。第二条路是 B 路，车辆可沿 3 号方向由西向东行驶，也可沿 4 号方向由东向西行驶。

每条路在路口前都有一个红绿灯。红绿灯可以亮起红灯或绿灯。

1. 绿灯表示两个方向的车辆都可通过路口。
2. 红灯表示两个方向的车辆都不可以通过路口，必须等待绿灯亮起。

两条路上的红绿灯不可以同时为绿灯。这意味着，当 A 路上的绿灯亮起时，B 路上的红灯会亮起；当 B 路上的绿灯亮起时，A 路上的红灯会亮起.

开始时，A 路上的绿灯亮起，B 路上的红灯亮起。当一条路上的绿灯亮起时，所有车辆都可以从任意两个方向通过路口，直到另一条路上的绿灯亮起。不同路上的车辆不可以同时通过路口。

给这个路口设计一个没有死锁的红绿灯控制系统。

实现函数 void carArrived(carId, roadId, direction, turnGreen, crossCar) :

• carId 为到达车辆的编号。
• roadId 为车辆所在道路的编号。
• direction 为车辆的行进方向。
• turnGreen 是一个函数，调用此函数会使当前道路上的绿灯亮起。
• crossCar 是一个函数，调用此函数会允许车辆通过路口。

当你的答案避免了车辆在路口出现死锁，此答案会被认定为正确的。当路口已经亮起绿灯时仍打开绿灯，此答案会被认定为错误的。

 

示例 1:

输入: cars = [1,3,5,2,4], directions = [2,1,2,4,3], arrivalTimes = [10,20,30,40,50]
输出: [
"Car 1 Has Passed Road A In Direction 2",    // A 路上的红绿灯为绿色，1 号车可通过路口。
"Car 3 Has Passed Road A In Direction 1",    // 红绿灯仍为绿色，3 号车通过路口。
"Car 5 Has Passed Road A In Direction 2",    // 红绿灯仍为绿色，5 号车通过路口。
"Traffic Light On Road B Is Green",          // 2 号车在 B 路请求绿灯。
"Car 2 Has Passed Road B In Direction 4",    // B 路上的绿灯现已亮起，2 号车通过路口。
"Car 4 Has Passed Road B In Direction 3"     // 红绿灯仍为绿色，4 号车通过路口。
]

示例 2:

输入: cars = [1,2,3,4,5], directions = [2,4,3,3,1], arrivalTimes = [10,20,30,40,40]
输出: [
"Car 1 Has Passed Road A In Direction 2",    // A 路上的红绿灯为绿色，1 号车可通过路口。
"Traffic Light On Road B Is Green",          // 2 号车在 B 路请求绿灯。
"Car 2 Has Passed Road B In Direction 4",    // B 路上的绿灯现已亮起，2 号车通过路口。
"Car 3 Has Passed Road B In Direction 3",    // B 路上的绿灯现已亮起，3 号车通过路口。
"Traffic Light On Road A Is Green",          // 5 号车在 A 路请求绿灯。
"Car 5 Has Passed Road A In Direction 1",    // A 路上的绿灯现已亮起，5 号车通过路口。
"Traffic Light On Road B Is Green",          // 4 号车在 B 路请求绿灯。4 号车在路口等灯，直到 5 号车通过路口，B 路的绿灯亮起。
"Car 4 Has Passed Road B In Direction 3"     // B 路上的绿灯现已亮起，4 号车通过路口。
]
解释: 这是一个无死锁的方案。注意，在 A 路上的绿灯亮起、5 号车通过前让 4 号车通过，也是一个正确且可被接受的方案。

 

提示：

• 1 <= cars.length <= 20
• cars.length = directions.length
• cars.length = arrivalTimes.length
• cars 中的所有值都是唯一的。
• 1 <= directions[i] <= 4
• arrivalTimes 是非递减的。

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

基于 Doocs 参考改写：按 Python 的互斥临界区方案，用一把锁覆盖判断绿灯、必要时切换、车辆通过的全过程。初始 road=1。只有目标道路与当前道路不同时才调用 turnGreen，避免重复切换已亮的绿灯；整个回调期间保持互斥，不允许异路车辆同时通过。

变量与复杂度：road 为当前绿灯道路；每车有效操作 O(1)，对象空间 O(1)，不计等待和回调耗时。

平台接口：Constructor() TrafficLight；CarArrived(carId, roadId, direction int, turnGreen, crossCar func())。roadId 为 1/2，direction 为题目给定的 1..4；carId 和 direction 由闭包用于记录实际车辆，无需参与同步决策。并发对象应只构造一次，由所有 goroutine 共享，开始使用后不能复制。回调按题意假定会正常返回且不重入对象；复杂度不包含等待其他线程和回调自身的耗时。

出处与许可：基于 Doocs 原题及参考资料，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；Go 代码及本说明按 CC BY-SA 4.0 共享。

// 依据 Doocs/leetcode 题目与参考资料进行 Go 改写/整理。
// 来源：https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/1200-1299/1279.Traffic%20Light%20Controlled%20Intersection/README.md
// 许可：CC BY-SA 4.0，https://creativecommons.org/licenses/by-sa/4.0/

import "sync"

type TrafficLight struct {
	mu   sync.Mutex
	road int
}

func Constructor() TrafficLight { return TrafficLight{road: 1} }
func (l *TrafficLight) CarArrived(carId, roadId, direction int, turnGreen, crossCar func()) {
	l.mu.Lock()
	defer l.mu.Unlock()
	if l.road != roadId {
		turnGreen()
		l.road = roadId
	}
	crossCar()
}

力扣原题 · Doocs 题解来源