2026/06/14

[LeetCode] 981 Time Based Key-Value Store 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class TimeMap {
public:
  using TimeMapEntry = pair<int, string>;
  unordered_map<string, vector<TimeMapEntry>> timeMap;
  TimeMap() {}

  void set(string key, string value, int timestamp) {
    timeMap[key].push_back(make_pair(timestamp, value));
  }

  string get(string key, int timestamp) {
    if (timeMap.find(key) == timeMap.end())
      return "";

    auto &v = timeMap[key];
    auto it = upper_bound(
        v.begin(), v.end(), timestamp,
        [](int t, const TimeMapEntry &entry) { return t < entry.first; });
    if (it == v.begin())
      return "";
    return prev(it)->second;
  }
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap* obj = new TimeMap();
 * obj->set(key,value,timestamp);
 * string param_2 = obj->get(key,timestamp);
 */
Labels:

2026/06/08

[LeetCode] 621 Task Scheduler

結論題

出現最多次的task決定了「固定輪數」

用其他task去把間隔填滿

若其他task出現跟最多次task一樣多, 則一定要在「固定輪數」後再+1

若其他task出現比最多次task少, 則不影響「固定輪數」

(其他task不可能比最多次task)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
  int leastInterval(vector<char> &tasks, int n) {
    unordered_map<char, int> cnt;
    for (char task : tasks)
      cnt[task]++;
    auto maxIt =
        max_element(cnt.begin(), cnt.end(), [](const auto &p0, const auto &p1) {
          return p0.second < p1.second;
        });
    int tmp = (maxIt->second - 1) * n;
    for (auto &it : cnt)
      if (it.first != maxIt->first)
        tmp -= min(maxIt->second - 1, it.second);
    if (tmp < 0)
      return tasks.size();
    return tasks.size() + tmp;
  }
};
Labels:
訂閱： 文章 (Atom)