Huahua's Tech Road

花花酱 LeetCode 1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers

By zxi on September 5, 2020

Given two arrays of integers nums1 and nums2, return the number of triplets formed (type 1 and type 2) under the following rules:

Type 1: Triplet (i, j, k) if nums1[i]² == nums2[j] * nums2[k] where 0 <= i < nums1.length and 0 <= j < k < nums2.length.
Type 2: Triplet (i, j, k) if nums2[i]² == nums1[j] * nums1[k] where 0 <= i < nums2.length and 0 <= j < k < nums1.length.

Example 1:

Input: nums1 = [7,4], nums2 = [5,2,8,9]
Output: 1
Explanation: Type 1: (1,1,2), nums1[1]^2 = nums2[1] * nums2[2]. (4^2 = 2 * 8).

Example 2:

Input: nums1 = [1,1], nums2 = [1,1,1]
Output: 9
Explanation: All Triplets are valid, because 1^2 = 1 * 1.
Type 1: (0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2).  nums1[i]^2 = nums2[j] * nums2[k].
Type 2: (0,0,1), (1,0,1), (2,0,1). nums2[i]^2 = nums1[j] * nums1[k].

Example 3:

Input: nums1 = [7,7,8,3], nums2 = [1,2,9,7]
Output: 2
Explanation: There are 2 valid triplets.
Type 1: (3,0,2).  nums1[3]^2 = nums2[0] * nums2[2].
Type 2: (3,0,1).  nums2[3]^2 = nums1[0] * nums1[1].

Example 4:

Input: nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18]
Output: 0
Explanation: There are no valid triplets.

Constraints:

1 <= nums1.length, nums2.length <= 1000
1 <= nums1[i], nums2[i] <= 10^5

Solution: Hashtable

For each number y in the second array, count its frequency.

For each number x in the first, if x * x % y == 0, let r = x * x / y
if r == y: ans += f[y] * f[y-1]
else ans += f[y] * f[r]

Final ans /= 2

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

C++

// Author: Huahua

class Solution {

public:

int numTriplets(vector<int>& nums1, vector<int>& nums2) {

return solve(nums1, nums2) + solve(nums2, nums1);

}

private:

int solve(vector<int>& nums1, vector<int>& nums2) {

int ans = 0;

unordered_map<int, int> f;

for (int y : nums2) ++f[y];

for (long x : nums1)

for (const auto& [y, c] : f) {

long r = x * x / y;

if (x * x % y || !f.count(r)) continue;

if (r == y) ans += c * (c - 1);

else ans += c * f[r];

}

return ans / 2;

}

};

花花酱 LeetCode 1576. Replace All ?’s to Avoid Consecutive Repeating Characters

By zxi on September 5, 2020

Given a string s containing only lower case English letters and the ‘?’ character, convert all the ‘?’ characters into lower case letters such that the final string does not contain any consecutive repeating characters. You cannot modify the non ‘?’ characters.

It is guaranteed that there are no consecutive repeating characters in the given string except for ‘?’.

Return the final string after all the conversions (possibly zero) have been made. If there is more than one solution, return any of them. It can be shown that an answer is always possible with the given constraints.

Example 1:

Input: s = "?zs"
Output: "azs"
Explanation: There are 25 solutions for this problem. From "azs" to "yzs", all are valid. Only "z" is an invalid modification as the string will consist of consecutive repeating characters in "zzs".

Example 2:

Input: s = "ubv?w"
Output: "ubvaw"
Explanation: There are 24 solutions for this problem. Only "v" and "w" are invalid modifications as the strings will consist of consecutive repeating characters in "ubvvw" and "ubvww".

Example 3:

Input: s = "j?qg??b"
Output: "jaqgacb"

Example 4:

Input: s = "??yw?ipkj?"
Output: "acywaipkja"

Constraints:

1 <= s.length <= 100
s contains only lower case English letters and ‘?’.

Solution: Greedy

For each ?, find the first one among ‘abc’ that is not same as left or right.

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

C++

