0451-0460

451. Sort Characters By Frequency $\star\star$

452. Minimum Number of Arrows to Burst Balloons $\star\star$

453. Minimum Moves to Equal Array Elements $\star$

454. 4Sum II $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C,
                   vector<int>& D) {
    int ans = 0;
    unordered_map<int, int> map;

    for (int a : A)
      for (int b : B) ++map[a + b];

    for (int c : C)
      for (int d : D) ans += map.count(-c - d) ? map[-c - d] : 0;

    return ans;
  }
};

455. Assign Cookies $\star$

456. 132 Pattern $\star\star$

457. Circular Array Loop $\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
28
29
30
31
32
33
34
35
36
37
class Solution {
 public:
  bool circularArrayLoop(vector<int>& nums) {
    if (nums.size() < 2) return false;

    function<int(int)> advance = [&](int i) {
      const int n = nums.size();
      int val = (i + nums[i]) % n;
      return i + nums[i] >= 0 ? val : n + val;
    };

    for (int i = 0; i < nums.size(); ++i) {
      if (nums[i] == 0) continue;

      int slow = i;
      int fast = advance(slow);
      while (nums[i] * nums[fast] > 0 && nums[i] * nums[advance(fast)] > 0) {
        if (slow == fast) {
          if (slow == advance(slow)) break;
          return true;
        }
        slow = advance(slow);
        fast = advance(advance(fast));
      }

      slow = i;
      int sign = nums[i];
      while (sign * nums[slow] > 0) {
        int next = advance(slow);
        nums[slow] = 0;
        slow = next;
      }
    }

    return false;
  }
};

458. Poor Pigs $\star\star\star$

459. Repeated Substring Pattern $\star$

460. LFU Cache $\star\star\star$