数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告