目录

T の weblog

X

【LeetCode刷题】按序打印

原题:按序打印

我们提供了一个类:

public class Foo {
  public void one() { print("one"); }
  public void two() { print("two"); }
  public void three() { print("three"); }
}

三个不同的线程将会共用一个 Foo 实例。

  • 线程 A 将会调用 one() 方法
  • 线程 B 将会调用 two() 方法
  • 线程 C 将会调用 three() 方法

请设计修改程序,以确保 two() 方法在 one() 方法之后被执行,three() 方法在 two() 方法之后被执行。
示例 1:

输入: [1,2,3]
输出: "onetwothree"
解释: 
有三个线程会被异步启动。
输入 [1,2,3] 表示线程 A 将会调用 one() 方法,线程 B 将会调用 two() 方法,线程 C 将会调用 three() 方法。
正确的输出是 "onetwothree"。

示例 2:

输入: [1,3,2]
输出: "onetwothree"
解释: 
输入 [1,3,2] 表示线程 A 将会调用 one() 方法,线程 B 将会调用 three() 方法,线程 C 将会调用 two() 方法。
正确的输出是 "onetwothree"。

注意:

尽管输入中的数字似乎暗示了顺序,但是我们并不保证线程在操作系统中的调度顺序。
你看到的输入格式主要是为了确保测试的全面性。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/print-in-order
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法:

这道题的解法其实挺简单的,可以使用 ,或者使用 信号量 的方式解决,然后比较麻烦的是不知道怎么测试,这里提供一下我的测试方法

