LeetCode-多线程题库一锅端！

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”

解答

这个是一个典型的制造屏障的问题，可以通过lock，CountDownLatch等多种方法解决，我们用信号量的方法解决，按顺序输出。没什么需要特别说的，Show you the code.

import java.util.concurrent.Semaphore;

class Foo {
    Semaphore s2, s3;
    public Foo() {
        s2 = new Semaphore(0);
        s3 = new Semaphore(0);
    }

    public void first(Runnable printFirst) throws InterruptedException {

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

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

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

    }
}

1115 交替打印FooBar 中等

描述

我们提供了一个类：

class FooBar {
  public void foo() {
    for (int i = 0; i < n; i++) {
      print("foo");
    }
  }

  public void bar() {
    for (int i = 0; i < n; i++) {
      print("bar");
    }
  }
}

两个不同的线程将会共用一个 FooBar 实例。其中一个线程将会调用 foo() 方法，另一个线程将会调用 bar() 方法。

请设计修改程序，以确保 “foobar” 被输出 n 次。

示例1

输入: n = 1
输出: “foobar”
解释: 这里有两个线程被异步启动。其中一个调用 foo() 方法, 另一个调用 bar() 方法，”foobar” 将被输出一次。

示例2

输入: n = 2
输出: “foobarfoobar”
解释: “foobar” 将被输出两次。

解答

这道题看起来比第一道稍复杂一点，但其实都差不多，也是一个线程在另一个线程之后调度，用信号量的话，两个线程相互唤醒就可以了，Show you the code.

import java.util.concurrent.Semaphore;

class FooBar {
    private int n;
    Semaphore s1,s2;
    
    public FooBar(int n) {
        this.n = n;
        s1 = new Semaphore(1);
        s2 = new Semaphore(0);
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        
        for (int i = 0; i < n; i++) {
            s1.acquire();
        	// printFoo.run() outputs "foo". Do not change or remove this line.
        	printFoo.run();
            s2.release();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        
        for (int i = 0; i < n; i++) {
            s2.acquire();
            // printBar.run() outputs "bar". Do not change or remove this line.
        	printBar.run();
            s1.release();
        }
    }
}

1116 打印零与奇偶数 中等

描述

假设有这么一个类:

class ZeroEvenOdd {
  public ZeroEvenOdd(int n) { ... }      // 构造函数
  public void zero(printNumber) { ... }  // 仅打印出 0
  public void even(printNumber) { ... }  // 仅打印出 偶数
  public void odd(printNumber) { ... }   // 仅打印出 奇数
}

相同的一个ZeroEvenOdd类实例将会传递给三个不同的线程：

• 线程A将调用zero()，它只输出 0 。
• 线程B将调用even()，它只输出偶数。
• 线程C将调用odd()，它只输出奇数。

每个线程都有一个printNumber方法来输出一个整数。请修改给出的代码以输出整数序列 010203040506... ，其中序列的长度必须为2n。

示例1

输入: n = 2
输出: “0102”
解释: 三条线程异步执行，其中一个调用 zero()，另一个线程调用 even()，最后一个线程调用odd()。正确的输出为 “0102”。

示例2

输入: n = 5
输出: “0102030405”

解答

我们分析一下这三个线程的输出顺序，先是0，再分别是奇数和偶数，那就是在输出0的线程后根据当前的奇偶情况唤醒对应的奇偶线程，然后对应的奇偶线程再唤醒0。Show you the code.

import java.util.concurrent.Semaphore;

class ZeroEvenOdd {
 private int n;
  Semaphore s1, s2, s3, s4;

  public ZeroEvenOdd(int n) {
    this.n = n;
    s1 = new Semaphore(1);
    s2 = new Semaphore(0);
    s3 = new Semaphore(0);
    s4 = new Semaphore(1);

  }

  // printNumber.accept(x) outputs "x", where x is an integer.
  public void zero(IntConsumer printNumber) throws InterruptedException {
   for (int i = 1; i <= n; i++) {
      s4.acquire();
      s1.acquire();
      printNumber.accept(0);
      if ((i & 1) == 0) {
        s2.release();
      } else {
        s3.release();
      }
      s1.release();
    }
  }

  public void even(IntConsumer printNumber) throws InterruptedException {
    for (int i = 2; i <= n ; i+=2) {
      s2.acquire();
      printNumber.accept(i);
      s4.release();
    }

  }

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

1117 H2O 生成 困难

描述

现在有两种线程，氢oxygen和氧hydrogen，你的目标是组织这两种线程来产生水分子。

存在一个屏障（barrier）使得每个线程必须等候直到一个完整水分子能够被产生出来。

氢和氧线程会被分别给予releaseHydrogen和releaseOxygen方法来允许它们突破屏障。

这些线程应该三三成组突破屏障并能立即组合产生一个水分子。

你必须保证产生一个水分子所需线程的结合必须发生在下一个水分子产生之前。

换句话说:

• 如果一个氧线程到达屏障时没有氢线程到达，它必须等候直到两个氢线程到达。
• 如果一个氢线程到达屏障时没有其它线程到达，它必须等候直到一个氧线程和另一个氢线程到达。

书写满足这些限制条件的氢、氧线程同步代码。

示例1

输入: “HOH”
输出: “HHO”
解释: “HOH” 和 “OHH” 依然都是有效解。

示例2

输入: “OOHHHH”
输出: “HHOHHO”
解释: “HOHHHO”, “OHHHHO”, “HHOHOH”, “HOHHOH”, “OHHHOH”, “HHOOHH”, “HOHOHH” 和 “OHHOHH” 依然都是有效解。

解答

这个解法是看到底下评论的大神的解法，也是看了这个解法我才把这四道题都用信号量做了一遍。注释写的很清楚，当确保两个H线程和一个O线程都到的时候再输出，Show you the code.

import java.util.concurrent.*;

class H2O {
    
    private Semaphore s1,s2,s3,s4;
    
    public H2O() {
        s1 = new Semaphore(2); // H线程信号量
        s2 = new Semaphore(1); // O线程信号量
        
        s3 = new Semaphore(0); // 反应条件信号量
        s4 = new Semaphore(0); // 反应条件信号量
    }

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        s1.acquire(); // 保证只有2个H线程进入执行
        s3.release(); // 释放H原子到达信号
        s4.acquire(); // 等待O原子到达
        releaseHydrogen.run();
        s1.release(); // 相当于唤醒1个H线程
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        s2.acquire(); // 保证只有1个O线程进入执行
        s4.release(2); // 释放O原子到达信号，因为有2个H线程等待所以释放2个
        s3.acquire(2); // 等待H原子到达，2个原因同上
        releaseOxygen.run();
        s2.release(); // 相当于唤醒1个O线程
    }
}