0711-0720

711. Number of Distinct Islands II $\star\star\star$

712. Minimum ASCII Delete Sum for Two Strings $\star\star$

713. Subarray Product Less Than K $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    if (k <= 1) return 0;

    int ans = 0;
    int prod = 1;

    for (int i = 0, j = 0; i < nums.size(); ++i) {
      prod *= nums[i];
      while (prod >= k) prod /= nums[j++];
      ans += i - j + 1;
    }

    return ans;
  }
};

714. Best Time to Buy and Sell Stock with Transaction Fee $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  int maxProfit(vector<int>& prices, int fee) {
    int sell = 0;
    int hold = INT_MIN;

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

    return sell;
  }
};

715. Range Module $\star\star\star$

716. Max Stack $\star$

717. 1-bit and 2-bit Characters $\star$

1
2
3
4
5
6
7
8
9
class Solution {
 public:
  bool isOneBitCharacter(vector<int>& bits) {
    int i = 0;
    while (i < bits.size() - 1) i += bits[i] + 1;

    return i == bits.size() - 1;
  }
};

718. Maximum Length of Repeated Subarray $\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 findLength(vector<int>& A, vector<int>& B) {
    const int m = A.size();
    const int n = B.size();

    int ans = 0;
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = m - 1; i >= 0; --i)
      for (int j = n - 1; j >= 0; --j)
        if (A[i] == B[j]) dp[i][j] = dp[i + 1][j + 1] + 1;

    for (vector<int>& row : dp)
      ans = max(ans, *max_element(row.begin(), row.end()));

    return ans;
  }
};

719. Find K-th Smallest Pair Distance $\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
class Solution {
 public:
  int smallestDistancePair(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());

    int l = 0;
    int r = nums.back() - nums.front();

    while (l < r) {
      int m = l + (r - l) / 2;
      int count = 0;

      for (int i = 0, j = 0; i < nums.size(); ++i) {
        while (j < nums.size() && nums[j] <= nums[i] + m) ++j;
        count += j - i - 1;
      }

      if (count < k)
        l = m + 1;
      else
        r = m;
    }

    return l;
  }
};

720. Longest Word in Dictionary $\star$