資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C++ 中的最近公約數
假設我們有一個整數 num，我們必須找到絕對差中最近的兩個整數，它們的乘積等於 num + 1 或 num + 2。我們必須以任何順序找到這兩個整數。因此，如果輸入為 8，那麼輸出將為 [3, 3]，對於 num + 1，它將為 9，最近的公約數為 3 和 3，對於 num + 2 = 10，最近的公約數為 2 和 5，因此選擇 3 和 3。
為了解決這個問題，我們將遵循以下步驟：
定義一個名為 getDiv() 的方法，它將 x 作為輸入
diff := 無窮大，建立一個名為 ret 的大小為 2 的陣列
對於 i := 1，如果 i^2 <= x，則將 i 增加 1
如果 x 可以被 i 整除，則
a := i
b := x / i
newDiff := |a – b|
如果 newDiff < diff，則
diff := newDiff
ret[0] := a 且 ret[1] := b
返回 ret
從 main 方法中，找到 op1 := getDiv(num + 1) 且 op2 := getDiv(num + 2)
如果 |op1[0] – op[1]| <= |op2[0] – op2[1]|，則返回 op1，否則返回 op2
示例 (C++)
讓我們看看以下實現以獲得更好的理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector <int> getDiv(int x){
int diff = INT_MAX;
vector <int> ret(2);
for(int i = 1; i * i <= x; i++){
if(x % i == 0){
int a = i;
int b = x / i;
int newDiff = abs(a - b);
if(newDiff < diff){
diff = newDiff;
ret[0] = a;
ret[1] = b;
}
}
}
return ret;
}
vector<int> closestDivisors(int num) {
vector <int> op1 = getDiv(num + 1);
vector <int> op2 = getDiv(num + 2);
return abs(op1[0] - op1[1]) <= abs(op2[0] - op2[1]) ? op1 : op2;
}
};
main(){
Solution ob;
print_vector(ob.closestDivisors(8));
}輸入
8
輸出
[3,3]
更新於：2020 年 4 月 29 日
325 次瀏覽
廣告