Posts tagged as “hard”

花花酱 LeetCode 1250. Check If It Is a Good Array

By zxi on November 8, 2019

Given an array nums of positive integers. Your task is to select some subset of nums, multiply each element by an integer and add all these numbers. The array is said to be good if you can obtain a sum of 1 from the array by any possible subset and multiplicand.

Return True if the array is good otherwise return False.

Example 1:

Input: nums = [12,5,7,23]
Output: true
Explanation: Pick numbers 5 and 7.
5*3 + 7*(-2) = 1

Example 2:

Input: nums = [29,6,10]
Output: true
Explanation: Pick numbers 29, 6 and 10.
29*1 + 6*(-3) + 10*(-1) = 1

Example 3:

Input: nums = [3,6]
Output: false

Constraints:

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

Solution: Math

Bézout’s lemma: b[1] * A[1] + b[2] * A[2] + …. + b[n] * A[n] = 1 <==> gcd(A[1], A[2], …, A[n]) = 1 <=> at least two numbers are co-prime

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

C++

// Author: Huahua

class Solution {

public:

bool isGoodArray(vector<int>& nums) {

int g = nums[0];

for (int x : nums)

g = gcd(g, x);

return g == 1;

}

};

花花酱 LeetCode 1240. Tiling a Rectangle with the Fewest Squares

By zxi on October 27, 2019

Given a rectangle of size n x m, find the minimum number of integer-sided squares that tile the rectangle.

Example 1:

Input: n = 2, m = 3
Output: 3
Explanation: 3 squares are necessary to cover the rectangle.
2 (squares of 1x1)
1 (square of 2x2)

Example 2:

Input: n = 5, m = 8
Output: 5

Example 3:

Input: n = 11, m = 13
Output: 6

Solution1: DP + Cheating

DP can not handle case 3, for m, n <= 13, (11,13) is the only case of that special case.

dp[i][j] := min squares to tile a i x j rectangle.

dp[i][i] = 1

dp[i][j] = min(dp[r][j] + dp[i-r][j], dp[i][c] + dp[i][j – c]), 1 <= r <= i/2, 1 <= c <= j /2

answer dp[m][n]

Time complexity: O(m*n*max(n, m))
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

int tilingRectangle(int n, int m) {

if (max(n, m) == 13 && min(n, m) == 11) return 6;

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

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

for (int j = 1; j <= m; ++j) {

dp[i][j] = INT_MAX;

if (i == j) {

dp[i][j] = 1;

continue;

}

for (int r = 1; r <= i / 2; ++r)

dp[i][j] = min(dp[i][j], dp[r][j] + dp[i - r][j]);

for (int c = 1; c <= j / 2; ++c)

dp[i][j] = min(dp[i][j], dp[i][c] + dp[i][j - c]);

}

return dp[n][m];

}

};

Solution 2: DFS

C++

// Author: Huahua

class Solution {

public:

int tilingRectangle(int n, int m) {

if (n > m) return tilingRectangle(m, n);

int ans = n * m;

vector<int> h(n);

function<void(int)> dfs = [&](int cur) {

if (cur >= ans) return;

auto it = min_element(begin(h), end(h));

if (*it == m) { // All filled

ans = cur;

return;

}

int low = *it;

int s = it - begin(h);

int e = s;

// Find the base

while (e < n && h[e] == h[s] && (e - s + 1 + low) <= m) ++e;

for (int i = --e; i >= s; --i) {

// Try all possible square sizes in reverse order.

int size = i - s + 1;

for (int j = s; j <= i; ++j) h[j] += size;

dfs(cur + 1);

for (int j = s; j <= i; ++j) h[j] -= size;

}

};

dfs(0);

return ans;

}

};

花花酱 LeetCode 1235. Maximum Profit in Job Scheduling

By zxi on October 24, 2019

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime , endTime and profit arrays, you need to output the maximum profit you can take such that there are no 2 jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:


Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

Constraints:

1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
1 <= startTime[i] < endTime[i] <= 10^9
1 <= profit[i] <= 10^4

Solution: DP + binary search

Sort jobs by ending time.
dp[t] := max profit by end time t.

for a job = (s, e, p)
dp[e] = dp[u] + p, u <= s, and if dp[u] + p > last_element in dp.

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

C++

// Author: Huahua

