Huahua’s Tech Road

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

}

};

花花酱 LeetCode 2074. Reverse Nodes in Even Length Groups

By zxi on November 15, 2021

You are given the head of a linked list.

The nodes in the linked list are sequentially assigned to non-empty groups whose lengths form the sequence of the natural numbers (1, 2, 3, 4, ...). The length of a group is the number of nodes assigned to it. In other words,

The 1^st node is assigned to the first group.
The 2^nd and the 3^rd nodes are assigned to the second group.
The 4^th, 5^th, and 6^th nodes are assigned to the third group, and so on.

Note that the length of the last group may be less than or equal to 1 + the length of the second to last group.

Reverse the nodes in each group with an even length, and return the head of the modified linked list.

Example 1:

Input: head = [5,2,6,3,9,1,7,3,8,4]
Output: [5,6,2,3,9,1,4,8,3,7]
Explanation:
- The length of the first group is 1, which is odd, hence no reversal occurrs.
- The length of the second group is 2, which is even, hence the nodes are reversed.
- The length of the third group is 3, which is odd, hence no reversal occurrs.
- The length of the last group is 4, which is even, hence the nodes are reversed.

Example 2:

Input: head = [1,1,0,6]
Output: [1,0,1,6]
Explanation:
- The length of the first group is 1. No reversal occurrs.
- The length of the second group is 2. The nodes are reversed.
- The length of the last group is 1. No reversal occurrs.

Example 3:

Input: head = [2,1]
Output: [2,1]
Explanation:
- The length of the first group is 1. No reversal occurrs.
- The length of the last group is 1. No reversal occurrs.

Example 4:

Input: head = [8]
Output: [8]
Explanation: There is only one group whose length is 1. No reversal occurrs.

Constraints:

The number of nodes in the list is in the range [1, 10⁵].
0 <= Node.val <= 10⁵

Solution: List

Reuse ReverseList from 花花酱 LeetCode 206. Reverse Linked List

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

C++

class Solution {

public:

ListNode* reverseEvenLengthGroups(ListNode* head) {

ListNode dummy(0, head);

ListNode* prev = &dummy;

auto reverse = [](ListNode* head) {

ListNode* prev = nullptr;

while (head) {

ListNode* next = head->next;

head->next = prev;

prev = head;

head = next;

}

return prev;

};

for (int k = 1; head; ++k) {

ListNode* tail = head;

int l = 1;

while (l < k && tail && tail->next) {

tail = tail->next;

++l;

}

ListNode* next = tail->next;

if (l % 2 == 0) {

tail->next = nullptr;

prev->next = reverse(head);

head->next = next;

prev = head;

head = head->next;

} else {

prev = tail;

head = next;

}

return dummy.next;

}

};

Huahua's Tech Road

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

花花酱 LeetCode 2074. Reverse Nodes in Even Length Groups

Solution: List

C++