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

1. 数组中有一个以上的0出现， 比如 [1,2, 0, 0, 3, 4]， 最后的结果肯定都是0： [0,0,0,0,0,0]
2. 数组中有一个0出现，比如[1,2,0,3,4]，按照题目的定义，最后的输出结果是[0,0,24,0,0]. 除了0的那一位是有值，其他位都是0
3. 数组中没有0， 假设数组位[a0, a1, a2, ......], 其中所有数值的乘积为M， 那个数组的输出就是[M/a0, M/a1, M/a2.....].

[Code]
``````1:    vector<int> productExceptSelf(vector<int>& nums) {
2:      int64_t product = 1;
3:
4:      int zeros = 0;
5:      for(int i =0; i< nums.size(); i++) {
6:        if(nums[i] == 0){
7:          zeros++;
8:          continue;
9:        }
10:        product *= nums[i];
11:      }
12:
13:      vector<int> result;
14:      for(int i =0; i< nums.size(); i++) {
15:        if(zeros > 1) {
16:          result.push_back(0);
17:          continue;
18:        } else if( zeros == 1){
19:          if(nums[i] == 0) result.push_back(product);
20:          else result.push_back(0);
21:          continue;
22:        }
23:
24:        result.push_back(product/nums[i]);
25:      }
26:
27:      return result;
28:    }
``````

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

## Friday, October 2, 2015

### [Leetcode] Move Zeroes, Solution

Given an array `nums`, write a function to move all `0`'s to the end of it while maintaining the relative order of the non-zero elements.
For example, given `nums = [0, 1, 0, 3, 12]`, after calling your function, `nums` should be `[1, 3, 12, 0, 0]`.
Note:
1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

[Thoughts]

[Code]
``````1:  class Solution {
2:  public:
3:    void moveZeroes(vector<int>& nums) {
4:      for(int zero_index = 0, none_zero_index = 0;
5:        none_zero_index < nums.size() && zero_index < nums.size();
6:      ) {
7:        if(nums[zero_index] != 0) {
8:          zero_index++;
9:          none_zero_index = zero_index;
10:          continue;
11:        }
12:        if(nums[none_zero_index] == 0) {
13:          none_zero_index++;
14:          continue;
15:        }
16:        int temp = nums[zero_index];
17:        nums[zero_index] = nums[none_zero_index];
18:        nums[none_zero_index] = temp;
19:        zero_index++;
20:        none_zero_index++;
21:      }
22:    }
23:  };
``````

git: https://github.com/codingtmd/leetcode/blob/master/src/Move_Zeroes.cpp

### [Leetcode] Peeking Iterator, Solution

Given an Iterator class interface with methods: `next()` and `hasNext()`, design and implement a PeekingIterator that support the `peek()` operation -- it essentially peek() at the element that will be returned by the next call to next().

Here is an example. Assume that the iterator is initialized to the beginning of the list: `[1, 2, 3]`.
Call `next()` gets you 1, the first element in the list.
Now you call `peek()` and it returns 2, the next element. Calling `next()` after that still return 2.
You call `next()` the final time and it returns 3, the last element. Calling `hasNext()` after that should return false.

[Thoughts]

[Code]
``````1:  // Below is the interface for Iterator, which is already defined for you.
2:  // **DO NOT** modify the interface for Iterator.
3:  class Iterator {
4:    struct Data;
5:       Data* data;
6:  public:
7:       Iterator(const vector<int>& nums);
8:       Iterator(const Iterator& iter);
9:       virtual ~Iterator();
10:       // Returns the next element in the iteration.
11:       int next();
12:       // Returns true if the iteration has more elements.
13:       bool hasNext() const;
14:  };
15:  class PeekingIterator : public Iterator {
16:  public:
17:       PeekingIterator(const vector<int>& nums) : Iterator(nums) {
18:         // Initialize any member here.
19:         // **DO NOT** save a copy of nums and manipulate it directly.
20:         // You should only use the Iterator interface methods.
21:         this->length = nums.size();
22:         this->nums = &nums;
23:       }
24:       // Returns the next element in the iteration without advancing the iterator.
25:       int peek() {
26:         if(currentIndex < length) {
27:           return (*this->nums)[currentIndex];
28:         }
29:         return -1;
30:       }
31:       // hasNext() and next() should behave the same as in the Iterator interface.
32:       // Override them if needed.
33:       int next() {
34:         if(currentIndex < length) {
35:           currentIndex ++;
36:           return (*this->nums)[currentIndex-1];
37:         }
38:         return -1;
39:       }
40:       bool hasNext() const {
41:         return currentIndex < length;
42:       }
43:  private:
44:    int currentIndex = 0;
45:    int length = 0;
46:    const vector<int>* nums = NULL;
47:  };
``````

github：https://github.com/codingtmd/leetcode/blob/master/src/Peeking_Iterator.cpp

### [Leetcode] Find the Duplicate Number, Solution

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Note:
1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than `O(n2)`.
4. There is only one duplicate number in the array, but it could be repeated more than once.

[Thoughts]

[Code]
``````1:  class Solution {
2:  public:
3:    int findDuplicate(vector<int>& nums) {
4:      int length = nums.size();
5:      for(int i =0; i< length; i++) {
6:        if(nums[i] == i+1) {
7:          continue;
8:        }
9:        int oldIndex = i;
10:        int newIndex = nums[i]-1;
11:        while(nums[oldIndex] != oldIndex +1 ) {
12:          if(nums[oldIndex] == nums[newIndex] ) {
13:            return nums[oldIndex];
14:          }
15:          int temp = nums[newIndex];
16:          nums[newIndex] = nums[oldIndex];
17:          nums[oldIndex] = temp;
18:          newIndex = nums[oldIndex] -1;
19:        }
20:      }
21:    }
22:  };
``````

github: https://github.com/codingtmd/leetcode/blob/master/src/Find_the_Duplicate_Number.cpp