資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中新增括號的不同方法
假設我們有一串數字和運算子，我們需要找到計算所有不同可能的數字和運算子分組方式的所有可能結果。這裡有效的運算子是 +、- 和 *。所以如果輸入類似於“2*3-4*5”，那麼輸出將是 [-34, -14, -10, -10, 10]。這是因為 -
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
為了解決這個問題，我們將遵循以下步驟 -
定義一個名為 memo 的對映。
定義一個名為 solve() 的方法。這將以輸入字串作為輸入。
建立一個名為 ret 的陣列
如果 memo 包含輸入，則返回 memo[input]
對於 i 從 0 到輸入字串的大小 -
如果 input[i] 是任何受支援的運算子，則
一個數組 part1 := solve(從 0 到 i - 1 的輸入子字串)
一個數組 part2 := solve(從 i 到字串末尾的輸入子字串)
對於 j 從 0 到 part1 的大小
對於 k 從 0 到 part2 的大小
如果 input[i] 是加法，則
執行 part[j] + part[k] 並新增到 ret 中
如果 input[i] 是乘法，則
執行 part[j] * part[k] 並新增到 ret 中
如果 input[i] 是減法，則
執行 part[j] - part[k] 並新增到 ret 中
如果 ret 為空，則返回輸入字串作為整數
memo[input] := ret，並返回 ret
示例 (C++)
讓我們看看以下實現以更好地理解 -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
map <string, vector<int>> memo;
vector<int> diffWaysToCompute(string input) {
vector <int> ret;
if(memo.count(input)) return memo[input];
for(int i = 0; i < input.size(); i++){
if(input[i] == '+' || input[i] == '*' || input[i] == '-'){
vector <int> part1 = diffWaysToCompute(input.substr(0, i));
vector <int> part2 = diffWaysToCompute(input.substr(i + 1));
for(int j = 0; j < part1.size(); j++ ){
for(int k = 0; k < part2.size(); k++){
if(input[i] == '+'){
ret.push_back(part1[j] + part2[k]);
}
else if(input[i] == '*'){
ret.push_back(part1[j] * part2[k]);
} else {
ret.push_back(part1[j] - part2[k]);
}
}
}
}
}
if(ret.empty()){
ret.push_back(stoi(input));
}
return memo[input] = ret;
}
};
main(){
Solution ob;
print_vector(ob.diffWaysToCompute("2*3-4*5"));
}輸入
"2*3-4*5"
輸出
[-34, -10, -14, -10, 10, ]
更新於: 2020年5月2日
844 次檢視
廣告