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

Follow up:
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]

一般这种题都可以分解成若干子问题来解决。As defined, 

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

简单的说

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

问题就解决了，首先从前往后扫描数组一遍，对每一个i，得到{i 前面的数的乘积}(可以称做output_before)，然后在从后往前扫描数组一遍，获得 { i 后面的数的乘积}(可以称做output_after)。 将两数相乘即为所求。

举个例子(如下图)，nums = {1,2,3,4}, 第一遍，从前往后扫描一遍，得到的output_before = {1, 1, 2, 6}. 从后往前扫描一遍，得到的output_after = {24, 12, 4, 1}.

那么  output [i] = output_before[i] * output_after[i],   output = {24, 12, 8, 6}

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

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

对于字符出现次数做个统计就好了。因为只有26个小写字母，所以可以建立一个大小为26的索引数组charcount，用来统计每个字符的出现次数。

对于s, 将其作为字符数组进行遍历，在遍历的过程中，对每个出现的字符计数加一。

对于t， 同样将其遍历，对每个出现的字符计数减一。

如果s和t是anagram ， 那么最后的charcount数组中所有字符的计数都应该是0， 否则就不是anagram。

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

Github: https://github.com/codingtmd/leetcode/blob/master/src/Valid%20Anagram.cpp

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

关于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

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

这就是多链表Merge Sort的一个扩展题。

对于任意一个ugly number - K, 2*K, 3*K, 和5*K都是ugly number，所以说新的ugly number都是从已有的ugly number上，通过与{2,3,5}相乘而产生的。

如果

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

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

                             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

都是ugly number。只要不断把新产生的ugly number通过merge sort添加到原有的ugly number数组中就可以了，直到找到第N个。

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

考虑到通用性，可以扩展如下，可以支持任意长度的因子数组factors。

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

从空间的优化来说，没有必要用一个uglys的数组保存所有的ugly number，尤其是当n是个非常大的数字。对于indexes指针扫过的ugly number，都可以丢掉了。不过，懒得写了。

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

这题简单。既然已经说了ugly number是{2,3,5}的组合乘积构成的，那么判断逻辑也就简单了，对于任意一个给定的数字，拼命除这三个因子，最后能整除的就是ugly number，否则就不是。

逻辑看code

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

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

典型的双指针问题。使用两个指针遍历数组，一个指向数值为0的元素，另一个指向数值不为0的元素，在遍历的过程中，不断交换两个指针的值。

例如，

比较简单的一道题。

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

链表的一道设计题。next其实在这里就是获取头元素的值，并移动到下一个元素。peek在这里就是返回当前元素的值。

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

这题想清楚了就不难，想不清楚就麻烦。

假设数组A长度是n, 里面存储1到n的整数，那么很清楚，我们可以在按照A[i] = i+1，进行排序。但是现在有n+1个整数，而且至少有一个数字存在冗余。如果我们仍然按照A[i] = i+1来排序数组的话，那么当发现A[i]上已经是i+1的值时，说明我们已经找到了冗余数了。

举个例子，

简单的说，就是遍历数组的同时，按照A[i]应该放到A[A[i]]原则，进行swap，第一个无法swap的数字就是所求。

[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