Huahua’s Tech Road

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

}

};

花花酱 LeetCode 65. Valid Number

By zxi on November 26, 2021

A valid number can be split up into these components (in order):

A decimal number or an integer.
(Optional) An 'e' or 'E', followed by an integer.

A decimal number can be split up into these components (in order):

(Optional) A sign character (either '+' or '-').
One of the following formats:
1. One or more digits, followed by a dot '.'.
2. One or more digits, followed by a dot '.', followed by one or more digits.
3. A dot '.', followed by one or more digits.

An integer can be split up into these components (in order):

(Optional) A sign character (either '+' or '-').
One or more digits.

For example, all the following are valid numbers: ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"], while the following are not valid numbers: ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"].

Given a string s, return true if s is a valid number.

Example 1:

Input: s = "0"
Output: true

Example 2:

Input: s = "e"
Output: false

Example 3:

Input: s = "."
Output: false

Example 4:

Input: s = ".1"
Output: true

Constraints:

1 <= s.length <= 20
s consists of only English letters (both uppercase and lowercase), digits (0-9), plus '+', minus '-', or dot '.'.

Solution: Rule checking

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

C++

// Author: Huahua

class Solution {

public:

bool isNumber(string s) {

for (int i = 0; i < s.length(); ++i)

if (s[i] != ' ') {

s = s.substr(i);

break;

}

while (!s.empty() && s.back() == ' ') s.pop_back();

bool dot = false;

bool e = false;

bool digit = false;

for (int i = 0; i < s.length(); ++i) {

s[i] = tolower(s[i]);

if (isdigit(s[i])) {

digit = true;

} else if (s[i] == '.') {

if (e || dot) return false;

dot = true;

} else if (s[i] == 'e') {

if (e || !digit) return false;

e = true;

digit = false;

} else if (s[i] == '-' || s[i] == '+') {

if (i != 0 && s[i - 1] != 'e')

return false;

} else {

return false;

}

return digit;

}

};

Huahua's Tech Road

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

花花酱 LeetCode 65. Valid Number

Solution: Rule checking

C++