[知识总结] 【leetcode】多线程编程题题解

本文将记录力扣多线程下的题目：

每道题基本都有很多种解法，基本都可以使用变量、Semaphore、CountDownLatch等手段来控制。

1114.按序打印

1.变量控制

    class Foo {

        private volatile int flag = 1;

        public Foo() {}

        public void first(Runnable printFirst) throws InterruptedException {

            // printSecond.run() outputs "first". Do not change or remove this line.
            printFirst.run();
            flag = 2;
        }

        public void second(Runnable printSecond) throws InterruptedException {
            while (flag != 2);
            // printSecond.run() outputs "second". Do not change or remove this line.
            printSecond.run();
            flag = 3;
        }

        public void third(Runnable printThird) throws InterruptedException {
            while (flag != 3);
            // printThird.run() outputs "third". Do not change or remove this line.
            printThird.run();
        }
    }

2.Semaphore

    class Foo {

        public Semaphore seam_first_two = new Semaphore(0);

        public Semaphore seam_two_second = new Semaphore(0);

        public Foo() {}

        public void first(Runnable printFirst) throws InterruptedException {

            // printSecond.run() outputs "first". Do not change or remove this line.
            printFirst.run();
            seam_first_two.release();
        }

        public void second(Runnable printSecond) throws InterruptedException {
            seam_first_two.acquire();
            // printSecond.run() outputs "second". Do not change or remove this line.
            printSecond.run();
            seam_two_second.release();
        }

        public void third(Runnable printThird) throws InterruptedException {
            seam_two_second.acquire();
            // printThird.run() outputs "third". Do not change or remove this line.
            printThird.run();
        }
    }

3.CountDownLatch

    class Foo {

        private CountDownLatch second = new CountDownLatch(1);
        private CountDownLatch third = new CountDownLatch(1);

        public Foo() {}

        public void first(Runnable printFirst) throws InterruptedException {

            // printSecond.run() outputs "first". Do not change or remove this line.
            printFirst.run();
            second.countDown();
        }

        public void second(Runnable printSecond) throws InterruptedException {
            second.await();
            // printSecond.run() outputs "second". Do not change or remove this line.
            printSecond.run();
            third.countDown();
        }

        public void third(Runnable printThird) throws InterruptedException {
            third.await();
            // printThird.run() outputs "third". Do not change or remove this line.
            printThird.run();
        }
    }

4.AtomicInteger

    class Foo {

        private AtomicInteger firstJobDone = new AtomicInteger(0);
        private AtomicInteger secondJobDone = new AtomicInteger(0);

        public Foo() {}

        public void first(Runnable printFirst) throws InterruptedException {
            // printFirst.run() outputs "first".
            printFirst.run();
            // mark the first job as done, by increasing its count.
            firstJobDone.incrementAndGet();
        }

        public void second(Runnable printSecond) throws InterruptedException {
            while (firstJobDone.get() != 1) {
                // waiting for the first job to be done.
            }
            // printSecond.run() outputs "second".
            printSecond.run();
            // mark the second as done, by increasing its count.
            secondJobDone.incrementAndGet();
        }

        public void third(Runnable printThird) throws InterruptedException {
            while (secondJobDone.get() != 1) {
                // waiting for the second job to be done.
            }
            // printThird.run() outputs "third".
            printThird.run();
        }
    }

1115.交替打印FooBar

1.Semaphore

    class FooBar {
        private int n;
        public Semaphore semaphoreFoo = new Semaphore(1);
        public Semaphore semaphoreBar = new Semaphore(0);
        public FooBar(int n) {
            this.n = n;
        }

        public void foo(Runnable printFoo) throws InterruptedException {

            for (int i = 0; i < n; i++) {
                semaphoreBar.acquire();
                // printFoo.run() outputs "foo". Do not change or remove this line.
                printFoo.run();
                semaphoreBar.release();
            }
        }

        public void bar(Runnable printBar) throws InterruptedException {

            for (int i = 0; i < n; i++) {
                semaphoreBar.acquire();
                // printBar.run() outputs "bar". Do not change or remove this line.
                printBar.run();
                semaphoreFoo.release();
            }
        }
    }

2.CyclicBarrier

    class FooBar {
        private int n;

        private CyclicBarrier cb = new CyclicBarrier(2);
        private volatile boolean fooExec = true;

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

        public void foo(Runnable printFoo) throws InterruptedException {

            for (int i = 0; i < n; i++) {
                while (!fooExec) {
                    //false的时候，bar线程在执行，foo线程在这此处空转
                }
                printFoo.run();//打印foo
                fooExec = false;//设置变量
                try {
                    cb.await();//线程foo到达同步点
                } catch (BrokenBarrierException e) {
                    e.printStackTrace();
                }
            }
        }

        public void bar(Runnable printBar) throws InterruptedException {

            for (int i = 0; i < n; i++) {
                try {
                    cb.await();
                } catch (BrokenBarrierException e) {
                    e.printStackTrace();
                }
                printBar.run();
                fooExec = true;
            }
        }
    }

3.Thread.yield()

    class FooBar {
        private int n;

        private volatile boolean fooExec = true;

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

        public void foo(Runnable printFoo) throws InterruptedException {

            for (int i = 0; i < n;) {
                if (fooExec) {
                    printFoo.run();
                    fooExec = false;
                    i++;
                } else {
                    Thread.yield();
                }
            }
        }

        public void bar(Runnable printBar) throws InterruptedException {

            for (int i = 0; i < n;) {
                if (!fooExec) {
                    printBar.run();
                    fooExec = true;
                    i++;
                } else {
                    Thread.yield();
                }
            }
        }
    }

