class Solution {<br /> int gcd(int a, int b) { // 欧几里得算法<br /> return b == 0 ? a : gcd(b, a % b);<br /> }<br /> public List<String> simplifiedFractions(int n) {<br /> List<String> ans = new ArrayList<>();<br /> for (int i = 1; i < n; i++) {<br /> for (int j = i + 1; j <= n; j++) {<br /> if (gcd(i, j) == 1) ans.add(i + "/" + j);<br /> }<br /> }<br /> return ans;<br /> }<br />}<br />
复制代码
C++ 代码(欧几里得算法):
class Solution {<br />public:<br /> int gcd(int a, int b) { // 欧几里得算法<br /> return b == 0 ? a : gcd(b, a % b); <br /> }<br /> vector<string> simplifiedFractions(int n) {<br /> vector<string> ans;<br /> for (int i = 1; i < n; i++) {<br /> for (int j = i + 1; j <= n; j++) {<br /> if (gcd(i, j) == 1) ans.push_back(to_string(i) + "/" + to_string(j));<br /> }<br /> }<br /> return ans;<br /> }<br />};<br />
复制代码
Python 代码(欧几里得算法):
class Solution:<br /> def gcd(self, a: int, b: int) -> int: # 欧几里得算法<br /> return a if b == 0 else self.gcd(b, a % b)<br /><br /> def simplifiedFractions(self, n: int) -> List[str]:<br /> ans = []<br /> for i in range(1, n + 1):<br /> for j in range(i + 1, n + 1):<br /> if self.gcd(i, j) == 1:<br /> ans.append(f"{i}/{j}")<br /> return ans<br />
复制代码
TypeScript 代码(欧几里得算法):
function gcd(a: number, b: number): number { // 欧几里得算法<br /> return b == 0 ? a : gcd(b, a % b);<br />}<br />function simplifiedFractions(n: number): string[] {<br /> const ans = [];<br /> for (let i = 1; i < n; i++) {<br /> for (let j = i + 1; j <= n; j++) {<br /> if (gcd(i, j) === 1) ans.push(`${i}/${j}`);<br /> }<br /> }<br /> return ans;<br />};<br />
复制代码
Java 代码(更相减损法):
class Solution {<br /> int gcd(int a, int b) { // 更相减损法<br /> while (true) {<br /> if (a > b) a -= b;<br /> else if (a < b) b -= a;<br /> else return a;<br /> }<br /> }<br /> public List<String> simplifiedFractions(int n) {<br /> List<String> ans = new ArrayList<>();<br /> for (int i = 1; i < n; i++) {<br /> for (int j = i + 1; j <= n; j++) {<br /> if (gcd(i, j) == 1) ans.add(i + "/" + j);<br /> }<br /> }<br /> return ans;<br /> }<br />}<br />
复制代码
Java 代码(stein):
class Solution {<br /> int gcd(int a, int b) { // stein<br /> if (a == 0 || b == 0) return Math.max(a, b);<br /> if (a % 2 == 0 && b % 2 == 0) return 2 * gcd(a >> 1, b >> 1);<br /> else if (a % 2 == 0) return gcd(a >> 1, b);<br /> else if (b % 2 == 0) return gcd(a, b >> 1);<br /> else return gcd(Math.abs(a - b), Math.min(a, b));<br /> }<br /> public List<String> simplifiedFractions(int n) {<br /> List<String> ans = new ArrayList<>();<br /> for (int i = 1; i < n; i++) {<br /> for (int j = i + 1; j <= n; j++) {<br /> if (gcd(i, j) == 1) ans.add(i + "/" + j);<br /> }<br /> }<br /> return ans;<br /> }<br />}<br />