

0181-0190

181. Employees Earning More Than Their Managers $\star$

182. Duplicate Emails $\star$

183. Customers Who Never Order $\star$

184. Department Highest Salary $\star\star$

185. Department Top Three Salaries $\star\star\star$

186. Reverse Words in a String II $\star\star$

187. Repeated DNA Sequences $\star\star$

class Solution {
 public:
  vector<string> findRepeatedDnaSequences(string s) {
    const int n = s.length();

    unordered_set<string> ans;
    unordered_set<string> set;

    for (int i = 0; i <= n - 10; ++i) {
      string seq = s.substr(i, 10);
      if (set.count(seq)) ans.insert(seq);
      set.insert(seq);
    }

    return vector<string>(ans.begin(), ans.end());
  }
};

188. Best Time to Buy and Sell Stock IV $\star\star\star$

class Solution {
 public:
  int maxProfit(int k, vector<int>& prices) {
    if (k >= prices.size() / 2) {
      int sell = 0;
      int hold = INT_MIN;

      for (int price : prices) {
        sell = max(sell, hold + price);
        hold = max(hold, sell - price);
      }

      return sell;
    }

    vector<int> sell(k + 1);
    vector<int> hold(k + 1, INT_MIN);

    for (int price : prices)
      for (int i = k; i > 0; --i) {
        sell[i] = max(sell[i], hold[i] + price);
        hold[i] = max(hold[i], sell[i - 1] - price);
      }

    return sell[k];
  }
};

189. Rotate Array $\star$

class Solution {
 public:
  void rotate(vector<int>& nums, int k) {
    k %= nums.size();
    reverse(nums, 0, nums.size() - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.size() - 1);
  }

 private:
  void reverse(vector<int>& nums, int l, int r) {
    while (l < r) swap(nums[l++], nums[r--]);
  }
};

190. Reverse Bits $\star$

class Solution {
 public:
  uint32_t reverseBits(uint32_t num) {
    unsigned int NO_OF_BITS = sizeof(num) * 8;
    unsigned int reverse_num = 0, temp;

    for (int i = 0; i < NO_OF_BITS; ++i) {
      temp = (num & (1 << i));
      if (temp) reverse_num |= (1 << ((NO_OF_BITS - 1) - i));
    }

    return reverse_num;
  }
};