## Sunday, October 25, 2015

### [Leetcode] Product of Array Except Self, Solution

Given an array of n integers where n > 1, `nums`, return an array `output` such that `output[i]` is equal to the product of all the elements of `nums` except `nums[i]`.
Solve it without division and in O(n).
For example, given `[1,2,3,4]`, return `[24,12,8,6]`.
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
[Thoughts]

`output[i]` is equal to the product of all the elements of `nums` except `nums[i]`.

output[i] =  { i 前面的数的乘积}  X  { i 后面的数的乘积}

[Code]
``````1:  class Solution {
2:  public:
3:    vector<int> productExceptSelf(vector<int>& nums) {
4:      vector<int> products;
5:      if(nums.size() == 0) return products;
6:      int product = 1;
7:      products.push_back(1);
8:      for(int i =1; i< nums.size(); i++) {
9:        product *= nums[i-1];
10:        products.push_back(product);
11:      }
12:      product = 1;
13:      for(int i =nums.size()-2; i>=0; i--) {
14:        product = product * nums[i+1];
15:        products[i] = products[i] * product;
16:      }
17:      return products;
18:    }
19:  };
``````

github: https://github.com/codingtmd/leetcode/blob/master/src/Product%20of%20Array%20Except%20Self.cpp

## Saturday, October 17, 2015

### [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]

[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:  };
``````

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) {
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:  };
``````

### [Leetcode] Valid Anagram, Solution

Given two strings s and t, write a function to determine if t is an anagram of s.
For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.
Note:
You may assume the string contains only lowercase alphabets.
[Thoughts]

[Code]
``````1:  class Solution {
2:  public:
3:    bool isAnagram(string s, string t) {
4:      vector<int> charcount(26, 0);
5:      for(int i =0; i< s.length(); i++) {
6:        charcount[s[i] - 'a'] ++;
7:      }
8:      for(int i =0; i< t.length(); i++) {
9:        charcount[t[i] - 'a'] --;
10:      }
11:      for(int i =0; i<charcount.size(); i++) {
12:        if(charcount[i] != 0) {
13:          return false;
14:        }
15:      }
16:      return true;
17:    }
18:  };
``````

## Friday, October 16, 2015

### [Leetcode] Binary Tree Paths, Solution

Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
```   1
/   \
2     3
\
5
```
All root-to-leaf paths are:
`["1->2->5", "1->3"]`

[Thought]

[Code]
``````1:  class Solution {
2:  public:
3:    vector<string> binaryTreePaths(TreeNode* root) {
4:      vector<string> paths;
5:      vector<int> nodes;
6:      getAllPaths(root, nodes, paths);
7:      return paths;
8:    }
9:    void getAllPaths(TreeNode* node, vector<int>& nodes,vector<string>& paths) {
10:      if(node == NULL) {
11:        return;
12:      }
13:      if(node->left== NULL && node->right == NULL) {
14:        stringstream ss;
15:        for(int i =0; i< nodes.size(); i++) {
16:          ss << nodes[i] << "->";
17:        }
18:        ss << node->val;
19:        paths.push_back(ss.str());
20:        return;
21:      }
22:      nodes.push_back(node->val);
23:      getAllPaths(node->left, nodes, paths);
24:      getAllPaths(node->right, nodes, paths);
25:      nodes.pop_back();
26:    }
27:  };
``````

Github: https://github.com/codingtmd/leetcode/blob/master/src/Binary%20Tree%20Paths.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]

^[A]   =  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

## Monday, October 5, 2015

### [Leetcode] Ugly Number II, Solution

Write a program to find the `n`-th ugly number.
Ugly numbers are positive numbers whose prime factors only include `2, 3, 5`. For example, `1, 2, 3, 4, 5, 6, 8, 9, 10, 12` is the sequence of the first `10` ugly numbers.
Note that `1` is typically treated as an ugly number.

[Thoughts]

Ugly Number:       1,         2,          3,           4,           5,           6,            8,         10,     ..............

1*3      2*3        3*3         4*3         5*3         6*3         8*3        10*3  .............. *3
1*5      2*5        3*5         4*5         5*5         6*5         8*5        10*5  .............. *5

[Code]
``````1:  class Solution {
2:  public:
3:    int nthUglyNumber(int n) {
4:      vector<int> uglys(1, 1);
5:      int p2 = 0, p3 = 0, p5 = 0;
6:      while (uglys.size() < n) {
7:        int ugly2 = uglys[p2] * 2, ugly3 = uglys[p3] * 3, ugly5 = uglys[p5] * 5;
8:        int min_v = min(ugly2, min(ugly3, ugly5));
9:        if (min_v == ugly2) ++p2;
10:        if (min_v == ugly3) ++p3;
11:        if (min_v == ugly5) ++p5;
12:        if(min_v != uglys.back()) {
13:          // skip duplicate
14:          uglys.push_back(min_v);
15:        }
16:      }
17:      return uglys[n-1];
18:    }
19:  };
``````

``````1:  class Solution {
2:  public:
3:    int nthUglyNumber(int n) {
4:      vector<int> factors{ 2, 3, 5};
5:      return nthUglyNumberGeneral(n, factors);
6:    }
7:    int nthUglyNumberGeneral(int n, vector<int>& factors) {
8:      vector<int> uglys(1,1);
9:      vector<int> indexes(factors.size(), 0);
10:      while(uglys.size() < n) {
11:        int min_v = INT_MAX;
12:        int min_index = 0;
13:        for(int k =0; k< factors.size(); k++) {
14:          int temp = uglys[indexes[k]] * factors[k];
15:          if(temp < min_v) {
16:            min_v = temp;
17:            min_index = k;
18:          }
19:        }
20:        indexes[min_index]++;
21:        // need to avoid duplicate ugly number
22:        if(uglys[uglys.size()-1] != min_v) {
23:          uglys.push_back(min_v);
24:         }
25:      }
26:      return uglys[n-1];
27:    }
28:  };
``````

### [Leetcode] Ugly Number, Solution

Write a program to check whether a given number is an ugly number.
Ugly numbers are positive numbers whose prime factors only include `2, 3, 5`. For example, `6, 8` are ugly while `14` is not ugly since it includes another prime factor `7`.
Note that `1` is typically treated as an ugly number.

[Thoughts]

[Code]
``````1:  class Solution {
2:  public:
3:    bool isUgly(int num) {
4:      if (num <= 0) return false;
5:      while (num % 2 == 0) num /= 2;
6:      while (num % 3 == 0) num /= 3;
7:      while (num % 5 == 0) num /= 5;
8:      return num == 1;
9:    }
10:  };
``````