题目描述
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
Example 1:
1 2 3 4 5
Input: "2-1-1" Output: [0, 2] Explanation: ((2-1)-1) = 0 (2-(1-1)) = 2
Example 2:
1 2 3 4 5 6 7 8
Input: "2*3-4*5" Output: [-34, -14, -10, -10, 10] Explanation: (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
这题需要使用分治法。比如对于2*3-4*5，可以根据操作符来进行分治，比如根据’-‘可以分成2*3和4*5，然后再算每一个小块的所有可能值，最后用’-‘在所有可能值之间进行减法操作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
class {private : vector <int > getInt(string input) { vector <int > result; int startIndex = 0 ; for (int i = 0 ; i < input.length(); i++) { if (input[i] == '+' || input[i] == '-' || input[i] == '*' ){ result.push_back(stoi(input.substr(startIndex, i-startIndex))); startIndex = i+1 ; } } result.push_back(stoi(input.substr(startIndex, input.length()-startIndex))); return result; } vector <char > getChar(string input) { vector <char > result; for (int i = 0 ; i < input.length(); i++) { if (input[i] == '+' || input[i] == '-' || input[i] == '*' ) result.push_back(input[i]); } return result; } vector <int > divide(vector <int > ints, vector <char > chars, int left, int right) { vector <int > result; if (left == right) { result.push_back(ints[left]); return result; } for (int i=left; i<right; i++) { vector <int > leftVector = divide(ints, chars, left, i); vector <int > rightVector = divide(ints, chars, i+1 , right); for (int j: leftVector) { for (int k: rightVector) { if (chars[i] == '+' ) result.push_back(j+k); if (chars[i] == '-' ) result.push_back(j-k); if (chars[i] == '*' ) result.push_back(j*k); } } } return result; } public : vector <int > diffWaysToCompute(string input) { vector <int > ints = getInt(input); vector <char > chars = getChar(input); return divide(ints, chars, 0 , ints.size()-1 ); } };
近期评论