难度: Easy
有一个同学在学习分式。他需要将一个连分数化成最简分数，你能帮助他吗？
连分数是形如上图的分式。在本题中，所有系数都是大于等于0的整数。
输入的cont代表连分数的系数（cont[0]代表上图的a0，以此类推）。返回一个长度为2的数组[n, m]，使得连分数的值等于n / m，且n, m最大公约数为1。
示例 1：
输入：cont = [3, 2, 0, 2] 输出：[13, 4] 解释：原连分数等价于3 + (1 / (2 + (1 / (0 + 1 / 2))))。注意[26, 8], [-13, -4]都不是正确答案。
示例 2：
输入：cont = [0, 0, 3] 输出：[3, 1] 解释：如果答案是整数，令分母为1即可。
限制：
cont[i] >= 01 <= cont的长度 <= 10cont最后一个元素不等于0n, m的取值都能被32位int整型存下（即不超过2 ^ 31 - 1）。运行时间: 22 ms
内存: 16.0 MB
class Solution:
def fraction(self, cont: List[int]) -> List[int]:
n, m = 0, 1
for a in cont[::-1]:
n, m = m, m * a + n
return [m, n]
题解的思路是从连分数的最后一个元素开始向前处理，通过逆向计算的方式逐步构建连分数的分子和分母。具体来说，初始化分子n为0，分母m为1，然后逆序遍历输入数组的每一个元素a，每次更新分子n和分母m的值。更新规则是：将当前的分母m赋值给分子n，新的分母m计算为当前元素a乘以原分母m加上原分子n。这种逆序处理方式直接得到了最简形式的分数，因为每步计算都保证分子和分母的最大公约数为1。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def fraction(self, cont: List[int]) -> List[int]:
n, m = 0, 1 # 初始化分子n为0，分母m为1
for a in cont[::-1]: # 逆序遍历输入数组
n, m = m, m * a + n # 更新分子和分母
return [m, n] # 返回结果，注意返回顺序为分母，分子
在处理连分数时，初始值设置为分子n为0和分母m为1是为了开始逆序计算时能正确地构造分数。这种初始化相当于从一个非常简单的分数0/1开始，确保了在算法的第一步，即使连分数的最后一个元素被处理，也能正确地将其转化为有效的分数形式。此外，分子为0和分母为1的分数在数学上表示为0，这是一个合理的起点，因为任何数与0的和都是那个数本身，这保证了连分数的最后一个元素可以正确初始化整个逆序处理过程。
在连分数的逆序处理中，每次更新都是用当前元素a、前一步的分母m和前一步的分子n来计算新的分母。由于分子n和分母m在更新前是互质的（即最大公约数为1），并且每次更新分母为 `m * a + n`，这种更新方式相当于对两个互质的数进行线性组合。根据数论中的性质，两个互质的整数的任何线性组合也与这两个数的任何一个互质。因此，每次更新后的新分子（旧的分母m）和新分母（m * a + n）仍然是互质的。
这种设计可能是为了强调算法输出的特别格式或者是为了适应特定的编程或数据处理需求。在数学和大多数实际应用中，分数通常表示为分子在前、分母在后。然而，在特定的上下文或系统中，可能需要按照分母在前的顺序来处理数据，以便于特定的数学操作或编程逻辑。在没有具体上下文的情况下，这种设计可能仅是为了说明或者测试输出格式的不同可能性。