Huahua’s Tech Road

花花酱 LeetCode 1298. Maximum Candies You Can Get from Boxes

By zxi on December 28, 2019

Given n boxes, each box is given in the format [status, candies, keys, containedBoxes] where:

status[i]: an integer which is 1 if box[i] is open and 0 if box[i] is closed.
candies[i]: an integer representing the number of candies in box[i].
keys[i]: an array contains the indices of the boxes you can open with the key in box[i].
containedBoxes[i]: an array contains the indices of the boxes found in box[i].

You will start with some boxes given in initialBoxes array. You can take all the candies in any open box and you can use the keys in it to open new boxes and you also can use the boxes you find in it.

Return the maximum number of candies you can get following the rules above.

Example 1:

Input: status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
Output: 16
Explanation: You will be initially given box 0. You will find 7 candies in it and boxes 1 and 2. Box 1 is closed and you don't have a key for it so you will open box 2. You will find 4 candies and a key to box 1 in box 2.
In box 1, you will find 5 candies and box 3 but you will not find a key to box 3 so box 3 will remain closed.
Total number of candies collected = 7 + 4 + 5 = 16 candy.

Example 2:

Input: status = [1,0,0,0,0,0], candies = [1,1,1,1,1,1], keys = [[1,2,3,4,5],[],[],[],[],[]], containedBoxes = [[1,2,3,4,5],[],[],[],[],[]], initialBoxes = [0]
Output: 6
Explanation: You have initially box 0. Opening it you can find boxes 1,2,3,4 and 5 and their keys. The total number of candies will be 6.

Example 3:

Input: status = [1,1,1], candies = [100,1,100], keys = [[],[0,2],[]], containedBoxes = [[],[],[]], initialBoxes = [1]
Output: 1

Example 4:

Input: status = [1], candies = [100], keys = [[]], containedBoxes = [[]], initialBoxes = []
Output: 0

Example 5:

Input: status = [1,1,1], candies = [2,3,2], keys = [[],[],[]], containedBoxes = [[],[],[]], initialBoxes = [2,1,0]
Output: 7

Constraints:

1 <= status.length <= 1000
status.length == candies.length == keys.length == containedBoxes.length == n
status[i] is 0 or 1.
1 <= candies[i] <= 1000
0 <= keys[i].length <= status.length
0 <= keys[i][j] < status.length
All values in keys[i] are unique.
0 <= containedBoxes[i].length <= status.length
0 <= containedBoxes[i][j] < status.length
All values in containedBoxes[i] are unique.
Each box is contained in one box at most.
0 <= initialBoxes.length <= status.length
0 <= initialBoxes[i] < status.length

Solution: BFS

Only push boxes that we can open into the queue.

When can we open the box?
1. When we find it and have the key in hand.
2. When we find the key and have the box in hand.

Time complexity: O(B + K)
Space complexity: O(B)

C++

// Author: Huahua

class Solution {

public:

int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {

vector<int> found(status.size());

vector<int> hasKeys(status);

queue<int> q;

for (int b : initialBoxes) {

found[b] = 1;

if (hasKeys[b]) q.push(b);

}

int ans = 0;

while (!q.empty()) {

int b = q.front();

q.pop();

ans += candies[b];

for (int t : containedBoxes[b]) {

found[t] = 1;

if (hasKeys[t]) q.push(t);

}

for (int t : keys[b]) {

if (!hasKeys[t] && found[t]) q.push(t);

hasKeys[t] = 1;

}

return ans;

}

};

花花酱 LeetCode 1296. Divide Array in Sets of K Consecutive Numbers

By zxi on December 26, 2019

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into sets of k consecutive numbers
Return True if its possibleotherwise return False.

Example 1:

Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].

Example 2:

Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
Output: true
Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].

Example 3:

Input: nums = [3,3,2,2,1,1], k = 3
Output: true

Example 4:

Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= nums.length

Solution: BST + Greedy

Start from the smallest available number and find k consecutive numbers.

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

C++

// Author: Huahua

class Solution {

public:

bool isPossibleDivide(vector<int>& nums, int k) {

if (nums.size() % k) return false;

map<int, int> m;

for (int num : nums) ++m[num];

while (m.size()) {

const int s = m.cbegin()->first;

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

auto it = m.find(s + i);

if (it == m.cend()) return false;

if (--it->second == 0) m.erase(it);

}

return true;

}

};

C++/V2

// Author: Huahua

