返回目录

1)示例1:
输入:4 输出:[1/2,1/3,2/3,1/4,3/4]
2)示例2:
输入:12 输出:[6/11, 4/11, 2/11, 8/11, 1/2, 1/3, 2/3, 1/4, 1/5, 3/4, 2/5, 1/6, 3/5, 1/7, 10/11, 4/5, 2/7, 1/8, 3/7, 1/9, 5/6, 4/7, 3/8, 2/9, 5/7, 6/7, 5/8, 4/9, 5/9, 7/8, 7/12, 7/9, 7/11, 8/9, 5/11, 5/12, 1/11, 1/12, 1/10, 3/11, 3/10, 9/11, 7/10, 9/10, 11/12]

Python源码

public static void main(String[] args) {
    // 测试方法 solution,参数为 n = 12
    System.out.println(solution(12));
}

/**
 * 查找并返回小于等于 n 且大于 0 的分母的分数,并以哈希集合的形式返回唯一的分数表示。
 * 
 * @param n 需要考虑的最大分母值。
 * @return 一个包含唯一分数表示的 HashSet。
 */
private static HashSet<String> solution(int n) {
    // 用于存储唯一分数表示的 HashSet
    HashSet<String> set = new HashSet<>();
    // 用于存储唯一分数值的 HashSet
    HashSet<Double> doubles = new HashSet<>();
  
    // 遍历所有可能的分母,从 1 到 n
    for (int i = 1; i <= n; i++) {
        // 遍历所有可能的分子,从 1 到当前分母
        for (int j = 1; j <= i; j++) {
            // 将分数计算为一个双精度数值
            double res = (double) j / (double) i;
    
            // 如果双精度数值已经存在于集合中,则跳过该分数
            if (doubles.contains(res)) {
                continue;
            }
    
            // 如果分数在 0 到 1 之间(不包括 1),则将其加入集合
            if (res < 1 && res > 0) {
                set.add(j + "/" + i);
                // 将分数的双精度数值加入到唯一的 doubles 集合中
                doubles.add(res);
            }
        }
    }
    return set; // 返回唯一分数表示的集合
}

C语言源码

#include <stdio.h>
#include <stdlib.h>

// 找到并返回一组唯一的有理数的分数表示,这些分数的分母小于或等于给定的数n,大于0。
// 参数:
//   n: 要考虑的最大分母值。
// 返回值:
//   包含唯一分数表示的字符串数组。
char** solution(int n) {
    // 为存储唯一分数表示分配内存
    char** set = (char**)malloc(n * sizeof(char*));
    // 为存储分数的 double 值分配内存
    double* doubles = (double*)malloc(n * sizeof(double));
    // 初始化找到的唯一分数数量的计数器
    int count = 0;

    // 循环遍历所有可能的分母直到 n
    for (int i = 1; i <= n; i++) {
        // 循环遍历当前分母以下的所有可能的分子
        for (int j = 1; j <= i; j++) {
            // 将分数计算为 double 值
            double res = (double)j / (double)i;

            // 用于检查分数的 double 值是否已经存在于集合中的标志
            int exists = 0;
            // 检查分数的 double 值是否已经存在于集合中
            for (int k = 0; k < count; k++) {
                if (doubles[k] == res) {
                    exists = 1;
                    break;
                }
            }

            // 如果分数的 double 值不在集合中且分数值在 0 和 1 之间
            if (!exists && res < 1 && res > 0) {
                // 为分数的字符串表示分配内存
                set[count] = (char*)malloc(20 * sizeof(char)); // 假设分数的最大长度为20
                // 存储分数的字符串表示
                sprintf(set[count], "%d/%d", j, i);
                // 存储分数的 double 值
                doubles[count] = res;
                // 增加找到的唯一分数数量的计数器
                count++;
            }
        }
    }

    // 用 NULL 指针终止字符串数组
    set[count] = NULL;

    // 释放为 double 值数组分配的内存
    free(doubles);

    return set; // 返回唯一分数表示的字符串数组
}

int main() {
    // 使用 n = 12 测试解决方法
    char** result = solution(12);
  
    // 打印唯一分数表示
    for (int i = 0; result[i] != NULL; i++) {
        printf("%s\n", result[i]);
        // 释放为每个字符串表示分配的内存
        free(result[i]);
    }
  
    // 释放为字符串数组分配的内存
    free(result);

    return 0;
}

Java源码

import java.util.HashSet;

public class Main {
    // 找到并返回一组唯一的有理数的分数表示,这些分数的分母小于或等于给定的数n,大于0。
    // 参数:
    //   n: 要考虑的最大分母值。
    // 返回值:
    //   包含唯一分数表示的HashSet。
    public static HashSet<String> solution(int n) {
        // 用于存储唯一分数表示的HashSet
        HashSet<String> set = new HashSet<>();

        // 循环遍历所有可能的分母直到 n
        for (int i = 1; i <= n; i++) {
            // 循环遍历当前分母以下的所有可能的分子
            for (int j = 1; j <= i; j++) {
                // 计算分数的值
                double res = (double) j / (double) i;

                // 如果分数的值在 0 和 1 之间且不在集合中
                if (res < 1 && res > 0 && !set.contains(j + "/" + i)) {
                    // 将分数添加到HashSet中
                    set.add(j + "/" + i);
                }
            }
        }

        return set; // 返回包含唯一分数表示的HashSet
    }

    public static void main(String[] args) {
        // 使用 n = 12 测试解决方法
        HashSet<String> result = solution(12);

        // 打印唯一分数表示
        for (String fraction : result) {
            System.out.println(fraction);
        }
    }
}
最后修改:2024 年 04 月 18 日
如果觉得我的文章对你有用,请随意赞赏