LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 互斥量

class H2O {
 public:
  H2O() {}

  void hydrogen(function<void()> releaseHydrogen) {
    h.lock();
    // releaseHydrogen() outputs "H". Do not change or remove this line.
    releaseHydrogen();
    ++a;
    if (a < 2) {
      h.unlock();
      return;
    }
    if (b == 1) {
      a = 0;
      b = 0;
      h.unlock();
      o.unlock();
    }
  }

  void oxygen(function<void()> releaseOxygen) {
    o.lock();
    // releaseOxygen() outputs "O". Do not change or remove this line.
    releaseOxygen();
    ++b;
    if (a == 2 && b == 1) {
      a = 0;
      b = 0;
      h.unlock();
      o.unlock();
    }
  }

 private:
  mutex h;
  mutex o;
  int a = 0;
  int b = 0;
};

• 信号量

#include <semaphore.h>

class H2O {
 public:
  H2O() {
    sem_init(&h, 0, 2);
    sem_init(&o, 0, 0);
  }

  void hydrogen(function<void()> releaseHydrogen) {
    sem_wait(&h);
    // releaseHydrogen() outputs "H". Do not change or remove this line.
    releaseHydrogen();
    --n;
    if (!n) {
      n = 2;
      sem_post(&o);
    }
  }

  void oxygen(function<void()> releaseOxygen) {
    sem_wait(&o);
    // releaseOxygen() outputs "O". Do not change or remove this line.
    releaseOxygen();
    sem_post(&h);
    sem_post(&h);
  }

 private:
  sem_t h;
  sem_t o;
  int n = 2;
};

• 用 std::this_thread::yield 让出时间片，注意这种做法在实际情况中容易造成 CPU 空转

class H2O {
 public:
  H2O() {}

  void hydrogen(function<void()> releaseHydrogen) {
    lock_guard<mutex> l{h};
    while (a == 2) {
      this_thread::yield();
    }
    // releaseHydrogen() outputs "H". Do not change or remove this line.
    releaseHydrogen();
    ++a;
    if (a == 2 && b == 1) {
      a = 0;
      b = 0;
    }
  }

  void oxygen(function<void()> releaseOxygen) {
    lock_guard<mutex> l{o};
    while (b == 1) {
      this_thread::yield();
    }
    // releaseOxygen() outputs "O". Do not change or remove this line.
    releaseOxygen();
    ++b;
    if (a == 2 && b == 1) {
      a = 0;
      b = 0;
    }
  }

 private:
  mutex h;
  mutex o;
  int a = 0;
  int b = 0;
};

• 条件变量

class H2O {
 public:
  H2O() {}

  void hydrogen(function<void()> releaseHydrogen) {
    unique_lock<mutex> l{m1};
    cv.wait(l, [this] { return n < 2; });
    ++n;
    // releaseHydrogen() outputs "H". Do not change or remove this line.
    releaseHydrogen();
    cv.notify_one();
  }

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

 private:
  int n = 0;
  mutex m1;
  mutex m2;
  condition_variable cv;
};