Posts tagged as “medium”

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;

}

};

花花酱 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 998. Maximum Binary Tree II

By zxi on February 24, 2019

We are given the root node of a maximum tree: a tree where every node has a value greater than any other value in its subtree.

Just as in the previous problem, the given tree was constructed from an list A (root = Construct(A)) recursively with the following Construct(A) routine:

If A is empty, return null.
Otherwise, let A[i] be the largest element of A. Create a root node with value A[i].
The left child of root will be Construct([A[0], A[1], ..., A[i-1]])
The right child of root will be Construct([A[i+1], A[i+2], ..., A[A.length - 1]])
Return root.

Note that we were not given A directly, only a root node root = Construct(A).

Suppose B is a copy of A with the value val appended to it. It is guaranteed that B has unique values.

Return Construct(B).

Example 1:

Input: root = [4,1,3,null,null,2], val = 5
Output: [5,4,null,1,3,null,null,2]
Explanation: A = [1,4,2,3], B = [1,4,2,3,5]

Example 2:

Input: root = [5,2,4,null,1], val = 3
Output: [5,2,4,null,1,null,3]
Explanation: A = [2,1,5,4], B = [2,1,5,4,3]

Example 3:

Input: root = [5,2,3,null,1], val = 4
Output: [5,2,4,null,1,3]
Explanation: A = [2,1,5,3], B = [2,1,5,3,4]

Note:

1 <= B.length <= 100

Solution: Recursion

Since val is the last element of the array, we compare root->val with val, if root->val > val then val can be inserted into the right subtree recursively, otherwise, root will be the left subtree of val.

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

C++

class Solution {

public:

TreeNode* insertIntoMaxTree(TreeNode* root, int val) {

if (root && root->val > val) {

root->right = insertIntoMaxTree(root->right, val);

return root;

}

auto node = new TreeNode(val);

node->left = root;

return node;

}

};

花花酱 LeetCode 74. Search a 2D Matrix

By zxi on February 13, 2019

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input:

matrix = [

[1, 3, 5, 7],

[10, 11, 16, 20],

[23, 30, 34, 50]

]

target = 3

Output: true

Example 2:

Input:

matrix = [

[1, 3, 5, 7],

[10, 11, 16, 20],

[23, 30, 34, 50]

]

target = 13

Output: false

Solution: Binary Search

Treat the 2D array as a 1D array. matrix[index / cols][index % cols]

Time complexity: O(log(m*n))
Space complexity: O(1)

C++

class Solution {

public:

bool searchMatrix(vector<vector<int>>& matrix, int target) {

if (matrix.empty()) return false;

int l = 0;

int r = matrix.size() * matrix[0].size();

const int cols = matrix[0].size();

while (l < r) {

const int m = l + (r - l) / 2;

if (matrix[m / cols][m % cols] == target) {

return true;

} else if (matrix[m / cols][m % cols] > target) {

r = m;

} else {

l = m + 1;

}

return false;

}

};