Huahua's Tech Road

花花酱 LeetCode 1537. Get the Maximum Score

By zxi on August 2, 2020

You are given two sorted arrays of distinct integers nums1 and nums2.

A validpath is defined as follows:

Choose array nums1 or nums2 to traverse (from index-0).
Traverse the current array from left to right.
If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).

Score is defined as the sum of uniques values in a valid path.

Return the maximum score you can obtain of all possible valid paths.

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

Example 1:

Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],  (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]    (starting from nums2)
The maximum is obtained with the path in green [2,4,6,8,10].

Example 2:

Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]
Output: 109
Explanation: Maximum sum is obtained with the path [1,3,5,100].

Example 3:

Input: nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 40
Explanation: There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path [6,7,8,9,10].

Example 4:

Input: nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
Output: 61

Constraints:

1 <= nums1.length <= 10^5
1 <= nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 10^7
nums1 and nums2 are strictly increasing.

Solution: Two Pointers + DP

Since numbers are strictly increasing, we can always traverse the smaller one using two pointers.
Traversing ([2,4,5,8,10], [4,6,8,10])
will be like [2, 4/4, 5, 6, 8, 10/10]
It two nodes have the same value, we have two choices and pick the larger one, then both move nodes one step forward. Otherwise, the smaller node moves one step forward.
dp1[i] := max path sum ends with nums1[i-1]
dp2[j] := max path sum ends with nums2[j-1]
if nums[i -1] == nums[j – 1]:
dp1[i] = dp2[j] = max(dp[i-1], dp[j-1]) + nums[i -1]
i += 1, j += 1
else if nums[i – 1] < nums[j – 1]:
dp[i] = dp[i-1] + nums[i -1]
i += 1
else if nums[j – 1] < nums[i – 1]:
dp[j] = dp[j-1] + nums[j -1]
j += 1
return max(dp1[-1], dp2[-1])

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

C++

class Solution {

public:

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

constexpr int kMod = 1e9 + 7;

const int n1 = nums1.size();

const int n2 = nums2.size();

vector<long> dp1(n1 + 1); // max path sum ends with nums1[i-1]

vector<long> dp2(n2 + 1); // max path sum ends with nums2[j-1]

int i = 0;

int j = 0;

while (i < n1 || j < n2) {

if (i < n1 && j < n2 && nums1[i] == nums2[j]) {

// Same, two choices, pick the larger one.

dp2[j + 1] = dp1[i + 1] = max(dp1[i], dp2[j]) + nums1[i];

++i; ++j;

} else if (i < n1 && (j == n2 || nums1[i] < nums2[j])) {

dp1[i + 1] = dp1[i] + nums1[i];

++i;

} else if (j < n2 && (i == n1 || nums2[j] < nums1[i])) {

dp2[j + 1] = dp2[j] + nums2[j];

++j;

}

return max(dp1.back(), dp2.back()) % kMod;

}

};

Java

class Solution {

public int maxSum(int[] nums1, int[] nums2) {

final int kMod = 1_000_000_007;

int n1 = nums1.length;

int n2 = nums2.length;

int i = 0;

int j = 0;

long a = 0;

long b = 0;

while (i < n1 || j < n2) {

if (i < n1 && j < n2 && nums1[i] == nums2[j]) {

a = b = Math.max(a, b) + nums1[i];

++i;

++j;

} else if (i < n1 && (j == n2 || nums1[i] < nums2[j])) {

a += nums1[i++];

} else {

b += nums2[j++];

}

return (int)(Math.max(a, b) % kMod);

}

python3

class Solution:

def maxSum(self, nums1: List[int], nums2: List[int]) -> int:

n1, n2 = len(nums1), len(nums2)

i, j = 0, 0

a, b = 0, 0

while i < n1 or j < n2:

if i < n1 and j < n2 and nums1[i] == nums2[j]:

a = b = max(a, b) + nums1[i]

i += 1

j += 1

elif i < n1 and (j == n2 or nums1[i] < nums2[j]):

a += nums1[i]

i += 1

else:

b += nums2[j]

j += 1

return max(a, b) % (10**9 + 7)

花花酱 LeetCode 1536. Minimum Swaps to Arrange a Binary Grid

By zxi on August 2, 2020

Given an n x n binary grid, in one step you can choose two adjacent rows of the grid and swap them.

A grid is said to be valid if all the cells above the main diagonal are zeros.

Return the minimum number of steps needed to make the grid valid, or -1 if the grid cannot be valid.

The main diagonal of a grid is the diagonal that starts at cell (1, 1) and ends at cell (n, n).

Example 1:

Input: grid = [[0,0,1],[1,1,0],[1,0,0]]
Output: 3

Example 2:

Input: grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
Output: -1
Explanation: All rows are similar, swaps have no effect on the grid.

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,1]]
Output: 0

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 200
grid[i][j] is 0 or 1