class Solution {

public:

string modifyString(string s) {

const int n = s.length();

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

if (s[i] != '?') continue;

for (char c : "abc")

if ((i == 0 || s[i - 1] != c) && (i == n - 1 || s[i + 1] != c)) {

s[i] = c;

break;

}

return s;

}

};

花花酱 LeetCode 1575. Count All Possible Routes

By zxi on September 5, 2020

You are given an array of distinct positive integers locations where locations[i] represents the position of city i. You are also given integers start, finish and fuel representing the starting city, ending city, and the initial amount of fuel you have, respectively.

At each step, if you are at city i, you can pick any city j such that j != i and 0 <= j < locations.length and move to city j. Moving from city i to city j reduces the amount of fuel you have by |locations[i] - locations[j]|. Please notice that |x| denotes the absolute value of x.

Notice that fuel cannot become negative at any point in time, and that you are allowed to visit any city more than once (including start and finish).

Return the count of all possible routes from start to finish.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
Output: 4
Explanation: The following are all possible routes, each uses 5 units of fuel:
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3

Example 2:

Input: locations = [4,3,1], start = 1, finish = 0, fuel = 6
Output: 5
Explanation: The following are all possible routes:
1 -> 0, used fuel = 1
1 -> 2 -> 0, used fuel = 5
1 -> 2 -> 1 -> 0, used fuel = 5
1 -> 0 -> 1 -> 0, used fuel = 3
1 -> 0 -> 1 -> 0 -> 1 -> 0, used fuel = 5

Example 3:

Input: locations = [5,2,1], start = 0, finish = 2, fuel = 3
Output: 0
Explanation: It's impossible to get from 0 to 2 using only 3 units of fuel since the shortest route needs 4 units of fuel.

Example 4:

Input: locations = [2,1,5], start = 0, finish = 0, fuel = 3
Output: 2
Explanation: There are two possible routes, 0 and 0 -> 1 -> 0.

Example 5:

Input: locations = [1,2,3], start = 0, finish = 2, fuel = 40
Output: 615088286
Explanation: The total number of possible routes is 2615088300. Taking this number modulo 10^9 + 7 gives us 615088286.

Constraints:

2 <= locations.length <= 100
1 <= locations[i] <= 10^9
All integers in locations are distinct.
0 <= start, finish < locations.length
1 <= fuel <= 200

Solution: DP

dp[j][f] := # of ways to start from city ‘start’ to reach city ‘j’ with fuel level f.

dp[j][f] = sum(dp[i][f + d]) d = dist(i, j)

init: dp[start][fuel] = 1

Time complexity: O(n^2*fuel)
Space complexity: O(n*fuel)

C++

class Solution {

public:

int countRoutes(vector<int>& x, int start, int finish, int fuel) {

constexpr int kMod = 1e9 + 7;

const int n = x.size();

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

dp[start][fuel] = 1;

for (int f = fuel; f > 0; --f)

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

if (!dp[i][f] || abs(x[i] - x[finish]) > f) continue; // pruning.

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

const int d = abs(x[i] - x[j]);

if (i == j || f < d) continue;

dp[j][f - d] = (dp[j][f - d] + dp[i][f]) % kMod;

}

return accumulate(begin(dp[finish]), end(dp[finish]), 0LL) % kMod;

}

};

Python3

# Author: Huahua

class Solution:

def countRoutes(self, x: List[int], start: int, finish: int, fuel: int) -> int:

@lru_cache(None)

if f < 0: return 0

return (sum(dp(j, f - abs(x[i] - x[j]))

for j in range(len(x)) if i != j) + (i == finish)) % (10**9 + 7)

return dp(start, fuel)

花花酱 LeetCode 1574. Shortest Subarray to be Removed to Make Array Sorted

By zxi on September 5, 2020

Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.

A subarray is a contiguous subsequence of the array.

Return the length of the shortest subarray to remove.

Example 1:

Input: arr = [1,2,3,10,4,2,3,5]
Output: 3
Explanation: The shortest subarray we can remove is [10,4,2] of length 3. The remaining elements after that will be [1,2,3,3,5] which are sorted.
Another correct solution is to remove the subarray [3,10,4].

Example 2:

