LCP 2 分式化简 leetcode

简介: LCP 2 分式化简 leetcode

![在这里插入图片描述](https://ucc.alicdn.com/images/user-upload-01/20191006173909657.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTY5NjQz,size_16,color_FFFFFF,t_70)

输入的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] >= 0

1 <= cont的长度 <= 10

cont最后一个元素不等于0

答案的n, m的取值都能被32位int整型存下(即不超过2 ^ 31 - 1)。


来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/deep-dark-fraction

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


```cpp

class Solution {


   int test(int x,int y)

   {

       return y?test(y,x%y):x;

     

   }

 

 

   public:

   vector<int> fraction(vector<int>& cont) {

       vector<int> result;

   

      if(cont.size()==1)

      {

          result.push_back(cont[0]);

           result.push_back(1);

          return result;

      }

        int x=1,y=cont[cont.size()-1];

       for(int i=cont.size()-2;i>=0;i--)

       {

         

       

           x=x+cont[i]*y;

           int t=test(x,y);

           int z=x;

           x=y/t;

           y=z/t;

       }

       result.push_back(y);

        result.push_back(x);

       return result;

   }

};

```

找到规律

目录
相关文章
|
3月前
|
测试技术
【动态规划】【状态压缩】LCP04 覆盖
【动态规划】【状态压缩】LCP04 覆盖
|
3月前
|
算法 测试技术 C++
【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠
【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠
【动态规划】【树形dp】【深度优先搜索】LCP 26. 导航装置
【动态规划】【树形dp】【深度优先搜索】LCP 26. 导航装置
|
3月前
【每日一题Day213】LCP 33. 蓄水 | 枚举+贪心
【每日一题Day213】LCP 33. 蓄水 | 枚举+贪心
29 0
|
3月前
|
人工智能 BI
【每日一题Day354】LC2316统计无向图中无法互相到达点对数 | 并查集
【每日一题Day354】LC2316统计无向图中无法互相到达点对数 | 并查集
39 0
|
3月前
|
算法 测试技术 C++
【动态规划 状态机dp】3082. 求出所有子序列的能量和
【动态规划 状态机dp】3082. 求出所有子序列的能量和
|
3月前
|
算法 测试技术 C#
【图论】 【割点】 【双连通分类】LCP 54. 夺回据点
【图论】 【割点】 【双连通分类】LCP 54. 夺回据点
|
3月前
leetcode-LCP 06. 拿硬币
leetcode-LCP 06. 拿硬币
24 0
|
3月前
【每日一题Day223】LC1130叶值的最小代价生成树 | 贪心 区间dp
【每日一题Day223】LC1130叶值的最小代价生成树 | 贪心 区间dp
35 0
|
10月前
|
人工智能 算法 测试技术
华为机试HJ52:计算字符串的距离(动态规划)
华为机试HJ52:计算字符串的距离(动态规划)