最简分数(leetcode 1447)

/ 0评 / 0

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

思考: 例如n ,它应该有(n-1)+(n-2)+....加到n的值为0就可以,但是要考虑分母和分子可以进行相除,相约的关系,所以规律不成立,那么尝试一下暴力解法

class Solution {
   public List<String> simplifiedFractions(int n) {
       List<String> list = new ArrayList();
       for (int i=2; i<=n; i++){
           for (int j=1; j<i; j++) {
               if (checkTheSimplest(j,i)){
                   list.add(String.valueOf(j+"/"+i));
              }
          }
      }
       return list;
  }
   public Boolean checkTheSimplest(int a, int b) {
       for (int j=2; j<=a; j++ ){
           if (a%j==0 && b%j==0){
               return false;
          }
      }
       return true;
  }
}

题解主要采用的gcd函数,也就是欧几里得解法

欧几里得算法基于下面这个原理: 设a,b均为正整数,则gcd(a,b)=gcd(b,a%b)。

证明:设 a = kb + r,其中 k 和 r 分别为 a 除以 b 得到的商和余数。 则有 r = a - kb 成立。 设 d 为 a 和 b 的一个公约数, 那么由 r = a - kb,得 d 也是 r 的一个约数。 因此 d 是 b 和 r 的一个公约数。 又由 r = a % b,得 d 为 b 和 a % b 的一个公约数。 因此 d 既是 a 和 b 的公约数,也是 b 和 a % b的公约数。 由 d 的任意性,得 a 和 b 的公约数都是 b 和 a % b 的公约数。 由 a = kb + r,同理可证 b 和 a % b的公约数都是 a 和 b 的公约数。 因此 a 和 b 的公约数与 b 和 a % b的公约数都是 a 和 b 的公约数。 即有 gcd(a,b) = gcd(b,a % b)。 证毕。

递归的两个关键: ① 递归式:gcd(a,b) = gcd(b,a % b) 。 ② 递归边界:gcd(a,0) = a 。

于是可得到下面的求解最大公约数的代码:

int gcd(int a, int b){
  if(b == 0) return a;
  else return gcd (b, a % b);
}

更简洁的写法:

int gcd(int a, int b){
  return !b ? a : gcd (b, a % b);
}

对于最小公倍数的实现可以通过求解最大公约数来间接的实现,即a,b的最小公倍数lcm(a,b)=a/gcd(a,b)*b

所以又可以得到另外一种解法:

class Solution {
   int gcd(int a, int b) { // 欧几里得算法
       return b == 0 ? a : gcd(b, a % b);
  }
   public List<String> simplifiedFractions(int n) {
       List<String> ans = new ArrayList<>();
       for (int i = 1; i < n; i++) {
           for (int j = i + 1; j <= n; j++) {
               if (gcd(i, j) == 1) ans.add(i + "/" + j);
          }
      }
       return ans;
  }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注