leetcode-每日一题2022.2.10 最简分数
2022/2/11 6:15:20
本文主要是介绍leetcode-每日一题2022.2.10 最简分数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
力扣
思路 暴力
遍历分子和分母,判断最小公因数是1的话,就添加进结果中。
求最小公因素的笨蛋代码
class Solution { public: vector<string> simplifiedFractions(int n) { vector<string> ans; for(int i = 1; i < n; i++){ for(int j = i+1; j <= n; j++){ bool flag = true; for(int k = 2; k <= i; k++){ if(i % k == 0 && j % k ==0){ // cout<<i<<' '<<j<<endl; flag = false; break; } } if(!flag) continue; ans.push_back(to_string(i)+'/'+to_string(j)); } } return ans; } };
C++内置函数__gcd
class Solution { public: vector<string> simplifiedFractions(int n) { vector<string> ans; for(int i = 1; i < n; i++){ for(int j = i+1; j <= n; j++){ if(__gcd(i,j)==1) ans.push_back(to_string(i)+'/'+to_string(j)); } } return ans; } };
欧几里得算法
class Solution { public: int gcd(int a,int b){ return b == 0 ? a : gcd(b, a % b); } vector<string> simplifiedFractions(int n) { vector<string> ans; for(int i = 1; i < n; i++){ for(int j = i+1; j <= n; j++){ if(gcd(i,j)==1) ans.push_back(to_string(i)+'/'+to_string(j)); } } return ans; } };
这篇关于leetcode-每日一题2022.2.10 最简分数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升