Huahua’s Tech Road

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

}

};

花花酱 LeetCode 2006. Count Number of Pairs With Absolute Difference K

By zxi on November 25, 2021

Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums[i] - nums[j]| == k.

The value of |x| is defined as:

x if x >= 0.
-x if x < 0.

Example 1:

Input: nums = [1,2,2,1], k = 1
Output: 4
Explanation: The pairs with an absolute difference of 1 are:
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]

Example 2:

Input: nums = [1,3], k = 3
Output: 0
Explanation: There are no pairs with an absolute difference of 3.

Example 3:

Input: nums = [3,2,1,5,4], k = 2
Output: 3
Explanation: The pairs with an absolute difference of 2 are:
- [3,2,1,5,4]
- [3,2,1,5,4]
- [3,2,1,5,4]

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 100
1 <= k <= 99

Solution: Hashtable
|y – x| = k
y = x + k or y = x – k

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

C++

// Author: Huahua

class Solution {

public:

int countKDifference(vector<int>& nums, int k) {

unordered_map<int, int> m;

int ans = 0;

for (int x : nums) {

ans += m[x - k];

ans += m[x + k];

++m[x];

}

return ans;

}

};

花花酱 LeetCode 2081. Sum of k-Mirror Numbers

By zxi on November 21, 2021

A k-mirror number is a positive integer without leading zeros that reads the same both forward and backward in base-10 as well as in base-k.

For example, 9 is a 2-mirror number. The representation of 9 in base-10 and base-2 are 9 and 1001 respectively, which read the same both forward and backward.
On the contrary, 4 is not a 2-mirror number. The representation of 4 in base-2 is 100, which does not read the same both forward and backward.

Given the base k and the number n, return the sum of the n smallest k-mirror numbers.

Example 1:

Input: k = 2, n = 5
Output: 25
Explanation:
The 5 smallest 2-mirror numbers and their representations in base-2 are listed as follows:
  base-10    base-2
    1          1
    3          11
    5          101
    7          111
    9          1001
Their sum = 1 + 3 + 5 + 7 + 9 = 25.

Example 2:

Input: k = 3, n = 7
Output: 499
Explanation:
The 7 smallest 3-mirror numbers are and their representations in base-3 are listed as follows:
  base-10    base-3
    1          1
    2          2
    4          11
    8          22
    121        11111
    151        12121
    212        21212
Their sum = 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499.

Example 3:

Input: k = 7, n = 17
Output: 20379000
Explanation: The 17 smallest 7-mirror numbers are:
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596

Constraints:

2 <= k <= 9
1 <= n <= 30

Solution: Generate palindromes in base-k.

Python

# Author: Huahua

class Solution:

def kMirror(self, k: int, n: int) -> int:

def getNext(x: str) -> str:

s = list(x)

l = len(s)

for i in range(l // 2, l):

if int(s[i]) + 1 >= k: continue

s[i] = s[~i] = str(int(s[i]) + 1)

for j in range(l // 2, i): s[j] = s[~j] = "0"

return "".join(s)

return "1" + "0" * (l - 1) + "1"

ans = 0

x = "0"

for _ in range(n):

while True:

x = getNext(x)

val = int(x, k)

if str(val) == str(val)[::-1]: break

ans += val

return ans

花花酱 LeetCode 2080. Range Frequency Queries

By zxi on November 21, 2021

Design a data structure to find the frequency of a given value in a given subarray.

The frequency of a value in a subarray is the number of occurrences of that value in the subarray.

Implement the RangeFreqQuery class:

RangeFreqQuery(int[] arr) Constructs an instance of the class with the given 0-indexed integer array arr.
int query(int left, int right, int value) Returns the frequency of value in the subarray arr[left...right].

A subarray is a contiguous sequence of elements within an array. arr[left...right] denotes the subarray that contains the elements of nums between indices left and right (inclusive).

Example 1:

Input
["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
Output

[null, 1, 2]

Explanation RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]); rangeFreqQuery.query(1, 2, 4); // return 1. The value 4 occurs 1 time in the subarray [33, 4] rangeFreqQuery.query(0, 11, 33); // return 2. The value 33 occurs 2 times in the whole array.

Constraints:

1 <= arr.length <= 10⁵
1 <= arr[i], value <= 10⁴
0 <= left <= right < arr.length
At most 10⁵ calls will be made to query

Solution: Hashtable + Binary Search

Time complexity: Init: O(max(arr) + n), query: O(logn)
Space complexity: O(max(arr) + n)

C++

// Author: Huahua

class RangeFreqQuery {

public:

RangeFreqQuery(vector<int>& arr) : s_(10001) {

for (int i = 0; i < arr.size(); ++i)

s_[arr[i]].push_back(i);

}

int query(int left, int right, int value) {

const auto& m = s_[value];

if (m.empty()) return 0;

auto r = prev(upper_bound(begin(m), end(m), right));

auto l = lower_bound(begin(m), end(m), left);

return r - l + 1;

}

private:

vector<vector<int>> s_;

};

/**

* Your RangeFreqQuery object will be instantiated and called as such:

* RangeFreqQuery* obj = new RangeFreqQuery(arr);

* int param_1 = obj->query(left,right,value);

Huahua's Tech Road

花花酱 LeetCode 2008. Maximum Earnings From Taxi

Solution: DP

C++

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

Solution 1: Multiset

C++/Multiset

Solution 2: Hashtable

C++/Hashtable

花花酱 LeetCode 2006. Count Number of Pairs With Absolute Difference K

Solution: Hashtable|y – x| = ky = x + k or y = x – k

C++

花花酱 LeetCode 2081. Sum of k-Mirror Numbers

Solution: Generate palindromes in base-k.

Python

花花酱 LeetCode 2080. Range Frequency Queries

C++

Solution: Hashtable
|y – x| = k
y = x + k or y = x – k