Huahua’s Tech Road

花花酱 1007. Minimum Domino Rotations For Equal Row

By zxi on March 9, 2019

In a row of dominoes, A[i] and B[i] represent the top and bottom halves of the i-th domino. (A domino is a tile with two numbers from 1 to 6 – one on each half of the tile.)

We may rotate the i-th domino, so that A[i] and B[i] swap values.

Return the minimum number of rotations so that all the values in A are the same, or all the values in B are the same.

If it cannot be done, return -1.

Example 1:

Input: A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]
Output: 2
Explanation: 
The first figure represents the dominoes as given by A and B: before we do any rotations.
If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.

Example 2:

Input: A = [3,5,1,2,3], B = [3,6,3,3,4]
Output: -1
Explanation: 
In this case, it is not possible to rotate the dominoes to make one row of values equal.

Note:

1 <= A[i], B[i] <= 6
2 <= A.length == B.length <= 20000

Solution: Brute Force

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

C++

// Author: Huahua, 72 ms, 14.8 MB

class Solution {

public:

int minDominoRotations(vector<int>& A, vector<int>& B) {

int ans = INT_MAX;

for (int r = 1; r <= 6; ++r) {

bool flag = true;

int count_a = 0;

int count_b = 0;

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

if (A[i] != r && B[i] != r) {

flag = false;

break;

}

else if (A[i] == r && B[i] == r) continue;

else if (A[i] == r) {

++count_a;

} else if (B[i] == r) {

++count_b;

}

if (flag) ans = min(ans, min(count_a, count_b));

}

return ans == INT_MAX ? -1 : ans;

}

};

花花酱 LeetCode 1006. Clumsy Factorial

By zxi on March 9, 2019

Normally, the factorial of a positive integer n is the product of all positive integers less than or equal to n. For example, factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1.

We instead make a clumsy factorial: using the integers in decreasing order, we swap out the multiply operations for a fixed rotation of operations: multiply (*), divide (/), add (+) and subtract (-) in this order.

For example, clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1. However, these operations are still applied using the usual order of operations of arithmetic: we do all multiplication and division steps before any addition or subtraction steps, and multiplication and division steps are processed left to right.

Additionally, the division that we use is floor division such that 10 * 9 / 8 equals 11. This guarantees the result is an integer.

Implement the clumsy function as defined above: given an integer N, it returns the clumsy factorial of N.

Example 1:

Input: 4
Output: 7
Explanation: 7 = 4 * 3 / 2 + 1

Example 2:

Input: 10
Output: 12
Explanation: 12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

Note:

1 <= N <= 10000
-2^31 <= answer <= 2^31 - 1 (The answer is guaranteed to fit within a 32-bit integer.)

Solution: Simulation

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

C++

// Author: Huahua 4ms 8.2 MB

class Solution {

public:

int clumsy(int N) {

if (N <= 0) return 0;

if (N == 1) return 1;

if (N == 2) return 2 * 1;

if (N == 3) return 3 * 2 / 1;

int ans = N * (N - 1) / (N - 2) + (N - 3);

while ((N -= 4) >= 4)

ans = ans - N * (N - 1) / (N - 2) + (N - 3);

return ans - clumsy(N);

}

};

花花酱 LeetCode 1005. Maximize Sum Of Array After K Negations

By zxi on March 9, 2019

Given an array A of integers, we must modify the array in the following way: we choose an i and replace A[i] with -A[i], and we repeat this process K times in total. (We may choose the same index i multiple times.)

Return the largest possible sum of the array after modifying it in this way.

Example 1:

Input: A = [4,2,3], K = 1
Output: 5
Explanation: Choose indices (1,) and A becomes [4,-2,3].

Example 2:

Input: A = [3,-1,0,2], K = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and A becomes [3,1,0,2].

Example 3:

Input: A = [2,-3,-1,5,-4], K = 2
Output: 13
Explanation: Choose indices (1, 4) and A becomes [2,3,-1,5,4].

Note:

1 <= A.length <= 10000
1 <= K <= 10000
-100 <= A[i] <= 100

Solution: Sorting

Flip as many as negative numbers as possible, if K > # of negative numbers and K is odd, flip the smallest element in the array.

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

C++

// Author: Huahua 8 ms 8.6MB

