leetcode解题思路分析（一百三十二）1111 - 1117 题

60 阅读 0 评论 40 点赞

我是靠谱客的博主踏实咖啡豆，最近开发中收集的这篇文章主要介绍leetcode解题思路分析（一百三十二）1111 - 1117 题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

有效括号的嵌套深度
给你一个「有效括号字符串」 seq，请你将其分成两个不相交的有效括号字符串，A 和 B，并使这两个字符串的深度最小。

在遍历过程中，我们保证栈内一半的括号属于序列 A，一半的括号属于序列 B，那么就能保证拆分后最大的嵌套深度最小，是当前最大嵌套深度的一半。要实现这样的对半分配，我们只需要把奇数层的 ( 分配给 A，偶数层的 ( 分配给 B 即可。

class Solution {
public:
vector<int> maxDepthAfterSplit(string seq) {
int d = 0;
vector<int> ans;
for (char& c : seq)
if (c == '(') {
++d;
ans.push_back(d % 2);
}
else {
ans.push_back(d % 2);
--d;
}
return ans;
}
};

删除某些元素后的数组均值
给你一个整数数组 arr ，请你删除最小 5% 的数字和最大 5% 的数字后，剩余数字的平均值。与标准答案误差在 10-5 的结果都被视为正确结果。

简单的加法。

class Solution {
public:
double trimMean(vector<int>& arr)
{
double ret = 0;
int n = arr.size() * 0.05;
sort(arr.begin(), arr.end());
for (int i = n; i < arr.size() - n; ++i)
{
ret += arr[i];
}
ret = ret / (arr.size() - 2 * n);
return ret;
}
};

字母组合迭代器
请你设计一个迭代器类 CombinationIterator

类似于返回字符串/数组的下一个较大的数，做法也是类似的，贪心取最小能增大的地方，然后处理后面的字符

class CombinationIterator {
private:
vector<int> pos;
string s;
bool finished;
public:
CombinationIterator(string characters, int combinationLength) {
s = characters;
pos.resize(combinationLength);
iota(pos.begin(), pos.end(), 0);
finished = false;
}
string next() {
string ans;
for (int p: pos) {
ans += s[p];
}
int i = -1;
for (int k = pos.size() - 1; k >= 0; --k) {
if (pos[k] != s.size() - pos.size() + k) {
i = k;
break;
}
}
if (i == -1) {
finished = true;
}
else {
++pos[i];
for (int j = i + 1; j < pos.size(); ++j) {
pos[j] = pos[j - 1] + 1;
}
}
return ans;
}
bool hasNext() {
return !finished;
}
};

按序打印
三个不同的线程 A、B、C 将会共用一个 Foo 实例。请设计修改程序，以确保 second() 方法在 first() 方法之后被执行，third() 方法在 second() 方法之后被执行。

可以用互斥锁条件变量信号量异步操作原子操作解决

class Foo {
promise<void> pro1, pro2;
public:
void first(function<void()> printFirst) {
printFirst();
pro1.set_value();
}
void second(function<void()> printSecond) {
pro1.get_future().wait();
printSecond();
pro2.set_value();
}
void third(function<void()> printThird) {
pro2.get_future().wait();
printThird();
}
};

交替打印 FooBar
两个不同的线程将会共用一个 FooBar 实例：请设计修改程序，以确保 “foobar” 被输出 n 次。

解法同上题

class FooBar {
private:
int n;
atomic<bool>foo_done=false;
public:
FooBar(int n) {
this->n = n;
}
void foo(function<void()> printFoo) {
for (int i = 0; i < n; i++) {
while(foo_done){
this_thread::yield();
}
printFoo();
foo_done=true;
}
}
void bar(function<void()> printBar) {
for (int i = 0; i < n; i++) {
while(foo_done==false){
this_thread::yield();
}
printBar();
foo_done=false;
}
}
};

打印零与奇偶数
修改给出的类，以输出序列 “010203040506…” ，其中序列的长度必须为 2n 。

三个线程思路同上。

class ZeroEvenOdd {
private:
int n;
atomic<int> flag = 0;
public:
ZeroEvenOdd(int n) {
this->n = n;
}
// printNumber(x) outputs "x", where x is an integer.
void zero(function<void(int)> printNumber) {
for (int i = 1; i <= n; ++i) {
while (flag != 0) {
this_thread::yield();
}
printNumber(0);
if (i % 2 == 0) {
flag = 2;
} else {
flag = 1;
}
}
}
void even(function<void(int)> printNumber) {
for (int i = 2; i <= n; i += 2) {
while (flag != 2) {
this_thread::yield();
}
printNumber(i);
flag = 0;
}
}
void odd(function<void(int)> printNumber) {
for (int i = 1; i <= n; i += 2) {
while (flag != 1) {
this_thread::yield();
}
printNumber(i);
flag = 0;
}
}
};

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

氢和氧线程以2比1的关系互相阻塞，使用条件变量解题

class Semaphore {
private:
int n_;
mutex mu_;
condition_variable cv_;
public:
Semaphore(int n): n_{n} {}
public:
void wait() {
unique_lock<mutex> lock(mu_);
if (!n_) {
cv_.wait(lock, [this]{return n_;});
}
--n_;
}
void signal() {
unique_lock<mutex> lock(mu_);
++n_;
cv_.notify_one();
}
};
class H2O {
private:
Semaphore s_hIn, s_oIn;
Semaphore s_hBarrier, s_oBarrier;
public:
H2O(): s_hIn{2}, s_oIn{1}, s_hBarrier{0}, s_oBarrier{0} {}
void hydrogen(function<void()> releaseHydrogen) {
s_hIn.wait();
s_oBarrier.signal();
s_hBarrier.wait();
releaseHydrogen();
s_hIn.signal();
}
void oxygen(function<void()> releaseOxygen) {
s_oIn.wait();
s_oBarrier.wait();
s_oBarrier.wait();
s_hBarrier.signal();
s_hBarrier.signal();
releaseOxygen();
s_oIn.signal();
}
};