1116. 打印零与奇偶数

Posted on | In
Words count in article: 670 | Reading time ≈ 3

题目

假设有这么一个类：

1
2
3
4
5
6
class ZeroEvenOdd {
  public ZeroEvenOdd(int n) { ... }      // 构造函数
  public void zero(printNumber) { ... }  // 仅打印出 0
  public void even(printNumber) { ... }  // 仅打印出 偶数
  public void odd(printNumber) { ... }   // 仅打印出 奇数
}

相同的一个 ZeroEvenOdd 类实例将会传递给三个不同的线程：

  1. 线程 A 将调用 zero()，它只输出 0 。
  2. 线程 B 将调用 even()，它只输出偶数。
  3. 线程 C 将调用 odd()，它只输出奇数。

每个线程都有一个 printNumber 方法来输出一个整数。请修改给出的代码以输出整数序列 010203040506… ，其中序列的长度必须为 2n。

示例1:

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

示例2:

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

解法

解法一：

使用Lock和Condition

Java

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class ZeroEvenOdd {
    private int n;

    private volatile int     start = 1;

    private volatile int who;
    private Lock lock = new ReentrantLock();
    private Condition zero = lock.newCondition();
    private Condition even = lock.newCondition();
    private Condition odd = lock.newCondition();

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

     // printNumber.accept(x) outputs "x", where x is an integer.
    public void zero(IntConsumer printNumber) throws InterruptedException {
        lock.lock();
        try {
            while (start <= n) {
                if (who!=0) {
                    zero.await();
                }
                printNumber.accept(0);
                if (start % 2 == 0) {
                    who=2;
                    even.signal();
                } else {
                    who=1;
                    odd.signal();
                }
                zero.await();
            }
            odd.signal();
            even.signal();
        } finally {
            lock.unlock();
        }
    }

    //偶数
    public void even(IntConsumer printNumber) throws InterruptedException {
        lock.lock();
        try {
            while (start <= n) {
                if (who!=2) {
                    even.await();
                } else {
                    printNumber.accept(start++);
                    who=0;
                    zero.signal();
                }
            }
        } finally {
            lock.unlock();
        }
    }

    //基数
    public void odd(IntConsumer printNumber) throws InterruptedException {
        lock.lock();
        try {
            while (start <= n) {
                if (who!=1) {
                    odd.await();
                } else {
                    printNumber.accept(start++);
                    who=0;
                    zero.signal();
                }
            }
        } finally {
            lock.unlock();
        }
    }
}

JAVA

解法二：

使用Semaphore

Java

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
43
44
45
46
47
48
49
50
51
52
53
class ZeroEvenOdd {
    private int n;
    private Semaphore zeroSemaphore = new Semaphore(0);
    private Semaphore evenSemaphore = new Semaphore(0);
    private Semaphore oddSemaphore = new Semaphore(1);
    private int i = 1;
    
    public ZeroEvenOdd(int n) {
        this.n = n;
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void zero(IntConsumer printNumber) throws InterruptedException {
        while (true) {
            zeroSemaphore.acquire();
            if (i > n) {
                return;
            }
            printNumber.accept(0);
            oddSemaphore.release();// 打印完0后继续执行odd方法
        }
    }

    public void even(IntConsumer printNumber) throws InterruptedException {
        while (true) {
            evenSemaphore.acquire();
            if (i > n) {
                return;
            }
            printNumber.accept(i);
            oddSemaphore.release();// 打印完偶数后继续执行odd方法
        }
    }

    public void odd(IntConsumer printNumber) throws InterruptedException {
        while (i <= n) {
            oddSemaphore.acquire();          
            zeroSemaphore.release();// 打印0
            oddSemaphore.acquire();// 阻塞当前线程，等待0打印完成
            if ((i & 1) != 0) {
                printNumber.accept(i);// 打印奇数
            } else {
                evenSemaphore.release();// 打印偶数
                oddSemaphore.acquire();// 阻塞当前线程，等待偶数打印完成
            }
            i++;    
            oddSemaphore.release();
        }
        // 释放最后遗留的锁
        zeroSemaphore.release();
        evenSemaphore.release();
    }
}
0%