Huahua’s Tech Road

花花酱 LeetCode 1360. Number of Days Between Two Dates

By zxi on February 23, 2020

Write a program to count the number of days between two dates.

The two dates are given as strings, their format is YYYY-MM-DD as shown in the examples.

Example 1:

Input: date1 = "2019-06-29", date2 = "2019-06-30"
Output: 1

Example 2:

Input: date1 = "2020-01-15", date2 = "2019-12-31"
Output: 15

Constraints:

The given dates are valid dates between the years 1971 and 2100.

Solution: Convert to days since epoch

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

C++

// Author: Huahua

class Solution {

public:

int daysBetweenDates(string date1, string date2) {

array<int, 12> m{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

auto isLeap = [](int year) {

return year % 4 == 0 && (year % 100 != 0 || year % 400 == 0);

};

auto daysFromEpoch = [&](const string& date) {

int year = stoi(date.substr(0, 4));

int month = stoi(date.substr(5, 2));

int days = stoi(date.substr(8, 2));

for (int i = 1970; i < year; ++i)

days += 365 + isLeap(i);

for (int i = 1; i < month; ++i)

days += m[i - 1];

days += month > 2 && isLeap(year);

return days;

};

return abs(daysFromEpoch(date1) - daysFromEpoch(date2));

}

};

花花酱 LeetCode 1359. Count All Valid Pickup and Delivery Options

By zxi on February 23, 2020

Given n orders, each order consist in pickup and delivery services.

Count all valid pickup/delivery possible sequences such that delivery(i) is always after of pickup(i).

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

Example 1:

Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

Example 2:

Input: n = 2
Output: 6
Explanation: All possible orders: 
(P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) and (P2,D2,P1,D1).
This is an invalid order (P1,D2,P2,D1) because Pickup 2 is after of Delivery 2.

Example 3:

Input: n = 3
Output: 90

Constraints:

1 <= n <= 500

Solution: Combination

Let dp[i] denote the number of valid sequence of i nodes.

For i-1 nodes, the sequence length is 2(i-1).
For the i-th nodes,
If we put Pi at index = 0, then we can put Di at 1, 2, …, 2i – 2 => 2i-1 options.
If we put Pi at index = 1, then we can put Di at 2,3,…, 2i – 2 => 2i – 2 options.
…
If we put Pi at index = 2i-1, then we can put Di at 2i – 1=> 1 option.
There are total (2i – 1 + 1) / 2 * (2i – 1) = i * (2*i – 1) options

dp[i] = dp[i – 1] * i * (2*i – 1)

dp[i] = 2n! / 2^n

C++

// Author: Huahua

class Solution {

public:

int countOrders(int n) {

constexpr int kMod = 1e9 + 7;

long ans = 1;

for (int i = 2; i <= n; ++i)

ans = ans * i * (2 * i - 1) % kMod;

return ans;

}

};

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

Huahua's Tech Road

花花酱 LeetCode 1360. Number of Days Between Two Dates

Solution: Convert to days since epoch

C++

花花酱 LeetCode 1359. Count All Valid Pickup and Delivery Options

C++

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

Solution

C++

Python3

花花酱 LeetCode 1357. Apply Discount Every n Orders

Solution: Simulation

C++

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

Solution: Sorting

C++

Python3