LeetCode 1116. 打印零与奇偶数

Categories:

题目描述
思路分析
1. 解法一：信号量同步（推荐）
相似题目

题目描述

✅ 1116. 打印零与奇偶数

思路分析

解法一：信号量同步（推荐）

核心思路：

使用三个信号量控制打印顺序：zero、odd、even。

zero 每次打印 0 后唤醒对应奇偶信号量。

odd/even 打印后再唤醒 zero。

复杂度分析：

时间复杂度：O(n)，其中 n 表示打印次数。

空间复杂度：O(1)，仅使用常数额外空间。

import java.util.concurrent.Semaphore;

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

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

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

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

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

type ZeroEvenOdd struct {
	n    int
	zero chan struct{}
	even chan struct{}
	odd  chan struct{}
}

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

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

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

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

相似题目

题目	难度	考察点
1116. 打印零与奇偶数	中等	并发控制
1114. 按序打印	简单	并发控制
1115. 交替打印 FooBar	中等	并发控制
1226. 哲学家进餐	中等	并发控制
1195. 交替打印字符串	中等	并发控制

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/75452796