Combination Sum II -- Leetcode

Question:

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8, 
A solution set is: 
[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6] 

Answer:
Using the code for Combination Sum, differentce:
1. just add while() loop code to avoid push the same element in a same level in DFS when pop back an element in a level.
2. for the further level, the start index should be (i+1) instead of (i), as each element can only be used once!

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        sort(num.begin(),num.end());
        vector<int> subres;
        vector<vector<int>> res;
        conbinationSumDFS(subres,res,num,0,target);
        return res;
    }
 
    void conbinationSumDFS(vector<int> &subres, vector<vector<int>> &res, vector<int> &num, int start, int sum){
        if(sum==0){
            res.push_back(subres);
            return;
        }
     
        for(int i= start; i< num.size();++i){
            if(num[i] <= sum){
                subres.push_back(num[i]);
                conbinationSumDFS(subres,res,num,i+1,sum-num[i]);   //Note the start index is i+1, for each ele can only be used once!
                subres.pop_back();
               
                while(i+1 < num.size() && num[i] == num[i+1]){    //To avoid push same element in a same level.
                    ++i;
                }
            }
            else
                break;
        }
        return;
    }
};

Combination Sum -- Leetcode

Question:

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3] 

Answer:
DFS method, using backtrack!
Note: each element can be used for more than one time!

class Solution {
public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<int> subres;
        vector<vector<int>> res;
        conbinationSumDFS(subres,res,candidates,0,target);
        return res;
    }
   
    void conbinationSumDFS(vector<int> &subres, vector<vector<int>> &res, vector<int> &candidates, int start, int sum){
        if(sum==0){
            res.push_back(subres);
            return;
        }
       
        for(int i= start; i< candidates.size();++i){
            if(candidates[i] <= sum){
                subres.push_back(candidates[i]);
                conbinationSumDFS(subres,res,candidates,i,sum-candidates[i]);   //Note the start index is i !!!
                subres.pop_back();
            }
            else
                break;
        }
        return;
    }
};

3 Sum Closest -- Leetcode

Question:

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Answer:
Similar to "3 Sum", additionally add a minv to track |a+b+c-target|, find the smallest value.

class Solution {
public:
  int threeSumClosest(vector<int> &num, int target) {
    int minv = INT_MAX, res;
    int flag = 0;
    sort(num.begin(), num.end());
   
    for (int i = 0;i < num.size(); i++) {
        if(i>0 && num[i]==num[i-1]) continue;
       
        int j = i + 1;
        int k = num.size() - 1;
        while (j < k) {
            int sum = num[i] + num[j] + num[k];
            if ( sum < target) {
                if(target - sum < minv){
                    minv = target - sum;
                    res = sum;
                }
                j++;
            }
            else if ( sum > target) {
                if(sum - target < minv){
                    minv = sum - target;
                    res = sum;
                }
                k--;
            }
            else {
                minv = 0;
                res = sum;
                flag = 1;
                break;
            }
        }
        if(flag)break;
    }
    return res;
    }
};

[Facebook] Products of all elements

Question：

Given an array of numbers, nums, return an array of numbers products, where products[i] is the product of all nums[j], j != i.

Input : [1, 2, 3, 4, 5]

Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]

      = [120, 60, 40, 30, 24]

You must do this in O(N) without using division.

[Thoughts]

An explaination of polygenelubricants method is: The trick is to construct the arrays (in the case for 4 elements)

{              1,         a[0],    a[0]*a[1],    a[0]*a[1]*a[2],  }
{ a[1]*a[2]*a[3],    a[2]*a[3],         a[3],                 1,  }

Both of which can be done in O(n) by starting at the left and right edges respectively.
Then multiplying the two arrays element by element gives the required result
My code would look something like this:

int a[N] // This is the input
int products_below[N];
p=1;
for(int i=0;i<N;++i)
{
  products_below[i]=p;
  p*=a[i];
}

int products_above[N];
p=1;
for(int i=N-1;i>=0;--i)
{
  products_above[i]=p;
  p*=a[i];
}

int products[N]; // This is the result
for(int i=0;i<N;++i)
{
  products[i]=products_below[i]*products_above[i];
}

If you need to be O(1) in space too you can do this (which is less clear IMHO)

int a[N] // This is the input
int products[N];

// Get the products below the curent index
p=1;
for(int i=0;i<N;++i)
{
  products[i]=p;
  p*=a[i];
}

// Get the products above the curent index
p=1;
for(int i=N-1;i>=0;--i)
{
  products[i]*=p;
  p*=a[i];
}

转自：

http://fisherlei.blogspot.com/2013/01/facebook-products-of-all-elements.html

Inorder Successor in BST -- PG

Question:

