🌕🌕 LCP 02. 分式化简

难度: 🌕🌕

问题描述

---

解法

class Solution {
    public int[] fraction(int[] cont) {
        // 思路：
        // 模拟 - 递归
        int len = cont.length;
        int[] res = mySol(cont, 0, len - 1);
        int c = gcd(res[0], res[1]);
        res[0] /= c;
        res[1] /= c;
        return res;
    }

    private int gcd(int a, int b) {
        // 辗转相除法求最大公约数
        if(b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

    private int[] mySol(int[] cont, int left, int right) {
        // 递归终止条件
        if(left == right) {
            return new int[]{cont[left], 1}; // 分子 / 分母
        }
        // left < right
        int[] second = mySol(cont, left + 1, right);
        // 单层递归逻辑
        // [left] + 1/second = ([left] * second[0] + second[1]) / second[0]
        int[] res = new int[2];
        res[0] = cont[left] * second[0] + second[1];
        res[1] = second[0];
        return res;
    }
}

---

输出