0381-0390

381. Insert Delete GetRandom O(1) - Duplicates allowed $\star\star\star$

 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
class RandomizedCollection {
 public:
  bool insert(int val) {
    map[val].push_back(vals.size());
    vals.emplace_back(val, map[val].size() - 1);
    return map[val].size() == 1;
  }

  bool remove(int val) {
    if (!map.count(val) || map[val].empty()) return false;
    int index = map[val].back();
    map[vals.back().first][vals.back().second] = index;
    map[val].pop_back();
    swap(vals[index], vals.back());
    vals.pop_back();
    return true;
  }

  int getRandom() {
    int index = rand() % vals.size();
    return vals[index].first;
  }

 private:
  vector<pair<int, int>> vals;
  unordered_map<int, vector<int>> map;
};

382. Linked List Random Node $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  Solution(ListNode* head) {
    privateHead = head;
    for (auto curr = head; curr; curr = curr->next) ++length;
  }

  int getRandom() {
    int n = rand() % length;
    ListNode* curr = privateHead;
    while (n-- > 0) curr = curr->next;
    return curr->val;
  }

 private:
  ListNode* privateHead;
  int length = 0;
};

383. Ransom Note $\star$

384. Shuffle an Array $\star\star$

385. Mini Parser $\star\star$

386. Lexicographical Numbers $\star\star$

387. First Unique Character in a String $\star$

388. Longest Absolute File Path $\star\star$

389. Find the Difference $\star$

390. Elimination Game $\star\star$