Posts tagged as “hard”

花花酱 LeetCode 1411. Number of Ways to Paint N × 3 Grid

By zxi on April 12, 2020

You have a grid of size n x 3 and you want to paint each cell of the grid with exactly one of the three colours: Red, Yellow or Green while making sure that no two adjacent cells have the same colour (i.e no two cells that share vertical or horizontal sides have the same colour).

You are given n the number of rows of the grid.

Return the number of ways you can paint this grid. As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: n = 1
Output: 12
Explanation: There are 12 possible way to paint the grid as shown:

Example 2:

Input: n = 2
Output: 54

Example 3:

Input: n = 3
Output: 246

Example 4:

Input: n = 7
Output: 106494

Example 5:

Input: n = 5000
Output: 30228214

Constraints:

n == grid.length
grid[i].length == 3
1 <= n <= 5000

Solution: DP

dp[i][0] := # of ways to paint i rows with 2 different colors at the i-th row
dp[i][1] := # of ways to paint i rows with 3 different colors at the i-th row
dp[1][0] = dp[1][1] = 6
dp[i][0] = dp[i-1][0] * 3 + dp[i-1][1] * 2
dp[i][1] = dp[i-1][0] * 2 + dp[i-1][1] * 2

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

C++

// Author: Huahua

class Solution {

public:

int numOfWays(int n) {

constexpr int kMod = 1e9 + 7;

// dp[i][0] = # of ways to paint i rows with i-th row has 2 colors (e.g. 121)

// dp[i][1] = # of ways to paint i rows with i-th row has 3 colors (e.g. 123)

// dp[1][0] = dp[1][1] = 6.

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

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

// 121 => 2 colors x 3 {212, 232, 313}, 3 colors x 2 {213, 312}

// 123 => 2 colors x 2 {212, 232}, 3 colors x 2 {231, 312}

dp[i][0] = (dp[i - 1][0] * 3 + dp[i - 1][1] * 2) % kMod;

dp[i][1] = (dp[i - 1][0] * 2 + dp[i - 1][1] * 2) % kMod;

}

return (dp[n][0] + dp[n][1]) % kMod;

}

};

Python3

# Author: Huahua

class Solution:

def numOfWays(self, n: int) -> int:

kMod = 10**9 + 7

dp2, dp3 = 6, 6

for i in range(1, n):

t2, t3 = dp2 * 3 + dp3 * 2, dp2 * 2 + dp3 * 2

dp2, dp3 = t2 % kMod, t3 % kMod

return (dp2 + dp3) % kMod

Solution 2: DP w/ Matrix Chain Multiplication

ans = {6, 6} * {{3, 2}, {2,2}} ^ (n-1)

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

C++

// Author: Huahua

class Solution {

public:

int numOfWays(int n) {

constexpr long kMod = 1e9 + 7;

vector<vector<long>> ans{{6, 6}}; // 1x2

vector<vector<long>> M{{3, 2},{2,2}}; // 2x2

auto mul = [kMod](const vector<vector<long>>& A,

const vector<vector<long>>& B) {

const int m = A.size(); // m * n

const int n = B.size(); // n * p

const int p = B[0].size();

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

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

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

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

C[i][j] += (A[i][k] * B[k][j]) % kMod;

return C;

};

--n;

while (n) {

if (n & 1) ans = mul(ans, M); // ans = ans * M;

M = mul(M, M); // M = M^2

n >>= 1;

}

// ans = ans0 * M^(n-1)

return (ans[0][0] + ans[0][1]) % kMod;

}

};

花花酱 LeetCode 1392. Longest Happy Prefix

By zxi on March 21, 2020

A string is called a happy prefix if is a non-empty prefix which is also a suffix (excluding itself).

Given a string s. Return the longest happy prefix of s .

Return an empty string if no such prefix exists.

Example 1:

Input: s = "level"
Output: "l"
Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"), and suffix ("l", "el", "vel", "evel"). The largest prefix which is also suffix is given by "l".

Example 2:

Input: s = "ababab"
Output: "abab"
Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.

Example 3:

Input: s = "leetcodeleet"
Output: "leet"

Example 4:

Input: s = "a"
Output: ""

Constraints:

1 <= s.length <= 10^5
s contains only lowercase English letters.

Solution: Rolling Hash

Time complexity: O(n) / worst case: O(n^2)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string longestPrefix(string_view s) {

const int kMod = 16769023;

const int kBase = 128;

const int n = s.length();

int p = 0;

int q = 0;

int a = 1;

int ans = 0;

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

p = (p + a * s[i - 1]) % kMod;

q = (q * kBase + s[n - i]) % kMod;

a = (a * kBase) % kMod;

if (p == q && s.substr(0, i) == s.substr(n - i))

ans = i;

}

return string(s.substr(0, ans));

}

};

花花酱 LeetCode 1383. Maximum Performance of a Team

By zxi on March 21, 2020

