Huahua’s Tech Road

花花酱 LeetCode 1736. Latest Time by Replacing Hidden Digits

By zxi on January 23, 2021

You are given a string time in the form of hh:mm, where some of the digits in the string are hidden (represented by ?).

The valid times are those inclusively between 00:00 and 23:59.

Return the latest valid time you can get from time by replacing the hidden digits.

Example 1:

Input: time = "2?:?0"
Output: "23:50"
Explanation: The latest hour beginning with the digit '2' is 23 and the latest minute ending with the digit '0' is 50.

Example 2:

Input: time = "0?:3?"
Output: "09:39"

Example 3:

Input: time = "1?:22"
Output: "19:22"

Constraints:

time is in the format hh:mm.
It is guaranteed that you can produce a valid time from the given string.

Solution 1: Brute Force

Enumerate all possible clock in reverse order and find the first matching one.

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

C++

// Author: Huahua

class Solution {

public:

string maximumTime(string time) {

for (int m = 60 * 24 - 1; m >= 0; --m) {

int hh = m / 60;

int mm = m % 60;

if (time[0] != '?' && time[0] - '0' != hh / 10) continue;

if (time[1] != '?' && time[1] - '0' != hh % 10) continue;

if (time[3] != '?' && time[3] - '0' != mm / 10) continue;

if (time[4] != '?' && time[4] - '0' != mm % 10) continue;

time[0] = (hh / 10) + '0';

time[1] = (hh % 10) + '0';

time[3] = (mm / 10) + '0';

time[4] = (mm % 10) + '0';

break;

}

return time;

}

};

Solution 2: Rules

Using rules, fill from left to right.

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

C++

// Author: Huahua

class Solution {

public:

string maximumTime(string time) {

if (time[0] == '?') time[0] = time[1] >= '4' && time[1] <= '9' ? '1' : '2';

if (time[1] == '?') time[1] = time[0] == '2' ? '3' : '9';

if (time[3] == '?') time[3] = '5';

if (time[4] == '?') time[4] = '9';

return time;

}

};

花花酱 LeetCode 1735. Count Ways to Make Array With Product

By zxi on January 23, 2021

You are given a 2D integer array, queries. For each queries[i], where queries[i] = [n_i, k_i], find the number of different ways you can place positive integers into an array of size n_i such that the product of the integers is k_i. As the number of ways may be too large, the answer to the i^th query is the number of ways modulo 10⁹ + 7.

Return an integer array answer where answer.length == queries.length, and answer[i] is the answer to the i^th query.

Example 1:

Input: queries = [[2,6],[5,1],[73,660]]
Output: [4,1,50734910]
Explanation: Each query is independent.
[2,6]: There are 4 ways to fill an array of size 2 that multiply to 6: [1,6], [2,3], [3,2], [6,1].
[5,1]: There is 1 way to fill an array of size 5 that multiply to 1: [1,1,1,1,1].
[73,660]: There are 1050734917 ways to fill an array of size 73 that multiply to 660. 1050734917 modulo 10⁹ + 7 = 50734910.

Example 2:

Input: queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: [1,2,3,10,5]

Constraints:

1 <= queries.length <= 10⁴
1 <= n_i, k_i <= 10⁴

Solution1: DP

let dp(n, k) be the ways to have product k of array size n.
dp(n, k) = sum(dp(n – 1, i)) where i is a factor of k and i != k.
base case:
dp(0, 1) = 1, dp(0, *) = 0
dp(i, 1) = C(n, i)
e.g.
dp(2, 6) = dp(1, 1) + dp(1, 2) + dp(1, 3)
= 2 + 1 + 1 = 4
dp(4, 4) = dp(3, 1) + dp(3, 2)
= dp(3, 1) + dp(2, 1)
= 4 + 6 = 10

Time complexity: O(sum(k_i))?
Space complexity: O(sum(k_i))?

C++

// Author: Huahua

class Solution {

public:

vector<int> waysToFillArray(vector<vector<int>>& queries) {

constexpr int kMod = 1e9 + 7;

int n = 0;

unordered_map<int, int> c, dp;

function<int(int, int)> cnk = [&](int n, int k) {

if (k > n) return 0;

if (k == 0 || k == n) return 1;

int& ans = c[(n << 16) | k];

if (!ans) ans = (cnk(n - 1, k - 1) + cnk(n - 1, k)) % kMod;

return ans;

};

function<int(int, int)> dfs = [&](int s, int k) -> int {

if (s == 0) return k == 1;

if (k == 1) return cnk(n, s);

int& ans = dp[(s << 16) | k];

if (ans) return ans;

for (int i = 1; i * i <= k; ++i) {

if (k % i) continue;

if (i != 1)

ans = (ans + dfs(s - 1, k / i)) % kMod;

if (i * i != k)

ans = (ans + dfs(s - 1, i)) % kMod;

}

return ans;

};

vector<int> ans;

for (const auto& q : queries) {

dp.clear();

n = q[0];

ans.push_back(dfs(n, q[1]));

}

return ans;

}

};

花花酱 LeetCode 1734. Decode XORed Permutation

