0에서 9까지의 숫자만 포함하는 문자열이 있다고 가정합니다. 그리고 하나의 대상 값이 제공됩니다. 목표 값을 얻기 위해 이진 연산자 +, - 및 *를 숫자에 추가할 수 있는 모든 가능성을 반환해야 합니다. 따라서 입력이 "232"이고 대상이 8이면 답은 ["2*3+2", "2+3*2"]
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
solve()라는 메서드를 정의하면 index, s, curr, target, temp, mult −
가 필요합니다. -
idx>=s의 크기인 경우
-
대상이 curr과 같으면
-
ret 끝에 temp 삽입
-
-
반환
-
-
aux :=빈 문자열
-
i :=idx 초기화를 위해 i
-
보조 =보조 + s[i]
-
aux[0]이 '0'이고 크기가 aux> 1이면
-
다음 반복으로 건너뛰고 다음 부분은 무시합니다.
-
-
idx가 0과 같으면
-
solve(i + 1, s, aux를 정수로, target, aux, aux를 정수로) 호출
-
-
그렇지 않으면
-
solve(i + 1, s, curr + aux를 정수로, target, temp + " + " + aux, aux asinteger) 호출
-
solve(i + 1, s, curr - aux를 정수로 호출, target, temp + " - " + aux, - aux asinteger)
-
solve(i + 1, s, curr - mult + mult * aux를 정수로, target, temp + " * " +aux, mult * aux를 정수로) 호출
-
-
-
메인 메소드 호출에서 solve(0, num, 0, target, empty string, 0)
-
리턴 렛
예
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#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;
}
typedef long long int lli;
class Solution {
public:
vector <string> ret;
void solve(int idx, string s, lli curr, lli target, string temp, lli mult){
//cout << temp << " " << curr << endl;
if(idx >= s.size()){
if(target == curr){
ret.push_back(temp);
}
return;
}
string aux = "";
for(int i = idx; i < s.size(); i++){
aux += s[i];
if(aux[0] == '0' && aux.size() > 1) continue;
if(idx == 0){
solve(i + 1, s, stol(aux), target, aux, stol(aux));
} else {
solve(i + 1, s, curr + stol(aux), target, temp + "+" + aux, stol(aux));
solve(i + 1, s, curr - stol(aux), target, temp + "-" + aux, -stol(aux));
solve(i + 1, s, curr - mult + mult * stol(aux), target, temp + "*" + aux, mult * stol(aux));
}
}
}
vector<string> addOperators(string num, int target) {
solve(0, num, 0, target, "", 0);
return ret;
}
};
main(){
Solution ob;
print_vector(ob.addOperators("232", 8));
} 입력
"232", 8
출력
[2+3*2, 2*3+2, ]