資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的簡化分數
假設我們有一個整數 n，我們需要找到 0 和 1（不包括 0 和 1）之間所有簡化分數的列表，使得分母 <= n。這裡分數可以按任意順序排列。
因此，如果輸入為 n = 4，則輸出將為 ["1/2","1/3","1/4","2/3","3/4"]，因為 "2/4" 不是簡化分數，因為它可以簡化為 "1/2"。
為了解決這個問題，我們將遵循以下步驟：
定義一個數組 ret
初始化 i := 2，當 i <= n 時，更新（i 增加 1），執行：
初始化 j := 1，當 j < i 時，更新（j 增加 1），執行：
c := i 和 j 的最大公約數
a := j / c
b := i / c
將 (a 作為字串連線 "/" 連線 b 作為字串) 插入到 ret 的末尾
返回 ret 中所有唯一元素的陣列
示例
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<string> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<string> simplifiedFractions(int n) {
vector<string> ret;
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
int c = __gcd(i, j);
int a = j / c;
int b = i / c;
ret.push_back(to_string(a) + "/" + to_string(b));
}
}
set<string> s(ret.begin(), ret.end());
return vector<string>(s.begin(), s.end());
}
};
main(){
Solution ob;
print_vector(ob.simplifiedFractions(4));
}輸入
4
輸出
[1/2, 1/3, 1/4, 2/3, 3/4, ]
更新於: 2020年11月17日
279 次檢視
廣告