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 ZeroEvenOdd {
 public:
  ZeroEvenOdd(int n) {
    this->n = n;
    m2.lock();
    m3.lock();
  }

  // printNumber(x) outputs "x", where x is an integer.
  void zero(function<void(int)> printNumber) {
    for (int i = 0; i < n; ++i) {
      m1.lock();
      printNumber(0);
      i % 2 == 0 ? m3.unlock() : m2.unlock();
    }
  }

  void even(function<void(int)> printNumber) {
    for (int i = 2; i <= n; i += 2) {
      m2.lock();
      printNumber(i);
      m1.unlock();
    }
  }

  void odd(function<void(int)> printNumber) {
    for (int i = 1; i <= n; i += 2) {
      m3.lock();
      printNumber(i);
      m1.unlock();
    }
  }

 private:
  int n;
  mutex m1;
  mutex m2;
  mutex m3;
};

• 信号量

#include <semaphore.h>

class ZeroEvenOdd {
 public:
  ZeroEvenOdd(int n) {
    this->n = n;
    sem_init(&s1, 0, 1);
    sem_init(&s2, 0, 0);
    sem_init(&s3, 0, 0);
  }

  // printNumber(x) outputs "x", where x is an integer.
  void zero(function<void(int)> printNumber) {
    for (int i = 0; i < n; ++i) {
      sem_wait(&s1);
      printNumber(0);
      i % 2 == 0 ? sem_post(&s3) : sem_post(&s2);
    }
  }

  void even(function<void(int)> printNumber) {
    for (int i = 2; i <= n; i += 2) {
      sem_wait(&s2);
      printNumber(i);
      sem_post(&s1);
    }
  }

  void odd(function<void(int)> printNumber) {
    for (int i = 1; i <= n; i += 2) {
      sem_wait(&s3);
      printNumber(i);
      sem_post(&s1);
    }
  }

 private:
  int n;
  sem_t s1;
  sem_t s2;
  sem_t s3;
};

• 条件变量

class ZeroEvenOdd {
 public:
  ZeroEvenOdd(int n) { this->n = n; }

  // printNumber(x) outputs "x", where x is an integer.
  void zero(function<void(int)> printNumber) {
    while (cur <= n) {
      unique_lock<mutex> l{m};
      cv.wait(l, [this] { return b; });
      if (cur <= n) {
        printNumber(0);
      }
      b = false;
      cv.notify_all();
    }
  }

  void even(function<void(int)> printNumber) {
    while (cur <= n) {
      unique_lock<mutex> l{m};
      cv.wait(l, [this] { return !b && cur % 2 == 0; });
      if (cur <= n) {
        printNumber(cur++);
      }
      b = true;
      cv.notify_all();
    }
  }

  void odd(function<void(int)> printNumber) {
    while (cur <= n) {
      unique_lock<mutex> l{m};
      cv.wait(l, [this] { return !b && cur % 2 == 1; });
      if (cur <= n) {
        printNumber(cur++);
      }
      b = true;
      cv.notify_all();
    }
  }

 private:
  int n;
  int cur = 1;
  mutex m;
  condition_variable cv;
  bool b = true;
};