Huahua’s Tech Road

花花酱 LeetCode 2001. Number of Pairs of Interchangeable Rectangles

By zxi on November 20, 2021

You are given n rectangles represented by a 0-indexed 2D integer array rectangles, where rectangles[i] = [width_i, height_i] denotes the width and height of the i^th rectangle.

Two rectangles i and j (i < j) are considered interchangeable if they have the same width-to-height ratio. More formally, two rectangles are interchangeable if width_i/height_i == width_j/height_j (using decimal division, not integer division).

Return the number of pairs of interchangeable rectangles in rectangles.

Example 1:

Input: rectangles = [[4,8],[3,6],[10,20],[15,30]]
Output: 6
Explanation: The following are the interchangeable pairs of rectangles by index (0-indexed):
- Rectangle 0 with rectangle 1: 4/8 == 3/6.
- Rectangle 0 with rectangle 2: 4/8 == 10/20.
- Rectangle 0 with rectangle 3: 4/8 == 15/30.
- Rectangle 1 with rectangle 2: 3/6 == 10/20.
- Rectangle 1 with rectangle 3: 3/6 == 15/30.
- Rectangle 2 with rectangle 3: 10/20 == 15/30.

Example 2:

Input: rectangles = [[4,5],[7,8]]
Output: 0
Explanation: There are no interchangeable pairs of rectangles.

Constraints:

n == rectangles.length
1 <= n <= 10⁵
rectangles[i].length == 2
1 <= width_i, height_i <= 10⁵

Solution: Hashtable

Use aspect ratio as the key.

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

C++

// Author: Huahua

class Solution {

public:

long long interchangeableRectangles(vector<vector<int>>& rectangles) {

long long ans = 0;

unordered_map<long long, int> m;

for (const auto& r : rectangles) {

long long d = gcd(r[0], r[1]);

ans += m[((r[0] / d) << 20) | (r[1] / d)]++;

}

return ans;

}

};

花花酱 LeetCode 2000. Reverse Prefix of Word

By zxi on November 20, 2021

Given a 0-indexed string word and a character ch, reverse the segment of word that starts at index 0 and ends at the index of the first occurrence of ch (inclusive). If the character ch does not exist in word, do nothing.

For example, if word = "abcdefd" and ch = "d", then you should reverse the segment that starts at 0 and ends at 3 (inclusive). The resulting string will be "dcbaefd".

Return the resulting string.

Example 1:

Input: word = "abcdefd", ch = "d"
Output: "dcbaefd"
Explanation: The first occurrence of "d" is at index 3. 
Reverse the part of word from 0 to 3 (inclusive), the resulting string is "dcbaefd".

Example 2:

Input: word = "xyxzxe", ch = "z"
Output: "zxyxxe"
Explanation: The first and only occurrence of "z" is at index 3.
Reverse the part of word from 0 to 3 (inclusive), the resulting string is "zxyxxe".

Example 3:

Input: word = "abcd", ch = "z"
Output: "abcd"
Explanation: "z" does not exist in word.
You should not do any reverse operation, the resulting string is "abcd".

Constraints:

1 <= word.length <= 250
word consists of lowercase English letters.
ch is a lowercase English letter.

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

string reversePrefix(string word, char ch) {

for (size_t i = 0; i < word.size(); ++i)

if (word[i] == ch) return

string(rbegin(word) + word.size() - i - 1, rend(word)) + word.substr(i + 1);

return word;

}

};

花花酱 LeetCode 2050. Parallel Courses III

By zxi on November 18, 2021

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given a 2D integer array relations where relations[j] = [prevCourse_j, nextCourse_j] denotes that course prevCourse_j has to be completed before course nextCourse_j (prerequisite relationship). Furthermore, you are given a 0-indexed integer array time where time[i] denotes how many months it takes to complete the (i+1)^th course.

You must find the minimum number of months needed to complete all the courses following these rules:

You may start taking a course at any time if the prerequisites are met.
Any number of courses can be taken at the same time.

Return the minimum number of months needed to complete all the courses.

Note: The test cases are generated such that it is possible to complete every course (i.e., the graph is a directed acyclic graph).

Example 1:

Input: n = 3, relations = [[1,3],[2,3]], time = [3,2,5]
Output: 8
Explanation: The figure above represents the given graph and the time required to complete each course. 
We start course 1 and course 2 simultaneously at month 0.
Course 1 takes 3 months and course 2 takes 2 months to complete respectively.
Thus, the earliest time we can start course 3 is at month 3, and the total time required is 3 + 5 = 8 months.

Example 2:

Input: n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]
Output: 12
Explanation: The figure above represents the given graph and the time required to complete each course.
You can start courses 1, 2, and 3 at month 0.
You can complete them after 1, 2, and 3 months respectively.
Course 4 can be taken only after course 3 is completed, i.e., after 3 months. It is completed after 3 + 4 = 7 months.
Course 5 can be taken only after courses 1, 2, 3, and 4 have been completed, i.e., after max(1,2,3,7) = 7 months.
Thus, the minimum time needed to complete all the courses is 7 + 5 = 12 months.

Constraints:

1 <= n <= 5 * 10⁴
0 <= relations.length <= min(n * (n - 1) / 2, 5 * 10⁴)
relations[j].length == 2
1 <= prevCourse_j, nextCourse_j <= n
prevCourse_j != nextCourse_j
All the pairs [prevCourse_j, nextCourse_j] are unique.
time.length == n
1 <= time[i] <= 10⁴
The given graph is a directed acyclic graph.

Solution: Topological Sorting

Time complexity: O(V+E)
Space complexity: O(V+E)

C++

// Author: Huahua

class Solution {

public:

int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {

vector<vector<int>> g(n);

for (const auto& r: relations)

g[r[0] - 1].push_back(r[1] - 1);

vector<int> t(n, -1);

function<int(int)> dfs = [&](int u) {

if (t[u] != -1) return t[u];

t[u] = 0;

for (int v : g[u])

t[u] = max(t[u], dfs(v));

return t[u] += time[u];

};

int ans = 0;

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

ans = max(ans, dfs(i));

return ans;

}

};

Python3

class Solution:

def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:

g = [[] for _ in range(n)]

for u, v in relations: g[u - 1].append(v - 1)

@cache

def dfs(u: int) -> int:

return max([dfs(v) for v in g[u]] + [0]) + time[u]

return max(dfs(u) for u in range(n))

花花酱 LeetCode 2076. Process Restricted Friend Requests

By zxi on November 15, 2021

You are given an integer n indicating the number of people in a network. Each person is labeled from 0 to n - 1.

You are also given a 0-indexed 2D integer array restrictions, where restrictions[i] = [x_i, y_i] means that person x_i and person y_i cannot become friends,either directly or indirectly through other people.

Initially, no one is friends with each other. You are given a list of friend requests as a 0-indexed 2D integer array requests, where requests[j] = [u_j, v_j] is a friend request between person u_j and person v_j.

A friend request is successful if u_j and v_j can be friends. Each friend request is processed in the given order (i.e., requests[j] occurs before requests[j + 1]), and upon a successful request, u_j and v_j become direct friends for all future friend requests.

Return a boolean array result, where each result[j] is true if the j^th friend request is successful or false if it is not.

Note: If u_j and v_j are already direct friends, the request is still successful.

Example 1:

Input: n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]]
Output: [true,false]
Explanation:
Request 0: Person 0 and person 2 can be friends, so they become direct friends. 
Request 1: Person 2 and person 1 cannot be friends since person 0 and person 1 would be indirect friends (1--2--0).

Example 2:

Input: n = 3, restrictions = [[0,1]], requests = [[1,2],[0,2]]
Output: [true,false]
Explanation:
Request 0: Person 1 and person 2 can be friends, so they become direct friends.
Request 1: Person 0 and person 2 cannot be friends since person 0 and person 1 would be indirect friends (0--2--1).

Example 3:

Input: n = 5, restrictions = [[0,1],[1,2],[2,3]], requests = [[0,4],[1,2],[3,1],[3,4]]
Output: [true,false,true,false]
Explanation:
Request 0: Person 0 and person 4 can be friends, so they become direct friends.
Request 1: Person 1 and person 2 cannot be friends since they are directly restricted.
Request 2: Person 3 and person 1 can be friends, so they become direct friends.
Request 3: Person 3 and person 4 cannot be friends since person 0 and person 1 would be indirect friends (0--4--3--1).

