Combination Sum

/*

Combination Sum

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 (a₁, a₂, � , a_k) must be in non-descending order. (ie, a₁ ? a₂ ? � ? a_k).
• 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]

*/
class Solution {
public:
    vector<vector<int>> findSum(vector<int> candidates, int size, int target){
       vector<vector<int>> result;
       if(size==-1) return result;
       result = findSum(candidates, size-1, target);
       int elem = candidates[size];
       int num;
       vector<int> newComb;
       if(elem > target) return result;
      
       num = target/elem;
       if(target%elem == 0){
          newComb.insert(newComb.begin(), num, elem);
          result.push_back(newComb);
       }
       vector<vector<int>> inter;
      
       int j;
       int i;
       for(j=1; j<=num; j++){
       inter = findSum(candidates, size-1, target-j*elem);
       for(i=0; i<inter.size(); i++){
         inter[i].insert(inter[i].begin()+inter[i].size(), j, elem);
       }
       result.insert(result.begin()+result.size(), inter.begin(), inter.end());
       }
      
       return result;
    }
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int>> result;
        if(target<=0) return result;
        int size = candidates.size();
        int i;
        set<int> inter;
        for(i=0; i<size; i++){
         inter.insert(candidates[i]);
        }
        candidates.clear();
        set<int>::iterator it;
        for(it=inter.begin(); it!=inter.end(); it++){
         candidates.push_back(*it);
        }
        return  findSum(candidates, size-1, target);
    }
};

Remove Duplicates from Sorted Array

/*

Remove Duplicates from Sorted ArrayFeb 16 '12

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

*/
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(n==0 || n==1) return n;
        int i;
        int const Impossible = -500;
        int curr;
       
        curr = A[0];
        for(i=1; i<n; i++){
            if(A[i]==curr){
                A[i] = Impossible;
            } else {
                curr = A[i];
            }
        }
        int pos = 1;
        while(A[pos]!=Impossible && pos<n){
            pos++;
        }
        if(pos==n) return n;
       
        curr = pos+1;
        while(curr<n){
            while(A[curr]==Impossible && curr<n){
              curr++;
            }
            if(curr!=n){
              A[pos] = A[curr];
              A[curr] = Impossible;
              while(A[pos]!=Impossible && pos<n){
                  pos++;
              }
            }
        }
       
        if(A[pos]==Impossible) return pos;
        else return pos+1;
    }
};

Merge k Sorted Lists

/*

Merge k Sorted ListsFeb 14 '12

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = lists.size();
        if(size==0) return NULL;
        if(size==1 && lists[0]!=NULL) return lists[0];
        if(size==1 && lists[0]==NULL) return NULL;
        int const MaxVal = 500;
       
        int i;
        ListNode *node = NULL;
        ListNode *curr = NULL;
        int currVal = MaxVal;
        int k = -1;
        for(i=0; i<size; i++){
            if(lists[i]!=NULL){
                if(lists[i]->val < currVal){
                    currVal = lists[i]->val;
                    curr = lists[i];
                    k = i;
                }
            }
        }
        if(k!=-1){
            node = lists[k];
            lists[k] = lists[k]->next;
        }
        if(node!=NULL) node->next = mergeKLists(lists);
       
        return node;
    }
};

Swap Nodes in Pairs

/*

Swap Nodes in PairsFeb 15 '12

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(head==NULL) return NULL;
        if(head->next == NULL) return head;
        ListNode *first = head;
        ListNode *second = head->next;
        int temp;
        while(first!=NULL && second!=NULL){
            temp = first->val;
            first->val = second->val;
            second->val = temp;
            first = second->next;
            if(first!=NULL) second = first->next;
        }
       
        return head;
    }
};

Convert Sorted List to Binary Search Tree

/*

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
TreeNode *findMidNode(ListNode *head){
        if(head==NULL) return NULL;
    ListNode *prev = NULL;
        ListNode *curr = head;
        ListNode *tail = curr->next;
        if(tail!=NULL) tail = tail->next;
        while(tail!=NULL){
prev = curr;
            curr = curr->next;
            tail = tail->next;
            if(tail!=NULL) tail = tail->next;
        }
if(curr==NULL) return NULL;
TreeNode *node = new TreeNode(curr->val);
        if(prev!=NULL) prev->next = NULL;
        if(head!=curr) node->left = findMidNode(head);
        node->right = findMidNode(curr->next);
        return node;
    }
   
    TreeNode *sortedListToBST(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(head==NULL) return NULL;
        if(head->next==NULL){
           TreeNode* root = new TreeNode(head->val);
           return root;
        }
       
        return findMidNode(head);
    }
};

Longest Consecutive Sequence

/*

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.

*/
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = num.size();
        if(size==0) return 0;
        if(size==1) return 1;
        int const MaxNum = 50000;
        int const offset = MaxNum/2;
        vector<bool> existNum;
        existNum.insert(existNum.begin(), MaxNum, false);
        int i;
        for(i=0; i<size; i++){
          if((num[i]+offset) > MaxNum || (num[i]+offset) <0 ) return 0;
          existNum[num[i]+offset] = true;
        }
        int longest = 0;
        int currSum = 0;
        for(i=0; i<MaxNum; i++){
           if(i==0 && existNum[i]==true){
             currSum = 1;
           }
           if(i>0 && existNum[i-1]==true && existNum[i]==1){
            currSum++;
           }
           if(i>0 && existNum[i-1]==0 && existNum[i]==1){
            currSum = 1;
           }
           if(i>0 && existNum[i-1]==1 && existNum[i]==0){
            longest = max(longest, currSum);
            currSum = 0;
           }
          
           if(i==MaxNum-1){
            longest = max(longest, currSum);
           }
        }
       
        return longest;
    }
};

move Element

/*

Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.

*/
class Solution {
public:
    void swap(int A[], int i, int j){
      int temp = A[i];
      A[i] = A[j];
      A[j] = temp;
    }
    int removeElement(int A[], int n, int elem) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(n<=0) return 0;
       
        int i = 0;
       
        while(i<n && A[i]!=elem){
          i++;
        }
       
        if(i==n) return n;
       
        int j = n-1;
        while(j>=0 && A[j]==elem){
          j--;
        }
       
        if(j==-1) return 0;
       
        if(i>=j) return i;
               
        int pos = 0;              
        while(i<j){
          swap(A, i, j);
          pos = i;
          i++;
          j--;
          while(i<n && A[i]!=elem){
           i++;
          }
          while(j>=0 && A[j]==elem){
           j--;
          }
        }
       
        while(pos<n && A[pos]!=elem){
         pos++;
        }
        return pos;
    }
};