0761-0770

761. Special Binary String $\star\star\star$

762. Prime Number of Set Bits in Binary Representation $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
 public:
  int countPrimeSetBits(int L, int R) {
    // (10100010100010101100)2 = (665772)10
    constexpr int magic = 665772;
    int ans = 0;

    for (int n = L; n <= R; ++n)
      if (magic & (1 << __builtin_popcountll(n))) ++ans;

    return ans;
  }
};

763. Partition Labels $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  vector<int> partitionLabels(string S) {
    vector<int> ans;

    vector<int> map(26);
    for (int i = 0; i < S.length(); ++i) map[S[i] - 'a'] = i;

    int start = 0;
    int end = 0;

    for (int i = 0; i < S.length(); ++i) {
      end = max(end, map[S[i] - 'a']);
      if (i == end) {
        ans.push_back(end - start + 1);
        start = end + 1;
      }
    }

    return ans;
  }
};

764. Largest Plus Sign $\star\star$

765. Couples Holding Hands $\star\star\star$

766. Toeplitz Matrix $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
 public:
  bool isToeplitzMatrix(vector<vector<int>>& matrix) {
    for (int i = 0; i + 1 < matrix.size(); ++i)
      for (int j = 0; j + 1 < matrix[0].size(); ++j)
        if (matrix[i][j] != matrix[i + 1][j + 1]) return false;

    return true;
  }
};

767. Reorganize String $\star\star$

768. Max Chunks To Make Sorted II $\star\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int maxChunksToSorted(vector<int>& arr) {
    const int n = arr.size();

    int ans = 0;
    int max = INT_MIN;
    vector<int> min(n, arr.back());

    for (int i = n - 2; i >= 0; --i) min[i] = std::min(min[i + 1], arr[i]);

    for (int i = 0; i < n - 1; ++i) {
      max = std::max(max, arr[i]);
      if (max <= min[i + 1]) ++ans;
    }

    return ans + 1;
  }
};

769. Max Chunks To Make Sorted $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  int maxChunksToSorted(vector<int>& arr) {
    int ans = 0;
    int max = INT_MIN;

    for (int i = 0; i < arr.size(); ++i) {
      max = std::max(max, arr[i]);
      if (max == i) ++ans;
    }

    return ans;
  }
};

770. Basic Calculator IV $\star\star\star$