leetcode第一题怎么做(LeetCode力扣官方题解)

leetcode第一题怎么做(LeetCode力扣官方题解)(1)

题目描述

给你一个整数 n,请你返回所有 0 到 1 之间(不包括 0 和 1)满足分母小于等于 n 的 最简 分数。分数可以以 任意 顺序返回。

示例 1:

输入:n = 2 输出:["1/2"] 解释:"1/2" 是唯一一个分母小于等于 2 的最简分数。

示例 2:

输入:n = 3 输出:["1/2","1/3","2/3"]

示例 3:

输入:n = 4 输出:["1/2","1/3","1/4","2/3","3/4"] 解释:"2/4" 不是最简分数,因为它可以化简为 "1/2" 。

示例 4:

输入:n = 1 输出:[]

提示:

  • 1 <= n <= 100
解决方案方法一:数学思路

由于要保证分数在(0,1)范围内,我们可以枚举分母 denominator ∈ [2,n] 和分子 numerator ∈ [1,denominator],若分子分母的最大公约数为 1,则我们找到了一个最简分数。

代码

Python3

class Solution: def simplifiedFractions(self, n: int) -> List[str]: return [f"{numerator}/{denominator}" for denominator in range(2, n 1) for numerator in range(1, denominator) if gcd(denominator, numerator) == 1]

C

class Solution { public: vector<string> simplifiedFractions(int n) { vector<string> ans; for (int denominator = 2; denominator <= n; denominator) { for (int numerator = 1; numerator < denominator; numerator) { if (__gcd(numerator, denominator) == 1) { ans.emplace_back(to_string(numerator) "/" to_string(denominator)); } } } return ans; } };

Java

class Solution { public List<String> simplifiedFractions(int n) { List<String> ans = new ArrayList<String>(); for (int denominator = 2; denominator <= n; denominator) { for (int numerator = 1; numerator < denominator; numerator) { if (gcd(numerator, denominator) == 1) { ans.add(numerator "/" denominator); } } } return ans; } public int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; } }

C#

public class Solution { public IList<string> SimplifiedFractions(int n) { IList<string> ans = new List<string>(); for (int denominator = 2; denominator <= n; denominator) { for (int numerator = 1; numerator < denominator; numerator) { if (GCD(numerator, denominator) == 1) { ans.Add(numerator "/" denominator); } } } return ans; } public int GCD(int a, int b) { return b != 0 ? GCD(b, a % b) : a; } }

Golang

func simplifiedFractions(n int) (ans []string) { for denominator := 2; denominator <= n; denominator { for numerator := 1; numerator < denominator; numerator { if gcd(numerator, denominator) == 1 { ans = append(ans, strconv.Itoa(numerator) "/" strconv.Itoa(denominator)) } } } return } func gcd(a, b int) int { for a != 0 { a, b = b%a, a } return b }

C

#define MAX_FRACTION_LEN 10 int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } char ** simplifiedFractions(int n, int* returnSize) { char ** ans = (char **)malloc(sizeof(char *) * n * (n - 1) / 2 ); int pos = 0; for (int denominator = 2; denominator <= n; denominator ) { for (int numerator = 1; numerator < denominator; numerator ) { if (gcd(numerator, denominator) == 1) { ans[pos] = (char *)malloc(sizeof(char) * MAX_FRACTION_LEN); snprintf(ans[pos ], MAX_FRACTION_LEN, "%d%c%d", numerator, '/', denominator); } } } *returnSize = pos; return ans; }

JavaScript

var simplifiedFractions = function(n) { const ans = []; for (let denominator = 2; denominator <= n; denominator) { for (let numerator = 1; numerator < denominator; numerator) { if (gcd(numerator, denominator) == 1) { ans.push(numerator "/" denominator); } } } return ans; }; const gcd = (a, b) => { if (b === 0) { return a; } return gcd(b, a % b); }

复杂度分析

  • 时间复杂度: O(n2logn)。需要枚举 O(n2) 对分子分母的组合,每对分子分母计算最大公因数和生成字符串的复杂度均为 O(logn)。
  • 空间复杂度:O(1) 。除答案数组外,我们只需要常数个变量。

BY /

本文作者:力扣

声明:本文归“力扣”版权所有,如需转载请联系。

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页