2023-05-25:给定一个正整数 x,我们将会写出一个形如 x (op1) x (op2) x (op3) x … 的表达式
其中每个运算符 op1,op2,… 可以是加、减、乘、除之一
例如,对于 x = 3,我们可以写出表达式 3 * 3 / 3 + 3 – 3,该式的值为3
在写这样的表达式时,我们需要遵守下面的惯例:
除运算符(/)返回有理数
任何地方都没有括号
我们使用通常的操作顺序:乘法和除法发生在加法和减法之前
不允许使用一元否定运算符(-)。例如,“x – x” 是一个有效的表达
因为它只使用减法,但是 “-x + x” 不是,因为它使用了否定运算符
我们希望编写一个能使表达式等于给定的目标值 target 且运算符最少的表达式。
返回所用运算符的最少数量。
输入:x = 5, target = 501。
输出:8。
答案2023-05-25:
大体过程如下:
1.定义函数 leastOpsExpressTarget,传入参数 x 和 target。
2.初始化一个 map 类型的变量 dp,用于记录已经计算过的结果。
3.调用函数 dpf,传入参数 0、target、x 和 dp。函数 dpf 的作用是计算在当前情况下,target 最少需要几个运算符才能被表达出来。
4.在函数 dpf 中,首先判断当前情况是否已经计算过,如果已经计算过则直接返回结果。
5.如果没有计算过,则根据题目要求,最多只能使用 x 的 i 次方来进行运算,所以需要记录当前来到了 x 的 i 次方这个数字。
6.如果 target 大于 0 且 i 小于 39(为了防止溢出),则根据题目要求,将 target 分解成商和余数两部分,然后分别计算用加、减、乘、除运算符可以得到的最小的运算次数。
7.最后,将计算出的结果保存到 dp 中,并返回该结果。
8.定义函数 cost,传入参数 i,用于得到 x 的 i 次方这个数字需要几个运算符,默认前面再加个’+’或’-‘。
9.定义函数 min,传入参数 a 和 b,用于比较 a 和 b 的大小,并返回较小的值。
10.在主函数 main 中,定义变量 x 和 target,分别赋值为 5 和 501。然后调用函数 leastOpsExpressTarget,并将结果输出。
时间复杂度:
- 函数 leastOpsExpressTarget 中调用了函数 dpf,而函数 dpf 的时间复杂度为 O(log(target))(因为 i 最大可以达到 39,x^39 已经大于等于 target),所以最终的时间复杂度为 O(log(target))。
空间复杂度:
- 函数 leastOpsExpressTarget 中创建了一个 map 类型的变量 dp,其中存储的元素个数最多为 O(log(target) * 40),所以空间复杂度为 O(log(target))。
go完整代码如下:
package main
import (
"fmt"
)
func leastOpsExpressTarget(x, target int) int {
dp := make(map[int]map[int]int)
return dpf(0, target, x, dp) - 1
}
// i : 当前来到了x的i次方
// target : 认为target只能由x的i次方,或者更高次方来解决,不能使用更低次方!
// 返回在这样的情况下,target最少能由几个运算符搞定!
// (3, 1001231) -> 返回值!
// dp.get(3) -> {1001231 对应的value}
func dpf(i, target, x int, dp map[int]map[int]int) int {
if val, ok := dp[i][target]; ok {
return val
}
ans := 0
if target > 0 && i
rust完整代码如下:
use std::collections::HashMap;
fn least_ops_express_target(x: i32, target: i32) -> i32 {
let mut dp: HashMap> = HashMap::new();
dpf(0, target, x, &mut dp) - 1
}
// i : 当前来到了x的i次方
// target : 认为target只能由x的i次方,或者更高次方来解决,不能使用更低次方!
// 返回在这样的情况下,target最少能由几个运算符搞定!
// (3, 1001231) -> 返回值!
// dp.get(3) -> {1001231 对应的value}
fn dpf(i: i32, target: i32, x: i32, dp: &mut HashMap>) -> i32 {
if let Some(map) = dp.get(&i) {
if let Some(val) = map.get(&target) {
return *val;
}
}
let ans: i32;
if target > 0 && i i32 {
if i == 0 {
2
} else {
i
}
}
fn main() {
let x = 3;
let target = 19;
println!("{}", least_ops_express_target(x, target));
let x = 5;
let target = 501;
println!("{}", least_ops_express_target(x, target));
let x = 100;
let target = 100000000;
println!("{}", least_ops_express_target(x, target));
}
c语言完整代码如下:
#include
#include
int leastOpsExpressTarget(int x, int target);
int cost(int i);
int dpf(int i, int target, int x, int*** dp) {
if (dp[i][target] != 0) {
return dp[i][target];
}
int ans = 0;
if (target > 0 && i
c++完整代码如下:
#include
#include
using namespace std;
int cost(int i);
int dpf(int i, int target, int x, unordered_map>& dp) {
if (dp.count(i) && dp[i].count(target)) {
return dp[i][target];
}
int ans = 0;
if (target > 0 && i ();
}
dp[i][target] = ans;
return ans;
}
int leastOpsExpressTarget(int x, int target) {
unordered_map> dp;
return dpf(0, target, x, dp) - 1;
}
// 得到x的i次方这个数字
// 需要几个运算符,默认前面再加个'+'或'-'
int cost(int i) {
return i == 0 ? 2 : i;
}
int main() {
int x = 5;
int target = 501;
cout
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
相关推荐: 银河麒麟v10 sp1 安装 PostgreSQL 11.16
一、安装环境 操作系统:银河麒麟v10 sp3 x86_64 内核版本: PostgreSQL版本:11.16 二、安装过程 2.1 下载源码包 创建目录 mkdir -p /tools/postgresql 下载文件:wget https:…