1116_打印零与奇偶数

难度：中等

题目

现有函数 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 以输出奇数。

示例

示例一：

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

示例一：

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

提示

  • 1 <= n <= 1000

解题

Java 信号量

Semaphore(信号量)：是一种计数器，用来保护一个或者多个共享资源的访问。如果线程要访问一个资源就必须先获得信号量。如果信号量内部计数器大于0，信号量减1，然后允许共享这个资源；否则，如果信号量的计数器等于0，信号量将会把线程置入休眠直至计数器大于0.当信号量使用完时，必须释放。

主要方法：

  • void acquire() ：从信号量获取一个许可，如果无可用许可前将一直阻塞等待
  • boolean tryAcquire()：从信号量尝试获取一个许可，如果无可用许可，直接返回false，不会阻塞
  • void release()： 释放一个许可。注意：多次调用该方法，会使信号量的许可数增加，达到动态扩展的效果
  • int availablePermits()： 获取当前信号量可用的许可

在多线程中，通常会使用 Semaphore 信号量来进行资源共享。

每当线程需要执行时，就调用 acquire 方法获取一个许可，等待获取到资源后执行，执行完成后调用 release 方法是放一个许可。

题解

在此题中，三个线程开始遍历 n，zero 线程首先获得一个许可，打印 0 后，从 1 到 n 进行遍历，奇数对 odd 信号量释放一个许可，偶数则对 even 信号量释放一个许可，odd 线程从 1 到 n 每隔一位进行遍历，等待获取许可，获取许可后打印当前奇数，然后对 zero 信号量释放一个许可，even 线程同样，从 2 到 n 没隔一位进行遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class ZeroEvenOdd {
    private int n;
    Semaphore zero;
    Semaphore even;
    Semaphore odd;

    public ZeroEvenOdd(int n) {
        this.n = n;
        zero = new Semaphore(1);
        even = new Semaphore(0);
        odd = new Semaphore(0);
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void zero(IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i++) {
            zero.acquire();
            printNumber.accept(0);
            if (i % 2 == 0) {
                even.release();
            } else {
                odd.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();
        }
    }
}