当前位置:网站首页>LeetCode 1447. Simplest fraction
LeetCode 1447. Simplest fraction
2022-07-06 16:42:00 【Daylight629】
1447. Simplest fraction
Give you an integer n
, Please return to all 0 To 1 Between ( barring 0 and 1) Satisfy that the denominator is less than or equal to n
Of Simplest fraction . The score can be in the form of arbitrarily Sequential return .
Example 1:
Input :n = 2
Output :["1/2"]
explain :"1/2" Is the only denominator less than or equal to 2 The simplest fraction of .
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"]
explain :"2/4" It's not the simplest fraction , Because it can be reduced to "1/2" .
Example 4:
Input :n = 1
Output :[]
Tips :
1 <= n <= 100
Two 、 Method 1
class Solution {
public List<String> simplifiedFractions(int n) {
List<String> res = new ArrayList<>();
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if(gcb(i, j) == 1) res.add(i + "/" + j);
}
}
return res;
}
// More derogation
public int gcb(int a, int b) {
while(true) {
if (a > b) a -= b;
else if (b > a) b -= a;
else return a;
}
}
}
Complexity analysis
- Time complexity : The complexity of enumerating numerators and denominators is O(n^2); The complexity of judging whether two numbers can be combined into the simplest fraction is O(logn). The overall complexity is O(n2∗logn)
- Spatial complexity : Ignore the extra space overhead caused by recursion , The complexity is O(1)
3、 ... and 、 Method 2
class Solution {
public List<String> simplifiedFractions(int n) {
List<String> res = new ArrayList<>();
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if(gcb(i, j) == 1) res.add(i + "/" + j);
}
}
return res;
}
// Euclid algorithm
public int gcb(int a, int b) {
return b == 0 ? a : gcb(b, a % b);
}
}
Complexity analysis
- Time complexity : The complexity of enumerating numerators and denominators is O(n^2); The complexity of judging whether two numbers can be combined into the simplest fraction is O(logn). The overall complexity is O(n2∗logn)
- Spatial complexity : Ignore the extra space overhead caused by recursion , The complexity is O(1)
边栏推荐
- China double brightening film (dbef) market trend report, technical dynamic innovation and market forecast
- 300th weekly match - leetcode
- Codeforces Round #799 (Div. 4)A~H
- (lightoj - 1369) answering queries (thinking)
- (lightoj - 1349) Aladdin and the optimal invitation (greed)
- Input can only input numbers, limited input
- Codeforces Round #797 (Div. 3)无F
- 顺丰科技智慧物流校园技术挑战赛(无t4)
- Oneforall installation and use
- Pull branch failed, fatal: 'origin/xxx' is not a commit and a branch 'xxx' cannot be created from it
猜你喜欢
Spark独立集群动态上线下线Worker节点
ffmpeg命令行使用
Audio and video development interview questions
Simply try the new amp model of deepfacelab (deepfake)
QT implementation window gradually disappears qpropertyanimation+ progress bar
Raspberry pie 4B installation opencv3.4.0
antd upload beforeUpload中禁止触发onchange
第5章 NameNode和SecondaryNameNode
Chapter 5 namenode and secondarynamenode
Use JQ to realize the reverse selection of all and no selection at all - Feng Hao's blog
随机推荐
Specify the format time, and fill in zero before the month and days
China tetrabutyl urea (TBU) market trend report, technical dynamic innovation and market forecast
视频压缩编码和音频压缩编码基本原理
Chapter 7__ consumer_ offsets topic
MP4格式详解
Cmake Express
CMake速成
QT simulates mouse events and realizes clicking, double clicking, moving and dragging
Oneforall installation and use
Spark independent cluster dynamic online and offline worker node
Hbuilder X格式化快捷键设置
Chapter 6 datanode
Basic principles of video compression coding and audio compression coding
Audio and video development interview questions
Market trend report, technological innovation and market forecast of double door and multi door refrigerators in China
(lightoj - 1369) answering queries (thinking)
Educational Codeforces Round 122 (Rated for Div. 2)
Educational Codeforces Round 130 (Rated for Div. 2)A~C
Advancedinstaller installation package custom action open file
Sublime text code formatting operation