LeetCode 1447. Simplest fraction

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)