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

  // printFizz() outputs "fizz".
  void fizz(function<void()> printFizz) {
    for (int i = 3; i <= n; i += 3) {
      if (i % 5 != 0) {
        m1.lock();
        printFizz();
        m4.unlock();
      }
    }
  }

  // printBuzz() outputs "buzz".
  void buzz(function<void()> printBuzz) {
    for (int i = 5; i <= n; i += 5) {
      if (i % 3 != 0) {
        m2.lock();
        printBuzz();
        m4.unlock();
      }
    }
  }

  // printFizzBuzz() outputs "fizzbuzz".
  void fizzbuzz(function<void()> printFizzBuzz) {
    for (int i = 15; i <= n; i += 15) {
      m3.lock();
      printFizzBuzz();
      m4.unlock();
    }
  }

  // printNumber(x) outputs "x", where x is an integer.
  void number(function<void(int)> printNumber) {
    for (int i = 1; i <= n; ++i) {
      m4.lock();
      if (i % 3 == 0 && i % 5 == 0) {
        m3.unlock();
      } else if (i % 3 == 0) {
        m1.unlock();
      } else if (i % 5 == 0) {
        m2.unlock();
      } else {
        printNumber(i);
        m4.unlock();
      }
    }
  }

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

• 信号量

#include <semaphore.h>

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

  // printFizz() outputs "fizz".
  void fizz(function<void()> printFizz) {
    for (int i = 3; i <= n; i += 3) {
      if (i % 5 != 0) {
        sem_wait(&s1);
        printFizz();
        sem_post(&s4);
      }
    }
  }

  // printBuzz() outputs "buzz".
  void buzz(function<void()> printBuzz) {
    for (int i = 5; i <= n; i += 5) {
      if (i % 3 != 0) {
        sem_wait(&s2);
        printBuzz();
        sem_post(&s4);
      }
    }
  }

  // printFizzBuzz() outputs "fizzbuzz".
  void fizzbuzz(function<void()> printFizzBuzz) {
    for (int i = 15; i <= n; i += 15) {
      sem_wait(&s3);
      printFizzBuzz();
      sem_post(&s4);
    }
  }

  // printNumber(x) outputs "x", where x is an integer.
  void number(function<void(int)> printNumber) {
    for (int i = 1; i <= n; ++i) {
      sem_wait(&s4);
      if (i % 3 == 0 && i % 5 == 0) {
        sem_post(&s3);
      } else if (i % 3 == 0) {
        sem_post(&s1);
      } else if (i % 5 == 0) {
        sem_post(&s2);
      } else {
        printNumber(i);
        sem_post(&s4);
      }
    }
  }

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

• 条件变量

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

  // printFizz() outputs "fizz".
  void fizz(function<void()> printFizz) {
    unique_lock<mutex> l{m};
    while (cur <= n) {
      cv.wait(l, [this] { return cur > n || (cur % 3 == 0 && cur % 5 != 0); });
      if (cur <= n) {
        printFizz();
        ++cur;
      }
      cv.notify_all();
    }
  }

  // printBuzz() outputs "buzz".
  void buzz(function<void()> printBuzz) {
    unique_lock<mutex> l{m};
    while (cur <= n) {
      cv.wait(l, [this] { return cur > n || (cur % 5 == 0 && cur % 3 != 0); });
      if (cur <= n) {
        printBuzz();
        ++cur;
      }
      cv.notify_all();
    }
  }

  // printFizzBuzz() outputs "fizzbuzz".
  void fizzbuzz(function<void()> printFizzBuzz) {
    unique_lock<mutex> l{m};
    while (cur <= n) {
      cv.wait(l, [this] { return cur > n || (cur % 3 == 0 && cur % 5 == 0); });
      if (cur <= n) {
        printFizzBuzz();
        ++cur;
      }
      cv.notify_all();
    }
  }

  // printNumber(x) outputs "x", where x is an integer.
  void number(function<void(int)> printNumber) {
    unique_lock<mutex> l{m};
    while (cur <= n) {
      cv.wait(l, [this] { return cur > n || (cur % 3 != 0 && cur % 5 != 0); });
      if (cur <= n) {
        printNumber(cur);
        ++cur;
      }
      cv.notify_all();
    }
  }

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