0921-0930

921. Minimum Add to Make Parentheses Valid $\star\star$

922. Sort Array By Parity II $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  vector<int> sortArrayByParityII(vector<int>& A) {
    const int n = A.size();

    for (int i = 0, j = 1; i < n; i += 2, j += 2) {
      while (i < n && A[i] % 2 == 0) i += 2;
      while (j < n && A[j] % 2 == 1) j += 2;
      if (i < n) swap(A[i], A[j]);
    }

    return A;
  }
};

923. 3Sum With Multiplicity $\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
class Solution {
 public:
  int threeSumMulti(vector<int>& A, int target) {
    long ans = 0;

    unordered_map<int, long> map;
    for (int a : A) ++map[a];

    for (auto& [i, x] : map)
      for (auto& [j, y] : map) {
        int k = target - i - j;
        if (!map.count(k)) continue;
        if (i == j && j == k)
          ans += x * (x - 1) * (x - 2) / 6;
        else if (i == j && j != k)
          ans += x * (x - 1) / 2 * map[k];
        else if (i < j && j < k)
          ans += x * y * map[k];
      }

    return ans % int(1e9 + 7);
  }
};

924. Minimize Malware Spread $\star\star\star$

925. Long Pressed Name $\star$

926. Flip String to Monotone Increasing $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  int minFlipsMonoIncr(string S) {
    vector<int> dp(2);

    for (int i = 0; i < S.length(); ++i) {
      int temp = dp[0] + (S[i] == '1');
      dp[1] = min(dp[0], dp[1]) + (S[i] == '0');
      dp[0] = temp;
    }

    return min(dp[0], dp[1]);
  }
};

927. Three Equal Parts $\star\star\star$

928. Minimize Malware Spread II $\star\star\star$

929. Unique Email Addresses $\star$

930. Binary Subarrays With Sum $\star\star$