2023-05-25:给定一个正整数 x,我们将会写出一个形如 x (op1) x (op2) x (op3)

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 < 39 {
        if target == 1 {
            ans = cost(i)
        } else {
            div := target / x
            mod := target % x
            p1 := mod*cost(i) + dpf(i+1, div, x, dp)
            p2 := (x-mod)*cost(i) + dpf(i+1, div+1, x, dp)
            ans = min(p1, p2)
        }
    }
    if _, ok := dp[i]; !ok {
        dp[i] = make(map[int]int)
    }
    dp[i][target] = ans
    return ans
}

// 得到x的i次方这个数字
// 需要几个运算符,默认前面再加个'+'或'-'
func cost(i int) int {
    if i == 0 {
        return 2
    }
    return i
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
    x := 5
    target := 501
    fmt.Println(leastOpsExpressTarget(x, target))
}

在这里插入图片描述

rust完整代码如下:

use std::collections::HashMap;

fn least_ops_express_target(x: i32, target: i32) -> i32 {
    let mut dp: HashMap<i32, HashMap<i32, i32>> = 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, HashMap<i32, i32>>) -> i32 {
    if let Some(map) = dp.get(&i) {
        if let Some(val) = map.get(&target) {
            return *val;
        }
    }

    let ans: i32;
    if target > 0 && i < 39 {
        if target == 1 {
            ans = cost(i);
        } else {
            let div = target / x;
            let mod0 = target % x;
            let p1 = mod0 * cost(i) + dpf(i + 1, div, x, dp);
            let p2 = (x - mod0) * cost(i) + dpf(i + 1, div + 1, x, dp);
            ans = p1.min(p2);
        }
    } else {
        ans = 0;
    }

    dp.entry(i).or_insert(HashMap::new()).insert(target, ans);
    ans
}

// 得到x的i次方这个数字
// 需要几个运算符,默认前面再加个'+'或'-'
fn cost(i: i32) -> 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 <stdio.h>
#include <stdlib.h>

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 < 39) {
        if (target == 1) {
            ans = cost(i);
        }
        else {
            int div = target / x;
            int mod = target % x;
            int p1 = mod * cost(i) + dpf(i + 1, div, x, dp);
            int p2 = (x - mod) * cost(i) + dpf(i + 1, div + 1, x, dp);
            ans = p1 < p2 ? p1 : p2;
        }
    }
    dp[i][target] = ans;
    return ans;
}

int leastOpsExpressTarget(int x, int target) {
    int** dp = (int**)calloc(40, sizeof(int*));
    for (int i = 0; i < 40; ++i) {
        dp[i] = (int*)calloc(target + 1, sizeof(int));
    }
    int ans = dpf(0, target, x, dp) - 1;
    for (int i = 0; i < 40; ++i) {
        free(dp[i]);
    }
    free(dp);
    return ans;
}

// 得到x的i次方这个数字
// 需要几个运算符,默认前面再加个'+'或'-'
int cost(int i) {
    return i == 0 ? 2 : i;
}

int main() {
    int x = 5;
    int target = 501;
    printf("%d\n", leastOpsExpressTarget(x, target));
    return 0;
}

在这里插入图片描述

c++完整代码如下:

#include <iostream>
#include <unordered_map>

using namespace std;

int cost(int i);

int dpf(int i, int target, int x, unordered_map<int, unordered_map<int, int>>& dp) {
    if (dp.count(i) && dp[i].count(target)) {
        return dp[i][target];
    }

    int ans = 0;
    if (target > 0 && i < 39) {
        if (target == 1) {
            ans = cost(i);
        }
        else {
            int div = target / x;
            int mod = target % x;
            int p1 = mod * cost(i) + dpf(i + 1, div, x, dp);
            int p2 = (x - mod) * cost(i) + dpf(i + 1, div + 1, x, dp);
            ans = min(p1, p2);
        }
    }
    if (!dp.count(i)) {
        dp[i] = unordered_map<int, int>();
    }
    dp[i][target] = ans;
    return ans;
}

int leastOpsExpressTarget(int x, int target) {
    unordered_map<int, unordered_map<int, int>> 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 << leastOpsExpressTarget(x, target) << endl;
    return 0;
}

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
464
粉丝
21
喜欢
37
收藏
22
排名:461
访问:1.9 万
私信
所有博文
社区赞助商