Posts tagged as “medium”

花花酱 LeetCode 1807. Evaluate the Bracket Pairs of a String

By zxi on March 27, 2021

You are given a string s that contains some bracket pairs, with each pair containing a non-empty key.

For example, in the string "(name)is(age)yearsold", there are two bracket pairs that contain the keys "name" and "age".

You know the values of a wide range of keys. This is represented by a 2D string array knowledge where each knowledge[i] = [key_i, value_i] indicates that key key_i has a value of value_i.

You are tasked to evaluate all of the bracket pairs. When you evaluate a bracket pair that contains some key key_i, you will:

Replace key_i and the bracket pair with the key’s corresponding value_i.
If you do not know the value of the key, you will replace key_i and the bracket pair with a question mark "?" (without the quotation marks).

Each key will appear at most once in your knowledge. There will not be any nested brackets in s.

Return the resulting string after evaluating all of the bracket pairs.

Example 1:

Input: s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]
Output: "bobistwoyearsold"
Explanation:
The key "name" has a value of "bob", so replace "(name)" with "bob".
The key "age" has a value of "two", so replace "(age)" with "two".

Example 2:

Input: s = "hi(name)", knowledge = [["a","b"]]
Output: "hi?"
Explanation: As you do not know the value of the key "name", replace "(name)" with "?".

Example 3:

Input: s = "(a)(a)(a)aaa", knowledge = [["a","yes"]]
Output: "yesyesyesaaa"
Explanation: The same key can appear multiple times.
The key "a" has a value of "yes", so replace all occurrences of "(a)" with "yes".
Notice that the "a"s not in a bracket pair are not evaluated.

Example 4:

Input: s = "(a)(b)", knowledge = [["a","b"],["b","a"]]
Output: "ba"

Constraints:

1 <= s.length <= 10⁵
0 <= knowledge.length <= 10⁵
knowledge[i].length == 2
1 <= key_i.length, value_i.length <= 10
s consists of lowercase English letters and round brackets '(' and ')'.
Every open bracket '(' in s will have a corresponding close bracket ')'.
The key in each bracket pair of s will be non-empty.
There will not be any nested bracket pairs in s.
key_i and value_i consist of lowercase English letters.
Each key_i in knowledge is unique.

Solution: Hashtable + Simulation

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

C++

// Author: Huahua

class Solution {

public:

string evaluate(string s, vector<vector<string>>& knowledge) {

unordered_map<string, string> m;

for (const auto& p : knowledge)

m[p[0]] = p[1];

string ans;

string cur;

bool in = false;

for (char c : s) {

if (c == '(') {

in = true;

} else if (c == ')') {

if (m.count(cur))

ans += m[cur];

else

ans += "?";

cur.clear();

in = false;

} else {

if (!in) ans += c;

else cur += c;

}

return ans;

}

};

花花酱 LeetCode 1806. Minimum Number of Operations to Reinitialize a Permutation

By zxi on March 27, 2021

You are given an even integer n. You initially have a permutation perm of size n where perm[i] == i (0-indexed).

In one operation, you will create a new array arr, and for each i:

If i % 2 == 0, then arr[i] = perm[i / 2].
If i % 2 == 1, then arr[i] = perm[n / 2 + (i - 1) / 2].

You will then assign arr to perm.

Return the minimum non-zero number of operations you need to perform on perm to return the permutation to its initial value.

Example 1:

Input: n = 2
Output: 1
Explanation: prem = [0,1] initially.
After the 1^st operation, prem = [0,1]
So it takes only 1 operation.

Example 2:

Input: n = 4
Output: 2
Explanation: prem = [0,1,2,3] initially.
After the 1^st operation, prem = [0,2,1,3]
After the 2^nd operation, prem = [0,1,2,3]
So it takes only 2 operations.

Example 3:

Input: n = 6
Output: 4

Constraints:

2 <= n <= 1000
n is even.

Solution: Brute Force / Simulation

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

C++

// Author: Huahua

class Solution {

public:

int reinitializePermutation(int n) {

vector<int> perm(n);

vector<int> arr(n);

for (int i = 0; i < n; ++i) perm[i] = i;

int ans = 0;

bool flag = true;

while (flag && ++ans) {

flag = false;

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

arr[i] = i & 1 ? perm[n / 2 + (i - 1) / 2] : perm[i / 2];

flag |= arr[i] != i;

}

swap(perm, arr);

}

return ans;

}

};

