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;

   }

};

```

找到规律

目录
相关文章
|
消息中间件 DataWorks 物联网
MQTT问题之接入阿里云物联网平台如何解决
MQTT接入是指将设备或应用通过MQTT协议接入到消息服务器,以实现数据的发布和订阅;本合集着眼于MQTT接入的流程、配置指导以及常见接入问题的解决方法,帮助用户实现稳定可靠的消息交换。
805 1
|
存储 安全 Windows
U盘文件损坏且无法读取怎么修复?五个方法帮你搞定
U盘文件目录损坏无法读取可能是硬件、软件或人为操作导致的问题。修复方法包括:1) 使用数据恢复软件提取重要文件;2) 运行Windows的磁盘检查工具;3) 格式化U盘(数据会丢失);4) 检查U盘健康状况,如坏道修复;5) 若硬件故障,联系官方售后。在修复前,记得先备份数据。加强数据备份能减少损失。
|
运维 网络协议 Linux
linux系统命令 losf详解
**lsof命令**(List Open Files)是Linux系统中一个非常实用的工具,用于列出当前系统上所有打开的文件以及与之关联的进程。以下是对lsof命令的详细介绍: ### 一、基本功能 lsof命令可以显示系统中被进程打开的文件,这些文件可以是普通文件、目录、网络套接字、设备文件等。通过lsof命令,用户可以方便地查看哪些文件被哪些进程打开,以及这些文件的状态信息。 ### 二、基本语法 lsof命令的基本语法为:`lsof [选项] [文件]`。其中,选项用于指定lsof命令的行为,文件则是可选的,用于指定要查询的文件。 ### 三、常用选项 * `-a` 或 `-
616 6
|
存储 监控 安全
如何实施有效的网络安全策略?
【10月更文挑战第13天】如何实施有效的网络安全策略?
729 5
|
Web App开发 Windows
win 快捷键大全,虚拟窗口、桌面等操作细节,可以使界面整洁,分类工作;Chrome快捷键,都是一些开发的骚操作
这篇文章提供了Windows操作系统和Chrome浏览器的快捷键大全,以及Xshell的快捷键操作,旨在帮助用户提高工作效率和界面管理。
926 2
|
传感器 监控 安全
物联网:NB卡的应用场景
物联网NB-IoT(窄带物联网)卡作为一种低功耗、广覆盖、大连接的物联网通信技术,广泛应用于各种需要远程监控、数据传输和智能管理的场景中。以下是一些NB-IoT卡的具体应用场景及其操作概述:
|
敏捷开发 测试技术 持续交付
软件开发过程中的最佳实践和代码质量评估
在软件开发过程中,采用最佳实践和评估代码质量对于确保软件的稳定性和可维护性至关重要。通过明确的需求、合理的开发流程、良好的代码规范以及严格的代码评估,我们可以降低软件开发过程中的风险,并提升开发效率和软件质量。
1574 2
|
Web App开发 人工智能 测试技术
软件测试/人工智能|解决Selenium中的异常问题:“error sending request for url”
软件测试/人工智能|解决Selenium中的异常问题:“error sending request for url”
|
前端开发 JavaScript API
交互设计:隐藏或显示大段文本的UI组件有哪些?
应用场景: 在手机上要给列表中的每一项添加一个大段的介绍,应该用什么UI组件 A: 这里可以用,模态对话框,弹出提示,工具提示这类组件。模态对话框的好处,就是用关闭的按钮,用户操作方便;而弹出提示和工具提示只能通过点击来切换   模态对话框: http://v2.bootcss.com/javascript.html#modals http://www.runoob.com/bootstrap/bootstrap-modal-plugin.html Bootstrap 模态框(Modal)插件 模态框(Modal)是覆盖在父窗体上的子窗体。
1751 0
|
分布式计算 Hadoop 大数据
Hadoop生态系统中的安全性与权限管理:Kerberos和Apache Ranger的应用
Hadoop生态系统中的安全性与权限管理:Kerberos和Apache Ranger的应用