2023-05-25：給定一個正整數(shù) x，我們將會寫出一個形如 x (op1) x (op2) x (op3) x ..
2023-05-25：給定一個正整數(shù) x，我們將會寫出一個形如 x (op1) x (op2) x (op3) x ... 的表達式
其中每個運算符 op1，op2，… 可以是加、減、乘、除之一
例如，對于 x = 3，我們可以寫出表達式 3 * 3 / 3 + 3 - 3，該式的值為3
在寫這樣的表達式時，我們需要遵守下面的慣例：
除運算符（/）返回有理數(shù)
任何地方都沒有括號
我們使用通常的操作順序：乘法和除法發(fā)生在加法和減法之前
不允許使用一元否定運算符（-）。例如，“x - x” 是一個有效的表達
因為它只使用減法，但是 “-x + x” 不是，因為它使用了否定運算符
我們希望編寫一個能使表達式等于給定的目標值 target 且運算符最少的表達式。
返回所用運算符的最少數(shù)量。
輸入：x = 5, target = 501。
輸出：8。
答案2023-05-25：
大體過程如下：
1.定義函數(shù) leastOpsExpressTarget，傳入?yún)?shù) x 和 target。
2.初始化一個 map 類型的變量 dp，用于記錄已經(jīng)計算過的結(jié)果。
3.調(diào)用函數(shù) dpf，傳入?yún)?shù) 0、target、x 和 dp。函數(shù) dpf 的作用是計算在當前情況下，target 最少需要幾個運算符才能被表達出來。
4.在函數(shù) dpf 中，首先判斷當前情況是否已經(jīng)計算過，如果已經(jīng)計算過則直接返回結(jié)果。
5.如果沒有計算過，則根據(jù)題目要求，最多只能使用 x 的 i 次方來進行運算，所以需要記錄當前來到了 x 的 i 次方這個數(shù)字。
6.如果 target 大于 0 且 i 小于 39（為了防止溢出），則根據(jù)題目要求，將 target 分解成商和余數(shù)兩部分，然后分別計算用加、減、乘、除運算符可以得到的最小的運算次數(shù)。
7.最后，將計算出的結(jié)果保存到 dp 中，并返回該結(jié)果。
8.定義函數(shù) cost，傳入?yún)?shù) i，用于得到 x 的 i 次方這個數(shù)字需要幾個運算符，默認前面再加個'+'或'-'。
9.定義函數(shù) min，傳入?yún)?shù) a 和 b，用于比較 a 和 b 的大小，并返回較小的值。
10.在主函數(shù) main 中，定義變量 x 和 target，分別賦值為 5 和 501。然后調(diào)用函數(shù) leastOpsExpressTarget，并將結(jié)果輸出。
時間復(fù)雜度：
??函數(shù) leastOpsExpressTarget 中調(diào)用了函數(shù) dpf，而函數(shù) dpf 的時間復(fù)雜度為 O(log(target))（因為 i 最大可以達到 39，x^39 已經(jīng)大于等于 target），所以最終的時間復(fù)雜度為 O(log(target))。
空間復(fù)雜度：
??函數(shù) leastOpsExpressTarget 中創(chuàng)建了一個 map 類型的變量 dp，其中存儲的元素個數(shù)最多為 O(log(target) * 40)，所以空間復(fù)雜度為 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?對應(yīng)的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次方這個數(shù)字
//?需要幾個運算符，默認前面再加個'+'或'-'
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?對應(yīng)的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次方這個數(shù)字
//?需要幾個運算符，默認前面再加個'+'或'-'
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次方這個數(shù)字
//?需要幾個運算符，默認前面再加個'+'或'-'
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次方這個數(shù)字
//?需要幾個運算符，默認前面再加個'+'或'-'
int?cost(int?i)?{
????return?i?==?0???2?:?i;
}
int?main()?{
????int?x?=?5;
????int?target?=?501;
????cout?<<?leastOpsExpressTarget(x,?target)?<<?endl;
????return?0;
}