class Solution {

public:

int largestSumAfterKNegations(vector<int>& A, int K) {

std::sort(begin(A), end(A));

for (int& a : A) {

if (!K) break;

if (a < 0) {

a = -a;

--K;

}

return accumulate(begin(A), end(A), 0) - (K % 2 ? *min_element(begin(A), end(A)) * 2 : 0);

}

};

花花酱 LeetCode 1000. Minimum Cost to Merge Stones

By zxi on March 2, 2019

There are N piles of stones arranged in a row. The i-th pile has stones[i] stones.

A move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these K piles.

Find the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.

Example 1:

Input: stones = [3,2,4,1], K = 2
Output: 20
Explanation: 
We start with [3, 2, 4, 1].
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.

Example 2:

Input: stones = [3,2,4,1], K = 3
Output: -1
Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore.  So the task is impossible.

Example 3:

Input: stones = [3,5,1,2,6], K = 3
Output: 25
Explanation: 
We start with [3, 5, 1, 2, 6].
We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
We merge [3, 8, 6] for a cost of 17, and we are left with [17].
The total cost was 25, and this is the minimum possible.

Note:

1 <= stones.length <= 30
2 <= K <= 30
1 <= stones[i] <= 100

Solution: DP

dp[i][j][k] := min cost to merge subarray i ~ j into k piles
Init: dp[i][j][k] = 0 if i==j and k == 1 else inf
ans: dp[0][n-1][1]
transition:
1. dp[i][j][k] = min{dp[i][m][1] + dp[m+1][j][k-1]} for all i <= m < j
2. dp[i][j][1] = dp[i][j][K] + sum(A[i]~A[j])

Time complexity: O(n^3)
Space complexity: O(n^2*K)

C++

// Running time: 12 ms, 12.1 MB

class Solution {

public:

int mergeStones(vector<int>& stones, int K) {

const int n = stones.size();

if ((n - 1) % (K - 1)) return -1;

const int kInf = 1e9;

vector<int> sums(n + 1);

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

sums[i + 1] = sums[i] + stones[i];

// dp[i][j][k] := min cost to merge subarray i~j into k piles.

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

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

dp[i][i][1] = 0;

for (int l = 2; l <= n; ++l) // subproblem length

for (int i = 0; i <= n - l; ++i) { // start

int j = i + l - 1; // end

for (int k = 2; k <= K; ++k) // piles

for (int m = i; m < j; m += K - 1) // split point

dp[i][j][k] = min(dp[i][j][k], dp[i][m][1] + dp[m + 1][j][k - 1]);

dp[i][j][1] = dp[i][j][K] + sums[j + 1] - sums[i];

}

return dp[0][n - 1][1];

}

};

C++/top down

// Author: Huahua, running time: 12 ms

class Solution {

public:

int mergeStones(vector<int>& stones, int K) {

const int n = stones.size();

if ((n - 1) % (K - 1)) return -1;

const int kInf = 1e9;

vector<int> sums(n + 1);

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

sums[i + 1] = sums[i] + stones[i];

vector<vector<vector<int>>> cache(n, vector<vector<int>>(n, vector<int>(K + 1, INT_MAX)));

std::function<int(int, int, int)> dp = [&stones, &sums, &cache, kInf, n, K, &dp](int i, int j, int k) {

if ((j - i + 1 - k) % (K - 1)) return kInf;

if (i == j) return k == 1 ? 0 : kInf;

if (cache[i][j][k] != INT_MAX) return cache[i][j][k];

if (k == 1)

return cache[i][j][k] = dp(i, j, K) + sums[j + 1] - sums[i];

int ans = kInf;

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

int l = dp(i, m, 1);

if (l >= ans) continue;

int r = dp(m + 1, j, k - 1);

if (r >= ans) continue;

ans = min(ans, l + r);

}

return cache[i][j][k] = ans;

};

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

}

};

Solution 2: DP

dp[l][i] := min cost to merge [i, i + l) into as less piles as possible. Number of merges will be (l-1) / (K – 1) and
Transition: dp[l][i] = min(dp[m][i] + dp[l – m][i + m]) for 1 <= m < l
if ((l – 1) % (K – 1) == 0) [i, i + l) can be merged into 1 pile, dp[l][i] += sum(A[i:i+l])

Time complexity: O(n^3 / k)
Space complexity: O(n^2)

C++

// Author: Huahua 4ms, 9.6 MB

