Huahua’s Tech Road

花花酱 LeetCode 33. Search in Rotated Sorted Array

By zxi on November 26, 2021

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

1 <= nums.length <= 5000
-10⁴ <= nums[i] <= 10⁴
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-10⁴ <= target <= 10⁴

Solution: Binary Search

If the current range [l, r] is ordered, reduce to normal binary search. Otherwise, determine the range to search next by comparing target and nums[0].

Time complexity: O(logn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int search(vector<int>& nums, int target) {

int l = 0;

int r = nums.size();

while (l < r) {

int m = l + (r - l) / 2;

int x = (nums[m] < nums[0]) == (target < nums[0])

? nums[m]

: target < nums[0] ? INT_MIN : INT_MAX;

if (x < target)

l = m + 1;

else if (x > target)

r = m;

else

return m;

}

return -1;

}

};

花花酱 LeetCode 30. Substring with Concatenation of All Words

By zxi on November 26, 2021

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

Constraints:

1 <= s.length <= 10⁴
s consists of lower-case English letters.
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] consists of lower-case English letters.

Solution: Hashtable + Brute Force

Try every index and use a hashtable to check coverage.

Time complexity: O(n*m*l)
Space complexity: O(m*l)

C++

// Author: Huahua

class Solution {

public:

vector<int> findSubstring(string_view s, vector<string>& words) {

const int n = s.length();

const int m = words.size();

const int l = words[0].size();

if (m * l > n) return {};

unordered_map<string_view, int> freq;

for (const string& word : words) ++freq[word];

vector<int> ans;

for (int i = 0; i <= n - m * l; ++i) {

unordered_map<string_view, int> seen;

int count = 0;

for (int k = 0; k < m; ++k) {

string_view t = s.substr(i + k * l, l);

auto it = freq.find(t);

if (it == end(freq)) break;

if (++seen[t] > it->second) break;

++count;

}

if (count == m) ans.push_back(i);

}

return ans;

}

};

花花酱 LeetCode 29. Divide Two Integers

By zxi on November 26, 2021

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return the quotient after dividing dividend by divisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2³¹, 2³¹ − 1]. For this problem, if the quotient is strictly greater than 2³¹ - 1, then return 2³¹ - 1, and if the quotient is strictly less than -2³¹, then return -2³¹.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333.. which is truncated to 3.

Example 2:

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = -2.33333.. which is truncated to -2.

Example 3:

Input: dividend = 0, divisor = 1
Output: 0

Example 4:

Input: dividend = 1, divisor = 1
Output: 1

Constraints:

-2³¹ <= dividend, divisor <= 2³¹ - 1
divisor != 0

Solution: Binary / Bit Operation

The answer can be represented in binary format.

a / b = c
a >= b * Σ(d_i*2ⁱ)
c = Σ(d_i*2ⁱ)

e.g. 1: 10 / 3
=> 10 >= 3*(2¹ + 2⁰) = 3 * (2 + 1) = 9
ans = 2¹ + 2⁰ = 3

e.g. 2: 100 / 7
=> 100 >= 7*(2³ + 2²+2¹) = 7 * (8 + 4 + 2) = 7 * 14 = 98
ans = 2³+2²+2¹=8+4+2=14

Time complexity: O(32)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int divide(int A, int B) {

if (B == INT_MIN)

return A == INT_MIN ? 1 : 0;

if (A == INT_MIN) {

if (B == -1) return INT_MAX;

return B > 0 ? divide(A + B, B) - 1 : divide(A - B, B) + 1;

}

int a = abs(A);

int b = abs(B);

int ans = 0;

for (int x = 31; x >= 0; --x)

if (a >> x >= b)

ans += 1 << x, a -= b << x;

return (A > 0) == (B > 0) ? ans : -ans;

}

};

花花酱 LeetCode 2009. Minimum Number of Operations to Make Array Continuous

By zxi on November 26, 2021

You are given an integer array nums. In one operation, you can replace any element in nums with any integer.

nums is considered continuous if both of the following conditions are fulfilled:

All elements in nums are unique.
The difference between the maximum element and the minimum element in nums equals nums.length - 1.

For example, nums = [4, 2, 5, 3] is continuous, but nums = [1, 2, 3, 5, 6] is not continuous.

Return the minimum number of operations to make numscontinuous.

Example 1:

Input: nums = [4,2,5,3]
Output: 0
Explanation: nums is already continuous.

Example 2:

Input: nums = [1,2,3,5,6]
Output: 1
Explanation: One possible solution is to change the last element to 4.
The resulting array is [1,2,3,5,4], which is continuous.

Example 3:

Input: nums = [1,10,100,1000]
Output: 3
Explanation: One possible solution is to:
- Change the second element to 2.
- Change the third element to 3.
- Change the fourth element to 4.
The resulting array is [1,2,3,4], which is continuous.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Solution: Sliding Window

Remove duplicates and sort the numbers.
Try using nums[i] as the min number of the final array.
window [i, j), max – min < n, then change the rest of array to fit into or append after the window, which takes n – (j – i) steps.
e.g. input = [10, 3, 1, 4, 5, 6, 6, 6, 11, 15] => sorted + unique => [1, 3, 4, 5, 6, 10, 11, 15]
n = 10, window = [3, 4, 5, 6, 10, 11], max = 11, min = 3, max – min = 8 < 10
Final array = [3, 4, 5, 6, 1->7, 6₂->8, 6₃->9, 10, 11, 15->12]
Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& A) {

const int n = A.size();

sort(begin(A), end(A));

A.erase(unique(begin(A), end(A)), end(A));

int ans = INT_MAX;

for (int i = 0, j = 0, m = A.size(); i < m; ++i) {

while (j < m && A[j] < A[i] + n) ++j;

ans = min(ans, n - (j - i));

}

return ans;

}

};

花花酱 LeetCode 2008. Maximum Earnings From Taxi

By zxi on November 26, 2021

There are n points on a road you are driving your taxi on. The n points on the road are labeled from 1 to n in the direction you are going, and you want to drive from point 1 to point n to make money by picking up passengers. You cannot change the direction of the taxi.

The passengers are represented by a 0-indexed 2D integer array rides, where rides[i] = [start_i, end_i, tip_i] denotes the i^th passenger requesting a ride from point start_i to point end_i who is willing to give a tip_i dollar tip.

For each passenger i you pick up, you earn end_i - start_i + tip_i dollars. You may only drive at most one passenger at a time.

Given n and rides, return the maximum number of dollars you can earn by picking up the passengers optimally.

Note: You may drop off a passenger and pick up a different passenger at the same point.

Example 1:

Input: n = 5, rides = [[2,5,4],[1,5,1]]
Output: 7
Explanation: We can pick up passenger 0 to earn 5 - 2 + 4 = 7 dollars.

Example 2:

Input: n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
Output: 20
Explanation: We will pick up the following passengers:
- Drive passenger 1 from point 3 to point 10 for a profit of 10 - 3 + 2 = 9 dollars.
- Drive passenger 2 from point 10 to point 12 for a profit of 12 - 10 + 3 = 5 dollars.
- Drive passenger 5 from point 13 to point 18 for a profit of 18 - 13 + 1 = 6 dollars.
We earn 9 + 5 + 6 = 20 dollars in total.

Constraints:

1 <= n <= 10⁵
1 <= rides.length <= 3 * 10⁴
rides[i].length == 3
1 <= start_i < end_i <= n
1 <= tip_i <= 10⁵

Solution: DP

dp[i] := max earnings we can get at position i and the taxi is empty.

dp[i] = max(dp[i – 1], dp[s] + gain) where e = i, gain = e – s + tips

For each i, we check all the rides that end at i and find the best one (which may have different starting points), otherwise the earning will be the same as previous position (i – 1).

answer = dp[n]

Time complexity: O(m + n)
Space complexity: O(m + n)

C++

// Author: Huahua

class Solution {

public:

long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {

vector<long long> dp(n + 1);

vector<vector<pair<int, int>>> m(n + 1);

for (const auto& r : rides)

m[r[1]].emplace_back(r[0], r[1] - r[0] + r[2]);

for (int i = 1; i <= n; ++i) {

dp[i] = dp[i - 1];

for (const auto [s, g] : m[i])

dp[i] = max(dp[i], dp[s] + g);

}

return dp[n];

}

};

Huahua's Tech Road

花花酱 LeetCode 33. Search in Rotated Sorted Array

Solution: Binary Search

C++

花花酱 LeetCode 30. Substring with Concatenation of All Words

Solution: Hashtable + Brute Force

C++

花花酱 LeetCode 29. Divide Two Integers

Solution: Binary / Bit Operation

C++

花花酱 LeetCode 2009. Minimum Number of Operations to Make Array Continuous

Solution: Sliding Window

C++

花花酱 LeetCode 2008. Maximum Earnings From Taxi

Solution: DP

C++