In Binary Tree, Inorder successor of a node is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inoorder traversal.
In Binary Search Tree, Inorder Successor of an input node can also be defined as the node with the smallest key greater than the key of input node. So, it is sometimes important to find next node in sorted order.

In the above diagram, inorder successor of 8 is 10, inorder successor of 10 is 12 and inorder successor of 14 is 20.

Answer:

Method 1 (Uses Parent Pointer) 
In this method, we assume that every node has parent pointer.
The Algorithm is divided into two cases on the basis of right subtree of the input node being empty or not.
Input: node, root // node is the node whose Inorder successor is needed.
output: succ // succ is Inorder successor of node.
1) If right subtree of node is not NULL, then succ lies in right subtree. Do following.
Go to right subtree and return the node with minimum key value in right subtree.
2) If right sbtree of node is NULL, then succ is one of the ancestors. Do following.
Travel up using the parent pointer until you see a node which is left child of it’s parent. The parent of such a node is the succ.

Implementation
Note that the function to find InOrder Successor is highlighted (with gray background) in below code.

1:  #include <stdio.h>  
2:  #include <stdlib.h>  
3:  /* A binary tree node has data, pointer to left child  
4:    and a pointer to right child */  
5:  struct node  
6:  {  
7:    int data;  
8:    struct node* left;  
9:    struct node* right;  
10:    struct node* parent;  
11:  };  
12:  struct node * minValue(struct node* node);  
13:  struct node * inOrderSuccessor(struct node *root, struct node *n)  
14:  {  
15:   // step 1 of the above algorithm  
16:   if( n->right != NULL )  
17:    return minValue(n->right);  
18:   // step 2 of the above algorithm  
19:   struct node *p = n->parent;  
20:   while(p != NULL && n == p->right)  
21:   {  
22:     n = p;  
23:     p = p->parent;  
24:   }  
25:   return p;  
26:  }  
27:  /* Given a non-empty binary search tree, return the minimum data   
28:    value found in that tree. Note that the entire tree does not need  
29:    to be searched. */  
30:  struct node * minValue(struct node* node) {  
31:   struct node* current = node;  
32:   /* loop down to find the leftmost leaf */  
33:   while (current->left != NULL) {  
34:    current = current->left;  
35:   }  
36:   return current;  
37:  }  

Time Complexity: O(h) where h is height of tree.


Method 2 (Don't Use Parent Pointer)
Inorder travel the tree and
1) If current visit node is target node,  mark the indicator as true.
2) If indicator is true, print the node and return.

Implementation

1:  struct node * inOrderSuccessor(struct node *n, struct node* target, bool& indicator)  
2:  {  
3:   if( n== NULL )  
4:    return NULL;  
5:   if(indicator) return n;  
6:   if(n == target) { indicator = true; return;}  
7:   node* left = inOrderSuccessor(n->left, target, indicator);  
8:   node * right =inOrderSuccessor(n->right, target, indicator);  
9:   if(left != NULL) return left;  
10:   if(right!= NULL) return right;  
11:   return NULL;  
12:  }  

转自：

http://fisherlei.blogspot.com/search/label/google

4 Sum -- Leetcode

Question:

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

Answer:

Just like "3 Sum" problem, sort the array firstly, suppose a+b+c+d = target, choose a firstly, then b secondly, then using "2 Sum" method, keep 2 pointers, in the left right elements, to find c+d == target - a -b.

Time : O(n*n*n), Space: O(1).

class Solution {

public:

    vector<vector<int> > fourSum(vector<int> &num, int target) {

        int n=num.size();

        vector<int> quadruplet(4);

        vector<vector<int>> res;

        if(n<4)return res;

        

        sort(num.begin(),num.end());

        

        for(int i=0;i<n-3;++i){

            if(i>0 && num[i]==num[i-1])continue;

            for(int j=i+1;j<n-2;++j){

                if(j>i+1 && num[j]==num[j-1])continue;

                

                int l= j+1;

                int r= n-1;

                while(l < r){

                    if(l > j+1 && num[l]==num[l-1]) {

                        l++;

                    }

                    else if( r < n-1 && num[r]==num[r+1]){

                        r--;

                    }

                    else if(num[i]+num[j]+num[l]+num[r]< target){

                        l++;

                    }

                    else if(num[i]+num[j]+num[l]+num[r] > target){

                        r--;

                    }

                    else{

                        quadruplet[0]=num[i];

                        quadruplet[1]=num[j];

                        quadruplet[2]=num[l];

                        quadruplet[3]=num[r];

                        res.push_back(quadruplet);

                        l++;

                        r--;

                    }

                }

            }

        }

    }

};

3 Sum -- Leetcode