Constraints:

2 <= n <= 1000
0 <= restrictions.length <= 1000
restrictions[i].length == 2
0 <= x_i, y_i <= n - 1
x_i != y_i
1 <= requests.length <= 1000
requests[j].length == 2
0 <= u_j, v_j <= n - 1
u_j != v_j

Solution: Union Find / Brute Force

For each request, check all restrictions.

Time complexity: O(req * res)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {

vector<int> parents(n);

iota(begin(parents), end(parents), 0);

function<int(int)> find = [&](int x) {

if (parents[x] == x) return x;

return parents[x] = find(parents[x]);

};

auto check = [&](int u, int v) {

for (const auto& r : restrictions) {

int pu = find(r[0]);

int pv = find(r[1]);

if ((pu == u && pv == v) || (pu == v && pv == u))

return false;

}

return true;

};

vector<bool> ans;

for (const auto& r : requests) {

int pu = find(r[0]);

int pv = find(r[1]);

if (pu == pv || check(pu, pv)) {

parents[pu] = pv;

ans.push_back(true);

} else {

ans.push_back(false);

}

return ans;

}

};

花花酱 LeetCode 2075. Decode the Slanted Ciphertext

By zxi on November 15, 2021

A string originalText is encoded using a slanted transposition cipher to a string encodedText with the help of a matrix having a fixed number of rows rows.

originalText is placed first in a top-left to bottom-right manner.

The blue cells are filled first, followed by the red cells, then the yellow cells, and so on, until we reach the end of originalText. The arrow indicates the order in which the cells are filled. All empty cells are filled with ' '. The number of columns is chosen such that the rightmost column will not be empty after filling in originalText.

encodedText is then formed by appending all characters of the matrix in a row-wise fashion.

The characters in the blue cells are appended first to encodedText, then the red cells, and so on, and finally the yellow cells. The arrow indicates the order in which the cells are accessed.

For example, if originalText = "cipher" and rows = 3, then we encode it in the following manner:

The blue arrows depict how originalText is placed in the matrix, and the red arrows denote the order in which encodedText is formed. In the above example, encodedText = "ch ie pr".

Given the encoded string encodedText and number of rows rows, return the original string originalText.

Note: originalText does not have any trailing spaces ' '. The test cases are generated such that there is only one possible originalText.

Example 1:

Input: encodedText = "ch   ie   pr", rows = 3
Output: "cipher"
Explanation: This is the same example described in the problem description.

Example 2:

Input: encodedText = "iveo    eed   l te   olc", rows = 4
Output: "i love leetcode"
Explanation: The figure above denotes the matrix that was used to encode originalText. 
The blue arrows show how we can find originalText from encodedText.

Example 3:

Input: encodedText = "coding", rows = 1
Output: "coding"
Explanation: Since there is only 1 row, both originalText and encodedText are the same.

Example 4:

Input: encodedText = " b  ac", rows = 2
Output: " abc"
Explanation: originalText cannot have trailing spaces, but it may be preceded by one or more spaces.

Constraints:

0 <= encodedText.length <= 10⁶
encodedText consists of lowercase English letters and ' ' only.
encodedText is a valid encoding of some originalText that does not have trailing spaces.
1 <= rows <= 1000
The testcases are generated such that there is only one possible originalText.

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

string decodeCiphertext(string encodedText, int rows) {

const int cols = encodedText.size() / rows;

string ans;

ans.reserve(encodedText.size());

for (int i = 0; i < cols; ++i)

for (int j = 0; j < rows && i + j < cols; ++j)

ans += encodedText[j * cols + j + i];

while (ans.size() && !isalpha(ans.back())) ans.pop_back();

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2001. Number of Pairs of Interchangeable Rectangles

Solution: Hashtable

C++

花花酱 LeetCode 2000. Reverse Prefix of Word

Solution: Brute Force

C++

花花酱 LeetCode 2050. Parallel Courses III

Solution: Topological Sorting

C++

Python3

花花酱 LeetCode 2076. Process Restricted Friend Requests

C++

花花酱 LeetCode 2075. Decode the Slanted Ciphertext

Solution: Simulation

C++