rustgym/leetcode/
_1447_simplified_fractions.rs1struct Solution;
2use std::collections::HashSet;
3
4impl Solution {
5 fn simplified_fractions(n: i32) -> Vec<String> {
6 let mut hs: HashSet<String> = HashSet::new();
7 for i in 2..=n {
8 for j in 1..i {
9 let k = Self::gcd(i, j);
10 hs.insert(format!("{}/{}", j / k, i / k));
11 }
12 }
13 hs.into_iter().collect()
14 }
15
16 fn gcd(mut a: i32, mut b: i32) -> i32 {
17 while a != 0 {
18 let t = a;
19 a = b % t;
20 b = t;
21 }
22 b
23 }
24}
25
26#[test]
27fn test() {
28 let n = 2;
29 let res = vec_string!["1/2"];
30 assert_eq!(Solution::simplified_fractions(n), res);
31 let n = 3;
32 let mut res = vec_string!["1/2", "1/3", "2/3"];
33 let mut ans = Solution::simplified_fractions(n);
34 res.sort();
35 ans.sort();
36 assert_eq!(ans, res);
37 let n = 4;
38 let mut res = vec_string!["1/2", "1/3", "1/4", "2/3", "3/4"];
39 let mut ans = Solution::simplified_fractions(n);
40 res.sort();
41 ans.sort();
42 assert_eq!(ans, res);
43}