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接入的流程、配置指导以及常见接入问题的解决方法,帮助用户实现稳定可靠的消息交换。
974 1
|
Ubuntu Linux
几种Linux系统切换内核启动顺序方法
几种Linux系统切换内核启动顺序方法
|
存储 缓存 Linux
SMB小传 —— SMB网络文件系统协议介绍
SMB网络文件系统协议, 全名服务器消息块(Server Message Block),曾用名CIFS(通用互联网文件系统 Common Internet File System), 公元1983年诞生于IBM[1],幼年得到英特尔和微软的照料,最终在微软的培养下成长为当今世上网络文件系统协议两极之一的存在。
22487 0
|
7月前
|
存储 运维 监控
毅硕HPC | Lustre文件系统在HPC集群中的部署实战
Lustre作为一种开源的、分布式并行文件系统,凭借其卓越的可扩展性和极高的I/O吞吐量,成为了全球Top 500超算中心的首选。Lustre不仅仅是一个存储系统,它是连接计算资源与科学数据的纽带。
663 0
|
10月前
|
人工智能 测试技术 开发者
聊聊OpenAI那份Codex内部指南,以及它给我的启发
OpenAI发布《如何使用Codex》揭秘工程师真实用法:AI不仅是代码补全,更是重构助手、测试生成器和新人导师。几分钟完成数小时工作,保护开发“心流”,提升效率惊人。这才是AI编程的正确打开方式!
936 1
|
消息中间件 Kafka API
原理剖析| Kafka Exactly Once 语义实现原理:幂等性与事务消息
原理剖析| Kafka Exactly Once 语义实现原理:幂等性与事务消息
455 0
|
存储 安全 Windows
U盘文件损坏且无法读取怎么修复?五个方法帮你搞定
U盘文件目录损坏无法读取可能是硬件、软件或人为操作导致的问题。修复方法包括:1) 使用数据恢复软件提取重要文件;2) 运行Windows的磁盘检查工具;3) 格式化U盘(数据会丢失);4) 检查U盘健康状况,如坏道修复;5) 若硬件故障,联系官方售后。在修复前,记得先备份数据。加强数据备份能减少损失。
|
存储 消息中间件 对象存储
谈谈 RocketMQ 5.0 分级存储背后一些有挑战的技术优化
谈谈 RocketMQ 5.0 分级存储背后一些有挑战的技术优化
133704 356
|
运维 数据挖掘 索引
服务器数据恢复—Lustre分布式文件系统服务器数据恢复案例
5台节点服务器,每台节点服务器上有一组RAID5阵列。每组RAID5阵列上有6块硬盘(其中1块硬盘设置为热备盘,其他5块硬盘为数据盘)。上层系统环境为Lustre分布式文件系统。 机房天花板漏水导致这5台节点服务器进水,每台服务器都有至少2块硬盘出现故障。每台服务器中的RAID5阵列短时间内同时掉线2块或以上数量的硬盘,导致RAID崩溃,服务器中数据无法正常读取。
|
存储 缓存 运维
Lustre架构介绍的阅读笔记-HSM
HSM(Hierarchical Storage Management)是数据分级存储管理,根据数据生命周期、访问特性和设备成本,自动在CPU寄存器、缓存、主存、SSD、HDD、光盘、磁带库等不同存储层级间迁移数据。数据热度分为热、温、冷、冰,对应不同成本、性能和容量。迁移策略可基于人工判断或系统自动计算,并确保业务I/O不受影响、数据一致性。访问频率增加时,数据可反向迁移至更高层级。
576 2