Huahua’s Tech Road

花花酱 LeetCode 1008. Construct Binary Search Tree from Preorder Traversal

By zxi on March 9, 2019

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

Example 1:

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Note:

1 <= preorder.length <= 100
The values of preorder are distinct.

Solution: Recursion

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

C++

// Author: Huahua, 8 ms, 10.8 MB

class Solution {

public:

TreeNode* bstFromPreorder(vector<int>& preorder) {

return build(preorder, 0, preorder.size());

}

private:

TreeNode* build(const vector<int>& preorder, int s, int e) {

if (s >= e) return nullptr;

auto root = new TreeNode(preorder[s]);

int m = s;

while (m < e && preorder[m] <= root->val) ++m;

root->left = build(preorder, s + 1, m);

root->right = build(preorder, m, e);

return root;

}

};

C++/iterator

class Solution {

public:

TreeNode* bstFromPreorder(vector<int>& preorder) {

return build(begin(preorder), end(preorder));

}

private:

typedef vector<int>::const_iterator IT;

TreeNode* build(IT s, IT e) {

if (s >= e) return nullptr;

auto root = new TreeNode(*s);

IT m = s;

while (m < e && *m <= *s) ++m;

root->left = build(s + 1, m);

root->right = build(m, e);

return root;

}

};

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

}

};

Huahua's Tech Road

花花酱 LeetCode 1008. Construct Binary Search Tree from Preorder Traversal

Solution: Recursion

C++

C++/iterator

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