1117. H2O 生成

56 阅读 0 评论 37 点赞

我是靠谱客的博主迅速蚂蚁，最近开发中收集的这篇文章主要介绍1117. H2O 生成，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

现在有两种线程，氢 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。

class H2O {
private:
int flag=0;
mutex mx1;
condition_variable cv;
public:
H2O() {
}
void hydrogen(function<void()> releaseHydrogen) {
unique_lock<mutex> lck(mx1);
cv.wait(lck,[this]{return flag<2;});
// releaseHydrogen() outputs "H". Do not change or remove this line.
releaseHydrogen();
flag++;
cv.notify_one();
}
void oxygen(function<void()> releaseOxygen) {
unique_lock<mutex> lck(mx1);
cv.wait(lck,[this]{return flag==2;});
// releaseOxygen() outputs "O". Do not change or remove this line.
releaseOxygen();
flag=0;
cv.notify_one();
}
};

注意几点：

1.类 unique_lock 是通用互斥包装器，允许延迟锁定、锁定的有时限尝试、递归锁定、所有权转移和与条件变量一同使用。
unique_lock比lock_guard使用更加灵活，功能更加强大。
使用unique_lock需要付出更多的时间、性能成本。（总的来说与lock_guard类似，但是控制的东西更多一些）

2.条件变量wait函数，

std::condition_variable 提供了两种 wait() 函数。当前线程调用 wait() 后将被阻塞(此时当前线程应该获得了锁（mutex），不妨设获得锁 lck)，直到另外某个线程调用 notify_* 唤醒了当前线程。

在线程被阻塞时，该函数会自动调用 lck.unlock() 释放锁，使得其他被阻塞在锁竞争上的线程得以继续执行。另外，一旦当前线程获得通知(notified，通常是另外某个线程调用 notify_* 唤醒了当前线程)，wait() 函数也是自动调用 lck.lock()，使得 lck 的状态和 wait 函数被调用时相同。

在第二种情况下（即设置了 Predicate），只有当 pred 条件为 false 时调用 wait() 才会阻塞当前线程，并且在收到其他线程的通知后只有当 pred 为 true 时才会被解除阻塞。在本题中当flag小于2的时候由H获得锁，等于2的时候阻塞，释放锁，然后执行O,结束之后再唤醒H.

3.lambda表达式的写法，

[](int x, int y) { return x + y; } // 隐式返回类型
[](int& x) { ++x; }
// 没有return语句 -> lambda 函数的返回类型是'void'
[]() { ++global_x; }
// 没有参数,仅访问某个全局变量
[]{ ++global_x; }
// 与上一个相同,省略了()
可以像下面这样显示指定返回类型:
[](int x, int y) -> int { int z = x + y; return z; }
在这个例子中创建了一个临时变量z来存储中间值. 和普通函数一样,这个中间值不会保存到下次调用. 什么也不返回的Lambda函数可以省略返回类型, 而不需要使用 -> void 形式.
　　Lambda函数可以引用在它之外声明的变量. 这些变量的集合叫做一个闭包. 闭包被定义在Lambda表达式声明中的方括号[]内. 这个机制允许这些变量被按值或按引用捕获。
[]
//未定义变量.试图在Lambda内使用任何外部变量都是错误的.
[x, &y]
//x 按值捕获, y 按引用捕获.
[&]
//用到的任何外部变量都隐式按引用捕获
[=]
//用到的任何外部变量都隐式按值捕获
[&, x]
//x显式地按值捕获. 其它变量按引用捕获
[=, &z]
//z按引用捕获. 其它变量按值捕获