Huahua’s Tech Road

花花酱 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 1356. Sort Integers by The Number of 1 Bits

By zxi on February 22, 2020

Given an integer array arr. You have to sort the integers in the array in ascending order by the number of 1’s in their binary representation and in case of two or more integers have the same number of 1’s you have to sort them in ascending order.

Return the sorted array.

Example 1:

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example 2:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

Example 3:

Input: arr = [10000,10000]
Output: [10000,10000]

Example 4:

Input: arr = [2,3,5,7,11,13,17,19]
Output: [2,3,5,17,7,11,13,19]

Example 5:

Input: arr = [10,100,1000,10000]
Output: [10,100,10000,1000]

Constraints:

1 <= arr.length <= 500
0 <= arr[i] <= 10^4

Solution: Sorting

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

C++

// Author: Huahua

class Solution {

public:

vector<int> sortByBits(vector<int>& arr) {

sort(begin(arr), end(arr), [](const int a, const int b){

int key_a = __builtin_popcount(a);

int key_b = __builtin_popcount(b);

if (key_a != key_b) return key_a < key_b;

return a < b;

});

return arr;

}

};

Python3

# Author: Huahua

class Solution:

def sortByBits(self, arr: List[int]) -> List[int]:

return sorted(arr, key=lambda x: (bin(x).count('1') << 16) + x)

花花酱 LeetCode 1354. Construct Target Array With Multiple Sums

By zxi on February 16, 2020

Given an array of integers target. From a starting array, A consisting of all 1’s, you may perform the following procedure :

let x be the sum of all elements currently in your array.
choose index i, such that 0 <= i < target.size and set the value of A at index i to x.
You may repeat this procedure as many times as needed.

Return True if it is possible to construct the target array from A otherwise return False.

Example 1:

Input: target = [9,3,5]
Output: true
Explanation: Start with [1, 1, 1] 
[1, 1, 1], sum = 3 choose index 1
[1, 3, 1], sum = 5 choose index 2
[1, 3, 5], sum = 9 choose index 0
[9, 3, 5] Done

Example 2:

Input: target = [1,1,1,2]
Output: false
Explanation: Impossible to create target array from [1,1,1,1].

Example 3:

Input: target = [8,5]
Output: true

Constraints:

N == target.length
1 <= target.length <= 5 * 10^4
1 <= target[i] <= 10^9

Solution: Backwards Simulation

Start with the largest number in the array, since it should be the sum of all previous numbers.

[9,3,5] => [9 – (3+5), 3, 5] => [1, 3, 5] => [1, 3, 5 – (1+3)] => [1, 3, 1] => [1, 3 – (1+1), 1] => [1,1,1] done

Time complexity: O(n + log(n*t)*logn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool isPossible(vector<int>& target) {

priority_queue<int> q(begin(target), end(target));

long sum = accumulate(begin(target), end(target), 0LL);

while (true) {

int t = q.top(); q.pop();

sum -= t;

if (t == 1 || sum == 1) return true;

if (t < sum || sum == 0 || t % sum == 0) return false;

t %= sum;

sum += t;

q.push(t);

}

return true;

}

};

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

}

};

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

};

Huahua's Tech Road

花花酱 LeetCode 1357. Apply Discount Every n Orders

Solution: Simulation

C++

花花酱 LeetCode 1356. Sort Integers by The Number of 1 Bits

Solution: Sorting

C++

Python3

花花酱 LeetCode 1354. Construct Target Array With Multiple Sums

Solution: Backwards Simulation

C++

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

Solution: Greedy

C++

C++

Python

C++

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

Solution: Prefix product

C++