Question:

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Answer:
Similar to "2 Sum", sort the array firstly, a + b + c = t, choose (a) from array every time, then find from the left right elements for b and c whose sum to be (t-a), using two pointer method here.
Note: there exists duplicate elements in the array, so we need to avoid duplicate triplets in the solution result!

vector<vector<int> > threeSum(vector<int> &num) {
    sort(num.begin(), num.end());
 
    vector<vector<int> > triplets;
    vector<int> triplet(3,INT_MIN);
 
    for (int i = 0;i < num.size(); i++) {
        if(i>0 && num[i]==num[i-1]) continue;     // To avoid duplicate triplets!
     
        int j = i + 1;
        int k = num.size() - 1;
        while (j < k) {
            if (num[i] + num[j] + num[k] < 0) {
                j++;
            } else if (num[i] + num[j] + num[k] > 0) {
                k--;
            } else {
                if(num[j]!=triplet[1] || num[k]!=triplet[2]){       // To avoid duplicate triplets!
                    triplet[0] = num[i];
                    triplet[1] = num[j];
                    triplet[2] = num[k];
                    triplets.push_back(triplet);
                }
                j++;
                k--;
            }
        }
    }
    return triplets;
}

Two Sum -- Leetcode

Question:

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Solution:

1. Two pointer method, sort the array firstly. O(nlogn) time + O(1) space.
class Solution {
public:
    bool mycmp(int i, int j){
          return (i<j);
    }

    vector<int> twoSum(vector<int> &numbers, int target) {
              std::sort(numbers.begin(),numbers.end(),mycmp);
              vector<int> res;
              int i=0,j=numbers.size()-1;
              while(i<j){
                   if(numbers[i]+numbers[j]<target) i++;
                   else if(numbers[i]+numbers[j]>target) j++;
                   else {
                       res.push_back(i+1);
                       res.push_back(j+1);
                       break;
                   }
              }  
      }

};

2. Hash Map method. O(n) time + O(n) space.
class Solution {
public:
    vector<int> twoSum(vector<int> &numbers,int target){
        map<int,int> mmap;
        vector<int> res;
       
        for(int i=0;i<numbers.size();++i){
            mmap[numbers[i]]=i;
        }
       
        for(int i=0;i<numbers.size();++i){
            int p = target - numbers[i];
            if(mmap.find(p)!=mmap.end()){
                if(i<mmap[p]){
                    res.push_back(i+1);
                    res.push_back(mmap[p]+1);
                }
                else  if(i>mmap[p]){
                    res.push_back(mmap[p]+1);
                    res.push_back(i+1);
                }
            }
        }
        return res;
    }
};

Regular Expression Matching -- Leetcode

Question:

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Solution:

class Solution {

public:

   bool isMatch(const char *s, const char *p) {    

        if( *p == 0) return *s == 0;

        if(*(p+1) != '*'){                                         //One step match way.
            if(*s == *p || (*p) == '.' && (*s) != 0)
            {
                return isMatch(s+1, p+1);
            }
            return false;
        }
     
        else{                                          //*,multiple steps match way. while()s++....until(isMatch(s,p+2).
            while(*s == *p || ((*p) == '.') && (*s) != 0)
            {
                if(isMatch(s, p + 2))               //Forward check!!!
                {
                    return true;
                }
                s++;
            }
            return isMatch(s, p + 2);                //*,multiple steps match function has ended.
        }
    }
};

dp[i][j]表示字串 s[i...len(s)], p[j...len(p)] 是否可以匹配。

那么状态转移方程如下：

dp[i][j] = 

c1. p[j+1] != *.   if s[i] == p[j]  dp[i][j] = dp[i+1][j+1] 

                       else dp[i][j] = false

c2 p[j+1] == '*'  (这个情况下，要扩展 *, dp[i][j] 从拓展的情况下，选择一个是真的结果）

                       if( s[i] ==  p[j] || p[j] == '.' && (*s) != 0)  当s[i] 和 p[j] 一样的时候，例如 aba, a*b这个时候，i = 0, j = 0, 自然可以匹配a a

                      如果p[j] == .  因为他可以匹配任何字符，所以和相等关系有基本一样的方式。

                       并且每一步匹配都要递增 i 的值，如果有成立的，则返回true，否则到匹配终了，返回通配符匹配完成后的结果。

Max SubArray -- Leetcode

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

» Solve this problem

[解题思路]
O(n)就是一维DP.
假设A(0, i)区间存在k，使得[k, i]区间是以i结尾区间的最大值， 定义为Max[i], 在这里，当求取Max[i+1]时，
Max[i+1] = Max[i] + A[i+1],  if (Max[i] + A[i+1] >0)
                = 0, if(Max[i]+A[i+1] <0)，如果和小于零，A[i+1]必为负数，没必要保留，舍弃掉
然后从左往右扫描，求取Max数字的最大值即为所求。

[Code]

1:    int maxSubArray(int A[], int n) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int sum = 0;  
5:      int max = INT_MIN;  
6:      for(int i =0; i < n ; i ++)  
7:      {  
8:        sum +=A[i];        
9:        if(sum>max)  
10:          max = sum;  
11:        if(sum < 0)  
12:          sum = 0;  
13:      }  
14:      return max;  
15:    }  

