Leetcode 1114 - 按序打印

leetcode 1114 - 按序打印 - 题解以及解析

题目描述

我们提供了一个类：

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"。
   
  注意: 尽管输入中的数字似乎暗示了顺序，但是我们并不保证线程在操作系统中的调度顺序。你看到的输入格式主要是为了确保测试的全面性。

提交答案

class foo {
    public foo() {}

    private semaphore first = new semaphore(0);
    private semaphore second = new semaphore(0);
    private semaphore third = new semaphore(0);

    public void first(runnable printfirst) throws interruptedexception {
        // printfirst.run() outputs "first". do not change or remove this line.
        printfirst.run();
        first.release();
        second.release();
    }

    public void second(runnable printsecond) throws interruptedexception {
        // printsecond.run() outputs "second". do not change or remove this line.
        second.acquire();
        printsecond.run();
        second.release();
        third.release();
    }

    public void third(runnable printthird) throws interruptedexception {
        // printthird.run() outputs "third". do not change or remove this line.
        third.acquire();
        printthird.run();
        third.release();
    }
}

执行用时: 12 ms , 在所有 java 提交中击败了 74.80% 的用户

内存消耗: 39.3 mb , 在所有 java 提交中击败了 5.60% 的用户

题解反思

这道题主要的解题思路就是采用了三个初始化 permit 为 0 的信号量。这样在程序启动时，刚开始 second.acquire() 和 third.acquire() 均不会获取到线程资源，直到 first 执行完 run() 方法后，才会释放第二个信号量，这时 second.acquire() 才能获取到信号量，继而 printsecond.run() ，之后 second 又会释放第三个信号量，同样这时 third.acquire() 才能够获取到信号量，从而成功执行 printthird.run()，通过这样的方式，保证了线程的按许执行。

这里贴一下 java 中信号量 semaphore 的官方接口文档，可供查阅。https://docs.oracle.com/javase/8/docs/api/index.html?java/util/concurrent/semaphore.html

在并发问题中，他们都有一个共同的特征，即：多个线程/进程之间共享某些资源，从而导致并发访问时的冲突。由于在程序中无法消除所有对共享资源的依赖，在这种情况下，防止并发问题就变成了共享资源的协调问题了。因此，解决这类问题其中最核心的思想就是要保证共享资源在某个时刻只能有一个线程/进程访问，也就是确保系统中关键代码的独占性，这样就可以防止程序进入不一致的状态。

最后，再推荐一篇信号量相关的教程。