Huahua’s Tech Road

花花酱 LeetCode 2088. Count Fertile Pyramids in a Land

By zxi on November 27, 2021

A farmer has a rectangular grid of land with m rows and n columns that can be divided into unit cells. Each cell is either fertile (represented by a 1) or barren (represented by a 0). All cells outside the grid are considered barren.

A pyramidal plot of land can be defined as a set of cells with the following criteria:

The number of cells in the set has to be greater than 1 and all cells must be fertile.
The apex of a pyramid is the topmost cell of the pyramid. The height of a pyramid is the number of rows it covers. Let (r, c) be the apex of the pyramid, and its height be h. Then, the plot comprises of cells (i, j) where r <= i <= r + h - 1 and c - (i - r) <= j <= c + (i - r).

An inverse pyramidal plot of land can be defined as a set of cells with similar criteria:

The number of cells in the set has to be greater than 1 and all cells must be fertile.
The apex of an inverse pyramid is the bottommost cell of the inverse pyramid. The height of an inverse pyramid is the number of rows it covers. Let (r, c) be the apex of the pyramid, and its height be h. Then, the plot comprises of cells (i, j) where r - h + 1 <= i <= r and c - (r - i) <= j <= c + (r - i).

Some examples of valid and invalid pyramidal (and inverse pyramidal) plots are shown below. Black cells indicate fertile cells.

Given a 0-indexed m x n binary matrix grid representing the farmland, return the total number of pyramidal and inverse pyramidal plots that can be found in grid.

Example 1:

Input: grid = [[0,1,1,0],[1,1,1,1]]
Output: 2
Explanation:
The 2 possible pyramidal plots are shown in blue and red respectively.
There are no inverse pyramidal plots in this grid. 
Hence total number of pyramidal and inverse pyramidal plots is 2 + 0 = 2.

Example 2:

Input: grid = [[1,1,1],[1,1,1]]
Output: 2
Explanation:
The pyramidal plot is shown in blue, and the inverse pyramidal plot is shown in red. 
Hence the total number of plots is 1 + 1 = 2.

Example 3:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 0
Explanation:
There are no pyramidal or inverse pyramidal plots in the grid.

Example 4:

Input: grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]
Output: 13
Explanation:
There are 7 pyramidal plots, 3 of which are shown in the 2nd and 3rd figures.
There are 6 inverse pyramidal plots, 2 of which are shown in the last figure.
The total number of plots is 7 + 6 = 13.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 10⁵
grid[i][j] is either 0 or 1.

Solution: DP

Let dp[i][j] be the height+1 of a Pyramid tops at i, j
dp[i][j] = min(dp[i+d][j – 1], dp[i + d][j + 1]) + 1 if dp[i-1][j] else grid[i][j]

Time complexity: O(mn)
Space complexity: O(mn)

Python

# Author: Huahua

class Solution:

def countPyramids(self, grid: List[List[int]]) -> int:

m = len(grid)

n = len(grid[0])

ans = 0

@cache

def dp(i: int, j: int, d: int) -> int:

if grid[i][j] and 0 <= i + d < m and 0 < j < n - 1 and grid[i + d][j]:

return min(dp(i + d, j - 1, d), dp(i + d, j + 1, d)) + 1

return grid[i][j]

for i, j in product(range(m), range(n)):

ans += max(0, dp(i, j, 1) - 1)

ans += max(0, dp(i, j, -1) - 1)

return ans

花花酱 LeetCode 2087. Minimum Cost Homecoming of a Robot in a Grid

By zxi on November 27, 2021

There is an m x n grid, where (0, 0) is the top-left cell and (m - 1, n - 1) is the bottom-right cell. You are given an integer array startPos where startPos = [start_row, start_col] indicates that initially, a robot is at the cell (start_row, start_col). You are also given an integer array homePos where homePos = [home_row, home_col] indicates that its home is at the cell (home_row, home_col).

The robot needs to go to its home. It can move one cell in four directions: left, right, up, or down, and it can not move outside the boundary. Every move incurs some cost. You are further given two 0-indexed integer arrays: rowCosts of length m and colCosts of length n.

If the robot moves up or down into a cell whose row is r, then this move costs rowCosts[r].
If the robot moves left or right into a cell whose column is c, then this move costs colCosts[c].

Return the minimum total cost for this robot to return home.

Example 1:

Input: startPos = [1, 0], homePos = [2, 3], rowCosts = [5, 4, 3], colCosts = [8, 2, 6, 7]
Output: 18
Explanation: One optimal path is that:
Starting from (1, 0)
-> It goes down to (2, 0). This move costs rowCosts[2] = 3.
-> It goes right to (2, 1). This move costs colCosts[1] = 2.
-> It goes right to (2, 2). This move costs colCosts[2] = 6.
-> It goes right to (2, 3). This move costs colCosts[3] = 7.
The total cost is 3 + 2 + 6 + 7 = 18

Example 2:

Input: startPos = [0, 0], homePos = [0, 0], rowCosts = [5], colCosts = [26]
Output: 0
Explanation: The robot is already at its home. Since no moves occur, the total cost is 0.

Constraints:

m == rowCosts.length
n == colCosts.length
1 <= m, n <= 10⁵
0 <= rowCosts[r], colCosts[c] <= 10⁴
startPos.length == 2
homePos.length == 2
0 <= start_row, home_row < m
0 <= start_col, home_col < n

Solution: Manhattan distance

Move directly to the goal, no back and forth. Cost will be the same no matter which path you choose.

ans = sum(rowCosts[y1+1~y2]) + sum(colCosts[x1+1~x2])

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

C++

// Author: Huahua

