Huahua’s Tech Road

花花酱 LeetCode 1464. Maximum Product of Two Elements in an Array

By zxi on May 31, 2020

Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of(nums[i]-1)*(nums[j]-1).

Example 1:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12.

Example 2:

Input: nums = [1,5,4,5]
Output: 16
Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.

Example 3:

Input: nums = [3,7]
Output: 12

Constraints:

2 <= nums.length <= 500
1 <= nums[i] <= 10^3

Solution 1: Sort

We want to find the largest and second largest elements.

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

C++

// Author: Huahua

class Solution {

public:

int maxProduct(vector<int>& nums) {

sort(rbegin(nums), rend(nums));

return (nums[0] - 1) * (nums[1] - 1);

}

};

Solution 2: Without sorting

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

C++

// Author: Huahua

class Solution {

public:

int maxProduct(vector<int>& nums) {

int m1 = 0;

int m2 = 0;

for (int n : nums) {

if (n > m1) {

m2 = m1;

m1 = n;

} else if (n > m2) {

m2 = n;

}

return (m1 - 1) * (m2 - 1);

}

};

花花酱 LeetCode 1463. Cherry Pickup II

By zxi on May 30, 2020

Given a rows x cols matrix grid representing a field of cherries. Each cell in grid represents the number of cherries that you can collect.

You have two robots that can collect cherries for you, Robot #1 is located at the top-left corner (0,0) , and Robot #2 is located at the top-right corner (0, cols-1) of the grid.

Return the maximum number of cherries collection using both robots by following the rules below:

From a cell (i,j), robots can move to cell (i+1, j-1) , (i+1, j) or (i+1, j+1).
When any robot is passing through a cell, It picks it up all cherries, and the cell becomes an empty cell (0).
When both robots stay on the same cell, only one of them takes the cherries.
Both robots cannot move outside of the grid at any moment.
Both robots should reach the bottom row in the grid.

Example 1:

Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.

Example 2:

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

Example 3:

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

Example 4:

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

Constraints:

rows == grid.length
cols == grid[i].length
2 <= rows, cols <= 70
0 <= grid[i][j] <= 100

Solution: DP

dp[y][x1][x2] := max cherry when ro1 at (x1, y) and ro2 at (x2, y)
dp[y][x1][x2] = max(dp[y+1][x1 + dx1][x2 + dx2]) -1 <= dx1, dx2 <= 1

Time complexity: O(c^2*r)
Space complexity: O(c^2*r)

C++

// Author: Huahua

class Solution {

public:

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

const int r = grid.size();

const int c = grid[0].size();

vector<vector<vector<int>>> cache(r, vector<vector<int>>(c, vector<int>(c, -1)));

function<int(int, int, int)> dp = [&](int y, int x1, int x2) {

if (x1 < 0 || x1 >= c || x2 < 0 || x2 >= c || y < 0 || y >= r) return 0;

int& ans = cache[y][x1][x2];

if (ans != -1) return ans;

const int cur = grid[y][x1] + (x1 != x2) * grid[y][x2];

for (int d1 = -1; d1 <= 1; ++d1)

for (int d2 = -1; d2 <= 1; ++d2)

ans = max(ans, cur + dp(y + 1, x1 + d1, x2 + d2));

return ans;

};

return dp(0, 0, c - 1);

}

};

Bottom-up

C++

// Author: Huahua

class Solution {

public:

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

const int r = grid.size();

const int c = grid[0].size();

vector<vector<vector<int>>> dp(r + 2,

vector<vector<int>>(c + 2, vector<int>(c + 2)));

for (int y = r; y >= 1; --y)

for (int x1 = 1; x1 <= c; ++x1)

for (int x2 = 1; x2 <= c; ++x2) {

const int cur = grid[y - 1][x1 - 1] + (x1 != x2) * grid[y - 1][x2 - 1];

int& ans = dp[y][x1][x2];

for (int d1 = -1; d1 <= 1; ++d1)

for (int d2 = -1; d2 <= 1; ++d2)

ans = max(ans, cur + dp[y + 1][x1 + d1][x2 + d2]);

}

return dp[1][1][c];

}

};

O(c^2) Space

C++

// Author: Huahua

class Solution {

public:

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

const int r = grid.size();

const int c = grid[0].size();

vector<vector<int>> dp(c + 2, vector<int>(c + 2));

for (int y = r; y >= 1; --y) {

vector<vector<int>> tmp(c + 2, vector<int>(c + 2));

for (int x1 = 1; x1 <= c; ++x1)

for (int x2 = 1; x2 <= c; ++x2) {

const int cur = grid[y - 1][x1 - 1] + (x1 != x2) * grid[y - 1][x2 - 1];

for (int d1 = -1; d1 <= 1; ++d1)

for (int d2 = -1; d2 <= 1; ++d2)

tmp[x1][x2] = max(tmp[x1][x2], cur + dp[x1 + d1][x2 + d2]);

}

dp.swap(tmp);

}

return dp[1][c];

}

};

花花酱 LeetCode 1462. Course Schedule IV

By zxi on May 30, 2020

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have direct prerequisites, for example, to take course 0 you have first to take course 1, which is expressed as a pair: [1,0]

Given the total number of courses n, a list of direct prerequisite pairs and a list of queries pairs.

You should answer for each queries[i] whether the course queries[i][0] is a prerequisite of the course queries[i][1] or not.

Return a list of boolean, the answers to the given queries.

Please note that if course a is a prerequisite of course b and course b is a prerequisite of course c, then, course a is a prerequisite of course c.

Example 1:

Input: n = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation: course 0 is not a prerequisite of course 1 but the opposite is true.

