Huahua’s Tech Road

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

}

};

花花酱 LeetCode 1410. HTML Entity Parser

By zxi on April 11, 2020

HTML entity parser is the parser that takes HTML code as input and replace all the entities of the special characters by the characters itself.

The special characters and their entities for HTML are:

Quotation Mark: the entity is " and symbol character is ".
Single Quote Mark: the entity is ' and symbol character is '.
Ampersand: the entity is & and symbol character is &.
Greater Than Sign: the entity is > and symbol character is >.
Less Than Sign: the entity is < and symbol character is <.
Slash: the entity is &frasl; and symbol character is /.

Given the input text string to the HTML parser, you have to implement the entity parser.

Return the text after replacing the entities by the special characters.

Example 1:

Input: text = "&amp; is an HTML entity but &ambassador; is not."
Output: "& is an HTML entity but &ambassador; is not."
Explanation: The parser will replace the &amp; entity by &

Example 2:

Input: text = "and I quote: &quot;...&quot;"
Output: "and I quote: \"...\""

Example 3:

Input: text = "Stay home! Practice on Leetcode :)"
Output: "Stay home! Practice on Leetcode :)"

Example 4:

Input: text = "x &gt; y &amp;&amp; x &lt; y is always false"
Output: "x > y && x < y is always false"

Example 5:

Input: text = "leetcode.com&frasl;problemset&frasl;all"
Output: "leetcode.com/problemset/all"

Constraints:

1 <= text.length <= 10^5
The string may contain any possible characters out of all the 256 ASCII characters.

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

string entityParser(string text) {

map<string, string> m{

{""", "\""}, {"'", "'"}, {"&", "&"},

{">", ">"}, {"<", "<"}, {"&frasl;", "/"}};

string ans;

string buf;

for (char c : text) {

buf += c;

if (buf.back() != ';') continue;

const int l = buf.size();

for (const auto& [k, v] : m) {

const int kl = k.length();

if (l >= kl && buf.substr(l - kl) == k) {

ans += buf.substr(0, l - kl) + v;

buf.clear();

break;

}

return ans + buf;

}

};

花花酱 LeetCode 1409. Queries on a Permutation With Key

By zxi on April 11, 2020

Given the array queries of positive integers between 1 and m, you have to process all queries[i] (from i=0 to i=queries.length-1) according to the following rules:

In the beginning, you have the permutation P=[1,2,3,...,m].
For the current i, find the position of queries[i] in the permutation P (indexing from 0) and then move this at the beginning of the permutation P. Notice that the position of queries[i] in P is the result for queries[i].

Return an array containing the result for the given queries.

Example 1:

Input: queries = [3,1,2,1], m = 5
Output: [2,1,2,1] 
Explanation: The queries are processed as follow: 
For i=0: queries[i]=3, P=[1,2,3,4,5], position of 3 in P is 2, then we move 3 to the beginning of P resulting in P=[3,1,2,4,5]. 
For i=1: queries[i]=1, P=[3,1,2,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,3,2,4,5]. 
For i=2: queries[i]=2, P=[1,3,2,4,5], position of 2 in P is 2, then we move 2 to the beginning of P resulting in P=[2,1,3,4,5]. 
For i=3: queries[i]=1, P=[2,1,3,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,2,3,4,5]. 
Therefore, the array containing the result is [2,1,2,1].

Example 2:

Input: queries = [4,1,2,2], m = 4
Output: [3,1,2,0]

Example 3:

Input: queries = [7,5,5,8,3], m = 8
Output: [6,5,0,7,5]

Constraints:

1 <= m <= 10^3
1 <= queries.length <= m
1 <= queries[i] <= m

Solution1: Simulation + Hashtable

Use a hashtable to store the location of each key.
For each query q, use h[q] to get the index of q, for each key, if its current index is less than q, increase their indices by 1. (move right). Set h[q] to 0.

Time complexity: O(q*m)
Space complexity: O(m)

C++

class Solution {

public:

vector<int> processQueries(vector<int>& queries, int m) {

vector<int> p(m + 1);

iota(begin(p), end(p), -1);

vector<int> ans;

for (int q : queries) {

ans.push_back(p[q]);

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

if (p[i] < p[q]) ++p[i];

p[q] = 0;

}

return ans;

}

};

Solution 2: Fenwick Tree + HashTable

Time complexity: O(qlogm)
Space complexity: O(m)

C++

// Author: Huahua

class Fenwick {

public:

explicit Fenwick(int n): vals_(n) {}

// sum(A[1~i])

int query(int i) const {

int s = 0;

while (i > 0) {

s += vals_[i];

i -= i & -i;

}

return s;

}

// A[i] += delta

void update(int i, int delta) {

while (i < vals_.size()) {

vals_[i] += delta;

i += i & -i;

}

private:

vector<int> vals_;

};

class Solution {

public:

vector<int> processQueries(vector<int>& queries, int m) {

Fenwick tree(m * 2 + 1);

vector<int> pos(m + 1);

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

tree.update(pos[i] = i + m, 1);

vector<int> ans;

for (int q : queries) {

ans.push_back(tree.query(pos[q] - 1));

tree.update(pos[q], -1); // set to 0.

tree.update(pos[q] = m--, 1); // move to the front.

}

return ans;

}

};

Python3

class Fenwick:

def __init__(self, n):

self.n = n

self.val = [0] * n

def query(self, i):

s = 0

while i > 0:

s += self.val[i]

i -= i & -i

return s

def update(self, i, delta):

while i < self.n:

self.val[i] += delta

i += i & -i

class Solution:

def processQueries(self, queries: List[int], m: int) -> List[int]:

pos = [i + m for i in range(m + 1)]

tree = Fenwick(2 * m + 1)

for i in range(1, m + 1): tree.update(i + m, 1)

ans = []

for q in queries:

ans.append(tree.query(pos[q] - 1))

tree.update(pos[q], -1)

pos[q] = m

m -= 1

tree.update(pos[q], 1)

return ans

Huahua's Tech Road

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

花花酱 LeetCode 1410. HTML Entity Parser

Solution: Simulation

C++

花花酱 LeetCode 1409. Queries on a Permutation With Key

Solution1: Simulation + Hashtable

C++

Solution 2: Fenwick Tree + HashTable

C++

Python3