花花酱 LeetCode 1802. Maximum Value at a Given Index in a Bounded Array

By zxi on March 22, 2021

You are given three positive integers n, index and maxSum. You want to construct an array nums (0-indexed) that satisfies the following conditions:

nums.length == n
nums[i] is a positive integer where 0 <= i < n.
abs(nums[i] - nums[i+1]) <= 1 where 0 <= i < n-1.
The sum of all the elements of nums does not exceed maxSum.
nums[index] is maximized.

Return nums[index] of the constructed array.

Note that abs(x) equals x if x >= 0, and -x otherwise.

Example 1:

Input: n = 4, index = 2,  maxSum = 6
Output: 2
Explanation: The arrays [1,1,2,1] and [1,2,2,1] satisfy all the conditions. There are no other valid arrays with a larger value at the given index.

Example 2:

Input: n = 6, index = 1,  maxSum = 10
Output: 3

Constraints:

1 <= n <= maxSum <= 10⁹
0 <= index < n

Solution: Binary Search

To maximize nums[index], we can construct an array like this:
[1, 1, 1, …, 1, 2, 3, …, k – 1, k, k – 1, …,3, 2, 1, …., 1, 1, 1]

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

C++

// Author: Huahua

class Solution {

public:

int maxValue(int n, int index, int maxSum) {

int l = 1;

int r = maxSum + 1;

while (l < r) {

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

int64_t t1 = m - index;

int64_t t2 = m - (n - 1 - index);

int64_t s1 = (t1 + m) * (index + 1) / 2;

int64_t s2 = (m + t2) * (n - index) / 2;

if (t1 <= 0) s1 = (1 + m) * m / 2 + (index - m + 1);

if (t2 <= 0) s2 = (1 + m) * m / 2 + (n - index - m);

if (s1 + s2 - m > maxSum)

r = m;

else

l = m + 1;

}

return l - 1;

}

};

LeetCode 1801. Number of Orders in the Backlog

By zxi on March 21, 2021

You are given a 2D integer array orders, where each orders[i] = [price_i, amount_i, orderType_i] denotes that amount_iorders have been placed of type orderType_i at the price price_i. The orderType_i is:

0 if it is a batch of buy orders, or
1 if it is a batch of sell orders.

Note that orders[i] represents a batch of amount_i independent orders with the same price and order type. All orders represented by orders[i] will be placed before all orders represented by orders[i+1] for all valid i.

There is a backlog that consists of orders that have not been executed. The backlog is initially empty. When an order is placed, the following happens:

If the order is a buy order, you look at the sell order with the smallest price in the backlog. If that sell order’s price is smaller than or equal to the current buy order’s price, they will match and be executed, and that sell order will be removed from the backlog. Else, the buy order is added to the backlog.
Vice versa, if the order is a sell order, you look at the buy order with the largest price in the backlog. If that buy order’s price is larger than or equal to the current sell order’s price, they will match and be executed, and that buy order will be removed from the backlog. Else, the sell order is added to the backlog.

Return the total amount of orders in the backlog after placing all the orders from the input. Since this number can be large, return it modulo 10⁹ + 7.

Example 1:

Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
Output: 6
Explanation: Here is what happens with the orders:
- 5 orders of type buy with price 10 are placed. There are no sell orders, so the 5 orders are added to the backlog.
- 2 orders of type sell with price 15 are placed. There are no buy orders with prices larger than or equal to 15, so the 2 orders are added to the backlog.
- 1 order of type sell with price 25 is placed. There are no buy orders with prices larger than or equal to 25 in the backlog, so this order is added to the backlog.
- 4 orders of type buy with price 30 are placed. The first 2 orders are matched with the 2 sell orders of the least price, which is 15 and these 2 sell orders are removed from the backlog. The 3^rd order is matched with the sell order of the least price, which is 25 and this sell order is removed from the backlog. Then, there are no more sell orders in the backlog, so the 4^th order is added to the backlog.
Finally, the backlog has 5 buy orders with price 10, and 1 buy order with price 30. So the total number of orders in the backlog is 6.

