Huahua’s Tech Road

花花酱 LeetCode 151. Reverse Words in a String

By zxi on November 28, 2021

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Example 4:

Input: s = "  Bob    Loves  Alice   "
Output: "Alice Loves Bob"

Example 5:

Input: s = "Alice does not even like bob"
Output: "bob like even not does Alice"

Constraints:

1 <= s.length <= 10⁴
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Solution: Stack

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

C++

// Author: Huahua

class Solution {

public:

string reverseWords(string s) {

stringstream ss(s);

stack<string> st;

string w;

while (ss >> w)

st.push(w);

string ans;

while (!st.empty()) {

ans += st.top();

st.pop();

if (!st.empty()) ans += ' ';

}

return ans;

}

};

Solution: In-Place

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

C++

// Author: Huahua

class Solution {

public:

string reverseWords(string& s) {

reverse(begin(s), end(s));

int l = 0;

for (int i = 0, j = 0; i < s.length(); ++i) {

if (s[i] == ' ') continue;

if (l) ++l;

j = i;

while (j < s.length() && s[j] != ' ') ++j;

reverse(begin(s) + l, begin(s) + j);

l += (j - i);

i = j;

}

s.resize(l);

return s;

}

};

花花酱 LeetCode 142. Linked List Cycle II

By zxi on November 28, 2021

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Constraints:

The number of the nodes in the list is in the range [0, 10⁴].
-10⁵ <= Node.val <= 10⁵
pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Solution 1: Hashtset

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

C++

// Author: Huahua

class Solution {

public:

ListNode *detectCycle(ListNode *head) {

unordered_set<ListNode*> s;

for (ListNode* cur = head; cur; cur = cur->next)

if (!s.insert(cur).second) return cur;

return nullptr;

}

};

Solution: Fast slow pointers

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

C++

// Author: Huahua

class Solution {

public:

ListNode *detectCycle(ListNode *head) {

unordered_set<ListNode*> s;

for (ListNode* cur = head; cur; cur = cur->next)

if (!s.insert(cur).second) return cur;

return nullptr;

}

};

花花酱 LeetCode 2092. Find All People With Secret

By zxi on November 28, 2021

You are given an integer n indicating there are n people numbered from 0 to n - 1. You are also given a 0-indexed 2D integer array meetings where meetings[i] = [x_i, y_i, time_i] indicates that person x_i and person y_i have a meeting at time_i. A person may attend multiple meetings at the same time. Finally, you are given an integer firstPerson.

Person 0 has a secret and initially shares the secret with a person firstPerson at time 0. This secret is then shared every time a meeting takes place with a person that has the secret. More formally, for every meeting, if a person x_i has the secret at time_i, then they will share the secret with person y_i, and vice versa.

The secrets are shared instantaneously. That is, a person may receive the secret and share it with people in other meetings within the same time frame.

Return a list of all the people that have the secret after all the meetings have taken place. You may return the answer in any order.

Example 1:

Input: n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
Output: [0,1,2,3,5]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 5, person 1 shares the secret with person 2.
At time 8, person 2 shares the secret with person 3.
At time 10, person 1 shares the secret with person 5.
Thus, people 0, 1, 2, 3, and 5 know the secret after all the meetings.

Example 2:

Input: n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
Output: [0,1,3]
Explanation:
At time 0, person 0 shares the secret with person 3.
At time 2, neither person 1 nor person 2 know the secret.
At time 3, person 3 shares the secret with person 0 and person 1.
Thus, people 0, 1, and 3 know the secret after all the meetings.

Example 3:

Input: n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
Output: [0,1,2,3,4]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 1, person 1 shares the secret with person 2, and person 2 shares the secret with person 3.
Note that person 2 can share the secret at the same time as receiving it.
At time 2, person 3 shares the secret with person 4.
Thus, people 0, 1, 2, 3, and 4 know the secret after all the meetings.

Example 4:

Input: n = 6, meetings = [[0,2,1],[1,3,1],[4,5,1]], firstPerson = 1
Output: [0,1,2,3]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 1, person 0 shares the secret with person 2, and person 1 shares the secret with person 3.
Thus, people 0, 1, 2, and 3 know the secret after all the meetings.

Constraints:

2 <= n <= 10⁵
1 <= meetings.length <= 10⁵
meetings[i].length == 3
0 <= x_i, y_i<= n - 1
x_i != y_i
1 <= time_i <= 10⁵
1 <= firstPerson <= n - 1

Solution: Union Find

Sorting meetings by time.

At each time stamp, union people who meet.
Key step: “un-union” people if they DO NOT connected to 0 / known the secret after each timestamp.

Time complexity: O(nlogn + m + n)
Space complexity: O(m + n)

C++

// Author: Huahua

class Solution {

public:

vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {

map<int, vector<pair<int, int>>> events;

for (const auto& m : meetings)

events[m[2]].emplace_back(m[0], m[1]);

vector<int> p(n);

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

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

return p[x] == x ? x : (p[x] = find(p[x]));

};

p[firstPerson] = 0;

for (const auto& [t, s] : events) {

for (const auto [u, v] : s)

p[find(u)] = find(v);

for (const auto [u, v] : s) {

if (find(u) != find(0)) p[u] = u;

if (find(v) != find(0)) p[v] = v;

}

vector<int> ans;

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

if (find(i) == find(0)) ans.push_back(i);

return ans;

}

};

