[Leetcode] Different Ways to Add Parentheses, Solution

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

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(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

Output: [-34, -14, -10, -10, 10]

[Thoughts]

这题就是分治法- Divide and Conquer的一个例子。在递归的过程中，根据符号位，不断将一个字符串分成两个子串，然后将两个子串的结果merge起来。

[Code]

1:  class Solution {  
2:  public:  
3:    int compute(int a, int b, char op) {  
4:      switch(op) {  
5:        case '+': return a + b;  
6:        case '-': return a - b;  
7:        case '*': return a * b;  
8:      }  
9:    }  
10:    vector<int> diffWaysToCompute(string input) {  
11:      int number = 0, i=0;  
12:      for(; i< input.length() && isdigit(input[i]); ++i) {  
13:        number = number * 10 + input[i]-'0';  
14:      }  
15:      // if pure number, just return  
16:      if(i == input.length()) return {number};  
17:      vector<int> diffWays, lefts, rights;  
18:      for(int i =0; i< input.length(); i++) {  
19:        if(isdigit(input[i])) continue;  
20:        lefts =   
21:          diffWaysToCompute(input.substr(0, i));  
22:        rights =   
23:          diffWaysToCompute(input.substr(i + 1, input.length() - i - 1));  
24:        for(int j = 0; j < lefts.size(); ++j)   
25:          for( int k =0; k < rights.size(); ++k)   
26:            diffWays.push_back(compute(lefts[j], rights[k], input[i]));  
27:      }  
28:      return diffWays;  
29:    }  
30:  };  

Github: https://github.com/codingtmd/leetcode/blob/master/src/Different%20Ways%20to%20Add%20Parentheses.cpp

Note: 已有的实现有大量的重复计算，如果想进一步优化时间的话，可以考虑用memoization来避免冗余计算。比如，用个hash map 来保存中间计算的结果，如下：

1:  class Solution {  
2:  public:  
3:    unordered_map<string, vector<int>> memo;  
4:    int compute(int a, int b, char op) {  
5:      switch(op) {  
6:        case '+': return a + b;  
7:        case '-': return a - b;  
8:        case '*': return a * b;  
9:      }  
10:    }  
11:    string generateKey(int startIndex, int endIndex) {  
12:      return to_string(startIndex) + "-" + to_string(endIndex);  
13:    }  
14:    vector<int> diffWaysToCompute(string input) {  
15:      return diffWaysToComputeWithMemo(input, 0, input.size()-1);  
16:    }  
17:    vector<int> diffWaysToComputeWithMemo(string& input, int startIndex, int endIndex) {    
18:      string cache_key = generateKey(startIndex, endIndex);  
19:      if(memo.find(cache_key) != memo.end()) return memo[cache_key];  
20:      int number = 0, i=startIndex;  
21:      for(; i<= endIndex && isdigit(input[i]); ++i) {  
22:        number = number * 10 + input[i]-'0';  
23:      }  
24:      // if pure number, just return  
25:      if(i > endIndex) return {number};  
26:      vector<int> diffWays, lefts, rights;  
27:      for(int i =startIndex; i< endIndex; i++) {  
28:        if(isdigit(input[i])) continue;  
29:        lefts =   
30:          diffWaysToComputeWithMemo(input, startIndex, i-1);  
31:        rights =   
32:          diffWaysToComputeWithMemo(input, i+1, endIndex );  
33:        for(int j = 0; j < lefts.size(); ++j)   
34:          for( int k =0; k < rights.size(); ++k)   
35:            diffWays.push_back(compute(lefts[j], rights[k], input[i]));  
36:      }  
37:      memo[cache_key] = diffWays;  
38:      return diffWays;  
39:    }  
40:  };  

github: https://github.com/codingtmd/leetcode/blob/master/src/Different%20Ways%20to%20Add%20Parentheses(Memoization).cpp

[Leetcode] Single Number III, Solution

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

[Thought]

关于single number的解法，因为只有一个未知数，比较直观：http://fisherlei.blogspot.com/2013/11/leetcode-single-number-solution.html。

这题有两个未知数，直接做异或肯定是不行的，那么如何通过一些变换把这道题分解开，使得可以应用Single Number的解法来做，才是这个题目有意思的地方。

首先，对于数组A, 假设存在b，c两个数字，在数组中只出现了一次，那么对于整个数组进行异或操作的话，

^[A]   =  b^c ,  因为其他的数因为出现了两次，异或的过程中就被清零了。

但是仅仅通过最后异或出来的值，是没办法求出b和c的值的，但是足以帮我们把b和c划分到不同的子数组中去。

一个整数有32位bit，对于b和c，除非两者是相同的数，否则一定存在第K位bit，两者是不同的。看下面的例子，

当找到这个K以后，就可以按照第K位bit是否等于1，将A数组划分成两个子数组，而这两个子数组分别包含了b和c，那么剩下的就只需要把single number的算法直接应用到这两个子数组上，就可以得到b和c了。

[Code]

1:  class Solution {  
2:  public:  
3:    vector<int> singleNumber(vector<int>& nums) {  
4:      int length = nums.size();  
5:      // get the xor result of the array, b ^ c  
6:      int xor_result = 0;  
7:      for(int i =0; i< length; i++) {  
8:        xor_result ^= nums[i];  
9:      }  
10:      // get the K of first bit, which equals 1  
11:      int first_one_index = 0;  
12:      for(first_one_index =0; first_one_index< 32; first_one_index++) {  
13:        if((xor_result>>first_one_index) & 1 == 1) {  
14:          break;  
15:        }  
16:      }  
17:      // use k to split the array into two part  
18:      // xor the sub array, if the element's Kth bit also equals 1, b  
19:      int xor_twice = 0;  
20:      for(int i =0; i< length; i++) {  
21:        if((nums[i]>>first_one_index) & 1 == 1) {  
22:          xor_twice ^= nums[i];  
23:        }  
24:      }  
25:      // with b, easy to get c by math  
26:      vector<int> result = {xor_twice, xor_result ^ xor_twice };      
27:      return result;  
28:    }  
29:  };  

Git hub: https://github.com/codingtmd/leetcode/blob/master/src/Single_Number_III.cpp