原文链接: https://leetcode-cn.com/problems/print-zero-even-odd

英文原文

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

中文题目

假设有这么一个类：

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：

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

示例 2：

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

通过代码

高赞题解

原文地址： https://zhuanlan.zhihu.com/p/81626432

方案一：Semaphore

借助信号量来建立屏障，还是很方便的：

class ZeroEvenOdd {

    private int n;

    

    public ZeroEvenOdd(int n) {

        this.n = n;

    }



    Semaphore z = new Semaphore(1);

    Semaphore e = new Semaphore(0);

    Semaphore o = new Semaphore(0);

	

    public void zero(IntConsumer printNumber) throws InterruptedException {

        for(int i=0; i<n;i++) {

        	z.acquire();

        	printNumber.accept(0);

        	if((i&1)==0) {

        		o.release();

        	}else {

        		e.release();

        	}

        }

    }



    public void even(IntConsumer printNumber) throws InterruptedException {

        for(int i=2; i<=n; i+=2) {

        	e.acquire();

        	printNumber.accept(i);

        	z.release();

        }

    }



    public void odd(IntConsumer printNumber) throws InterruptedException {

        for(int i=1; i<=n; i+=2) {

        	o.acquire();

        	printNumber.accept(i);

        	z.release();

        }

    }

}

方案二：Lock

之前听课时听过老师讲：“凡是可以用信号量解决的问题，都可以用管程模型来解决”，那么我们试试吧（实践发现，也确实可以，但逻辑有点绕不够直观）：

class ZeroEvenOdd {

    private int n;

    

    public ZeroEvenOdd(int n) {

        this.n = n;

    }



    Lock lock = new ReentrantLock();

    Condition z = lock.newCondition();

    Condition num = lock.newCondition();

    volatile boolean zTurn = true;

    volatile int zIndex = 0;

	

    public void zero(IntConsumer printNumber) throws InterruptedException {

        for(;zIndex<n;) {

            lock.lock();

            try {

        	while(!zTurn) {

        		z.await();

        	}

        	printNumber.accept(0);

        	zTurn = false;

        	num.signalAll();

                zIndex++;

            }finally {

        	lock.unlock();

            }

        }

    }



    public void even(IntConsumer printNumber) throws InterruptedException {

        for(int i=2; i<=n; i+=2) {

            lock.lock();

            try {

        	while(zTurn || (zIndex&1)==1) {

        		num.await();

        	}

        	printNumber.accept(i);

        	zTurn = true;

        	z.signal();

            }finally {

        	lock.unlock();

            }

        }

    }



    public void odd(IntConsumer printNumber) throws InterruptedException {

        for(int i=1; i<=n; i+=2) {

            lock.lock();

            try {

        	while(zTurn || (zIndex&1)==0) {

        		num.await();

        	}

        	printNumber.accept(i);

        	zTurn = true;

        	z.signal();

            }finally {

        	lock.unlock();

            }

        }

    }

}

方案三：无锁

老规矩，但凡用了锁的，都来试试可否变成无锁的（本机测试是可行的，但测评平台报超时）：

class ZeroEvenOdd {

    private int n;

    

    public ZeroEvenOdd(int n) {

        this.n = n;

    }



    volatile int stage = 0;

	

    public void zero(IntConsumer printNumber) throws InterruptedException {

        for(int i=0;i<n;i++) {

        	while(stage>0);

    		printNumber.accept(0);

    		if((i&1)==0) {

    			stage = 1;

    		}else {

    			stage = 2;

    		}

        }

    }



    public void even(IntConsumer printNumber) throws InterruptedException {

        for(int i=2; i<=n; i+=2) {

        	while(stage!=2);

    		printNumber.accept(i);

    		stage = 0;

        }

    }



    public void odd(IntConsumer printNumber) throws InterruptedException {

        for(int i=1; i<=n; i+=2) {

        	while(stage!=1);

    		printNumber.accept(i);

    		stage = 0;

        }

    }

}

统计信息

通过次数	提交次数	AC比率
23802	45681	52.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
交替打印FooBar	中等