阅读 160

[Java多线程][LeetCode题解]1114.按序打印

[Java多线程][LeetCode题解]

LeetCode题解

1114. 按序打印

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

题目

我们提供了一个类:

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. 模拟一个简易的产品生产链环境,提供一个productionChain栈(或者队列)当做原料仓(简易的仓库里堆积物品,先堆上去的东西后面找半天才拿的出来hhh),用于存放原料,顺便初始化交个房租什么的
    private Stack<Integer> productionChain ;
    public Foo() {
        // Init Resources Pool
        productionChain = new Stack<>();
    }
    复制代码
  2. 然后先算一算需要哪些原料,原料之间存在怎样的依赖关系
    // 题意需要调用3个方法,后两种分别依赖前两种
    // 那么有依赖关系:1 -> 2 -> 3
    // 此处给出两种原料id,如果有更多的依赖条件就需要考虑更多
    private final int pidOfFirst = 1;
    private final int pidOfSecond = 2;
    // 同时需要有资源锁,可以当做一个生产厂房有限的生产器械,只能同时供一种原料生产或加工
    private final Object resLock = new Object();
    复制代码
  3. 生产线设计
    // 由题目提供的代码设定有以下三条生产线,要求按first-second-third的顺序进行生产
    public void first(Runnable printFirst) throws InterruptedException {
        // printFirst.run() outputs "first". Do not change or remove this line.
        printFirst.run();
    }
    public void second(Runnable printSecond) throws InterruptedException {
        // printSecond.run() outputs "second". Do not change or remove this line.
        printSecond.run();
    }
    public void third(Runnable printThird) throws InterruptedException {
        // printThird.run() outputs "third". Do not change or remove this line.
        printThird.run();
    }
    复制代码
  4. 原料分配和产品加工
  • 原料1生产
    public void first(Runnable printFirst) throws InterruptedException {
        // 交付给生产产商进行生产,占用工具resLock其他人暂时不得使用
        synchronized (resLock){
            // 生产 原料1
            productionChain.push(pidOfFirst);
            // printFirst.run() outputs "first". Do not change or remove this line.
            printFirst.run();
            // 生产完成,通知其他工序开始工作
            resLock.notifyAll();
        }
    }
    复制代码
  • 原料2生产
    public void second(Runnable printSecond) throws InterruptedException {
        // 交付给生产产商进行生产,占用工具resLock其他人暂时不得使用
        synchronized (resLock){
            // 需要先了解资源池是否有需要的原料
            while( productionChain.empty() || productionChain.peek() != pidOfFirst ){
                // 没有原料的话拿到工具也没用,还是坐等原料1吧
                resLock.wait();
            }
            // 确认原料1已提供,从资源池取出原料1
            productionChain.pop();
            // 加工生产原料2
            productionChain.push(pidOfSecond);
            // printSecond.run() outputs "second". Do not change or remove this line.
            printSecond.run();
            // 加工完成,通知其他工序开始工作
            resLock.notifyAll();
        }
    }
    复制代码
  • *题目无关,仅作思考——以此类推可以有:原料x生产
    public void xth(Runnable printSecond) throws InterruptedException {
        // 交付给生产产商进行生产,占用工具resLock其他人暂时不得使用
        synchronized (resLock){
            // 需要先了解资源池是否有需要的原料
            while( productionChain.empty() || productionChain.peek() != pidOfX_d1_th ){ 
                // pidOfX_d1_th:X decrease1 th -> (x-1)th -> 第(x-1)种原料
                // 没有原料的话拿到工具也没用,还是坐等原料x吧
                resLock.wait();
            }
            // 确认原料(x-1)已提供,从资源池取出原料(x-1)
            productionChain.pop();
            // 加工生产原料x
            productionChain.push(pidOfSecond);
            // printSecond.run() outputs "second". Do not change or remove this line.
            printSecond.run();
            // 加工完成,通知其他工序开始工作
            resLock.notifyAll();
        }
    }
    // 甚至感觉像数学归纳法……
    复制代码
  • 原料齐全,组装成品
    public void third(Runnable printThird) throws InterruptedException {
        synchronized (resLock){
            // 由于这里要求是1->2->3,且1和2也要保持顺序,所以只需要判断是否有原料2即可
            while( productionChain.empty() || productionChain.peek() != pidOfSecond ){
                // wait for resource
                resLock.wait();
            }
            // 通过前序工艺加工好的原料进行组装成品
            productionChain.pop();
            // 当然,这里可以改成输出成品等其他操作,但是至少要消耗掉原料2才能继续进行下面的操作
            // printThird.run() outputs "third". Do not change or remove this line.
            printThird.run();
        }
    }
    复制代码
  1. 简单测试生产线,样例1,顺序调用
    public static void main(String[] args) throws InterruptedException {
        Runnable a = () -> System.out.println("one");
        Runnable b = () -> System.out.println("two");
        Runnable c = () -> System.out.println("three");
    
        ProductionLine pl = new ProductionLine();
        pl.first(   a   );
        pl.second(  b   );
        pl.third(   c   );
        // one
        // two
        // three
    }
    复制代码
  2. 简单测试生产线,样例2,乱序调用
    public static void main(String[] args) throws InterruptedException {
        Runnable a = () -> System.out.println("one");
        Runnable b = () -> System.out.println("two");
        Runnable c = () -> System.out.println("three");
    
        ProductionLine pl = new ProductionLine();
        pl.first(   a   );
        pl.second(  c   ); //先跑c
        pl.third(   b   ); //再跑b
        // 看看是否还是顺序输出
        // one
        // two
        // three
        // OK,没问题
    }
    复制代码

