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

  void foo(function<void()> printFoo) {
    for (int i = 0; i < n; i++) {
      m1.lock();
      // printFoo() outputs "foo". Do not change or remove this line.
      printFoo();
      m2.unlock();
    }
  }

  void bar(function<void()> printBar) {
    for (int i = 0; i < n; i++) {
      m2.lock();
      // printBar() outputs "bar". Do not change or remove this line.
      printBar();
      m1.unlock();
    }
  }

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

• 信号量

#include <semaphore.h>

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

  void foo(function<void()> printFoo) {
    for (int i = 0; i < n; i++) {
      sem_wait(&s1);
      // printFoo() outputs "foo". Do not change or remove this line.
      printFoo();
      sem_post(&s2);
    }
  }

  void bar(function<void()> printBar) {
    for (int i = 0; i < n; i++) {
      sem_wait(&s2);
      // printBar() outputs "bar". Do not change or remove this line.
      printBar();
      sem_post(&s1);
    }
  }

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

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

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

  void foo(function<void()> printFoo) {
    for (int i = 0; i < n; i++) {
      // printFoo() outputs "foo". Do not change or remove this line.
      while (!b) {
        this_thread::yield();
      }
      printFoo();
      b = false;
    }
  }

  void bar(function<void()> printBar) {
    for (int i = 0; i < n; i++) {
      while (b) {
        this_thread::yield();
      }
      // printBar() outputs "bar". Do not change or remove this line.
      printBar();
      b = true;
    }
  }

 private:
  int n;
  bool b = true;
};

• 条件变量

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

  void foo(function<void()> printFoo) {
    for (int i = 0; i < n; i++) {
      unique_lock<mutex> l{m};
      cv1.wait(l, [this] { return b1; });
      // printFoo() outputs "foo". Do not change or remove this line.
      printFoo();
      b1 = false;
      b2 = true;
      cv2.notify_one();
    }
  }

  void bar(function<void()> printBar) {
    for (int i = 0; i < n; i++) {
      unique_lock<mutex> l{m};
      cv2.wait(l, [this] { return b2; });
      // printBar() outputs "bar". Do not change or remove this line.
      printBar();
      b1 = true;
      b2 = false;
      cv1.notify_one();
    }
  }

 private:
  int n;
  mutex m;
  condition_variable cv1;
  condition_variable cv2;
  bool b1 = true;
  bool b2 = false;
};