Posts tagged as “medium”

花花酱 LeetCode 69. Sqrt(x)

By zxi on November 26, 2021

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Example 1:

Input: x = 4
Output: 2

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Constraints:

0 <= x <= 2³¹ - 1

Solution 1: Binary Search

Find the smallest l such that l * l > x, sqrt(x) = l – 1.

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

C++

// Author: Huahua

class Solution {

public:

int mySqrt(int x) {

unsigned l = 1;

unsigned r = 1u + x;

while (l < r) {

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

if (m > x / m) {

r = m;

} else {

l = m + 1;

}

return l - 1;

}

};

花花酱 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 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 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];

}

};

花花酱 LeetCode 2007. Find Original Array From Doubled Array

By zxi on November 25, 2021

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

Example 1:

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].

Example 2:

Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.

Example 3:

Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.

Constraints:

1 <= changed.length <= 10⁵
0 <= changed[i] <= 10⁵

Solution 1: Multiset

Start from the smallest number x, erase one x * 2 from the set.

Time complexity: O(nlogn)
Space complexity: O(n)

C++/Multiset

// Author: Huahua

class Solution {

public:

vector<int> findOriginalArray(vector<int>& changed) {

if (changed.size() & 1) return {};

const int n = changed.size() / 2;

multiset<int> s(begin(changed), end(changed));

while (ans.size() != n) {

int o = *begin(s);

s.erase(begin(s));

ans.push_back(o);

auto it = s.find(o * 2);

if (it == end(s)) return {};

s.erase(it);

}

return ans;

}

};

Solution 2: Hashtable

Time complexity: O(max(nums) + n)
Space complexity: O(max(nums))

C++/Hashtable

// Author: Huahua

class Solution {

public:

vector<int> findOriginalArray(vector<int>& changed) {

if (changed.size() & 1) return {};

const int n = changed.size() / 2;

const int kMax = *max_element(begin(changed), end(changed));

vector<int> m(kMax + 1);

for (int x : changed) ++m[x];

if (m[0] & 1) return {};

vector<int> ans(m[0] / 2, 0);

for (int x = 1; ans.size() != n; ++x) {

if (x * 2 > kMax || m[x * 2] < m[x]) return {};

ans.insert(end(ans), m[x], x);

m[x * 2] -= m[x];

}

return ans;

}

};