class Solution {

public:

bool isPossibleDivide(vector<int>& nums, int k) {

if (nums.size() % k) return false;

map<int, int> m;

for (int num : nums) ++m[num];

while (m.size()) {

auto it = m.begin();

const int s = it->first;

for (int i = 0; i < k; ++i, ++it) {

if (it->first != s + i) return false;

if (--it->second == 0) m.erase(it);

}

return true;

}

};

Solution 2: HashTable

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

C++

class Solution {

public:

bool isPossibleDivide(vector<int>& nums, int k) {

if (nums.size() % k) return false;

unordered_map<int, int> m;

for (int num : nums) ++m[num];

queue<int> starts;

for (auto [n, f] : m)

if (!m.count(n - 1)) starts.push(n);

while (!starts.empty()) {

int s = starts.front();

starts.pop();

for (int t = s + k - 1; t >= s; t--) {

if (m[t] < m[s]) return false;

if ((m[t] -= m[s]) == 0) {

m.erase(t);

if (m.count(t + 1)) starts.push(t + 1);

}

return true;

}

};

花花酱 LeetCode 1295. Find Numbers with Even Number of Digits

By zxi on December 26, 2019

Given an array nums of integers, return how many of them contain an even number of digits.

Example 1:

Input: nums = [12,345,2,6,7896]
Output: 2
Explanation: 
12 contains 2 digits (even number of digits). 
345 contains 3 digits (odd number of digits). 
2 contains 1 digit (odd number of digits). 
6 contains 1 digit (odd number of digits). 
7896 contains 4 digits (even number of digits). 
Therefore only 12 and 7896 contain an even number of digits.

Example 2:

Input: nums = [555,901,482,1771]
Output: 1 
Explanation: 
Only 1771 contains an even number of digits.

Constraints:

1 <= nums.length <= 500
1 <= nums[i] <= 10^5

Solution: Math

Time complexity: O(n * log(max(num)))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int findNumbers(vector<int>& nums) {

return count_if(begin(nums), end(nums), [](int num) {

int d = 0;

do { ++d; } while (num /= 10);

return d % 2 == 0;

});

}

};

Python3

# Author: Huahua

class Solution:

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

return sum([len(str(x)) % 2 == 0 for x in nums])

花花酱 LeetCode 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

By zxi on December 17, 2019

Given a m x n matrix mat and an integer threshold. Return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

Example 1:

Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
Output: 2
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.

Example 2:

Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
Output: 0

Example 3:

Input: mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
Output: 3

Example 4:

Input: mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
Output: 2

Constraints:

1 <= m, n <= 300
m == mat.length
n == mat[i].length
0 <= mat[i][j] <= 10000
0 <= threshold <= 10^5

Solution: DP + Brute Force

Precompute the sums of sub-matrixes whose left-top corner is at (0,0).

Try all possible left-top corner and sizes.

Time complexity: O(m*n*min(m,n))
Space complexity: O(m*n)

C++

// Author: Huahua, 148 ms

class Solution {

public:

int maxSideLength(vector<vector<int>>& mat, int threshold) {

const int m = mat.size();

const int n = mat[0].size();

vector<vector<int>> dp(m + 1, vector<int>(n + 1));

for (int y = 1; y <= m; ++y)

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

dp[y][x] = dp[y][x - 1] + dp[y - 1][x] - dp[y - 1][x - 1] + mat[y - 1][x - 1];

auto rangeSum = [&](int x1, int y1, int x2, int y2) {

return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1];

};

int ans = 0;

for (int y = 1; y <= m; ++y)

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

for (int k = 0; y + k <= m && x + k <= n; ++k) {

if (rangeSum(x, y, x + k, y + k) > threshold) break;

ans = max(ans, k + 1);

}

return ans;

}

};

Solution 2: Binary Search

Search for the smallest size k that is greater than the threshold, ans = k – 1.

C++

// Author: Huahua, 116 ms

class Solution {

public:

int maxSideLength(vector<vector<int>>& mat, int threshold) {

const int m = mat.size();

const int n = mat[0].size();

vector<vector<int>> dp(m + 1, vector<int>(n + 1));

for (int y = 1; y <= m; ++y)

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

dp[y][x] = dp[y][x - 1] + dp[y - 1][x] - dp[y - 1][x - 1] + mat[y - 1][x - 1];

auto rangeSum = [&](int x1, int y1, int x2, int y2) {

return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1];

};

int ans = 0;

for (int y = 1; y <= m; ++y)

for (int x = 1; x <= n; ++x) {

int l = 0;

int r = min(m - y, n - x) + 1;

while (l < r) {

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

// Find smllest l that > threshold, ans = (l + 1) - 1

if (rangeSum(x, y, x + m, y + m) > threshold)

r = m;

else

l = m + 1;

}

ans = max(ans, (l + 1) - 1);

}

return ans;

}

};

Solution 3: Bounded Search

Time complexity: O(m*n + min(m,n))

C++

// Author: Huahua, 148 ms

class Solution {

public:

int maxSideLength(vector<vector<int>>& mat, int threshold) {

const int m = mat.size();

const int n = mat[0].size();

vector<vector<int>> dp(m + 1, vector<int>(n + 1));

for (int y = 1; y <= m; ++y)

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

dp[y][x] = dp[y][x - 1] + dp[y - 1][x] - dp[y - 1][x - 1] + mat[y - 1][x - 1];

auto rangeSum = [&](int x1, int y1, int x2, int y2) {

return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1];

};

int ans = 0;

for (int y = 1; y <= m; ++y)

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

for (int k = ans; y + k <= m && x + k <= n; ++k) {

if (rangeSum(x, y, x + k, y + k) > threshold) break;

ans = max(ans, k + 1);

}

return ans;

}

};

