Huahua’s Tech Road

花花酱 LeetCode 2105. Watering Plants II

By zxi on December 12, 2021

Problem

Solution: Simulation w/ Two Pointers

Simulate the watering process.

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

C++

// Author: Huahua

class Solution {

public:

int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {

const int n = plants.size();

int ans = 0;

for (int l = 0, r = n - 1, A = capacityA, B = capacityB; l <= r; ++l, --r) {

if (l == r)

return ans += max(A, B) < plants[l];

if ((A -= plants[l]) < 0)

A = capacityA - plants[l], ++ans;

if ((B -= plants[r]) < 0)

B = capacityB - plants[r], ++ans;

}

return ans;

}

};

花花酱 LeetCode 2104. Sum of Subarray Ranges

By zxi on December 12, 2021

Solution 0: Brute force [TLE]

Enumerate all subarrays, for each one, find min and max.

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

Solution 1: Prefix min/max

We can use prefix technique to extend the array while keep tracking the min/max of the subarray.

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

C++

// Author: Huahua

class Solution {

public:

long long subArrayRanges(vector<int>& nums) {

const int n = nums.size();

long long ans = 0;

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

int lo = nums[i];

int hi = nums[i];

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

lo = min(lo, nums[j]);

hi = max(hi, nums[j]);

ans += (hi - lo);

}

return ans;

}

};

Solution 2: Monotonic stack

This problem can be reduced to 花花酱 LeetCode 907. Sum of Subarray Minimums

Just need to run twice one for sum of mins and another for sum of maxs.

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

C++

// Author: Huahua

class Solution {

public:

long long subArrayRanges(vector<int>& nums) {

const int n = nums.size();

auto sumOf = [&](function<bool(int, int)> op) {

long long ans = 0;

stack<int> s;

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

while (!s.empty() and (i == n or op(nums[s.top()], nums[i]))) {

long long k = s.top(); s.pop();

long long j = s.empty() ? -1 : s.top();

ans += nums[k] * (i - k) * (k - j);

}

s.push(i);

}

return ans;

};

return sumOf(less<int>()) - sumOf(greater<int>());

}

};

花花酱 LeetCode 2103. Rings and Rods

By zxi on December 12, 2021

Problem

Solution: Hashset

Use 10 hashsets to track the status of each rod, check whether it contains three unique elements (R,G,B).

Time complexity: O(n)
Space complexity: O(10*3)

C++

// Author: Huahua

class Solution {

public:

int countPoints(string rings) {

constexpr int kRods = 10;

vector<unordered_set<char>> s(kRods);

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

s[rings[i + 1] - '0'].insert(rings[i]);

int ans = 0;

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

if (s[i].size() == 3)

++ans;

return ans;

}

};

花花酱 LeetCode 2102. Sequentially Ordinal Rank Tracker

By zxi on December 12, 2021

A scenic location is represented by its name and attractiveness score, where name is a unique string among all locations and score is an integer. Locations can be ranked from the best to the worst. The higher the score, the better the location. If the scores of two locations are equal, then the location with the lexicographically smaller name is better.

You are building a system that tracks the ranking of locations with the system initially starting with no locations. It supports:

Adding scenic locations, one at a time.
Querying the i^th best location of all locations already added, where i is the number of times the system has been queried (including the current query).
- For example, when the system is queried for the 4^th time, it returns the 4^th best location of all locations already added.

Note that the test data are generated so that at any time, the number of queries does not exceed the number of locations added to the system.

Implement the SORTracker class:

SORTracker() Initializes the tracker system.
void add(string name, int score) Adds a scenic location with name and score to the system.
string get() Queries and returns the i^th best location, where i is the number of times this method has been invoked (including this invocation).

Example 1:

Input

["SORTracker", "add", "add", "get", "add", "get", "add", "get", "add", "get", "add", "get", "get"]

[[], ["bradford", 2], ["branford", 3], [], ["alps", 2], [], ["orland", 2], [], ["orlando", 3], [], ["alpine", 2], [], []]

Output

[null, null, null, "branford", null, "alps", null, "bradford", null, "bradford", null, "bradford", "orland"]

Explanation

SORTracker tracker = new SORTracker(); // Initialize the tracker system.

tracker.add("bradford", 2); // Add location with name="bradford" and score=2 to the system.

tracker.add("branford", 3); // Add location with name="branford" and score=3 to the system.

tracker.get(); // The sorted locations, from best to worst, are: branford, bradford.

// Note that branford precedes bradford due to its higher score (3 > 2).

// This is the 1st time get() is called, so return the best location: "branford".

tracker.add("alps", 2); // Add location with name="alps" and score=2 to the system.

tracker.get(); // Sorted locations: branford, alps, bradford.