Example 2:

Input: n = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output: [false,false]
Explanation: There are no prerequisites and each course is independent.

Example 3:

Input: n = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
Output: [true,true]

Example 4:

Input: n = 3, prerequisites = [[1,0],[2,0]], queries = [[0,1],[2,0]]
Output: [false,true]

Example 5:

Input: n = 5, prerequisites = [[0,1],[1,2],[2,3],[3,4]], queries = [[0,4],[4,0],[1,3],[3,0]]
Output: [true,false,true,false]

Constraints:

2 <= n <= 100
0 <= prerequisite.length <= (n * (n - 1) / 2)
0 <= prerequisite[i][0], prerequisite[i][1] < n
prerequisite[i][0] != prerequisite[i][1]
The prerequisites graph has no cycles.
The prerequisites graph has no repeated edges.
1 <= queries.length <= 10^4
queries[i][0] != queries[i][1]

Solution: Floyd-Warshall Algorithm (All pairs shortest paths)

Time complexity: O(n^3 + q)
Space complexity: O(n^2)

C++

// Author: Huahua

class Solution {

public:

vector<bool> checkIfPrerequisite(int n,

vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {

vector<vector<int>> g(n, vector<int>(n));

for (const auto& p : prerequisites)

g[p[0]][p[1]] = 1;

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

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

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

g[i][j] |= g[i][k] & g[k][j];

vector<bool> ans;

for (const auto& q : queries)

ans.push_back(g[q[0]][q[1]]);

return ans;

}

};

花花酱 LeetCode 1461. Check If a String Contains All Binary Codes of Size K

By zxi on May 30, 2020

Given a binary string s and an integer k.

Return True if any binary code of length k is a substring of s. Otherwise, return False.

Example 1:

Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indicies 0, 1, 3 and 2 respectively.

Example 2:

Input: s = "00110", k = 2
Output: true

Example 3:

Input: s = "0110", k = 1
Output: true
Explanation: The binary codes of length 1 are "0" and "1", it is clear that both exist as a substring.

Example 4:

Input: s = "0110", k = 2
Output: false
Explanation: The binary code "00" is of length 2 and doesn't exist in the array.

Example 5:

Input: s = "0000000001011100", k = 4
Output: false

Constraints:

1 <= s.length <= 5 * 10^5
s consists of 0’s and 1’s only.
1 <= k <= 20

Solution: Hashtable

Insert all possible substrings into a hashtable, the size of the hashtable should be 2^k.

Time complexity: O(n*k)
Space complexity: O(2^k*k) -> O(2^k)

std::string_view: 484 ms, 40.1MB
std::string 644 ms, 58.6MB

C++

// Author: Huahua

// std::string_view: 468 ms, 37.3MB

// std::string: 636 ms, 58.6MB

class Solution {

public:

bool hasAllCodes(string_view s, int k) {

const int n = s.length();

if ((n - k + 1) * k < (1 << k)) return false;

unordered_set<string_view> c;

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

c.insert(s.substr(i, k));

return c.size() == (1 << k);

}

};

花花酱 LeetCode 1460. Make Two Arrays Equal by Reversing Sub-arrays

By zxi on May 30, 2020

Given two integer arrays of equal length target and arr.

In one step, you can select any non-empty sub-array of arr and reverse it. You are allowed to make any number of steps.

Return True if you can make arr equal to target, or False otherwise.

Example 1:

Input: target = [1,2,3,4], arr = [2,4,1,3]
Output: true
Explanation: You can follow the next steps to convert arr to target:
1- Reverse sub-array [2,4,1], arr becomes [1,4,2,3]
2- Reverse sub-array [4,2], arr becomes [1,2,4,3]
3- Reverse sub-array [4,3], arr becomes [1,2,3,4]
There are multiple ways to convert arr to target, this is not the only way to do so.

Example 2:

Input: target = [7], arr = [7]
Output: true
Explanation: arr is equal to target without any reverses.

Example 3:

Input: target = [1,12], arr = [12,1]
Output: true

Example 4:

Input: target = [3,7,9], arr = [3,7,11]
Output: false
Explanation: arr doesn't have value 9 and it can never be converted to target.

Example 5:

Input: target = [1,1,1,1,1], arr = [1,1,1,1,1]
Output: true

Constraints:

target.length == arr.length
1 <= target.length <= 1000
1 <= target[i] <= 1000
1 <= arr[i] <= 1000

Solution: Counting

target and arr must have same elements.

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

C++

// Author: Huahua

class Solution {

public:

bool canBeEqual(vector<int>& target, vector<int>& arr) {

vector<int> t(1001);

vector<int> a(1001);

for (int i = 0; i < target.size(); ++i) {

++t[target[i]];

++a[arr[i]];

}

return t == a;

}

};

Python3

# Author: Huahua

class Solution:

def canBeEqual(self, target: List[int], arr: List[int]) -> bool:

return Counter(target) == Counter(arr)

Huahua's Tech Road

花花酱 LeetCode 1464. Maximum Product of Two Elements in an Array

Solution 1: Sort

C++

Solution 2: Without sorting

C++

花花酱 LeetCode 1463. Cherry Pickup II

Solution: DP

C++

C++

C++

花花酱 LeetCode 1462. Course Schedule IV

Solution: Floyd-Warshall Algorithm (All pairs shortest paths)

C++

花花酱 LeetCode 1461. Check If a String Contains All Binary Codes of Size K

Solution: Hashtable

C++

花花酱 LeetCode 1460. Make Two Arrays Equal by Reversing Sub-arrays

Solution: Counting

C++

Python3