Input: arr = [5,4,3,2,1]
Output: 4
Explanation: Since the array is strictly decreasing, we can only keep a single element. Therefore we need to remove a subarray of length 4, either [5,4,3,2] or [4,3,2,1].

Example 3:

Input: arr = [1,2,3]
Output: 0
Explanation: The array is already non-decreasing. We do not need to remove any elements.

Example 4:

Input: arr = [1]
Output: 0

Constraints:

1 <= arr.length <= 10^5
0 <= arr[i] <= 10^9

Solution: Two Pointers

Find the right most j such that arr[j – 1] > arr[j], if not found which means the entire array is sorted return 0. Then we have a non-descending subarray arr[j~n-1].

We maintain two pointers i, j, such that arr[0~i] is non-descending and arr[i] <= arr[j] which means we can remove arr[i+1~j-1] to get a non-descending array. Number of elements to remove is j – i – 1 .

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

C++

// Author: Huahua

class Solution {

public:

int findLengthOfShortestSubarray(vector<int>& arr) {

const int n = arr.size();

int j = n - 1;

while (j > 0 && arr[j - 1] <= arr[j]) --j;

if (j == 0) return 0;

int ans = j; // remove arr[0~j-1]

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

if (i > 0 && arr[i - 1] > arr[i]) break;

while (j < n && arr[i] > arr[j]) ++j;

// arr[i] <= arr[j], remove arr[i + 1 ~ j - 1]

ans = min(ans, j - i - 1);

}

return ans;

}

};

花花酱 LeetCode 1573. Number of Ways to Split a String

By zxi on September 5, 2020

Given a binary string s (a string consisting only of ‘0’s and ‘1’s), we can split s into 3 non-empty strings s1, s2, s3 (s1+ s2+ s3 = s).

Return the number of ways s can be split such that the number of characters ‘1’ is the same in s1, s2, and s3.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: s = "10101"
Output: 4
Explanation: There are four ways to split s in 3 parts where each part contain the same number of letters '1'.
"1|010|1"
"1|01|01"
"10|10|1"
"10|1|01"

Example 2:

Input: s = "1001"
Output: 0

Example 3:

Input: s = "0000"
Output: 3
Explanation: There are three ways to split s in 3 parts.
"0|0|00"
"0|00|0"
"00|0|0"

Example 4:

Input: s = "100100010100110"
Output: 12

Constraints:

s[i] == '0' or s[i] == '1'
3 <= s.length <= 10^5

Solution: Counting

Count how many ones in the binary string as T, if not a factor of 3, then there is no answer.

Count how many positions that have prefix sum of T/3 as l, and how many positions that have prefix sum of T/3*2 as r.

Ans = l * r

But we need to special handle the all zero cases, which equals to C(n-2, 2) = (n – 1) * (n – 2) / 2

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

C++

class Solution {

public:

int numWays(string s) {

const int kMod = 1e9 + 7;

const long n = s.length();

int t = 0;

for (char c : s) t += c == '1';

if (t % 3) return 0;

if (t == 0)

return ((1 + (n - 2)) * (n - 2) / 2) % kMod;

t /= 3;

long l = 0;

long r = 0;

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

c += (s[i] == '1');

if (c == t) ++l;

else if (c == t * 2) ++r;

}

return (l * r) % kMod;

}

};

Python3

class Solution:

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

n = len(s)

t = s.count('1')

if t % 3 != 0: return 0

if t == 0: return ((n - 1) * (n - 2) // 2) % (10**9 + 7)

t //= 3

l, r, c = 0, 0, 0

for i, ch in enumerate(s):

if ch == '1': c += 1

if c == t: l += 1

elif c == t * 2: r += 1

return (l * r) % (10**9 + 7)

One pass: Space complexity: O(n)

Python3

class Solution:

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

n = len(s)

p = defaultdict(int)

c = 0

for ch in s:

if ch == '1': c += 1

p[c] += 1

if c % 3 != 0: return 0

if c == 0: return ((n - 1) * (n - 2) // 2) % (10**9 + 7)

return (p[c // 3] * p[c // 3 * 2]) % (10**9 + 7)