資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中用最少的運算子表示數字
假設我們有一個正整數 x，我們將編寫一個形如 x (op1) x (op2) x (op3) x ... 的表示式，其中 op1、op2 等是運算子。這些運算子可以是加法、減法、乘法或除法。例如，當 x = 3 時，我們可以寫 3 * 3 / 3 + 3 - 3，其值為 3。有一些規則，如下所示 -
除法運算子 (/) 返回有理數。
任何地方都不使用括號。
我們使用通常的運算順序 - 乘法和除法優先於加法和減法。
不允許使用一元否定運算子。
我們必須編寫一個運算子數量最少的表示式，使得該表示式等於給定的目標。因此，我們將找到最少的運算子數量。
因此，如果輸入類似於 x = 4，target = 15，則輸出將為 3，因為我們可以將 15 表示為 4*4- 4/4
為了解決這個問題，我們將遵循以下步驟 -
如果目標與 x 相同，則 -
如果 x > target，則 -
返回 (x - target) * 2 和 (target * 2) - 1 的最小值
sum := x，t := 0
當 sum < target 時，執行 -
sum := sum * x
(t 加 1)
如果 sum 與 target 相同，則 -
返回 t
l := inf，r := inf
如果 sum - target target，則 -
r := leastOpsExpressTarget(x, sum - target)
l := leastOpsExpressTarget(x, target - (sum / x))
返回 1 + l 和 r 的最小值
讓我們看看以下實現以獲得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int leastOpsExpressTarget(int x, int target) {
if(target == x) return 0;
if(x > target){
return min((x - target) * 2, (target * 2) - 1);
}
lli sum = x;
int t = 0;
while(sum < target){
sum *= x;
t++;
}
if(sum == target) return t;
int l = INT_MAX;
int r = INT_MAX;
if(sum - target < target){
r = leastOpsExpressTarget(x, sum - target) + t;
}
l = leastOpsExpressTarget(x, target - (sum / x)) + t - 1;
return min(l, r) + 1;
}
};
main(){
Solution ob;
cout << (ob.leastOpsExpressTarget(4, 15));
}輸入
4, 15
輸出
3
更新於: 2020年6月4日
275 次檢視
廣告