public static void main(String[] args) throws InterruptedException {
        FOO foo = new FOO();
        Thread t1 = new Thread(()->{
            try {
                foo.first(()->{
                    System.out.println("first");
                });
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
        Thread t2 = new Thread(()->{
            try {
                foo.second(()->{
                    System.out.println("second");
                });
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
        Thread t3 = new Thread(()->{
            try {
                foo.third(()->{
                    System.out.println("third");
                });
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });

        Integer[] orders = {1,2,3};
        for (int i = 0; i < orders.length; i++) {
            Integer in = orders[i];
            switch (in){
                case 1:
                    t1.start();
                    break;
                case 2:
                    t2.start();
                    break;
                case 3:
                    t3.start();
                    break;
            }
        }

    }

为什么要先定义三个线程对 foo 对象的方法进行执行呢,因为题目中是这样描述的

三个不同的线程将会共用一个 Foo 实例。

线程 A 将会调用 one() 方法
线程 B 将会调用 two() 方法
线程 C 将会调用 three() 方法

说的是三个不同的线程会调用同一个对象的三个方法,恰好对象的三个方法都是要传入线程的,所以我刚开始调试的时候也跑偏了,直接先执行对象的 1 方法,然后执行对象的 2 方法

ok,说重点,

解法一:使用 countDownLatch

这是最简单最容易理解的一种方式了,在之前写过的博客中也介绍到了并发工具(Java 升级计划 6)
countDownLatch 这个类使一个线程等待其他线程各自执行完毕后再执行。
是通过一个计数器来实现的,计数器的初始值是线程的数量。每当一个线程执行完毕后,计数器的值就-1,当计数器的值为 0 时,表示所有线程都执行完毕,然后在闭锁上等待的线程就可以恢复工作了。
涉及 API 有:

  • await():等待
  • countDown():减一
package com.test.excellearn.demo.learn;

import java.util.concurrent.CountDownLatch;

class FOO {

    CountDownLatch countDownLatchOneafter = null;
    CountDownLatch countDownLatchSecondfter = null;

    public FOO() {
        countDownLatchOneafter = new CountDownLatch(1);
        countDownLatchSecondfter = new CountDownLatch(1);
    }

    public void first(Runnable printFirst) throws InterruptedException {
        // printFirst.run() outputs "first". Do not change or remove this line.
        printFirst.run();
        countDownLatchOneafter.countDown();
    }

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

    public void third(Runnable printThird) throws InterruptedException {
        countDownLatchSecondfter.await();
        printThird.run();
    }

    public static void main(String[] args) throws InterruptedException {
        FOO foo = new FOO();
        Thread t1 = new Thread(()->{
            try {
                foo.first(()->{
                    System.out.println("first");
                });
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
        Thread t2 = new Thread(()->{
            try {
                foo.second(()->{
                    System.out.println("second");
                });
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
        Thread t3 = new Thread(()->{
            try {
                foo.third(()->{
                    System.out.println("third");
                });
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });

        Integer[] orders = {1,2,3};
        for (int i = 0; i < orders.length; i++) {
            Integer in = orders[i];
            switch (in){
                case 1:
                    t1.start();
                    break;
                case 2:
                    t2.start();
                    break;
                case 3:
                    t3.start();
                    break;
            }
        }

    }

}

解法二:信号量法 搬运的 LeetCode 题解

public class Foo03 {
    //声明两个 Semaphore变量
    private Semaphore spa,spb;
    public Foo03() {
        //初始化Semaphore为0的原因:如果这个Semaphore为零,如果另一线程调用(acquire)这个Semaphore就会产生阻塞,便可以控制second和third线程的执行
        spa = new Semaphore(0);
        spb = new Semaphore(0);
    }
    public void first(Runnable printFirst) throws InterruptedException {
            // printFirst.run() outputs "first". Do not change or remove this line.
            printFirst.run();
            //只有等first线程释放Semaphore后使Semaphore值为1,另外一个线程才可以调用(acquire)
            spa.release();
    }
    public void second(Runnable printSecond) throws InterruptedException {
            //只有spa为1才能执行acquire,如果为0就会产生阻塞
            spa.acquire();
            // printSecond.run() outputs "second". Do not change or remove this line.
            printSecond.run();
            spb.release();
    }
    public void third(Runnable printThird) throws InterruptedException {
            //只有spb为1才能通过,如果为0就会阻塞
            spb.acquire();
            // printThird.run() outputs "third". Do not change or remove this line.
            printThird.run();
    }
}

解法三:加锁 Synchronized 锁和控制变量 搬运的 LeetCode 题解

public class Foo {
    //控制变量
    private int flag = 0;
    //定义Object对象为锁
    private Object lock = new Object();
    public Foo() {
    }
    public void first(Runnable printFirst) throws InterruptedException {
        synchronized (lock){
            //如果flag不为0则让first线程等待,while循环控制first线程如果不满住条件就一直在while代码块中,防止出现中途跳入,执行下面的代码,其余线程while循环同理
            while( flag != 0){
                lock.wait();
            }
            // printFirst.run() outputs "first". Do not change or remove this line.
            printFirst.run();
            //定义成员变量为 1
            flag = 1;
            //唤醒其余所有的线程
            lock.notifyAll();
        }
    }
    public void second(Runnable printSecond) throws InterruptedException {
        synchronized (lock){
            //如果成员变量不为1则让二号等待
            while (flag != 1){
                lock.wait();
            }
            // printSecond.run() outputs "second". Do not change or remove this line.
            printSecond.run();
            //如果成员变量为 1 ,则代表first线程刚执行完,所以执行second,并且改变成员变量为 2
            flag = 2;
            //唤醒其余所有的线程
            lock.notifyAll();
        }
    }
    public void third(Runnable printThird) throws InterruptedException {
        synchronized (lock){
            //如果flag不等于2 则一直处于等待的状态
            while (flag != 2){
                lock.wait();
            }
            // printThird.run() outputs "third". Do not change or remove this line.
            //如果成员变量为 2 ,则代表second线程刚执行完,所以执行third,并且改变成员变量为 0
            printThird.run();
            flag = 0;
            lock.notifyAll();
        }
    }
}



标题:【LeetCode刷题】按序打印
作者:MingGH
地址:https://runnable.run/articles/2019/12/07/1575696484864.html