Posts published in March 2019

LeetCode 930. Binary Subarrays With Sum

By zxi on March 11, 2019

In an array A of 0s and 1s, how many non-empty subarrays have sum S?

Example 1:

Input: A = [1,0,1,0,1], S = 2
Output: 4
Explanation: 
The 4 subarrays are bolded below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]

Note:

A.length <= 30000
0 <= S <= A.length
A[i] is either 0 or 1.

Solution: Prefix Sum

counts[s] := # of subarrays start from 0 that have sum of s
ans += counts[s – S] if s >= S

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

C++

// Author: Huahua, 28 ms, 12.3 MB

class Solution {

public:

int numSubarraysWithSum(vector<int>& A, int S) {

const int n = A.size();

vector<int> counts(n + 1);

counts[0] = 1;

int ans = 0;

int sum = 0;

for (int a : A) {

sum += a;

if (sum >= S) ans += counts[sum - S];

++counts[sum];

}

return ans;

}

};

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

}

};