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接入的流程、配置指导以及常见接入问题的解决方法,帮助用户实现稳定可靠的消息交换。
820 1
|
Kubernetes Linux 程序员
k8s自定义controller三部曲之一:创建CRD(Custom Resource Definition)
通过自定义控制器开发深入理解k8s的控制器设计思想及其实现
1147 0
k8s自定义controller三部曲之一:创建CRD(Custom Resource Definition)
|
存储 安全 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` 或 `-
673 6
|
存储 监控 安全
如何实施有效的网络安全策略?
【10月更文挑战第13天】如何实施有效的网络安全策略?
769 5
|
Web App开发 Windows
win 快捷键大全,虚拟窗口、桌面等操作细节,可以使界面整洁,分类工作;Chrome快捷键,都是一些开发的骚操作
这篇文章提供了Windows操作系统和Chrome浏览器的快捷键大全,以及Xshell的快捷键操作,旨在帮助用户提高工作效率和界面管理。
965 2
|
传感器 监控 安全
物联网:NB卡的应用场景
物联网NB-IoT(窄带物联网)卡作为一种低功耗、广覆盖、大连接的物联网通信技术,广泛应用于各种需要远程监控、数据传输和智能管理的场景中。以下是一些NB-IoT卡的具体应用场景及其操作概述:
|
运维 安全 Linux
服务器基础知识大科普
服务器基础知识大科普
868 0
|
人工智能 API UED
🔍语言无界,沟通无阻:AI翻译技术,让职场国际交流零障碍!
【8月更文挑战第1天】全球化驱动跨国合作,但语言障碍影响交流效率。AI翻译技术突破此限制,实现实时多语种翻译,如会议中即时将发言转为所需语言,确保无障碍沟通。此外,AI能根据上下文精准翻译,避免误解。通过持续学习,AI翻译质量不断提升。这项技术打破语言壁垒,促进文化融合,未来将进一步优化职场国际交流,推动全球化进程。
391 0
|
机器学习/深度学习 自然语言处理 搜索推荐
深度学习中的自注意力机制:原理与应用
在深度学习领域,自注意力机制(Self-Attention Mechanism)已经成为一种强大的工具,它允许模型在处理序列数据时更加高效和灵活。本文将深入探讨自注意力机制的工作原理、数学基础以及在不同应用场景下的表现。我们将通过具体案例分析,展示自注意力如何提升神经网络对长距离依赖的捕捉能力,以及它在自然语言处理(NLP)、计算机视觉(CV)等领域的应用成效。
1098 0