花花酱 LeetCode 1293. Shortest Path in a Grid with Obstacles Elimination

By zxi on December 14, 2019

iven a m * n grid, where each cell is either 0 (empty) or 1 (obstacle). In one step, you can move up, down, left or right from and to an empty cell.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m-1, n-1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

Example 1:

Input: 
grid = 
[[0,0,0],
 [1,1,0],
 [0,0,0],
 [0,1,1],
 [0,0,0]], 
k = 1
Output: 6
Explanation: 
The shortest path without eliminating any obstacle is 10. 
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

Example 2:

Input: 
grid = 
[[0,1,1],
 [1,1,1],
 [1,0,0]], 
k = 1
Output: -1
Explanation: 
We need to eliminate at least two obstacles to find such a walk.

Constraints:

grid.length == m
grid[0].length == n
1 <= m, n <= 40
1 <= k <= m*n
grid[i][j] == 0 or 1
grid[0][0] == grid[m-1][n-1] == 0

Solution: BFS

State: (x, y, k) where k is the number of obstacles along the path.

Time complexity: O(m*n*k)
Space complexity: O(m*n*k)

C++

// Author: Huahua, 8 ms, 10.5 MB

class Solution {

public:

int shortestPath(vector<vector<int>>& grid, int k) {

const vector<int> dirs{0, 1, 0, -1, 0};

const int n = grid.size();

const int m = grid[0].size();

vector<vector<int>> seen(n, vector<int>(m, INT_MAX));

queue<tuple<int, int, int>> q;

int steps = 0;

q.emplace(0, 0, 0);

seen[0][0] = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

int cx, cy, co;

tie(cx, cy, co) = q.front(); q.pop();

if (cx == m - 1 && cy == n - 1) return steps;

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

int x = cx + dirs[i];

int y = cy + dirs[i + 1];

if (x < 0 || y < 0 || x >= m || y >= n) continue;

int o = co + grid[y][x];

if (o >= seen[y][x] || o > k) continue;

seen[y][x] = o;

q.emplace(x, y, o);

}

++steps;

}

return -1;

}

};

Solution 2: DP

Time complexity: O(mnk)
Space complexity: O(mnk)

Bottom-Up

// AC 236 ms

class Solution {

public:

int shortestPath(vector<vector<int>>& grid, int k) {

constexpr int kInf = 1e9;

const int m = grid.size();

const int n = grid[0].size();

vector<vector<vector<int>>> dp(m + 2, vector<vector<int>>(n + 2, vector<int>(k + 1, kInf)));

dp[1][1][0] = 0;

for (int s = 0; s < 3; ++s)

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

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

const int o = grid[i - 1][j - 1];

for (int z = 0; z + o <= k; ++z)

dp[i][j][z + o] = min(dp[i][j][z + o],

min({dp[i - 1][j][z],

dp[i][j - 1][z],

dp[i + 1][j][z],

dp[i][j + 1][z]}) + 1);

}

int ans = *min_element(begin(dp[m][n]), end(dp[m][n]));

return ans >= kInf ? -1 : ans;

}

};

Top-Down

class Solution {

public:

int shortestPath(vector<vector<int>>& grid, int K) {

constexpr int kInf = 1e9;

const vector<int> dirs{0, 1, 0, -1, 0};

const int m = grid.size();

const int n = grid[0].size();

vector<vector<vector<int>>> mem(m + 2, vector<vector<int>>(n + 2, vector<int>(K + 1, -1)));

vector<vector<int>> seen(m + 2, vector<int>(n + 2));

function<int(int, int, int)> dp = [&](int x, int y, int k) {

if (x < 1 || x > n || y < 1 || y > m || k < 0 || seen[y][x]) return kInf;

if (x == 1 && y == 1) return 0;

if (mem[y][x][k] != -1) return mem[y][x][k];

seen[y][x] = 1;

int ans = kInf;

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

ans = min(ans, 1 + dp(x + dirs[i], y + dirs[i + 1], k - grid[y - 1][x - 1]));

seen[y][x] = 0;

return mem[y][x][k] = ans;

};

const int ans = dp(n, m, K);

return ans >= kInf ? -1 : ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1298. Maximum Candies You Can Get from Boxes

Solution: BFS

C++

花花酱 LeetCode 1296. Divide Array in Sets of K Consecutive Numbers

Solution: BST + Greedy

C++

C++/V2

Solution 2: HashTable

C++

Related Problems

花花酱 LeetCode 1295. Find Numbers with Even Number of Digits

Solution: Math

C++

Python3

花花酱 LeetCode 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

Solution: DP + Brute Force

C++

Solution 2: Binary Search

C++

Solution 3: Bounded Search

C++

花花酱 LeetCode 1293. Shortest Path in a Grid with Obstacles Elimination

Solution: BFS

C++

Solution 2: DP

Bottom-Up

Top-Down