LeetCode H2O 生成

第1117題

現在有兩種線程，氫 oxygen 和氧 hydrogen，你的目标是組織這兩種線程來産生水分子。

存在一個屏障（barrier）使得每個線程必須等候直到一個完整水分子能夠被産生出來。

氫和氧線程會被分别給予 releaseHydrogen 和 releaseOxygen 方法來允許它們突破屏障。

這些線程應該三三成組突破屏障并能立即組合産生一個水分子。

你必須保證産生一個水分子所需線程的結合必須發生在下一個水分子産生之前。

換句話說:

如果一個氧線程到達屏障時沒有氫線程到達，它必須等候直到兩個氫線程到達。
如果一個氫線程到達屏障時沒有其它線程到達，它必須等候直到一個氧線程和另一個氫線程到達。
書寫滿足這些限制條件的氫、氧線程同步代碼。

 

示例 1:

輸入: "HOH"
輸出: "HHO"
解釋: "HOH" 和 "OHH" 依然都是有效解。
示例 2:

輸入: "OOHHHH"
輸出: "HHOHHO"
解釋: "HOHHHO", "OHHHHO", "HHOHOH", "HOHHOH", "OHHHOH", "HHOOHH", "HOHOHH" 和 "OHHOHH" 依然都是有效解。
 

限制條件:

輸入字元串的總長将會是 3n, 1 ≤ n ≤ 50；
輸入字元串中的 “H” 總數将會是 2n；
輸入字元串中的 “O” 總數将會是 n。

來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/building-h2o
           

解題思路

• 1.設定一個h資訊号
• 2.每生成一個h，當h等于2的時候則進入等待o。否則生成氫氣并且h自加1。
• 3.每生成一個o，當h小于2的時候則進入等侍h。否則生成o并且h清0，重新開始生成一個水份子
• 4.注意Runnable和Thread的差別，實作了Runnable接口，無法啟動線程，必須依托其他類或線程

代碼實作

public class Sub1117 {
    public static void main(String[] args) throws InterruptedException {
        //測試用例字元串
        String test = "HOHOHHOOHOHHHHHOHHHOH";

        //生成結果字元串
        StringBuffer result = new StringBuffer();

        //注意：建立的Runnable任務，無法啟動線程，必須依托其他類或線程啟動
        //建立生成氧氣任務
        Runnable releaseHydrogen = () -> result.append("H");

        //建立生成氧氣任務
        Runnable releaseOxygen = () -> result.append("O");

        //儲存線程數組
        Thread threads[] = new Thread[test.length()];

        H2O h2o = new H2O();
        for (int i = 0; i < test.length(); ++i) {
            Thread thread = null;
            //根據獲得的字元調用相應的氧氣或氫氣線程
            if (test.charAt(i) == 'O') {
                thread = new OGenerator(h2o, releaseOxygen);
            } else if (test.charAt(i) == 'H') {
                thread = new HGenerator(h2o, releaseHydrogen);
            }
            //開始線程
            thread.start();
            //儲存到線程數組
            threads[i] = thread;
        }

        //等侍所有線程執行完
        for (int i = 0; i < threads.length; i++) {
            threads[i].join();
        }

        //輸出結果串
        System.out.println(result.toString());
    }
}

//氫氣生成線程
class HGenerator extends Thread {
    H2O h2o;
    Runnable releaseHydrogen;

    public HGenerator(H2O h2o, Runnable releaseHydrogen) {
        this.h2o = h2o;
        this.releaseHydrogen = releaseHydrogen;
    }

    @Override
    public void run() {
        try {
            h2o.hydrogen(releaseHydrogen);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

//氧氣生成線程
class OGenerator extends Thread {
    H2O h2o;
    Runnable releaseOxygen;

    public OGenerator(H2O h2o, Runnable releaseOxygen) {
        this.h2o = h2o;
        this.releaseOxygen = releaseOxygen;
    }

    @Override
    public void run() {
        try {
            h2o.oxygen(releaseOxygen);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

class H2O {
    public H2O() {
    }

    int h = 0;

    public synchronized void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        while (h == 2) {
            this.wait();
        }
        releaseHydrogen.run();
        ++h;
        this.notify();
    }

    public synchronized void oxygen(Runnable releaseOxygen) throws InterruptedException {
        while (h < 2) {
            this.wait();
        }
        releaseOxygen.run();
        h = 0;
        this.notify();
    }
}
           

資料

• 示例源碼
• 原文位址
• Spring Boot、Spring Cloud 示例學習