4.BlockingQueue

    class FooBar {
        private int n;
        private BlockingQueue<Integer> fooQueue = new LinkedBlockingQueue<Integer>() {{
            add(0);
        }};
        private BlockingQueue<Integer> barQueue = new LinkedBlockingQueue<>();

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

        public void foo(Runnable printFoo) throws InterruptedException {
            for (int i = 0; i < n; i++) {
                fooQueue.take();
                printFoo.run();
                barQueue.add(0);
            }
        }

        public void bar(Runnable printBar) throws InterruptedException {

            for (int i = 0; i < n; i++) {
                barQueue.take();
                printBar.run();
                fooQueue.add(0);
            }
        }
    }

1116.打印零与奇偶数

1.Semaphore

    class ZeroEvenOdd {
        private int n;

        private Semaphore zeroSema = new Semaphore(1);
        private Semaphore oddSema = new Semaphore(0);
        private Semaphore evenSema = new Semaphore(0);

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

        // printNumber.accept(x) outputs "x", where x is an integer.
        public void zero(IntConsumer printNumber) throws InterruptedException {
            for (int i = 1; i <= n; i++) {
                zeroSema.acquire();
                printNumber.accept(0);
                if (i % 2 == 1) {
                    oddSema.release();
                } else {
                    evenSema.release();
                }
            }
        }

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

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

2.CountDownLatch

    class ZeroEvenOdd {
        private int n;

        private CountDownLatch zeroLatch = new CountDownLatch(0);
        private CountDownLatch evenLatch = new CountDownLatch(1);//偶数
        private CountDownLatch oddLatch = new CountDownLatch(1);//奇数

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

        public void zero(IntConsumer printNumber) throws InterruptedException {
            for (int i = 1; i <= n; i++) {
                zeroLatch.await();
                printNumber.accept(0);
                zeroLatch = new CountDownLatch(1);
                if (i % 2 == 1) {
                    oddLatch.countDown();
                } else {
                    evenLatch.countDown();
                }
            }
        }

        public void even(IntConsumer printNumber) throws InterruptedException {
            for (int i = 1; i <= n; i++) {
                if (i % 2 == 0) {
                    evenLatch.await();
                    printNumber.accept(i);
                    evenLatch = new CountDownLatch(1);
                    zeroLatch.countDown();
                }
            }
        }

        public void odd(IntConsumer printNumber) throws InterruptedException {
            for (int i = 1; i <= n; i++) {
                if (i % 2 == 1) {
                    oddLatch.await();
                    printNumber.accept(i);
                    oddLatch = new CountDownLatch(1);
                    zeroLatch.countDown();
                }
            }
        }
    }

3.AtomicInteger+Thread.yield()

    class ZeroEvenOdd {
        private int n;
        private AtomicInteger ai = new AtomicInteger(0);

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

        public void zero(IntConsumer printNumber) throws InterruptedException {
            for (int i = 0; i < n; i++) {
                while (ai.get() != 0 && ai.get() != 2) {
                    Thread.yield();
                }
                printNumber.accept(0);
                ai.incrementAndGet();
            }
        }

        public void even(IntConsumer printNumber) throws InterruptedException {
            for (int i = 2; i <= n; i += 2) {
                while (ai.get() != 3) {
                    Thread.yield();
                }
                printNumber.accept(i);
                ai.set(0);
            }
        }

        public void odd(IntConsumer printNumber) throws InterruptedException {
            for (int i = 1; i <= n; i += 2) {
                while (ai.get() != 1) {
                    Thread.yield();
                }
                printNumber.accept(i);
                ai.set(2);
            }
        }
    }

4.变量+Thread.yield()

    class ZeroEvenOdd {

        private int n;

        private volatile int state;

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

        public void zero(IntConsumer printNumber) throws InterruptedException {
            for (int i = 1; i <= n; i++) {
                while (state != 0) {
                    Thread.yield();
                }
                printNumber.accept(0);
                if (i % 2 == 1) {
                    state = 1;
                } else {
                    state = 2;
                }
            }
        }

        public void even(IntConsumer printNumber) throws InterruptedException {
            for (int i = 2; i <= n; i += 2) {
                while (state != 2) {
                    Thread.yield();
                }
                printNumber.accept(i);
                state = 0;
            }
        }

        public void odd(IntConsumer printNumber) throws InterruptedException {
            for (int i = 1; i <= n; i += 2) {
                while (state != 1) {
                    Thread.yield();
                }
                printNumber.accept(i);
                state = 0;
            }
        }
    }

5.ReentrantLock+Condition

    class ZeroEvenOdd {
        private int n;

        private volatile int start = 1;

        private volatile int state;
        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 (state != 0) {
                        zero.await();
                    }
                    printNumber.accept(0);
                    if (start % 2 == 0) {
                        state = 2;
                        even.signal();
                    } else {
                        state = 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 (state != 2) {
                        even.await();
                    } else {
                        printNumber.accept(start++);
                        state = 0;
                        zero.signal();
                    }
                }
            } finally {
                lock.unlock();
            }
        }

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