Posts tagged as “medium”

花花酱 LeetCode 2249. Count Lattice Points Inside a Circle

By zxi on April 27, 2022

Given a 2D integer array circles where circles[i] = [x_i, y_i, r_i] represents the center (x_i, y_i) and radius r_i of the i^th circle drawn on a grid, return the number of lattice points that are present inside at least one circle.

Note:

A lattice point is a point with integer coordinates.
Points that lie on the circumference of a circle are also considered to be inside it.

Example 1:

Input: circles = [[2,2,1]]
Output: 5
Explanation:
The figure above shows the given circle.
The lattice points present inside the circle are (1, 2), (2, 1), (2, 2), (2, 3), and (3, 2) and are shown in green.
Other points such as (1, 1) and (1, 3), which are shown in red, are not considered inside the circle.
Hence, the number of lattice points present inside at least one circle is 5.

Example 2:

Input: circles = [[2,2,2],[3,4,1]]
Output: 16
Explanation:
The figure above shows the given circles.
There are exactly 16 lattice points which are present inside at least one circle. 
Some of them are (0, 2), (2, 0), (2, 4), (3, 2), and (4, 4).

Constraints:

1 <= circles.length <= 200
circles[i].length == 3
1 <= x_i, y_i <= 100
1 <= r_i <= min(x_i, y_i)

Solution: Brute Force

Time complexity: O(m * m * n) = O(200 * 200 * 200)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countLatticePoints(vector<vector<int>>& circles) {

auto isIn = [](int u, int v, int x, int y, int r) {

return (u - x) * (u - x) + (v - y) * (v - y) <= r * r;

};

int ans = 0;

for (int u = 0; u <= 200; ++u)

for (int v = 0; v <= 200; ++v) {

bool found = false;

for (const auto& c : circles)

if (isIn(u, v, c[0], c[1], c[2])) {

found = true;

break;

}

ans += found;

}

return ans;

}

};

花花酱 LeetCode 2244. Minimum Rounds to Complete All Tasks

By zxi on April 17, 2022

You are given a 0-indexed integer array tasks, where tasks[i] represents the difficulty level of a task. In each round, you can complete either 2 or 3 tasks of the same difficulty level.

Return the minimum rounds required to complete all the tasks, or -1 if it is not possible to complete all the tasks.

Example 1:

Input: tasks = [2,2,3,3,2,4,4,4,4,4]
Output: 4
Explanation: To complete all the tasks, a possible plan is:
- In the first round, you complete 3 tasks of difficulty level 2. 
- In the second round, you complete 2 tasks of difficulty level 3. 
- In the third round, you complete 3 tasks of difficulty level 4. 
- In the fourth round, you complete 2 tasks of difficulty level 4.  
It can be shown that all the tasks cannot be completed in fewer than 4 rounds, so the answer is 4.

Example 2:

Input: tasks = [2,3,3]
Output: -1
Explanation: There is only 1 task of difficulty level 2, but in each round, you can only complete either 2 or 3 tasks of the same difficulty level. Hence, you cannot complete all the tasks, and the answer is -1.

Constraints:

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

Solution: Math

Count the frequency of each level. The only case that can not be finished is 1 task at some level. Otherwise we can always finish it by 2, 3 tasks at a time.

if n = 2: 2 => 1 round
if n = 3: 3 => 1 round
if n = 4: 2 + 2 => 2 rounds
if n = 5: 3 + 2 => 2 rounds
…
if n = 3k, n % 3 == 0 : 3 + 3 + … + 3 = k rounds
if n = 3k + 1, n % 3 == 1 : 3*(k – 1) + 2 + 2 = k + 1 rounds
if n = 3k + 2, n % 3 == 2 : 3*k + 2 = k + 1 rounds

We need (n + 2) / 3 rounds.

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

C++

// Author: Huahua

class Solution {

public:

int minimumRounds(vector<int>& tasks) {

unordered_map<int, int> m;

for (int t : tasks) ++m[t];

int ans = 0;

for (auto [level, count] : m) {

if (count == 1) return -1;

ans += (count + 2) / 3;

}

return ans;

}

};

花花酱 LeetCode 2241. Design an ATM Machine

By zxi on April 16, 2022

There is an ATM machine that stores banknotes of 5 denominations: 20, 50, 100, 200, and 500 dollars. Initially the ATM is empty. The user can use the machine to deposit or withdraw any amount of money.

When withdrawing, the machine prioritizes using banknotes of larger values.

For example, if you want to withdraw $300 and there are 2 $50 banknotes, 1 $100 banknote, and 1 $200 banknote, then the machine will use the $100 and $200 banknotes.
However, if you try to withdraw $600 and there are 3 $200 banknotes and 1 $500 banknote, then the withdraw request will be rejected because the machine will first try to use the $500 banknote and then be unable to use banknotes to complete the remaining $100. Note that the machine is not allowed to use the $200 banknotes instead of the $500 banknote.

Implement the ATM class:

ATM() Initializes the ATM object.
void deposit(int[] banknotesCount) Deposits new banknotes in the order $20, $50, $100, $200, and $500.
int[] withdraw(int amount) Returns an array of length 5 of the number of banknotes that will be handed to the user in the order $20, $50, $100, $200, and $500, and update the number of banknotes in the ATM after withdrawing. Returns [-1] if it is not possible (do not withdraw any banknotes in this case).

Example 1:

Input
["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"]
[[], [[0,0,1,2,1]], [600], [[0,1,0,1,1]], [600], [550]]
Output
[null, null, [0,0,1,0,1], null, [-1], [0,1,0,0,1]]

