Posts tagged as “medium”

花花酱 LeetCode 1348. Tweet Counts Per Frequency

By zxi on February 29, 2020

Implement the class TweetCounts that supports two methods:

1. recordTweet(string tweetName, int time)

Stores the tweetName at the recorded time (in seconds).

2. getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime)

Returns the total number of occurrences for the given tweetName per minute, hour, or day (depending on freq) starting from the startTime (in seconds) and ending at the endTime (in seconds).
freq is always minute, hour or day, representing the time interval to get the total number of occurrences for the given tweetName.
The first time interval always starts from the startTime, so the time intervals are [startTime, startTime + delta*1>, [startTime + delta*1, startTime + delta*2>, [startTime + delta*2, startTime + delta*3>, ... , [startTime + delta*i, min(startTime + delta*(i+1), endTime + 1)> for some non-negative number i and delta (which depends on freq).

Example:

Input
["TweetCounts","recordTweet","recordTweet","recordTweet","getTweetCountsPerFrequency","getTweetCountsPerFrequency","recordTweet","getTweetCountsPerFrequency"]
[[],["tweet3",0],["tweet3",60],["tweet3",10],["minute","tweet3",0,59],["minute","tweet3",0,60],["tweet3",120],["hour","tweet3",0,210]]

Output
[null,null,null,null,[2]
[2,1],null,[4]]

Explanation
TweetCounts tweetCounts = new TweetCounts();
tweetCounts.recordTweet("tweet3", 0);
tweetCounts.recordTweet("tweet3", 60);
tweetCounts.recordTweet("tweet3", 10);                             // All tweets correspond to "tweet3" with recorded times at 0, 10 and 60.
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59); // return [2]. The frequency is per minute (60 seconds), so there is one interval of time: 1) [0, 60> - > 2 tweets.
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60); // return [2, 1]. The frequency is per minute (60 seconds), so there are two intervals of time: 1) [0, 60> - > 2 tweets, and 2) [60,61> - > 1 tweet.
tweetCounts.recordTweet("tweet3", 120);                            // All tweets correspond to "tweet3" with recorded times at 0, 10, 60 and 120.
tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210);  // return [4]. The frequency is per hour (3600 seconds), so there is one interval of time: 1) [0, 211> - > 4 tweets.

Constraints:

There will be at most 10000 operations considering both recordTweet and getTweetCountsPerFrequency.
0 <= time, startTime, endTime <= 10^9

Solution: Hashtable + binary search

Time complexity:
Record: O(logn)
getCount: O(logn + |entries|)

Space complexity: O(n)

C++

// Author: Huahua

class TweetCounts {

public:

TweetCounts() {

m_.clear();

}

void recordTweet(string tweetName, int time) {

m_[tweetName].insert(time);

}

vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {

auto tit = m_.find(tweetName);

if (tit == m_.end()) return {};

const set<int>& s = tit->second;

int delta = 1;

if (freq == "minute") delta = 60;

else if (freq == "hour") delta = 60 * 60;

else if (freq == "day") delta = 60 * 60 * 24;

int slots = (endTime - startTime + delta - 1) / delta;

vector<int> ans(slots);

for (int i = startTime; i <= endTime; i += delta) {

auto it1 = s.lower_bound(i);

auto it2 = s.lower_bound(min(i + delta, endTime + 1));

ans.push_back(distance(it1, it2)); // O(|entries|)

}

return ans;

}

private:

unordered_map<string, set<int>> m_;

};

花花酱 LeetCode 1362. Closest Divisors

By zxi on February 23, 2020

Given an integer num, find the closest two integers in absolute difference whose product equals num + 1 or num + 2.

Return the two integers in any order.

Example 1:

Input: num = 8
Output: [3,3]
Explanation: For num + 1 = 9, the closest divisors are 3 & 3, for num + 2 = 10, the closest divisors are 2 & 5, hence 3 & 3 is chosen.

Example 2:

Input: num = 123
Output: [5,25]

Example 3:

Input: num = 999
Output: [40,25]

Constraints:

1 <= num <= 10^9

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

vector<int> closestDivisors(int num) {

auto divisors = [](int n) {

for (int i = sqrt(n); i >= 2; --i)

if (n % i == 0) return vector<int>{i, n / i};

return vector<int>{1, n};

};

auto ans1 = divisors(num + 1);

auto ans2 = divisors(num + 2);

return ans1[1] - ans1[0] < ans2[1] - ans2[0] ? ans1 : ans2;

}

};

