Given an integer n, return a list of all simplified fractions between 0 and 1 (exclusive) such that the denominator is less-than-or-equal-to n. The fractions can be in any order.
Example 1:
Input: n = 2
Output: ["1/2"]
Explanation: "1/2" is the only unique fraction with a denominator less-than-or-equal-to 2.
Example 2:
Input: n = 3
Output: ["1/2","1/3","2/3"]
Example 3:
Input: n = 4
Output: ["1/2","1/3","1/4","2/3","3/4"]
Explanation: "2/4" is not a simplified fraction because it can be simplified to "1/2".
Example 4:
Input: n = 1
Output: []
Constraints:
1 <= n <= 100
Solution: GCD
if gcd(a, b) == 1 then a/b is a simplified frication.
std::gcd is available since c++17.
Time complexity: O(n^2logn) Space complexity: O(1)
Given a sentence text (A sentence is a string of space-separated words) in the following format:
First letter is in upper case.
Each word in text are separated by a single space.
Your task is to rearrange the words in text such that all words are rearranged in an increasing order of their lengths. If two words have the same length, arrange them in their original order.
Return the new text following the format shown above.
Example 1:
Input: text = "Leetcode is cool"
Output: "Is cool leetcode"
Explanation: There are 3 words, "Leetcode" of length 8, "is" of length 2 and "cool" of length 4.
Output is ordered by length and the new first word starts with capital letter.
Example 2:
Input: text = "Keep calm and code on"
Output: "On and keep calm code"
Explanation: Output is ordered as follows:
"On" 2 letters.
"and" 3 letters.
"keep" 4 letters in case of tie order by position in original text.
"calm" 4 letters.
"code" 4 letters.
Example 3:
Input: text = "To be or not to be"
Output: "To be or to be not"
Constraints:
text begins with a capital letter and then contains lowercase letters and single space between words.
Given an array of integers nums and an integer limit, return the size of the longest continuous subarray such that the absolute difference between any two elements is less than or equal to limit.
In case there is no subarray satisfying the given condition return 0.
Example 1:
Input: nums = [8,2,4,7], limit = 4
Output: 2
Explanation: All subarrays are:
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4.
Therefore, the size of the longest subarray is 2.
Example 2:
Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.
Use a treeset to maintain a range of [l, r] such that max(nums[l~r]) – min(nums[l~r]) <= limit. Every time, we add nums[r] into the tree, and move l towards r to keep the max diff under limit.
Time complexity: O(nlogn) Space complexity: O(n)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Author: Huahua
classSolution{
public:
intlongestSubarray(vector<int>& nums, int limit) {
We want to maintain a range [l, r] that max(nums[l~r]) – min(nums[l~r]) <= limit, to track the max/min of a range efficiently we could use monotonic queue. One for max and one for min.
Time complexity: O(n) Space complexity: O(n)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Author: Huahua
classSolution{
public:
intlongestSubarray(vector<int>& nums, int limit) {