Huahua’s Tech Road

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

花花酱 LeetCode 1572. Matrix Diagonal Sum

By zxi on September 5, 2020

Given a square matrix mat, return the sum of the matrix diagonals.

Only include the sum of all the elements on the primary diagonal and all the elements on the secondary diagonal that are not part of the primary diagonal.

Example 1:

Input: mat = [[1,2,3],
              [4,5,6],
              [7,8,9]]
Output: 25
Explanation: Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25
Notice that element mat[1][1] = 5 is counted only once.

Example 2:

Input: mat = [[1,1,1,1],
              [1,1,1,1],
              [1,1,1,1],
              [1,1,1,1]]
Output: 8

Example 3:

Input: mat = [[5]]
Output: 5

Constraints:

n == mat.length == mat[i].length
1 <= n <= 100
1 <= mat[i][j] <= 100

Solution: Brute Force

Note: if n is odd, be careful not to double count the center one.

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

C++

class Solution {

public:

int diagonalSum(vector<vector<int>>& mat) {

const int n = mat.size();

int ans = 0;

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

ans += mat[i][i] + mat[i][n - i - 1];

if (n & 1) ans -= mat[n / 2][n / 2];

return ans;

}

};

花花酱 LeetCode 1569. Number of Ways to Reorder Array to Get Same BST

By zxi on August 30, 2020

Given an array nums that represents a permutation of integers from 1 to n. We are going to construct a binary search tree (BST) by inserting the elements of nums in order into an initially empty BST. Find the number of different ways to reorder nums so that the constructed BST is identical to that formed from the original array nums.

For example, given nums = [2,1,3], we will have 2 as the root, 1 as a left child, and 3 as a right child. The array [2,3,1] also yields the same BST but [3,2,1] yields a different BST.

Return the number of ways to reorder nums such that the BST formed is identical to the original BST formed from nums.

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

Example 1:

Input: nums = [2,1,3]
Output: 1
Explanation: We can reorder nums to be [2,3,1] which will yield the same BST. There are no other ways to reorder nums which will yield the same BST.

Example 2:

Input: nums = [3,4,5,1,2]
Output: 5
Explanation: The following 5 arrays will yield the same BST: 
[3,1,2,4,5]
[3,1,4,2,5]
[3,1,4,5,2]
[3,4,1,2,5]
[3,4,1,5,2]

Example 3:

Input: nums = [1,2,3]
Output: 0
Explanation: There are no other orderings of nums that will yield the same BST.

Example 4:

Input: nums = [3,1,2,5,4,6]
Output: 19

Example 5:

Input: nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]
Output: 216212978
Explanation: The number of ways to reorder nums to get the same BST is 3216212999. Taking this number modulo 10^9 + 7 gives 216212978.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= nums.length
All integers in nums are distinct.

Solution: Recursion + Combinatorics

For a given root (first element of the array), we can split the array into left children (nums[i] < nums[0]) and right children (nums[i] > nums[0]). Assuming there are l nodes for the left and r nodes for the right. We have C(l + r, l) different ways to insert l elements into a (l + r) sized array. Within node l / r nodes, we have ways(left) / ways(right) different ways to re-arrange those nodes. So the total # of ways is:
C(l + r, l) * ways(l) * ways(r)
Don’t forget to minus one for the final answer.

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

C++

class Solution {

public:

int numOfWays(vector<int>& nums) {

const int n = nums.size();

const int kMod = 1e9 + 7;

vector<vector<int>> cnk(n + 1, vector<int>(n + 1, 1));

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

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

cnk[i][j] = (cnk[i - 1][j] + cnk[i - 1][j - 1]) % kMod;

function<int(vector<int>)> trees = [&](const vector<int>& nums) {

const int n = nums.size();

if (n <= 2) return 1;

vector<int> left;

vector<int> right;

for (int i = 1; i < nums.size(); ++i)

if (nums[i] < nums[0]) left.push_back(nums[i]);

else right.push_back(nums[i]);

long ans = cnk[n - 1][left.size()];

ans = (ans * trees(left)) % kMod;

ans = (ans * trees(right)) % kMod;

return static_cast<int>(ans);

};

return trees(nums) - 1;

}

};

python3

class Solution:

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

def ways(nums):

if len(nums) <= 2: return 1

l = [x for x in nums if x < nums[0]]

r = [x for x in nums if x > nums[0]]

return comb(len(l) + len(r), len(l)) * ways(l) * ways(r)

return (ways(nums) - 1) % (10**9 + 7)

Huahua's Tech Road

花花酱 LeetCode 1575. Count All Possible Routes

Solution: DP

C++

Python3

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

Solution: Two Pointers

C++

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

Solution: Counting

C++

Python3

Python3

花花酱 LeetCode 1572. Matrix Diagonal Sum

Solution: Brute Force

C++

花花酱 LeetCode 1569. Number of Ways to Reorder Array to Get Same BST

Solution: Recursion + Combinatorics

C++

python3