题解

class Foo {
    // 题意需要调用3个方法,后两种分别依赖前两种
    // 那么有依赖关系:1 -> 2 -> 3
    // 此处给出两种原料id,如果有更多的依赖条件就需要考虑更多
    private final int pidOfFirst = 1;
    private final int pidOfSecond = 2;
    // 同时需要有资源锁,可以当做一个生产厂房有限的生产器械,只能同时供一种原料生产或加工
    private final Object resLock = new Object();
    
    private Stack<Integer> productionChain ;
    public Foo() {
        // Init Resources Pool
        productionChain = new Stack<>();
    }
    
    public void first(Runnable printFirst) throws InterruptedException {
        // 交付给生产产商进行生产,占用工具resLock其他人暂时不得使用
        synchronized (resLock){
            // 生产 原料1
            productionChain.push(pidOfFirst);
            // printFirst.run() outputs "first". Do not change or remove this line.
            printFirst.run();
            // 生产完成,通知其他工序开始工作
            resLock.notifyAll();
        }
    }
    public void second(Runnable printSecond) throws InterruptedException {
        // 交付给生产产商进行生产,占用工具resLock其他人暂时不得使用
        synchronized (resLock){
            // 需要先了解资源池是否有需要的原料
            while( productionChain.empty() || productionChain.peek() != pidOfFirst ){
                // 没有原料的话拿到工具也没用,还是坐等原料1吧
                resLock.wait();
            }
            // 确认原料1已提供,从资源池取出原料1
            productionChain.pop();
            // 加工生产原料2
            productionChain.push(pidOfSecond);
            // printSecond.run() outputs "second". Do not change or remove this line.
            printSecond.run();
            // 加工完成,通知其他工序开始工作
            resLock.notifyAll();
        }
    }
    public void third(Runnable printThird) throws InterruptedException {
        synchronized (resLock){
            // 由于这里要求是1->2->3,且1和2也要保持顺序,所以只需要判断是否有原料2即可
            while( productionChain.empty() || productionChain.peek() != pidOfSecond ){
                // wait for resource
                resLock.wait();
            }
            // 通过前序工艺加工好的原料进行组装成品
            productionChain.pop();
            // 当然,这里可以改成输出成品等其他操作,但是至少要消耗掉原料2才能继续进行下面的操作
            // printThird.run() outputs "third". Do not change or remove this line.
            printThird.run();
        }
    }
}
复制代码

后记

顺便回忆了一下线程创建、通信和锁的使用,以联系实际的场景来刷题目还是挺有趣的:D

关注下面的标签,发现更多相似文章
评论