Solution: Bubble Sort

Counting how many tailing zeros each row has.
Then input
[0, 0, 1]
[1, 1, 0]
[1, 0, 0]
becomes [0, 1, 2]
For i-th row, it needs n – i – 1 tailing zeros.
We need to find the first row that has at least n – i – 1 tailing zeros and bubbling it up to the i-th row. This process is very similar to bubble sort.
[0, 1, 2] -> [0, 2, 1] -> [2, 0, 1]
[2, 0, 1] -> [2, 1, 0]
Total 3 swaps.

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

C++

class Solution {

public:

int minSwaps(vector<vector<int>>& grid) {

const int n = grid.size();

vector<int> zeros;

for (const auto& row : grid) {

int zero = 0;

for (int i = n - 1; i >= 0 && row[i] == 0; --i)

++zero;

zeros.push_back(zero);

}

int ans = 0;

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

int j = i;

int z = n - i - 1; // the i-th needs n - i - 1 zeros

// Find first row with at least z tailing zeros.

while (j < n && zeros[j] < z) ++j;

if (j == n) return -1;

while (j > i) {

zeros[j] = zeros[j - 1];

--j;

++ans;

}

return ans;

}

};

花花酱 LeetCode 1535. Find the Winner of an Array Game

By zxi on August 1, 2020

Given an integer array arr of distinct integers and an integer k.

A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of the game, we compare arr[0] with arr[1], the larger integer wins and remains at position 0 and the smaller integer moves to the end of the array. The game ends when an integer wins k consecutive rounds.

Return the integer which will win the game.

It is guaranteed that there will be a winner of the game.

Example 1:

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

Example 2:

Input: arr = [3,2,1], k = 10
Output: 3
Explanation: 3 will win the first 10 rounds consecutively.

Example 3:

Input: arr = [1,9,8,2,3,7,6,4,5], k = 7
Output: 9

Example 4:

Input: arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
Output: 99

Constraints:

2 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
arr contains distinct integers.
1 <= k <= 10^9

Solution 1: Simulation with a List

Observation : if k >= n – 1, ans = max(arr)

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

C++

class Solution {

public:

int getWinner(vector<int>& arr, int k) {

if (k >= arr.size()) return *max_element(begin(arr), end(arr));

int win = 0;

list<int> a(begin(arr), end(arr));

while (true) {

auto it0 = begin(a);

auto it1 = next(it0);

if (*it0 > *it1) {

a.splice(a.end(), a, it1);

++win;

} else {

swap(it0, it1);

a.splice(a.end(), a, it1);

win = 1;

}

if (win == k) return *it0;

}

return -1;

}

};

Solution 2: One pass

Since smaller numbers will be put to the end of the array, we must compare the rest of array before meeting those used numbers again. And the winner is monotonically increasing. So we can do it in one pass, just keep the largest number seen so far. If we reach to the end of the array, arr[0] will be max(arr) and it will always win no matter what k is.

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

C++

class Solution {

public:

int getWinner(vector<int>& arr, int k) {

int winner = arr[0];

int win = 0;

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

if (arr[i] > winner) {

winner = arr[i];

win = 0;

}

if (++win == k) break;

}

return winner;

}

};