class Solution {

public:

int minCost(vector<int>& startPos, vector<int>& homePos, vector<int>& rowCosts, vector<int>& colCosts) {

int dx = homePos[1] > startPos[1] ? 1 : (homePos[1] < startPos[1] ? -1 : 0);

int dy = homePos[0] > startPos[0] ? 1 : (homePos[0] < startPos[0] ? -1 : 0);

int ans = 0;

while (homePos[1] != startPos[1]) ans += colCosts[startPos[1] += dx];

while (homePos[0] != startPos[0]) ans += rowCosts[startPos[0] += dy];

return ans;

}

};

花花酱 LeetCode 2086. Minimum Number of Buckets Required to Collect Rainwater from Houses

By zxi on November 27, 2021

You are given a 0-indexed string street. Each character in street is either 'H' representing a house or '.' representing an empty space.

You can place buckets on the empty spaces to collect rainwater that falls from the adjacent houses. The rainwater from a house at index i is collected if a bucket is placed at index i - 1 and/or index i + 1. A single bucket, if placed adjacent to two houses, can collect the rainwater from both houses.

Return the minimum number of buckets needed so that for every house, there is at least one bucket collecting rainwater from it, or -1 if it is impossible.

Example 1:

Input: street = "H..H"
Output: 2
Explanation:
We can put buckets at index 1 and index 2.
"H..H" -> "HBBH" ('B' denotes where a bucket is placed).
The house at index 0 has a bucket to its right, and the house at index 3 has a bucket to its left.
Thus, for every house, there is at least one bucket collecting rainwater from it.

Example 2:

Input: street = ".H.H."
Output: 1
Explanation:
We can put a bucket at index 2.
".H.H." -> ".HBH." ('B' denotes where a bucket is placed).
The house at index 1 has a bucket to its right, and the house at index 3 has a bucket to its left.
Thus, for every house, there is at least one bucket collecting rainwater from it.

Example 3:

Input: street = ".HHH."
Output: -1
Explanation:
There is no empty space to place a bucket to collect the rainwater from the house at index 2.
Thus, it is impossible to collect the rainwater from all the houses.

Example 4:

Input: street = "H"
Output: -1
Explanation:
There is no empty space to place a bucket.
Thus, it is impossible to collect the rainwater from the house.

Example 5:

Input: street = "."

Output: 0

Explanation:

There is no house to collect water from.

Thus, 0 buckets are needed.

Constraints:

1 <= street.length <= 10⁵
street[i] is either'H' or '.'.

Solution: Greedy

Try to put a bucket after a house if possible, otherwise put it before the house, or impossible.

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

C++

// Author: Huahua

class Solution {

public:

int minimumBuckets(string street) {

const int n = street.size();

int ans = 0;

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

if (street[i] == 'H')

if (i - 1 >= 0 and street[i - 1] == 'B')

continue;

else if (i + 1 < n and street[i + 1] == '.')

street[i + 1] = 'B', ++ans;

else if (i - 1 >= 0 and street[i - 1] == '.')

street[i - 1] = 'B', ++ans;

else

return -1;

return ans;

}

};

花花酱 LeetCode 2085. Count Common Words With One Occurrence

By zxi on November 27, 2021

Given two string arrays words1 and words2, return the number of strings that appear exactly once in each of the two arrays.

Example 1:

Input: words1 = ["leetcode","is","amazing","as","is"], words2 = ["amazing","leetcode","is"]
Output: 2
Explanation:
- "leetcode" appears exactly once in each of the two arrays. We count this string.
- "amazing" appears exactly once in each of the two arrays. We count this string.
- "is" appears in each of the two arrays, but there are 2 occurrences of it in words1. We do not count this string.
- "as" appears once in words1, but does not appear in words2. We do not count this string.
Thus, there are 2 strings that appear exactly once in each of the two arrays.

Example 2:

Input: words1 = ["b","bb","bbb"], words2 = ["a","aa","aaa"]
Output: 0
Explanation: There are no strings that appear in each of the two arrays.

Example 3:

Input: words1 = ["a","ab"], words2 = ["a","a","a","ab"]
Output: 1
Explanation: The only string that appears exactly once in each of the two arrays is "ab".

Constraints:

1 <= words1.length, words2.length <= 1000
1 <= words1[i].length, words2[j].length <= 30
words1[i] and words2[j] consists only of lowercase English letters.

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int countWords(vector<string>& words1, vector<string>& words2) {

unordered_map<string, int> c1;

unordered_map<string, int> c2;

for (const string& w : words1) ++c1[w];

for (const string& w : words2) ++c2[w];

int ans = 0;

for (const auto& [w, c] : c1)

if (c == 1 && c2[w] == 1) ++ans;

return ans;

}

};

花花酱 LeetCode 69. Sqrt(x)

By zxi on November 26, 2021

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Example 1:

Input: x = 4
Output: 2

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Constraints:

0 <= x <= 2³¹ - 1

Solution 1: Binary Search

Find the smallest l such that l * l > x, sqrt(x) = l – 1.

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

C++

// Author: Huahua

class Solution {

public:

int mySqrt(int x) {

unsigned l = 1;

unsigned r = 1u + x;

while (l < r) {

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

if (m > x / m) {

r = m;

} else {

l = m + 1;

}

return l - 1;

}

};

Huahua's Tech Road

花花酱 LeetCode 2088. Count Fertile Pyramids in a Land

Solution: DP

Python

花花酱 LeetCode 2087. Minimum Cost Homecoming of a Robot in a Grid

Solution: Manhattan distance

C++

花花酱 LeetCode 2086. Minimum Number of Buckets Required to Collect Rainwater from Houses

Solution: Greedy

C++

花花酱 LeetCode 2085. Count Common Words With One Occurrence

Solution: Hashtable

C++

花花酱 LeetCode 69. Sqrt(x)

Solution 1: Binary Search

C++