By zxi on January 23, 2021

There is an integer array perm that is a permutation of the first n positive integers, where n is always odd.

It was encoded into another integer array encoded of length n - 1, such that encoded[i] = perm[i] XOR perm[i + 1]. For example, if perm = [1,3,2], then encoded = [2,1].

Given the encoded array, return the original array perm. It is guaranteed that the answer exists and is unique.

Example 1:

Input: encoded = [3,1]
Output: [1,2,3]
Explanation: If perm = [1,2,3], then encoded = [1 XOR 2,2 XOR 3] = [3,1]

Example 2:

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

Constraints:

3 <= n < 10⁵
n is odd.
encoded.length == n - 1

Solution: XOR

The key is to find p[0]. p[i] = p[i – 1] ^ encoded[i – 1]

p[0] ^ p[1] ^ … ^ p[n-1] = 1 ^ 2 ^ … ^ n
encoded[1] ^ encode[3] ^ … ^ encoded[n-2] = (p[1] ^ p[2]) ^ (p[3] ^ p[4]) ^ … ^ (p[n-2] ^ p[n-1])

1) xor 2) = p[0]

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

C++

// Author: Huahua

class Solution {

public:

vector<int> decode(vector<int>& encoded) {

const int n = encoded.size() + 1;

vector<int> perm(n);

// p[0] = (p[0]^p[1]^...^p[n-1] = 1^2^...^n)

// ^ (p[1]^p[2]^...^p[n-1])

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

perm[0] ^= i;

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

perm[0] ^= encoded[i];

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

perm[i] = perm[i - 1] ^ encoded[i - 1];

return perm;

}

};

花花酱 LeetCode 1733. Minimum Number of People to Teach

By zxi on January 23, 2021

On a social network consisting of m users and some friendships between users, two users can communicate with each other if they know a common language.

You are given an integer n, an array languages, and an array friendships where:

There are n languages numbered 1 through n,
languages[i] is the set of languages the i^th user knows, and
friendships[i] = [u_i, v_i] denotes a friendship between the users u_i and v_i.

You can choose one language and teach it to some users so that all friends can communicate with each other. Return the minimum number of users you need to teach.Note that friendships are not transitive, meaning if x is a friend of y and y is a friend of z, this doesn’t guarantee that x is a friend of z.

Example 1:

Input: n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]
Output: 1
Explanation: You can either teach user 1 the second language or user 2 the first language.

Example 2:

Input: n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
Output: 2
Explanation: Teach the third language to users 1 and 2, yielding two users to teach.

Constraints:

2 <= n <= 500
languages.length == m
1 <= m <= 500
1 <= languages[i].length <= n
1 <= languages[i][j] <= n
1 <= u_i < v_i <= languages.length
1 <= friendships.length <= 500
All tuples (u_i,v_i) are unique
languages[i] contains only unique values

Solution: Brute Force

Enumerate all languages and see which one is the best.

If two friends speak a common language, we can skip counting them.

Time complexity: O(m*(n+|friendship|))
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {

const int m = languages.size();

vector<unordered_set<int>> langs;

for (auto& l : languages) {

sort(begin(l), end(l));

langs.emplace_back(begin(l), end(l));

}

for (auto& e : friendships) {

const auto& l0 = languages[--e[0]];

const auto& l1 = languages[--e[1]];

vector<int> common;

set_intersection(begin(l0), end(l0), begin(l1), end(l1), back_inserter(common));

if (common.size()) e[0] = e[1] = -1;

}

int ans = INT_MAX;

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

vector<int> users(m);

for (const auto& e : friendships) {

// e[0] and e[1] have a common language, skip this edge

if (e[0] == -1) continue;

if (!langs[e[0]].count(i)) users[e[0]] = 1;

if (!langs[e[1]].count(i)) users[e[1]] = 1;

}

ans = min(ans, accumulate(begin(users), end(users), 0));

}

return ans;

}

};

花花酱 LeetCode1732. Find the Highest Altitude

By zxi on January 23, 2021

There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.

You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < n). Return the highest altitude of a point.

Example 1:

Input: gain = [-5,1,5,0,-7]
Output: 1
Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.

Example 2:

Input: gain = [-4,-3,-2,-1,4,3,2]
Output: 0
Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.

Constraints:

n == gain.length
1 <= n <= 100
-100 <= gain[i] <= 100

Solution: Running Max

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

C++

// Author: Huahua

class Solution {

public:

int largestAltitude(vector<int>& gain) {

int ans = 0;

int cur = 0;

for (int diff : gain)

ans = max(ans, cur += diff);

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1736. Latest Time by Replacing Hidden Digits

Solution 1: Brute Force

C++

Solution 2: Rules

C++

花花酱 LeetCode 1735. Count Ways to Make Array With Product

Solution1: DP

C++

花花酱 LeetCode 1734. Decode XORed Permutation

Solution: XOR

C++

花花酱 LeetCode 1733. Minimum Number of People to Teach

Solution: Brute Force

C++

花花酱 LeetCode1732. Find the Highest Altitude

Solution: Running Max

C++