花花酱 LeetCode 2091. Removing Minimum and Maximum From Array

By zxi on November 28, 2021

You are given a 0-indexed array of distinct integers nums.

There is an element in nums that has the lowest value and an element that has the highest value. We call them the minimum and maximum respectively. Your goal is to remove both these elements from the array.

A deletion is defined as either removing an element from the front of the array or removing an element from the back of the array.

Return the minimum number of deletions it would take to remove both the minimum and maximum element from the array.

Example 1:

Input: nums = [2,10,7,5,4,1,8,6]
Output: 5
Explanation: 
The minimum element in the array is nums[5], which is 1.
The maximum element in the array is nums[1], which is 10.
We can remove both the minimum and maximum by removing 2 elements from the front and 3 elements from the back.
This results in 2 + 3 = 5 deletions, which is the minimum number possible.

Example 2:

Input: nums = [0,-4,19,1,8,-2,-3,5]
Output: 3
Explanation: 
The minimum element in the array is nums[1], which is -4.
The maximum element in the array is nums[2], which is 19.
We can remove both the minimum and maximum by removing 3 elements from the front.
This results in only 3 deletions, which is the minimum number possible.

Example 3:

Input: nums = [101]
Output: 1
Explanation:  
There is only one element in the array, which makes it both the minimum and maximum element.
We can remove it with 1 deletion.

Constraints:

1 <= nums.length <= 10⁵
-10⁵ <= nums[i] <= 10⁵
The integers in nums are distinct.

Solution: Three ways

There are only three ways to remove min/max elements.
1) Remove front elements
2) Remove back elements
3) Remove one with front elements, and another one with back elements.

Just find the best way to do it.

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

C++

// Author: Huahua

class Solution {

public:

int minimumDeletions(vector<int>& nums) {

const int n = nums.size();

auto [it1, it2] = minmax_element(begin(nums), end(nums));

int i = it1 - begin(nums);

int j = it2 - begin(nums);

return min({max(i, j) + 1, // remove front elements

n - min(i, j), // remove back elements

min(i, j) + 1 + n - max(i, j)} // front + back

);

}

};

花花酱 LeetCode 2090. K Radius Subarray Averages

By zxi on November 28, 2021

You are given a 0-indexed array nums of n integers, and an integer k.

The k-radius average for a subarray of nums centered at some index i with the radius k is the average of all elements in nums between the indices i - k and i + k (inclusive). If there are less than k elements before or after the index i, then the k-radius average is -1.

Build and return an array avgs of length n where avgs[i] is the k-radius average for the subarray centered at index i.

The average of x elements is the sum of the x elements divided by x, using integer division. The integer division truncates toward zero, which means losing its fractional part.

For example, the average of four elements 2, 3, 1, and 5 is (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75, which truncates to 2.

Example 1:

Input: nums = [7,4,3,9,1,8,5,2,6], k = 3
Output: [-1,-1,-1,5,4,4,-1,-1,-1]
Explanation:
- avg[0], avg[1], and avg[2] are -1 because there are less than k elements before each index.
- The sum of the subarray centered at index 3 with radius 3 is: 7 + 4 + 3 + 9 + 1 + 8 + 5 = 37.
  Using integer division, avg[3] = 37 / 7 = 5.
- For the subarray centered at index 4, avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4.
- For the subarray centered at index 5, avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4.
- avg[6], avg[7], and avg[8] are -1 because there are less than k elements after each index.

Example 2:

Input: nums = [100000], k = 0
Output: [100000]
Explanation:
- The sum of the subarray centered at index 0 with radius 0 is: 100000.
  avg[0] = 100000 / 1 = 100000.

Example 3:

Input: nums = [8], k = 100000
Output: [-1]
Explanation: 
- avg[0] is -1 because there are less than k elements before and after index 0.

Constraints:

n == nums.length
1 <= n <= 10⁵
0 <= nums[i], k <= 10⁵

Solution: Sliding Window

We compute i – k’s average at position i.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> getAverages(vector<int>& nums, int k) {

const int n = nums.size();

long long sum = 0;

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

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

sum += nums[i];

if (i >= 2 * k) {

ans[i - k] = sum / (2 * k + 1);

sum -= nums[i - 2 * k];

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 151. Reverse Words in a String

Solution: Stack

C++

Solution: In-Place

C++

花花酱 LeetCode 142. Linked List Cycle II

Solution 1: Hashtset

C++

Solution: Fast slow pointers

C++

花花酱 LeetCode 2092. Find All People With Secret

Solution: Union Find

C++

Related Problems

花花酱 LeetCode 2091. Removing Minimum and Maximum From Array

Solution: Three ways

C++

花花酱 LeetCode 2090. K Radius Subarray Averages

Solution: Sliding Window

C++