// Note that alps precedes bradford even though they have the same score (2).

// This is because "alps" is lexicographically smaller than "bradford".

// Return the 2nd best location "alps", as it is the 2nd time get() is called.

tracker.add("orland", 2); // Add location with name="orland" and score=2 to the system.

tracker.get(); // Sorted locations: branford, alps, bradford, orland.

// Return "bradford", as it is the 3rd time get() is called.

tracker.add("orlando", 3); // Add location with name="orlando" and score=3 to the system.

tracker.get(); // Sorted locations: branford, orlando, alps, bradford, orland.

// Return "bradford".

tracker.add("alpine", 2); // Add location with name="alpine" and score=2 to the system.

tracker.get(); // Sorted locations: branford, orlando, alpine, alps, bradford, orland.

// Return "bradford".

tracker.get(); // Sorted locations: branford, orlando, alpine, alps, bradford, orland.

// Return "orland".

Constraints:

name consists of lowercase English letters, and is unique among all locations.
1 <= name.length <= 10
1 <= score <= 10⁵
At any time, the number of calls to get does not exceed the number of calls to add.
At most 4 * 10⁴ calls in total will be made to add and get.

Solution: TreeSet w/ Iterator

Use a treeset to store all the entries and use a iterator that points to the entry to return. When inserting a new entry into the tree, if it’s higher than the current element then let the iterator go backward one step.

Time complexity: add O(logn) / get O(1)

C++

// Author: Huahua

class SORTracker {

public:

SORTracker() {}

void add(string name, int score) {

if (*s.emplace(-score, name).first < *cit) --cit;

}

string get() {

return (cit++)->second;

}

private:

set<pair<int, string>> s;

// Note: cit points to begin(s) after first insertion.

set<pair<int, string>>::const_iterator cit = end(s);

};

花花酱 LeetCode 2101. Detonate the Maximum Bombs

By zxi on December 12, 2021

You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb.

The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [x_i, y_i, r_i]. x_i and y_i denote the X-coordinate and Y-coordinate of the location of the i^th bomb, whereas r_i denotes the radius of its range.

You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range. These bombs will further detonate the bombs that lie in their ranges.

Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb.

Example 1:

Input: bombs = [[2,1,3],[6,1,4]]
Output: 2
Explanation:
The above figure shows the positions and ranges of the 2 bombs.
If we detonate the left bomb, the right bomb will not be affected.
But if we detonate the right bomb, both bombs will be detonated.
So the maximum bombs that can be detonated is max(1, 2) = 2.

Example 2:

Input: bombs = [[1,1,5],[10,10,5]]
Output: 1
Explanation:
Detonating either bomb will not detonate the other bomb, so the maximum number of bombs that can be detonated is 1.

Example 3:

Input: bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
Output: 5
Explanation:
The best bomb to detonate is bomb 0 because:
- Bomb 0 detonates bombs 1 and 2. The red circle denotes the range of bomb 0.
- Bomb 2 detonates bomb 3. The blue circle denotes the range of bomb 2.
- Bomb 3 detonates bomb 4. The green circle denotes the range of bomb 3.
Thus all 5 bombs are detonated.

Constraints:

1 <= bombs.length <= 100
bombs[i].length == 3
1 <= x_i, y_i, r_i <= 10⁵

Solution: Simulation w/ BFS

Enumerate the bomb to detonate, and simulate the process using BFS.

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

C++

// Author: Huahua

class Solution {

public:

int maximumDetonation(vector<vector<int>>& bombs) {

const int n = bombs.size();

auto check = [&](int i, int j) -> bool {

long x1 = bombs[i][0], y1 = bombs[i][1], r1 = bombs[i][2];

long x2 = bombs[j][0], y2 = bombs[j][1], r2 = bombs[j][2];

return ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= r1 * r1);

};

int ans = 0;

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

int count = 0;

queue<int> q{{s}};

vector<int> seen(n);

seen[s] = 1;

while (!q.empty()) {

++count;

int i = q.front(); q.pop();

for (int j = 0; j < n; ++j)

if (check(i, j) && !seen[j]++)

q.push(j);

}

ans = max(ans, count);

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2105. Watering Plants II

Problem

C++

花花酱 LeetCode 2104. Sum of Subarray Ranges

Problem

Solution 0: Brute force [TLE]

Solution 1: Prefix min/max

C++

Solution 2: Monotonic stack

C++

花花酱 LeetCode 2103. Rings and Rods

Solution: Hashset

C++

花花酱 LeetCode 2102. Sequentially Ordinal Rank Tracker

Solution: TreeSet w/ Iterator

C++

花花酱 LeetCode 2101. Detonate the Maximum Bombs

Solution: Simulation w/ BFS

C++