Example 2:

Input: orders = [[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]]
Output: 999999984
Explanation: Here is what happens with the orders:
- 10⁹ orders of type sell with price 7 are placed. There are no buy orders, so the 10⁹ orders are added to the backlog.
- 3 orders of type buy with price 15 are placed. They are matched with the 3 sell orders with the least price which is 7, and those 3 sell orders are removed from the backlog.
- 999999995 orders of type buy with price 5 are placed. The least price of a sell order is 7, so the 999999995 orders are added to the backlog.
- 1 order of type sell with price 5 is placed. It is matched with the buy order of the highest price, which is 5, and that buy order is removed from the backlog.
Finally, the backlog has (1000000000-3) sell orders with price 7, and (999999995-1) buy orders with price 5. So the total number of orders = 1999999991, which is equal to 999999984 % (10⁹ + 7).

Constraints:

1 <= orders.length <= 10⁵
orders[i].length == 3
1 <= price_i, amount_i <= 10⁹
orderType_i is either 0 or 1.

Solution: Treemap / PriorityQueue / Heap

buy backlog: max heap
sell backlog: min heap
Trade happens between the tops of two queues.

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

C++

// Author: Huahua

class Solution {

public:

int getNumberOfBacklogOrders(vector<vector<int>>& orders) {

constexpr int kMod = 1e9 + 7;

map<int64_t, int64_t> buys;

map<int64_t, int64_t> sells;

for (const auto& order : orders) {

auto& m = order[2] == 0 ? buys : sells;

m[order[0]] += order[1];

while (buys.size() && sells.size()) {

auto b = rbegin(buys);

auto s = begin(sells);

if (b->first < s->first) break;

const int k = min(b->second, s->second);

if (!(b->second -= k)) buys.erase((++b).base());

if (!(s->second -= k)) sells.erase(s);

}

int64_t ans = 0;

for (const auto& [p, c] : buys) ans += c;

for (const auto& [p, c] : sells) ans += c;

return ans % kMod;

}

};

花花酱 LeetCode 1798. Maximum Number of Consecutive Values You Can Make

By zxi on March 20, 2021

You are given an integer array coins of length n which represents the n coins that you own. The value of the i^th coin is coins[i]. You can make some value x if you can choose some of your n coins such that their values sum up to x.

Return the maximum number of consecutive integer values that you can make with your coins starting from and including 0.

Note that you may have multiple coins of the same value.

Example 1:

Input: coins = [1,3]
Output: 2
Explanation: You can make the following values:
- 0: take []
- 1: take [1]
You can make 2 consecutive integer values starting from 0.

Example 2:

Input: coins = [1,1,1,4]
Output: 8
Explanation: You can make the following values:
- 0: take []
- 1: take [1]
- 2: take [1,1]
- 3: take [1,1,1]
- 4: take [4]
- 5: take [4,1]
- 6: take [4,1,1]
- 7: take [4,1,1,1]
You can make 8 consecutive integer values starting from 0.

Example 3:

Input: nums = [1,4,10,3,1]
Output: 20

Constraints:

coins.length == n
1 <= n <= 4 * 10⁴
1 <= coins[i] <= 4 * 10⁴

Solution: Greedy + Math

We want to start with smaller values, sort input array in ascending order.

First of all, the first number has to be 1 in order to generate sum of 1.
Assuming the first i numbers can generate 0 ~ k.
Then the i+1-th number x can be used if and only if x <= k + 1, such that we can have a consecutive sum of k + 1 by adding x to a sum between [0, k] and the new maximum sum we have will be k + x.

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

C++

// Author: Huahua

class Solution {

public:

int getMaximumConsecutive(vector<int>& coins) {

sort(begin(coins), end(coins));

int ans = 0;

for (int c : coins) {

if (c > ans + 1) break;

ans += c;

}

return ans + 1;

}

};