Huahua’s Tech Road

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

花花酱 LeetCode 1361. Validate Binary Tree Nodes

By zxi on February 23, 2020

You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one valid binary tree.

If node i has no left child then leftChild[i] will equal -1, similarly for the right child.

Note that the nodes have no values and that we only use the node numbers in this problem.

Example 1:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

Example 2:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: false

Example 3:

Input: n = 2, leftChild = [1,0], rightChild = [-1,-1]
Output: false

Example 4:

Input: n = 6, leftChild = [1,-1,-1,4,-1,-1], rightChild = [2,-1,-1,5,-1,-1]
Output: false

Constraints:

1 <= n <= 10^4
leftChild.length == rightChild.length == n
-1 <= leftChild[i], rightChild[i] <= n - 1

Solution: Count in-degrees for each node

in degree must <= 1 and there must be exact one node that has 0 in-degree.

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

C++

// Author: Huahua

class Solution {

public:

bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {

vector<int> in(n);

for (int l : leftChild) if (l >= 0) ++in[l];

for (int r : rightChild) if (r >= 0) ++in[r];

int zero = 0;

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

if (in[i] > 1) return false;

if (in[i] == 0) ++zero;

}

// # of nodes without parent must be 1.

return zero == 1;

}

};

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

Huahua's Tech Road

花花酱 LeetCode 1362. Closest Divisors

Solution: Brute Force

C++

Python3

花花酱 LeetCode 1361. Validate Binary Tree Nodes

Solution: Count in-degrees for each node

C++

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