class Solution {

public:

int mergeStones(vector<int>& stones, int K) {

const int n = stones.size();

if ((n - 1) % (K - 1)) return -1;

vector<int> sums(n + 1);

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

sums[i + 1] = sums[i] + stones[i];

const int kInf = 1e9;

// dp[i][j] := min cost to merge subarray A[i] ~ A[j] into (j-i)%(K-1) + 1 piles

vector<vector<int>> dp(n, vector<int>(n, kInf));

for (int i = 0; i < n; ++i) dp[i][i] = 0;

for (int l = 2; l <= n; ++l) // subproblem length

for (int i = 0; i <= n - l; ++i) { // start

int j = i + l - 1;

for (int m = i; m < j ; m += K - 1) // split point

dp[i][j] = min(dp[i][j], dp[i][m] + dp[m + 1][j]);

// If the current length can be merged into 1 pile

// The cost is independent of the merge orders.

if ((l - 1) % (K - 1) == 0)

dp[i][j] += sums[j + 1] - sums[i];

}

return dp[0][n - 1];

}

};

C++/Top-Down

// Author: Huahua, 4 ms

class Solution {

public:

int mergeStones(vector<int>& stones, int K) {

const int n = stones.size();

if ((n - 1) % (K - 1)) return -1;

const int kInf = 1e9;

vector<vector<int>> cache(n, vector<int>(n, kInf));

vector<int> sums(n + 1);

for (int i = 0; i < stones.size(); ++i) sums[i + 1] = sums[i] + stones[i];

std::function<int(int, int)> dp;

dp = [&stones, &sums, &cache, &dp, K, kInf](int i, int j) {

const int l = j - i + 1;

if (l < K) return 0;

if (cache[i][j] != kInf) return cache[i][j];

int ans = kInf;

for (int m = i; m < j ; m += K - 1) // split point

ans = min(ans, dp(i, m) + dp(m + 1, j));

if ((l - 1) % (K - 1) == 0)

ans += sums[j + 1] - sums[i];

return cache[i][j] = ans;

};

return dp(0, n - 1);

}

};

花花酱 LeetCode 1003. Check If Word Is Valid After Substitutions

By zxi on March 2, 2019

We are given that the string "abc" is valid.

From any valid string V, we may split V into two pieces X and Y such that X + Y (X concatenated with Y) is equal to V. (X or Y may be empty.) Then, X + "abc" + Y is also valid.

If for example S = "abc", then examples of valid strings are: "abc", "aabcbc", "abcabc", "abcabcababcc". Examples of invalid strings are: "abccba", "ab", "cababc", "bac".

Return true if and only if the given string S is valid.

Example 1:

Input: "aabcbc"
Output: true
Explanation: 
We start with the valid string "abc".
Then we can insert another "abc" between "a" and "bc", resulting in "a" + "abc" + "bc" which is "aabcbc".

Example 2:

Input: "abcabcababcc"
Output: true
Explanation: 
"abcabcabc" is valid after consecutive insertings of "abc".
Then we can insert "abc" before the last letter, resulting in "abcabcab" + "abc" + "c" which is "abcabcababcc".

Example 3:

Input: "abccba"
Output: false

Example 4:

Input: "cababc"
Output: false

Note:

1 <= S.length <= 20000
S[i] is 'a', 'b', or 'c'

Solution: Stack

If current char can be appended to the stack do so, if the top of stack is “abc” pop, otherwise push the current char to the stack. Check whether the stack is empty after all chars were processed.

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

C++

// Author: Huahua, running time: 28 ms, 11.9 MB

class Solution {

public:

bool isValid(string S) {

stack<string> st;

for (char ch : S) {

if (st.empty()) {

st.push("");

}

string& s = st.top();

char exp = 'a' + s.length();

if (ch == exp) {

s += ch;

if (s == "abc") st.pop();

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

return false;

} else {

st.push("a");

}

return st.empty();

}

};

Huahua's Tech Road

花花酱 1007. Minimum Domino Rotations For Equal Row

Solution: Brute Force

C++

花花酱 LeetCode 1006. Clumsy Factorial

Solution: Simulation

C++

花花酱 LeetCode 1005. Maximize Sum Of Array After K Negations

Solution: Sorting

C++

花花酱 LeetCode 1000. Minimum Cost to Merge Stones

Solution: DP

C++

C++/top down

Solution 2: DP

C++

C++/Top-Down

花花酱 LeetCode 1003. Check If Word Is Valid After Substitutions

Solution: Stack

C++