Explanation
ATM atm = new ATM();
atm.deposit([0,0,1,2,1]); // Deposits 1 $100 banknote, 2 $200 banknotes,
                          // and 1 $500 banknote.
atm.withdraw(600);        // Returns [0,0,1,0,1]. The machine uses 1 $100 banknote
                          // and 1 $500 banknote. The banknotes left over in the
                          // machine are [0,0,0,2,0].
atm.deposit([0,1,0,1,1]); // Deposits 1 $50, $200, and $500 banknote.
                          // The banknotes in the machine are now [0,1,0,3,1].
atm.withdraw(600);        // Returns [-1]. The machine will try to use a $500 banknote
                          // and then be unable to complete the remaining $100,
                          // so the withdraw request will be rejected.
                          // Since the request is rejected, the number of banknotes
                          // in the machine is not modified.
atm.withdraw(550);        // Returns [0,1,0,0,1]. The machine uses 1 $50 banknote
                          // and 1 $500 banknote.

Constraints:

banknotesCount.length == 5
0 <= banknotesCount[i] <= 10⁹
1 <= amount <= 10⁹
At most 5000 calls in total will be made to withdraw and deposit.
At least one call will be made to each function withdraw and deposit.

Solution:

Follow the rules. Note: total count can be very large, use long instead.

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

C++

// Author: Huahua

constexpr int kNotes = 5;

constexpr long notes[kNotes] = {20, 50, 100, 200, 500};

class ATM {

public:

ATM(): counts(kNotes) {}

void deposit(vector<int> banknotesCount) {

for (int i = 0; i < kNotes; ++i)

counts[i] += banknotesCount[i];

}

vector<int> withdraw(int amount) {

vector<int> ans(kNotes);

vector<long> tmp(counts);

for (int i = kNotes - 1; i >= 0; --i)

if (amount >= notes[i]) {

int c = min(counts[i], amount / notes[i]);

ans[i] = c;

amount -= c * notes[i];

tmp[i] -= c;

}

if (amount != 0) return {-1};

counts.swap(tmp);

return ans;

}

private:

vector<long> counts;

};

花花酱 LeetCode 2233. Maximum Product After K Increments

By zxi on April 9, 2022

You are given an array of non-negative integers nums and an integer k. In one operation, you may choose any element from nums and increment it by 1.

Return the maximum product of nums after at most k operations. Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: nums = [0,4], k = 5
Output: 20
Explanation: Increment the first number 5 times.
Now nums = [5, 4], with a product of 5 * 4 = 20.
It can be shown that 20 is maximum product possible, so we return 20.
Note that there may be other ways to increment nums to have the maximum product.

Example 2:

Input: nums = [6,3,3,2], k = 2
Output: 216
Explanation: Increment the second number 1 time and increment the fourth number 1 time.
Now nums = [6, 4, 3, 3], with a product of 6 * 4 * 3 * 3 = 216.
It can be shown that 216 is maximum product possible, so we return 216.
Note that there may be other ways to increment nums to have the maximum product.

Constraints:

1 <= nums.length, k <= 10⁵
0 <= nums[i] <= 10⁶

Solution: priority queue

Always increment the smallest number. Proof?

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

C++

// Author: Huahua

class Solution {

public:

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

constexpr int kMod = 1e9 + 7;

priority_queue<int, vector<int>, greater<int>> q(begin(nums), end(nums));

while (k--) {

const int n = q.top();

q.pop();

q.push(n + 1);

}

long long ans = 1;

while (!q.empty()) {

ans *= q.top(); q.pop();

ans %= kMod;

}

return ans;

}

};

花花酱 LeetCode 2232. Minimize Result by Adding Parentheses to Expression

By zxi on April 9, 2022

You are given a 0-indexed string expression of the form "<num1>+<num2>" where <num1> and <num2> represent positive integers.

Add a pair of parentheses to expression such that after the addition of parentheses, expression is a valid mathematical expression and evaluates to the smallest possible value. The left parenthesis must be added to the left of '+' and the right parenthesis must be added to the right of '+'.

Return expression after adding a pair of parentheses such that expression evaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.

The input has been generated such that the original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

Example 1:

Input: expression = "247+38"
Output: "2(47+38)"
Explanation: The expression evaluates to 2 * (47 + 38) = 2 * 85 = 170.
Note that "2(4)7+38" is invalid because the right parenthesis must be to the right of the '+'.
It can be shown that 170 is the smallest possible value.

Example 2:

Input: expression = "12+34"
Output: "1(2+3)4"
Explanation: The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.

Example 3:

Input: expression = "999+999"
Output: "(999+999)"
Explanation: The expression evaluates to 999 + 999 = 1998.

Constraints:

3 <= expression.length <= 10
expression consists of digits from '1' to '9' and '+'.
expression starts and ends with digits.
expression contains exactly one '+'.
The original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

Solution: Brute Force

Try all possible positions to add parentheses and evaluate the new expression.

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

C++

// Author: Huahua

class Solution {

public:

string minimizeResult(string expression) {

const int n = expression.size();

auto p = expression.find('+');

int best = INT_MAX;

string ans;

for (int l = 0; l < p; ++l)

for (int r = p + 2; r < n + 1; ++r) {

const int m1 = l ? stoi(expression.substr(0, l)) : 1;

const int m2 = (r < n) ? stoi(expression.substr(r)) : 1;

const int n1 = stoi(expression.substr(l, p));

const int n2 = stoi(expression.substr(p + 1, r - p - 1));

const int cur = m1 * (n1 + n2) * m2;

if (cur < best) {

best = cur;

ans = expression;

ans.insert(l, "(");

ans.insert(r + 1, ")");

}

return ans;

}

};