H2O 生成

Category	Difficulty	Likes	Dislikes
concurrency	Medium (53.24%)	117	-

Tags

Unknown

Companies

Unknown

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

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

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

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

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

换句话说:

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

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

示例 1:

1
2
3
输入: water = "HOH"
输出: "HHO"
解释: "HOH" 和 "OHH" 依然都是有效解。

示例 2:

1
2
3
输入: water = "OOHHHH"
输出: "HHOHHO"
解释: "HOHHHO", "OHHHHO", "HHOHOH", "HOHHOH", "OHHHOH", "HHOOHH", "HOHOHH" 和 "OHHOHH" 依然都是有效解。

提示：

3 * n == water.length
1 <= n <= 20
water[i] == 'O' or 'H'
输入字符串 water 中的 'H' 总数将会是 2 * n 。
输入字符串 water 中的 'O' 总数将会是 n 。

Discussion | Solution

解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// 条件变量
class H2O {
    int cnt_h = 0;
    condition_variable cv;
    mutex mu;
public:
    H2O() {
    }

    void hydrogen(function<void()> releaseHydrogen) {
        unique_lock<mutex> lock(mu);
        cv.wait(lock, [this]{return this->cnt_h < 2;});

        // releaseHydrogen() outputs "H". Do not change or remove this line.
        releaseHydrogen();
        cnt_h++;
        if(cnt_h == 2) cv.notify_all();
    }

    void oxygen(function<void()> releaseOxygen) {
        unique_lock<mutex> lock(mu);
        cv.wait(lock, [this]{return this->cnt_h == 2;});
        // releaseOxygen() outputs "O". Do not change or remove this line.
        releaseOxygen();
        cnt_h=0;
        cv.notify_all();
    }
};

// 原子变量
class H2O {
    atomic<int> h = 0;
public:
    H2O() {
    }

    void hydrogen(function<void()> releaseHydrogen) {
        while (h == 2) {
            this_thread::yield();
        }
        // releaseHydrogen() outputs "H". Do not change or remove this line.
        releaseHydrogen();
        ++h;
    }

    void oxygen(function<void()> releaseOxygen) {
        while (h != 2) {
            this_thread::yield();
        }
        // releaseOxygen() outputs "O". Do not change or remove this line.
        releaseOxygen();
        h = 0;
    }
};


// 状态机+条件变量
class H2O {
public:
    int transitions[5][2] = {{2,1}, {4,3}, {-1,4}, {0,-1}, {-1,0}};
    int state = 0;
    
    condition_variable cv;
    mutex mu;

    H2O() {}

    void hydrogen(function<void()> releaseHydrogen) {
        unique_lock<mutex> lock(mu);    
        cv.wait(lock, [this]{return transitions[state][1] != -1;});
        state = transitions[state][1];
        // releaseHydrogen() outputs "H". Do not change or remove this line.
        releaseHydrogen();
        if(state == 0) cv.notify_all();
    }

    void oxygen(function<void()> releaseOxygen) {
        unique_lock<mutex> lock(mu);
        cv.wait(lock, [this]{return transitions[state][0] != -1;});
        state = transitions[state][0];
        // releaseOxygen() outputs "O". Do not change or remove this line.
        releaseOxygen();
        if(state == 0) cv.notify_all();
    }
};

H2O 生成

H2O 生成

解法

相关文章：