282. Expression Add Operators

My intuition is dfs. For each dfs, try one digit, two digits until the whole number. For each number, we compute the value. We take the computational value so far, do the addition, subtraction and production respectively. Addition and subtraction are straightforward, but production requires a little trick. Take "a+b*c" as example,  at position 'c',  the computational value so far is "a+b", so we need subtract b and add product of b and c. Therefore, we need to track the value for previous operation. So far, the api requires two more additional arguments: computational value so far and value for previous operation. Note, we don't have to do any operation for first number so we need to take it as special case. Also, since the number is converted from string, it's very easy to get overflow. So we must use long integer. Finally, "08" is not a valid number and we need to take care of this case. As a result, the code is as following.

1:  class Solution {  
2:  public:  
3:    vector<string> addOperators(string num, int target) {  
4:      vector<string> res;  
5:      if (num.empty()) return res;  
6:      dfs(num, target, "", res, 0, 0, 0);  
7:      return res;  
8:    }  
9:    void dfs(string &num, int target, string sol, vector<string> &res, int start, long long cur, long long prev) {  
10:      if (start == num.size()) {  
11:        if (target == cur) res.push_back(sol);  
12:        return;  
13:      }  
14:      for (int i = start; i < num.size(); i++) {  
15:        if (num[start] == '0' && i > start) break;  
16:        string s = num.substr(start, i-start+1);  
17:        // when dealing with string, be sure to use long long.  
18:        long long val = stol(s);  
19:        if (start == 0) {  
20:          // special case for first digit.  
21:          dfs(num, target, s, res, i+1, val, val);  
22:        } else {  
23:          dfs(num, target, sol+"+"+s, res, i+1, cur+val, val);  
24:          dfs(num, target, sol+"-"+s, res, i+1, cur-val, -val);  
25:          dfs(num, target, sol+"*"+s, res, i+1, cur-prev+prev*val, prev*val);  
26:        }  
27:      }  
28:    }  
29:  };  

166. Fraction to Recurring Decimal

The trick to solve this problem is to get the recurring numbers. Since we don't know when recurring happens, for example, 4/333 = 0.(012) and 1/6 = 0.1(6), we have to record all the remainders that we have seen before. We can use hash map here to retrieve the previous remainders fast. Also, once we find the recurring remainder, we need to insert a left parenthesis before it so the key-value pair of the hash map is remainder-position.
Besides these, we need to take care of overflow which can be solved by long long and the negative number which we need a prefix "-".

1:  class Solution {  
2:  public:  
3:    string fractionToDecimal(int numerator, int denominator) {  
4:      if (!numerator) return "0";  
5:      int sign = (numerator < 0) ^ (denominator < 0) ? -1 : 1;  
6:      string res = (sign == -1) ? "-" : "";  
7:      long long n = labs(numerator);  
8:      long long d = labs(denominator);  
9:      res += to_string(n / d);  
10:      long long r = n % d;  
11:      if (r == 0) return res;  
12:      res += ".";  
13:      r *= 10;  
14:      unordered_map<long long, int> rm;  
15:      while (r) {  
16:        if (rm.find(r) != rm.end()) {  
17:          res.insert(rm[r], 1, '(');  
18:          res += ")";  
19:          break;  
20:        }  
21:        rm[r] = res.size();  
22:        res += to_string(r / d);  
23:        r = (r % d) *10;  
24:      }  
25:      return res;  
26:    }  
27:  };  

29. Divide Two Integers

Let's see what we should do if we want 3 to divide 18 where 18 is dividend and 3 is divisor.
(1) We subtract 3 from 18 and we get 15. 15 is larger than 3, so we shift 3 to the left by 1 bit and we get 6 which means we have 2 of 3s.
(2) We subtract 6 from 18 again and we get 12. 12 is larger than 6, so we shift 6 to the left by 1 bit again and we get 12 which means we have 4 of 3s.
(3) We subtract 12 from 18 and we get 6. Now 6 is less than 12, so we stop here and add the 4 to the result and subtract 12 from 18 as new dividend and start from 3 again as divisor. Now we go back to step (1) again. At the end, we'll get 2 so the final result is 4+2 = 6.

When implementing, we should be careful about overflow. Since -INT_MIN will be overflowed, so we can't simply flip the sign for dividend or divisor if they are negative, for example at line 6 and 7.
We should either assign dvd by casted long long dividend or do labs(dividend).

1:  class Solution {  
2:  public:  
3:    int divide(int dividend, int divisor) {  
4:      if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX;  
5:      int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;  
6:      long long dvd = labs(dividend);  
7:      long long dvs = labs(divisor);  
8:      int res = 0;  
9:      while (dvd >= dvs) {  
10:        long long multiple = 1;  
11:        long long temp = dvs;  
12:        while (dvd >= (temp << 1)) {  
13:          multiple <<= 1;  
14:          temp <<= 1;  
15:        }  
16:        dvd -= temp;  
17:        res += multiple;  
18:      }  
19:      return sign == -1 ? -res : res;  
20:    }  
21:  };  

306. Additive Number

Let's observe the example first, "112358".
1st round, 1+1 = 2
2nd round, 1 + 2 = 3
3rd round, 2 + 3 = 5
4th round, 3 + 5 = 8

And let's observe the other example, "199100199"
1st round 1+ 9 = 10
2nd round 1+ 99 = 100
3rd round 99 + 100 = 199

What do you see? If there is an additive number in the substring, the additive number becomes the second number as input for next round. And we continue doing this until the following substring doesn't include the additive number or the following substring is right the additive number. Therefore, this can be done by recursion. Particularly, when calculating the sum, we should calculate by string instead of integer to avoid overflow.

1:  class Solution {  
2:  public:  
3:    bool isAdditiveNumber(string num) {  
4:      int n = num.size();  
5:      if (n < 3) return false;  
6:      for (int i = 1; i <= n/2; i++) {  
7:        for (int j = 1; j <= (n-i)/2; j++) {  
8:          if (validate(num.substr(0,i), num.substr(i,j), num.substr(i+j))) return true;  
9:        }  
10:      }  
11:      return false;  
12:    }  
13:    bool validate(string n1, string n2, string ns) {  
14:      if ((n1.size() > 1 && n1[0] == '0') || (n2.size() > 1 && n2[0] == '0')) return false;  
15:      string sum = add(n1, n2);  
16:      if (sum == ns) return true;  
17:      if (sum.size() > ns.size()) return false;  
18:      string ss = ns.substr(0, sum.size());  
19:      if (ss == sum) return validate(n2, sum, ns.substr(sum.size()));  
20:      else return false;  
21:    }  
22:    string add(string n1, string n2) {  
23:      int i = n1.size()-1, j = n2.size()-1, carry = 0;  
24:      string res;  
25:      while (i >= 0 && j >= 0) {  
26:        int sum = n1[i--]-'0' + n2[j--]-'0'+carry;  
27:        carry = sum / 10;  
28:        res.push_back(sum%10+'0');  
29:      }  
30:      while (i >= 0) {  
31:        int sum = n1[i--]-'0'+carry;  
32:        carry = sum / 10;  
33:        res.push_back(sum%10+'0');  
34:      }  
35:      while (j >= 0) {  
36:        int sum = n2[j--]-'0'+carry;  
37:        carry = sum / 10;  
38:        res.push_back(sum%10+'0');  
39:      }  
40:      if (carry) res.push_back(carry+'0');  
41:      reverse(res.begin(), res.end());  
42:      return res;  
43:    }  
44:  };