Python3

# Author: Huahua

class Solution:

def closestDivisors(self, num: int) -> List[int]:

def divisors(n: int) -> List[int]:

for i in range(int(math.sqrt(n)), 1, -1):

if n % i == 0: return [i, n // i]

return [1, n]

a1, a2 = divisors(num + 1), divisors(num + 2)

return a1 if a1[1] - a1[0] < a2[1] - a2[0] else a2

花花酱 1358. Number of Substrings Containing All Three Characters

By zxi on February 22, 2020

Given a string s consisting only of characters a, b and c.

Return the number of substrings containing at least one occurrence of all these characters a, b and c.

Example 1:

Input: s = "abcabc"
Output: 10
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again).

Example 2:

Input: s = "aaacb"
Output: 3
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "aaacb", "aacb" and "acb".

Example 3:

Input: s = "abc"
Output: 1

Constraints:

3 <= s.length <= 5 x 10^4
s only consists of a, b or c characters.

Solution

Record the last index of each character.

At each index i, we can choose any index j that j <= min(last_a, last_b, last_c) as the starting point, and there will be min(last_a, last_b, last_c) + 1 valid substrings.

e.g. aabbabcc…
last_a = 4
last_b = 5
last_c = 7
min(last_a, last_b, last_c) = 4
aabba | bcc
We can choose any char with index <= 4 as string point, there are 5 of them:
aabbabcc
abbabcc
bbabcc
babcc
abcc

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

C++

// Author: Huahua

