Posts tagged as “medium”

花花酱 LeetCode 1352. Product of the Last K Numbers

By zxi on February 16, 2020

Implement the class ProductOfNumbers that supports two methods:

1. add(int num)

Adds the number num to the back of the current list of numbers.

2. getProduct(int k)

Returns the product of the last k numbers in the current list.
You can assume that always the current list has at least k numbers.

At any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.

Example:

Input
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

Output: [null,null,null,null,null,null,20,40,0,null,32]
Explanation:
ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3);        // [3] 
productOfNumbers.add(0);        // [3,0] 
productOfNumbers.add(2);        // [3,0,2]
productOfNumbers.add(5);        // [3,0,2,5]
productOfNumbers.add(4);        // [3,0,2,5,4]
productOfNumbers.getProduct(2); // return 20.
The product of the last 2 numbers is 5 * 4 = 20
productOfNumbers.getProduct(3); // return 40. The product of the last 3 numbers is 2 * 5 * 4 = 40 
productOfNumbers.getProduct(4); // return 0. The product of the last 4 numbers is 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8);        // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // return 32. The product of the last 2 numbers is 4 * 8 = 32

Constraints:

There will be at most 40000 operations considering both add and getProduct.
0 <= num <= 100
1 <= k <= 40000

Solution: Prefix product

Use p[i] to store the prod of a1*a2*…ai
p[i] = ai*p[i-1]
If ai is 0, reset p = [1].
Compare k with the len(p), if k is greater than len(p) which means there is 0 recently, return 0.
otherwise return p[n] / p[n – k – 1]

Time complexity: Add: O(1), getProduct: O(1)
Space complexity: O(n)

C++

// Author: Huahua

class ProductOfNumbers {

public:

ProductOfNumbers(): p_(1, 1) { }

void add(int num) {

if (num == 0) {

p_.clear();

p_.push_back(1);

} else {

p_.push_back(p_.back() * num);

}

int getProduct(int k) {

if (k >= p_.size()) return 0;

// a_1*a_2*...*a_n / a_1*a_2*...*a_n-k-1.

return p_.back() / p_[p_.size() - k - 1];

}

private:

vector<int> p_;

};

花花酱 LeetCode 1344. Angle Between Hands of a Clock

By zxi on February 13, 2020

Given two numbers, hour and minutes. Return the smaller angle (in sexagesimal units) formed between the hour and the minute hand.

Example 1:

Input: hour = 12, minutes = 30
Output: 165

Example 2:

Input: hour = 3, minutes = 30
Output: 75

Example 3:

Input: hour = 3, minutes = 15
Output: 7.5

Example 4:

Input: hour = 4, minutes = 50
Output: 155

Example 5:

Input: hour = 12, minutes = 0
Output: 0

Constraints:

1 <= hour <= 12
0 <= minutes <= 59
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: Math

Compute the angle of the hour hand (h + m / 60.0) * 360 / 12 as a_h
Compute the angle of the minute hand m / 60.0 * 360 as a_m
ans = min(abs(a_h – a_m), 360 – abs(a_h – a_m))

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

C++

// Author: Huahua

class Solution {

public:

double angleClock(int hour, int minutes) {

double a_m = minutes * 360 / 60;

double a_h = (hour + minutes / 60.0) * 360 / 12;

return min(abs(a_m - a_h), 360 - abs(a_m - a_h));

}

};

花花酱 LeetCode 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

By zxi on February 13, 2020

Given an array of integers arr and two integers k and threshold.

Return the number of sub-arrays of size k and average greater than or equal to threshold.

Example 1:

Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).

Example 2:

Input: arr = [1,1,1,1,1], k = 1, threshold = 0
Output: 5

Example 3:

Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
Output: 6
Explanation: The first 6 sub-arrays of size 3 have averages greater than 5. Note that averages are not integers.

Example 4:

Input: arr = [7,7,7,7,7,7,7], k = 7, threshold = 7
Output: 1

Example 5:

Input: arr = [4,4,4,4], k = 4, threshold = 1
Output: 1

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^4
1 <= k <= arr.length
0 <= threshold <= 10^4

Solution: Sliding Window

Window size = k
Maintain the sum of the window
Check sum >= threshold * k

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

C++

// Author: Huahua

class Solution {

public:

int numOfSubarrays(vector<int>& arr, int k, int threshold) {

int ans = 0;

int sum = 0;

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

sum += arr[i];

if (i + 1 >= k) {

if (threshold * k <= sum) ++ans;

sum -= arr[i + 1 - k];

}

return ans;

}

};

花花酱 LeetCode 1093. Statistics from a Large Sample

By zxi on February 6, 2020

We sampled integers between 0 and 255, and stored the results in an array count: count[k] is the number of integers we sampled equal to k.

Return the minimum, maximum, mean, median, and mode of the sample respectively, as an array of floating point numbers. The mode is guaranteed to be unique.

(Recall that the median of a sample is:

The middle element, if the elements of the sample were sorted and the number of elements is odd;
The average of the middle two elements, if the elements of the sample were sorted and the number of elements is even.)

Example 1:

Input: count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: [1.00000,3.00000,2.37500,2.50000,3.00000]

Example 2:

Input: count = [0,4,3,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: [1.00000,4.00000,2.18182,2.00000,1.00000]

Constraints:

count.length == 256
1 <= sum(count) <= 10^9
The mode of the sample that count represents is unique.
Answers within 10^-5 of the true value will be accepted as correct.

Solution: TreeMap

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

C++

// Author: Huahua

class Solution {

public:

vector<double> sampleStats(vector<int>& count) {

int counts = 0;

int minVal = 255;

int maxVal = 0;

int mode = -1;

int modeCount = 0;

long sum = 0;

map<int, int> m;

for (int i = 0; i <= 255; ++i) {

if (!count[i]) continue;

sum += static_cast<long>(i) * count[i];

minVal = min(minVal, i);

maxVal = max(maxVal, i);

if (count[i] > modeCount) {

mode = i;

modeCount = count[i];

}

m[counts += count[i]] = i;

}

auto it1 = m.lower_bound(counts / 2);

double median = it1->second;

auto it2 = next(it1);

if (counts % 2 == 0 && it2 != m.end() && it1->first == counts / 2) {

median = (median + it2->second) / 2;

}

return {minVal, maxVal, static_cast<double>(sum) / counts, median, mode};

}

};

花花酱 LeetCode 1339. Maximum Product of Splitted Binary Tree

By zxi on February 1, 2020

Given a binary tree root. Split the binary tree into two subtrees by removing 1 edge such that the product of the sums of the subtrees are maximized.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)

Example 2:

Input: root = [1,null,2,3,4,null,null,5,6]
Output: 90
Explanation:  Remove the red edge and get 2 binary trees with sum 15 and 6.Their product is 90 (15*6)

Example 3:

Input: root = [2,3,9,10,7,8,6,5,4,11,1]
Output: 1025

Example 4:

Input: root = [1,1]
Output: 1

Constraints:

Each tree has at most 50000 nodes and at least 2 nodes.
Each node’s value is between [1, 10000].

Solution: Recursion

Two passes:
First pass, compute the sum of the entire tree S.
Second pass, for each node, compute the sum of left/right subtree S_l, S_r.
ans = max{(S – S_l) * S_l, (S – S_r) * S_r}

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

C++

// Author: Huahua

class Solution {

public:

int maxProduct(TreeNode* root) {

const int kMod = 1e9 + 7;

long s = 0;

long ans = 0;

function<int(TreeNode*)> sum = [&](TreeNode* r) {

if (!r) return 0;

int sl = sum(r->left);

int sr = sum(r->right);

if (s) ans = max({ans, (s - sl) * sl, (s - sr) * sr});

return r->val + sl + sr;

};

s = sum(root);

sum(root);

return ans % kMod;

}

};