There are n engineers numbered from 1 to n and two arrays: speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency for the i-th engineer respectively. Return the maximum performance of a team composed of at most k engineers, since the answer can be a huge number, return this modulo 10^9 + 7.

The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers.

Example 1:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation: 
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.

Example 2:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.

Example 3:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72

Constraints:

1 <= n <= 10^5
speed.length == n
efficiency.length == n
1 <= speed[i] <= 10^5
1 <= efficiency[i] <= 10^8
1 <= k <= n

Solution: Greedy + Sliding Window

Sort engineers by their efficiency in descending order.
For each window of K engineers (we can have less than K people in the first k-1 windows), ans is sum(speed) * min(efficiency).

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

C++

// Author: Huahua

class Solution {

public:

int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {

vector<pair<int, int>> es;

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

es.push_back({efficiency[i], speed[i]});

sort(rbegin(es), rend(es));

priority_queue<int, vector<int>, greater<int>> q;

long sum = 0;

long ans = 0;

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

if (i >= k) {

sum -= q.top();

q.pop();

}

sum += es[i].second;

q.push(es[i].second);

ans = max(ans, sum * es[i].first);

}

return ans % static_cast<int>(1e9 + 7);

}

};

Python3

# Author: Huahua

class Solution:

def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:

speeds = 0

ans = 0

q = []

for e, s in sorted(zip(efficiency, speed), reverse=True):

if len(q) >= k:

speeds -= heapq.heappop(q)

speeds += s

heapq.heappush(q, s)

ans = max(ans, speeds * e)

return ans % (10**9 + 7)

花花酱 LeetCode 87. Scramble String

By zxi on March 14, 2020

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Example 1:

Input: s1 = "great", s2 = "rgeat"
Output: true

Example 2:

Input: s1 = "abcde", s2 = "caebd"
Output: false

Solution: Recursion

isScramble(s1, s2)
if s1 == s2: return true
if sorted(s1) != sroted(s2): return false
We try all possible partitions:

s1[0:l] v.s s2[0:l] && s1[l:] vs s2[l:]
s1[0:l] vs s2[L-l:l] && s1[l:] vs s2[0:L-l]

Time complexity: O(n^5)
Space complexity: O(n^4)

C++

class Solution {

public:

bool isScramble(string_view s1, string_view s2) {

const int l = s1.length();

if (s1 == s2) return true;

if (freq(s1) != freq(s2)) return false;

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

if (isScramble(s1.substr(0, i), s2.substr(0, i))

&& isScramble(s1.substr(i), s2.substr(i))

|| isScramble(s1.substr(0, i), s2.substr(l - i, i))

&& isScramble(s1.substr(i), s2.substr(0, l - i)))

return true;

return false;

}

private:

vector<int> freq(string_view s) {

vector<int> f(26);

for (char c : s) ++f[c - 'a'];

return f;

}

};

Python3

# Author: Huahua

class Solution:

@lru_cache(maxsize=None) # optional

def isScramble(self, s1: str, s2: str) -> bool:

if s1 == s2: return True

# important, TLE if commneted out

if Counter(s1) != Counter(s2): return False

L = len(s1)

for l in range(1, L):

if self.isScramble(s1[0:l], s2[0:l]) and self.isScramble(s1[l:], s2[l:]):

return True

if self.isScramble(s1[0:l], s2[L-l:]) and self.isScramble(s1[l:], s2[0:L-l]):

return True

return False

花花酱 LeetCode 224. Basic Calculator

By zxi on March 9, 2020

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:

You may assume that the given expression is always valid.
Do not use the eval built-in library function.

Solution: Recursion

Make a recursive call when there is an open parenthesis and return if there is close parenthesis.

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

C++

// Author: Huahua

class Solution {

public:

int calculate(string s) {

function<int(int&)> eval = [&](int& pos) {

int ret = 0;

int sign = 1;

int val = 0;

while (pos < s.size()) {

const char ch = s[pos];

if (isdigit(ch)) {

val = val * 10 + (s[pos++] - '0');

} else if (ch == '+' || ch == '-') {

ret += sign * val;

val = 0;

sign = ch == '+' ? 1 : -1;

++pos;

} else if (ch == '(') {

val = eval(++pos);

} else if (ch == ')') {

++pos;

break;

} else {

++pos;

}

return ret += sign * val;

};

int pos = 0;

return eval(pos);

}

};

Python3

# Author: Huahua

class Solution:

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

self.pos = 0

def eval():

val = 0

sign = 1

ret = 0

while self.pos < len(s):

ch = s[self.pos]

if ch == ' ':

self.pos += 1

elif ch == '(':

self.pos += 1

val = eval()

elif ch == ')':

self.pos += 1

ret += sign * val

return ret

elif ch == '+' or ch == '-':

ret += sign * val

val = 0

sign = 1 if ch == '+' else -1

self.pos += 1

else:

val = val * 10 + (ord(ch) - ord('0'))

self.pos += 1

ret += val * sign

return ret

return eval()