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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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

 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 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
  }
};