class Solution {

public:

int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {

const int n = startTime.size();

vector<vector<int>> jobs(n);

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

jobs[i] = {endTime[i], startTime[i], profit[i]};

sort(begin(jobs), end(jobs));

int ans = 0;

map<int, int> m{{0, 0}}; // {end_time -> max_profit}

for (const auto& job : jobs) {

int p = prev(m.upper_bound(job[1]))->second + job[2];

if (p > rbegin(m)->second) {

m[job[0]] = p;

}

return rbegin(m)->second;

}

};

花花酱 LeetCode 1220. Count Vowels Permutation

By zxi on October 5, 2019

Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u')
Each vowel 'a' may only be followed by an 'e'.
Each vowel 'e' may only be followed by an 'a' or an 'i'.
Each vowel 'i' may not be followed by another 'i'.
Each vowel 'o' may only be followed by an 'i' or a 'u'.
Each vowel 'u' may only be followed by an 'a'.

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

Example 1:

Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".

Example 2:

Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

Example 3:

Input: n = 5
Output: 68

Constraints:

1 <= n <= 2 * 10^4

Solution: DP

dp[i][c] := number of strings of length i ends with letter c
transition: follow the definition
ans = sum(dp[n])

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

C++

// Author: Huahua

class Solution {

public:

int countVowelPermutation(int n) {

constexpr int kMod = 1e9 + 7;

vector<vector<long>> dp(n + 1, vector<long>(5));

fill(begin(dp[1]), end(dp[1]), 1);

// 0: a, 1: e, 2: i, 3: o, 4: u

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

dp[i][1] += dp[i - 1][0]; // a -> e

dp[i][0] += dp[i - 1][1]; // e -> a

dp[i][2] += dp[i - 1][1]; // e -> i

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

if (j == 2) continue;

dp[i][j] += dp[i - 1][2]; // i -> *

}

dp[i][2] += dp[i - 1][3]; // o -> i

dp[i][4] += dp[i - 1][3]; // o -> u

dp[i][0] += dp[i - 1][4]; // u -> a

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

dp[i][j] %= kMod;

}

return accumulate(begin(dp[n]), end(dp[n]), 0L) % kMod;

}

};

C++/O(1)

// Author: Huahua

class Solution {

public:

int countVowelPermutation(int n) {

constexpr int kMod = 1e9 + 7;

long a = 1, e = 1, i = 1, o = 1, u = 1;

for (int k = 2; k <= n; ++k) {

long aa = (i + e + u) % kMod;

long ee = (i + a) % kMod;

long ii = (e + o) % kMod;

long oo = i % kMod;

long uu = (i + o) % kMod;

a = aa;

e = ee;

i = ii;

o = oo;

u = uu;

}

return (a + e + i + o + u) % kMod;

}

};

Solution 2: Matrix multiplication

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

C++

// Author: Huahua

constexpr int kMod = 1e9 + 7;

vector<vector<long>> operator*(const vector<vector<long>>& A, const vector<vector<long>>& B) {

int m = A.size();

int x = A[0].size();

int n = B[0].size();

vector<vector<long>> C(m, vector<long>(n));

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

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

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

C[i][j] += A[i][k] * B[k][j];

C[i][j] %= kMod;

}

return C;

}

class Solution {

public:

int countVowelPermutation(int n) {

vector<vector<long>> m{

{0, 1, 0, 0, 0}, // a

{1, 0, 1, 0, 0}, // e

{1, 1, 0, 1, 1}, // i

{0, 0, 1, 0, 1}, // o

{1, 0, 0, 0, 0} // u

};

vector<vector<long>> ans{{1}, {1}, {1}, {1}, {1}};

n -= 1;

while (n > 0) {

if (n % 2) ans = m * ans;

m = m * m;

n /= 2;

}

long sum = 0;

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

sum += ans[i][0];

return sum % kMod;

}

};

花花酱 LeetCode 52. N-Queens II

By zxi on October 2, 2019

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Solution: DFS

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

C++

// Author: Huahua

class Solution {

public:

int totalNQueens(int n) {

vector<int> cols(n);

vector<int> diag1(2 * n - 1);

vector<int> diag2(2 * n - 1);

int ans = 0;

function<void(int)> dfs = [&](int r) {

if (r == n) {

++ans;

return;

}

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

int& c = cols[i];

int& d1 = diag1[r + i];

int& d2 = diag2[r - i + n - 1];

if (c || d1 || d2) continue;

c = d1 = d2 = 1;

dfs(r + 1);

c = d1 = d2 = 0;

}

};

dfs(0);

return ans;

}

};

Posts tagged as “hard”

花花酱 LeetCode 1250. Check If It Is a Good Array

Solution: Math

C++

花花酱 LeetCode 1240. Tiling a Rectangle with the Fewest Squares

Solution1: DP + Cheating

C++

Solution 2: DFS

C++

花花酱 LeetCode 1235. Maximum Profit in Job Scheduling

Solution: DP + binary search

C++

花花酱 LeetCode 1220. Count Vowels Permutation

Solution: DP

C++

C++/O(1)

Solution 2: Matrix multiplication

C++

花花酱 LeetCode 52. N-Queens II

Solution: DFS

C++

Related Problems