class Solution {

public:

int numberOfSubstrings(string s) {

vector<int> l{-1,-1,-1};

int ans = 0;

for (size_t i = 0; i < s.length(); ++i) {

l[s[i] - 'a'] = i;

ans += 1 + *min_element(begin(l), end(l));

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def numberOfSubstrings(self, s: str) -> int:

l = {'a':-1, 'b':-1, 'c':-1}

ans = 0

for i, ch in enumerate(s):

l[ch] = i

ans += min(l.values()) + 1

return ans

花花酱 LeetCode 1357. Apply Discount Every n Orders

By zxi on February 22, 2020

There is a sale in a supermarket, there will be a discount every n customer.
There are some products in the supermarket where the id of the i-th product is products[i] and the price per unit of this product is prices[i].
The system will count the number of customers and when the n-th customer arrive he/she will have a discount on the bill. (i.e if the cost is x the new cost is x - (discount * x) / 100). Then the system will start counting customers again.
The customer orders a certain amount of each product where product[i] is the id of the i-th product the customer ordered and amount[i] is the number of units the customer ordered of that product.

Implement the Cashier class:

Cashier(int n, int discount, int[] products, int[] prices) Initializes the object with n, the discount, the products and their prices.
double getBill(int[] product, int[] amount) returns the value of the bill and apply the discount if needed. Answers within 10^-5 of the actual value will be accepted as correct.

Example 1:

Input
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
Output
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]
Explanation
Cashier cashier = new Cashier(3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]);
cashier.getBill([1,2],[1,2]);                        // return 500.0, bill = 1 * 100 + 2 * 200 = 500.
cashier.getBill([3,7],[10,10]);                      // return 4000.0
cashier.getBill([1,2,3,4,5,6,7],[1,1,1,1,1,1,1]);    // return 800.0, The bill was 1600.0 but as this is the third customer, he has a discount of 50% which means his bill is only 1600 - 1600 * (50 / 100) = 800.
cashier.getBill([4],[10]);                           // return 4000.0
cashier.getBill([7,3],[10,10]);                      // return 4000.0
cashier.getBill([7,5,3,1,6,4,2],[10,10,10,9,9,9,7]); // return 7350.0, Bill was 14700.0 but as the system counted three more customers, he will have a 50% discount and the bill becomes 7350.0
cashier.getBill([2,3,5],[5,3,2]);                    // return 2500.0

Constraints:

1 <= n <= 10^4
0 <= discount <= 100
1 <= products.length <= 200
1 <= products[i] <= 200
There are not repeated elements in the array products.
prices.length == products.length
1 <= prices[i] <= 1000
1 <= product.length <= products.length
product[i] exists in products.
amount.length == product.length
1 <= amount[i] <= 1000
At most 1000 calls will be made to getBill.
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: Simulation

Time complexity: O(|Q|)
Space complexity: O(|P|)

C++

// Author: Huahua

class Cashier {

public:

Cashier(int n, int discount,

vector<int>& products,

vector<int>& prices): n_(n), c_(0), discount_(discount) {

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

prices_[products[i]] = prices[i];

}

double getBill(vector<int> product, vector<int> amount) {

++c_;

double bill = 0.0;

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

bill += prices_[product[i]] * amount[i];

if (c_ % n_ == 0)

bill *= 1.0 - discount_ / 100.0;

return bill;

}

private:

int n_;

int c_;

int discount_;

array<int, 201> prices_;

};

花花酱 LeetCode 1353. Maximum Number of Events That Can Be Attended

By zxi on February 16, 2020

Given an array of events where events[i] = [startDay_i, endDay_i]. Every event i starts at startDay_iand ends at endDay_i.

You can attend an event i at any day d where startTime_i <= d <= endTime_i. Notice that you can only attend one event at any time d.

Return the maximum number of events you can attend.

Example 1:

Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.

Example 2:

Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4

Example 3:

Input: events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
Output: 4

Example 4:

Input: events = [[1,100000]]
Output: 1

Example 5:

Input: events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
Output: 7

Constraints:

1 <= events.length <= 10^5
events[i].length == 2
1 <= events[i][0] <= events[i][1] <= 10^5

Solution: Greedy

Sort events by end time, for each event find the first available day to attend.

Time complexity: O(sum(endtime – starttime)) = O(10^10)
Space complexity: O(max(endtime – starttime) = O(10^5)

C++

// Author: Huahua, 216 ms, 45.7 MB

class Solution {

public:

int maxEvents(vector<vector<int>>& events) {

sort(begin(events), end(events), [](const auto& a, const auto& b){

return a[1] < b[1];

});

int ans = 0;

int seen[100001] = {0};

for (const auto& e : events) {

for (int i = e[0]; i <= e[1]; ++i) {

if (seen[i]) continue;

++seen[i];

++ans;

break;

}

return ans;

}

};

C++

// Author: Huahua, 216 ms, 45.6 MB

class Solution {

public:

int maxEvents(vector<vector<int>>& events) {

sort(begin(events), end(events), [](const auto& a, const auto& b){

return a[1] < b[1];

});

int ans = 0;

unsigned char seen[100000 / 8 + 1] = {0};

for (const auto& e : events) {

for (int i = e[0]; i <= e[1]; ++i) {

if (seen[i >> 3] & (1 << (i % 8))) continue;

seen[i >> 3] |= 1 << (i % 8);

++ans;

break;

}

return ans;

}

};

Python

// Author: Huahua, 824 ms

class Solution:

def maxEvents(self, events: List[List[int]]) -> int:

lo = min(e[0] for e in events)

hi = max(e[1] for e in events)

seen = [0] * (hi - lo + 1)

for s, t in sorted(events, key=lambda e:e[1]):

for i in range(s, t + 1):

if seen[i - lo]: continue

seen[i - lo] = 1

break

return sum(seen)

We can use a TreeSet to maintain the open days and do a binary search to find the first available day.

Time complexity: O(nlogd)
Space complexity: O(d)

C++

// Author: Huahua, 416 ms, 46.1MB

class Solution {

public:

int maxEvents(vector<vector<int>>& events) {

sort(begin(events), end(events), [](const auto& a, const auto& b){

return a[1] < b[1];

});

int min_d = INT_MAX;

int max_d = INT_MIN;

for (const auto& e : events) {

min_d = min(min_d, e[0]);

max_d = max(max_d, e[1]);

}

vector<int> days(max_d - min_d + 1);

iota(begin(days), end(days), min_d);

set<int> s(begin(days), end(days)); // O(n)

int ans = 0;

for (const auto& e : events) {

auto it = s.lower_bound(e[0]);

if (it == end(s) || *it > e[1]) continue;

s.erase(it);

++ans;

}

return ans;

}

};