Huahua’s Tech Road

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

}

};

花花酱 LeetCode 2100. Find Good Days to Rob the Bank

By zxi on December 12, 2021

You and a gang of thieves are planning on robbing a bank. You are given a 0-indexed integer array security, where security[i] is the number of guards on duty on the i^th day. The days are numbered starting from 0. You are also given an integer time.

The i^th day is a good day to rob the bank if:

There are at least time days before and after the i^th day,
The number of guards at the bank for the time days before i are non-increasing, and
The number of guards at the bank for the time days after i are non-decreasing.

More formally, this means day i is a good day to rob the bank if and only if security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time].

Return a list of all days (0-indexed) that are good days to rob the bank. The order that the days are returned in does not matter.

Example 1:

Input: security = [5,3,3,3,5,6,2], time = 2
Output: [2,3]
Explanation:
On day 2, we have security[0] >= security[1] >= security[2] <= security[3] <= security[4].
On day 3, we have security[1] >= security[2] >= security[3] <= security[4] <= security[5].
No other days satisfy this condition, so days 2 and 3 are the only good days to rob the bank.

Example 2:

Input: security = [1,1,1,1,1], time = 0
Output: [0,1,2,3,4]
Explanation:
Since time equals 0, every day is a good day to rob the bank, so return every day.

Example 3:

Input: security = [1,2,3,4,5,6], time = 2
Output: []
Explanation:
No day has 2 days before it that have a non-increasing number of guards.
Thus, no day is a good day to rob the bank, so return an empty list.

Example 4:

Input: security = [1], time = 5
Output: []
Explanation:
No day has 5 days before and after it.
Thus, no day is a good day to rob the bank, so return an empty list.

Constraints:

1 <= security.length <= 10⁵
0 <= security[i], time <= 10⁵

Solution: Pre-Processing

Pre-compute the non-increasing days at days[i] and the non-decreasing days at days[i] using prefix and suffix arrays.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> goodDaysToRobBank(vector<int>& security, int time) {

const int n = security.size();

vector<int> before(n);

vector<int> after(n);

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

before[i] = security[i - 1] >= security[i] ? before[i - 1] + 1 : 0;

for (int i = n - 2; i >= 0; --i)

after[i] = security[i + 1] >= security[i] ? after[i + 1] + 1 : 0;

vector<int> ans;

for (int i = time; i + time < n; ++i)

if (before[i] >= time && after[i] >= time)

ans.push_back(i);

return ans;

}

};

花花酱 LeetCode 2099. Find Subsequence of Length K With the Largest Sum

By zxi on December 12, 2021

You are given an integer array nums and an integer k. You want to find a subsequence of nums of length k that has the largest sum.

Return any such subsequence as an integer array of length k.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [2,1,3,3], k = 2
Output: [3,3]
Explanation:
The subsequence has the largest sum of 3 + 3 = 6.

Example 2:

Input: nums = [-1,-2,3,4], k = 3
Output: [-1,3,4]
Explanation: 
The subsequence has the largest sum of -1 + 3 + 4 = 6.

Example 3:

Input: nums = [3,4,3,3], k = 2
Output: [3,4]
Explanation:
The subsequence has the largest sum of 3 + 4 = 7. 
Another possible subsequence is [4, 3].

Constraints:

1 <= nums.length <= 1000
-10⁵ <= nums[i] <= 10⁵
1 <= k <= nums.length

Solution 1: Full sorting + Hashtable

Make a copy of the original array, sort it in whole and put k largest elements in a hashtable.

Scan the original array and append the number to the answer array if it’s in the hashtable.

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

C++

// Author: Huahua

class Solution {

public:

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

vector<int> ans;

vector<int> s(nums);

sort(rbegin(s), rend(s));

unordered_map<int, int> m;

for (int i = 0; i < k; ++i) ++m[s[i]];

for (int x : nums)

if (--m[x] >= 0)

ans.push_back(x);

return ans;

}

};

Solution 2: k-th element

Use quick select / partial sort to find the k-th largest element of the array. Any number greater than that must be in the sequence. The tricky part is: what about the pivot itself? We couldn’t include ’em all blindly. Need to figure out how many copies of the pivot is there in the k largest and only include as many as of that in the final answer.

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

C++

// Author: Huahua

class Solution {

public:

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

vector<int> ans;

vector<int> s(nums);

nth_element(begin(s), begin(s) + k - 1, end(s), greater<int>());

const int pivot = s[k - 1];

// How many pivots in the largest k elements.

int left = count(begin(s), begin(s) + k, pivot);

for (size_t i = 0; i != nums.size(); ++i)

if (nums[i] > pivot || (nums[i] == pivot && --left >= 0))

ans.push_back(nums[i]);

return ans;

}

};

花花酱 LeetCode Ultimate DP Study Plan Day 10

By zxi on December 11, 2021

413. Arithmetic Slices

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

def numberOfArithmeticSlices(self, nums: List[int]) -> int:

@cache

def dp(i: int) -> int:

"""Number of arithmetic subarrays end with nums[i]."""

if i < 2: return 0

if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]:

return 1 + dp(i - 1)

return 0

return sum(dp(i) for i in range(len(nums)))

91. Decode Ways

Python3

# Author: Huahua

# Time complexity: O(n^2) -> O(n)

# Space complexity: O(n)

class Solution:

@cache

def numDecodings(self, s: str) -> int:

if not s: return 1

if s[0] == '0': return 0

ans = self.numDecodings(s[1:])

if len(s) > 1 and (s[0] == '1' or (s[0] == '2' and s[1] <= '6')):

ans += self.numDecodings(s[2:])

return ans

花花酱 LeetCode Ultimate DP Study Plan Day 9

By zxi on December 11, 2021

139. Word Break

Python3

# Author: Huahua

# Time complexity: O(n^2)

# Space complexity: O(n^2)

class Solution:

def wordBreak(self, s: str, wordDict: List[str]) -> bool:

words = set(wordDict)

n = len(s)

@cache

def dp(s: str) -> bool:

"""Returns whether s is breakable."""

if not s: return True

for l in range(1, min(n, 20) + 1):

if s[0:l] in words and dp(s[l:]): return True

return dp(s)

Optimization

Python3

# Author: Huahua

# Time complexity: O(n*l^2)

# Space complexity: O(n)

class Solution:

def wordBreak(self, s: str, wordDict: List[str]) -> bool:

words = set(wordDict)

n = len(s)

@cache

def dp(i: int) -> bool:

"""Returns whether s[i:] is breakable."""

if i >= n: return True

for l in range(1, min(n, 20) + 1):

if s[i:i+l] in words and dp(i + l): return True

return dp(0)

Huahua's Tech Road

Solution: Simulation w/ BFS

C++

Solution: Pre-Processing

C++

Solution 1: Full sorting + Hashtable

C++

Solution 2: k-th element

C++

Python3

Python3

Python3

Optimization

Python3