Huahua’s Tech Road

花花酱 LeetCode 1415. The k-th Lexicographical String of All Happy Strings of Length n

By zxi on April 18, 2020

A happy string is a string that:

consists only of letters of the set ['a', 'b', 'c'].
s[i] != s[i + 1] for all values of i from 1 to s.length - 1 (string is 1-indexed).

For example, strings “abc”, “ac”, “b” and “abcbabcbcb” are all happy strings and strings “aa”, “baa” and “ababbc” are not happy strings.

Given two integers n and k, consider a list of all happy strings of length n sorted in lexicographical order.

Return the kth string of this list or return an empty string if there are less than k happy strings of length n.

Example 1:

Input: n = 1, k = 3
Output: "c"
Explanation: The list ["a", "b", "c"] contains all happy strings of length 1. The third string is "c".

Example 2:

Input: n = 1, k = 4
Output: ""
Explanation: There are only 3 happy strings of length 1.

Example 3:

Input: n = 3, k = 9
Output: "cab"
Explanation: There are 12 different happy string of length 3 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]. You will find the 9th string = "cab"

Example 4:

Input: n = 2, k = 7
Output: ""

Example 5:

Input: n = 10, k = 100
Output: "abacbabacb"

Constraints:

1 <= n <= 10
1 <= k <= 100

Solution: DFS

Generate the happy strings in lexical order, store the k-th one.
Time complexity: O(n + k)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

string getHappyString(int n, int k) {

string ans;

string cur;

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

if (k <= 0) return;

if (cur.length() == n) {

if (--k == 0) ans = cur;

return;

}

for (char ch = 'a'; ch <= 'c'; ++ch) {

if (!cur.empty() && ch == cur.back()) continue;

cur.push_back(ch);

dfs();

cur.pop_back();

}

};

dfs();

return k > 0 ? "" : ans;

}

};

花花酱 LeetCode 1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

By zxi on April 18, 2020

Given the number k, return the minimum number of Fibonacci numbers whose sum is equal to k, whether a Fibonacci number could be used multiple times.

The Fibonacci numbers are defined as:

F₁ = 1
F₂ = 1
F_n = F_n-1 + F_n-2 , for n > 2.

It is guaranteed that for the given constraints we can always find such fibonacci numbers that sum k.

Example 1:

Input: k = 7
Output: 2 
Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ... 
For k = 7 we can use 2 + 5 = 7.

Example 2:

Input: k = 10
Output: 2 
Explanation: For k = 10 we can use 2 + 8 = 10.

Example 3:

Input: k = 19
Output: 3 
Explanation: For k = 19 we can use 1 + 5 + 13 = 19.

Constraints:

1 <= k <= 10^9

Solution: Greedy

Find the largest fibonacci numbers x that x <= k, ans = 1 + find(k – x)

Time complexity: O(logk^2) -> O(logk)
Space complexity: O(logk) -> O(1)

Recursive

C++

// Author: Huahua

class Solution {

public:

int findMinFibonacciNumbers(int k) {

if (k == 0) return 0;

int f1 = 1;

int f2 = 1;

while (f2 <= k) {

swap(f1, f2);

f2 += f1;

}

return 1 + findMinFibonacciNumbers(k - f1);

}

};

Iterative

C++

// Author: Huahua

class Solution {

public:

int findMinFibonacciNumbers(int k) {

int f1 = 1;

int f2 = 1;

int ans = 1;

while (f2 <= k) {

swap(f1, f2);

f2 += f1;

}

k -= f1;

while (k) {

if (k >= f1) {

k -= f1;

ans += 1;

}

f2 -= f1;

swap(f1, f2);

}

return ans;

}

};

花花酱 LeetCode 1413. Minimum Value to Get Positive Step by Step Sum

By zxi on April 18, 2020

Given an array of integers nums, you start with an initial positive value startValue.

In each iteration, you calculate the step by step sum of startValue plus elements in nums (from left to right).

Return the minimum positive value of startValue such that the step by step sum is never less than 1.

Example 1:

Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
                step by step sum
                startValue = 4 | startValue = 5 | nums
                  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
                  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
                  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
                  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
                  (4 +2 ) = 6  | (5 +2 ) = 7    |   2

Example 2:

Input: nums = [1,2]
Output: 1
Explanation: Minimum start value should be positive.

Example 3:

Input: nums = [1,-2,-3]
Output: 5

Constraints:

1 <= nums.length <= 100
-100 <= nums[i] <= 100

Solution: Prefix sum

Find the minimum prefix sum, ans = – min(prefix_sum, 0) + 1

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

C++

// Author: Huahua

class Solution {

public:

int minStartValue(vector<int>& nums) {

int min_sum = 0;

int sum = 0;

for (int num : nums) {

sum += num;

min_sum = min(min_sum, sum);

}

return -min_sum + 1;

}

};

Fast Power for DP SP20

By zxi on April 15, 2020

Iterative DP usually takes O(n) to compute dp[n] from dp[0], we could do better if the problem can be written as matrix multiplication. With fast power, dp[n] can be computed in O(logn)

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

}

};

Huahua's Tech Road

花花酱 LeetCode 1415. The k-th Lexicographical String of All Happy Strings of Length n

Solution: DFS

C++

花花酱 LeetCode 1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Solution: Greedy

C++

C++

花花酱 LeetCode 1413. Minimum Value to Get Positive Step by Step Sum

Solution: Prefix sum

C++

Fast Power for DP SP20

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

Solution: DP

C++

Python3

Solution 2: DP w/ Matrix Chain Multiplication

C++