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

• 计数每个任务的数量，存储到最大堆中，每轮从最大堆中取 n + 1 个任务执行

class Solution {
 public:
  int leastInterval(vector<char>& tasks, int n) {
    unordered_map<char, int> m;
    for (auto& x : tasks) {
      ++m[x];
    }
    priority_queue<int> q;
    for (auto& x : m) {
      q.emplace(x.second);
    }
    int res = 0;
    while (!empty(q)) {
      vector<int> v;
      int cnt = 0;
      for (int i = 0; i < n + 1; ++i) {
        if (!empty(q)) {
          v.emplace_back(q.top());
          q.pop();
          ++cnt;
        }
      }
      for (auto& x : v) {
        if (--x > 0) q.emplace(x);
      }
      res += empty(q) ? cnt : n + 1;
    }
    return res;
  }
};

• 由上述思路，出现次数多的任务应该最先安排

执行任务 AAABBBCCD n = 3
出现次数 3321

A### A### A###
AB## AB## AB##
ABC# ABC# AB##
ABCD ABC# AB## => ABCD ABC# AB
最后一轮未排满，需单独计算 => (3 - 1) * 4 + 2


执行任务 AAAABBBBCCCDDE n = 2
出现次数 44321
A## A## A## A##
AB# AB# AB# AB#
ABC ABC ABC AB#
ABC ABC ABC ABDDE
全部排满且最后一轮排不下，结果即为任务总数

• 直接计算结果

class Solution {
 public:
  int leastInterval(vector<char>& tasks, int n) {
    vector<int> v(26);
    for (auto& x : tasks) {
      ++v[x - 'A'];
    }
    sort(begin(v), end(v));
    int mx = v.back();
    int res = (mx - 1) * (n + 1) + 1;
    for (int i = 24; i >= 0 && v[i] == mx; --i) {
      ++res;
    }
    return max(res, static_cast<int>(size(tasks)));
  }
};