Leetcode 1116 print zero even odd (concurrent multithreading countdownlatch lock condition)

You have a function printNumber that can be called with an integer parameter and prints it to the console.

• For example, calling printNumber(7) prints 7 to the console.

You are given an instance of the class ZeroEvenOdd that has three functions: zero, even, and odd. The same instance of ZeroEvenOdd will be passed to three different threads:

• Thread A: calls zero() that should only output 0's.
• Thread B: calls even() that should only output even numbers.
• Thread C: calls odd() that should only output odd numbers.

Modify the given class to output the series "010203040506..." where the length of the series must be 2n.

Implement the ZeroEvenOdd class:

• ZeroEvenOdd(int n) Initializes the object with the number n that represents the numbers that should be printed.
• void zero(printNumber) Calls printNumber to output one zero.
• void even(printNumber) Calls printNumber to output one even number.
• void odd(printNumber) Calls printNumber to output one odd number.

Example 1:

Input: n = 2
Output: "0102"
Explanation: There are three threads being fired asynchronously.
One of them calls zero(), the other calls even(), and the last one calls odd().
"0102" is the correct output.

Example 2:

Input: n = 5
Output: "0102030405"

Constraints:

• 1 <= n <= 1000

Topic link ：https://leetcode.com/problems/print-zero-even-odd/

The main idea of the topic ： Initialize a ZeroEvenOdd example , The three threads hold and call their respective zero,odd,even Method , requirement zero Only the output 0,odd Only odd numbers are output ,even Only even numbers are output , Final output "010203040506..." This sequence

Topic analysis ： There are many implementation methods , In this paper CountDownLatch + Lock + Condition The way ,CountDownLatch Used to ensure that when entering the cycle 0 First , The odd number is before, even after , After through condition Of await and signal Alternate operation , See notes for errors

8ms, Time beats 70.7%

public class ZeroEvenOdd {
    ReentrantLock lock;
    Condition cZero, cEven, cOdd;
    // Used to ensure non-zero numbers start after zero
    CountDownLatch zeroForOdd, zeroForEven;
    int n;

    public ZeroEvenOdd(int n) {
        this.n = n;
        lock = new ReentrantLock();
        cZero = lock.newCondition();
        cEven = lock.newCondition();
        cOdd = lock.newCondition();

        zeroForOdd = new CountDownLatch(1);
        zeroForEven = new CountDownLatch(1);
    }

    public void zero(IntConsumer printNumber) throws InterruptedException {
        lock.lock();
        try {
            for (int i = 1; i <= n; i ++) {
                printNumber.accept(0);
                if (i % 2 == 1) {
                    cOdd.signal();
                } else {
                    cEven.signal();
                }
                if (i == 1) {
                    zeroForOdd.countDown();
                }
                // latch should be released to ensure even thread can end normally if n == 1
                if (n == 1 || i == 2) {
                    zeroForEven.countDown();
                }
                cZero.await();
            }
            // **these "signal"s are important**
            // when the last non-zero number accepted, corresponding thread will be in blocking state, which should be woken up to ensure it end normally.
            cOdd.signal();
            cEven.signal();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
    }

    public void odd(IntConsumer printNumber) throws InterruptedException {
        try {
            zeroForOdd.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        lock.lock();
        try {
            for (int i = 1; i <= n; i += 2) {
                printNumber.accept(i);
                cZero.signal();
                cOdd.await();
            }
            cZero.signal();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
    }

    public void even(IntConsumer printNumber) throws InterruptedException {
        try {
            zeroForEven.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        lock.lock();
        try {
            for (int i = 2; i <= n; i += 2) {
                printNumber.accept(i);
                cZero.signal();
                cEven.await();
            }
            // **this judgement is important**
            // if lack of this judgement, odd can be blocked forever when n == 1:
            // 1. [zero] get lock -> release two latches -> release lock -> blocked
            // 2. [even] get lock -> release lock -> signal zero -> exit
            // 3. [zero] get lock -> signal even and odd -> exit
            // 4. [odd] get lock -> release lock -> blocked
            if (n > 1) {
                cZero.signal();
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
    }
}