Java

class Solution {

public int getWinner(int[] arr, int k) {

int winner = arr[0];

int win = 0;

for (int i = 1; i < arr.length && win < k; ++i, ++win)

if (arr[i] > winner) {

winner = arr[i];

win = 0;

}

return winner;

}

Python3

class Solution:

def getWinner(self, arr: List[int], k: int) -> int:

winner = arr[0]

win = 0

for x in arr[1:]:

if x > winner:

winner, win = x, 0

win += 1

if win == k: break

return winner

花花酱 LeetCode 1534. Count Good Triplets

By zxi on August 1, 2020

Given an array of integers arr, and three integers a, b and c. You need to find the number of good triplets.

A triplet (arr[i], arr[j], arr[k]) is good if the following conditions are true:

0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c

Where |x| denotes the absolute value of x.

Return the number of good triplets.

Example 1:

Input: arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
Output: 4
Explanation: There are 4 good triplets: [(3,0,1), (3,0,1), (3,1,1), (0,1,1)].

Example 2:

Input: arr = [1,1,2,2,3], a = 0, b = 0, c = 1
Output: 0
Explanation: No triplet satisfies all conditions.

Constraints:

3 <= arr.length <= 100
0 <= arr[i] <= 1000
0 <= a, b, c <= 1000

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int countGoodTriplets(vector<int>& arr, int a, int b, int c) {

const int n = arr.size();

int ans = 0;

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

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

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

if (abs(arr[i] - arr[j]) <= a &&

abs(arr[j] - arr[k]) <= b &&

abs(arr[i] - arr[k]) <= c)

++ans;

return ans;

}

};

花花酱 LeetCode 1513. Number of Substrings With Only 1s

By zxi on July 29, 2020

Given a binary string s (a string consisting only of ‘0’ and ‘1’s).

Return the number of substrings with all characters 1’s.

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

Example 1:

Input: s = "0110111"
Output: 9
Explanation: There are 9 substring in total with only 1's characters.
"1" -> 5 times.
"11" -> 3 times.
"111" -> 1 time.

Example 2:

Input: s = "101"
Output: 2
Explanation: Substring "1" is shown 2 times in s.

Example 3:

Input: s = "111111"
Output: 21
Explanation: Each substring contains only 1's characters.

Example 4:

Input: s = "000"
Output: 0

Constraints:

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

Solution: DP / Prefix Sum

dp[i] := # of all 1 subarrays end with s[i].
dp[i] = dp[i-1] if s[i] == ‘1‘ else 0
ans = sum(dp)
s=1101
dp[0] = 1 // 1
dp[1] = 2 // 11, *1
dp[2] = 0 // None
dp[3] = 1 // ***1
ans = 1 + 2 + 1 = 5

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

C++

class Solution {

public:

int numSub(string s) {

constexpr int kMod = 1e9 + 7;

long ans = 0;

vector<int> dp(s.length() + 1);

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

dp[i] = s[i - 1] == '1' ? dp[i - 1] + 1 : 0;

ans += dp[i];

}

return ans % kMod;

}

};

dp[i] only depends on dp[i-1], we can reduce the space complexity to O(1)

C++

class Solution {

public:

int numSub(string s) {

constexpr int kMod = 1e9 + 7;

long ans = 0;

int cur = 0;

for (char c : s) {

cur = c == '1' ? cur + 1 : 0;

ans += cur;

}

return ans % kMod;

}

};

Java

class Solution {

public int numSub(String s) {

final int kMod = 1_000_000_000 + 7;

int ans = 0;

int cur = 0;

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

cur = s.charAt(i) == '1' ? cur + 1 : 0;

ans = (ans + cur) % kMod;

}

return ans;

}

Python3

class Solution:

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

kMod = 10**9 + 7

ans = 0

cur = 0

for c in s:

cur = cur + 1 if c == '1' else 0

ans += cur

return ans % kMod