但是题目中要求，不要用这个O(n)解法，而是采用Divide & Conquer。这就暗示了，解法必然是二分。分析如下：

假设数组A[left, right]存在最大值区间[i, j](i>=left & j<=right)，以mid = (left + right)/2 分界，无非以下三种情况：

subarray A[i,..j] is
(1) Entirely in A[low,mid-1]
(2) Entirely in A[mid+1,high]
(3) Across mid
对于(1) and (2)，直接递归求解即可，对于(3)，则需要以min为中心，向左及向右扫描求最大值，意味着在A[left, Mid]区间中找出A[i..mid], 而在A[mid+1, right]中找出A[mid+1..j]，两者加和即为(3)的解。

代码实现如下：

1:    int maxSubArray(int A[], int n) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int maxV = INT_MIN;  
5:      return maxArray(A, 0, n-1, maxV);      
6:    }  
7:    int maxArray(int A[], int left, int right, int& maxV)  
8:    {  
9:      if(left>right)  
10:        return INT_MIN;  
11:      int mid = (left+right)/2;  
12:      int lmax = maxArray(A, left, mid -1, maxV);  
13:      int rmax = maxArray(A, mid + 1, right, maxV);  
14:      maxV = max(maxV, lmax);  
15:      maxV = max(maxV, rmax);  
16:      int sum = 0, mlmax = 0;  
17:      for(int i= mid -1; i>=left; i--)  
18:      {  
19:        sum += A[i];  
20:        if(sum > mlmax)  
21:          mlmax = sum;  
22:      }  
23:      sum = 0; int mrmax = 0;  
24:      for(int i = mid +1; i<=right; i++)  
25:      {  
26:        sum += A[i];  
27:        if(sum > mrmax)  
28:          mrmax = sum;  
29:      }  
30:      maxV = max(maxV, mlmax + mrmax + A[mid]);  
31:      return maxV;  
32:    }  

[注意]
考虑到最大和仍然可能是负数，所以对于有些变量的初始化不能为0，要为INT_MIN。

转自：

http://fisherlei.blogspot.com/search/label/DP

palindrome partitioning II -- Leetcode

Question:

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Answer:

1. Recursion method: For large set, time limit exceeded.

class Solution {

public:

    int minCut(string s) {

        vector<string> result=minpalindromepartiton(s);

        return result.size();

    }

    

    vector<string> minpalindromepartiton(string s){

    vector<string> res;

    vector<string> vs;

     if(s.length()==0){

         return res;

     }

     if(s.length()==1){

         res.push_back(s);

         return res;

     }

     

     int count=INT_MAX;

     int k=1;

     

     for(int i=1;i<=s.length();++i){            

        if(ispalindrome(s.substr(0,i))){

            vs=minpalindromepartiton(s.substr(i,s.length()-i));

            

            if(vs.size()<count){

                count=vs.size();

                k=i;

            }

        }            

    }

    if(count==0){

        res.push_back(s);

    }

    else{

        vs=minpalindromepartiton(s.substr(k,s.length()-k));

        vs.insert(vs.begin(),s.substr(0,k));

        res=vs;

    }        

    return res;      

    }

    

    bool ispalindrome(string s){

       for(int i=0;i<s.length();++i){

        if(i<=s.length()/2){

          if(s[i]!=s[s.length()-i-1])

          return false;

        }

        else break;

       }

       return true;

    } 

};

2.DP method: Optimal time solution.

 class Solution{
public:
int minCut(string s) {
     
       int leng = s.size();

        int dp[leng+1];
        bool palin[leng][leng];

      for(int i = 0; i <= leng; i++)
        dp[i] = leng-i;
        for(int i = 0; i < leng; i++)
            for(int j = 0; j < leng; j++)
                palin[i][j] = false;

      for(int i = leng-1; i >= 0; i--){
        for(int j = i; j < leng; j++){
          if(s[i] == s[j] && (j-i<2 || palin[i+1][j-1])){
            palin[i][j] = true;
            dp[i] = min(dp[i],dp[j+1]+1);
          }
        }
      }
      return dp[0]-1;
    }
};