Wenxing’s Blog

Just another WordPress.com weblog

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

 

/*
The key idea is to put every element in A such that A[i]=i
*/
class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        for(int i=0;i<n;i++){
            while(A[i]!=i+1){
                if(A[i] <= 0 || A[i] > n || A[i] == A[A[i]-1]) break;
                int temp = A[i];
                A[i] = A[temp-1];
                A[temp-1] = temp;
            }
        }
        for(int i=0;i<n;i++){
            if(A[i]!=i+1)   return i+1;
        }
        return n+1;
    }
};

Combination Sum II

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 (a1a2, … ,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]

#include <algorithm>

class Solution {
public:
    void getsum(vector<int> & cands, int target, int start, vector<vector<int> > &results, vector<int> path){
        if(target == 0){    // found the sum
            results.push_back(path);
            return;
        }
        if(start >= cands.size() || target < 0)   return; //reach the end of candidates
        if(cands[start] > target)
            getsum(cands, target, start+1, results, path);  //skip this element
        else{
            // exclude cands[start] or any following elements of equal value
            int k = 1;
            while(cands[start+k] == cands[start]) k++;
            getsum(cands,target,start+k,results, path);
            // include cands[start]
            path.push_back(cands[start]);
            getsum(cands,target-cands[start],start+1,results,path);
        }
    }
    vector<vector<int> > combinationSum2(vector<int> &candidates, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > results;
        vector<int> path;

        sort(candidates.begin(),candidates.end());
        getsum(candidates,target,0,results,path);
        return results;
    }
};

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 (a1a2, … ,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]

为了排除重复组合,可以预处理给定数值集合,去掉重复的数。由于每个数可以重复用,重复的数会产生冗余结果,比如{2,2,2}, target=4,结果应该是{2,2},只需要保留一个2,重复用它就行了.如果有多个2,程序不可避免的会产生多个重复的结果{2,2}, {2,2}…

#include <algorithm>

class Solution {
public:
    void getsum(vector<int> & cands, int target, int start, vector<vector<int> > &results, vector<int> path){
        if(target == 0){    // found the sum
            results.push_back(path);
            return;
        }
        if(start >= cands.size() || target < 0)   return; //reach the end of candidates
        if(cands[start] > target)
            getsum(cands, target, start+1, results, path);  //skip this element
        else{
            // exclude cands[start]
            getsum(cands,target,start+1,results, path);
            // include cands[start]
            path.push_back(cands[start]);
            getsum(cands,target-cands[start],start,results,path);
        }
    }
    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> > results;
        vector<int> path;
        getsum(candidates,target,0,results,path);
        for(int i=0; i<results.size(); i++){
            sort(results[i].begin(),results[i].end());
        }
        return results;
    }
};

Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

思路:从头到尾扫描字符串,遇到'(‘计数+1,遇到’)’计数-1,每当计数为0时,我们找到一个有效子串,如果计数<0,从下一个位置开始重新扫描.重复上述过程字符串尾向头扫描.最终最长的有效子串即所求.

class Solution {
public:
    int longestValidParentheses(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = s.length();
        int maxl = 0;
        int count = 0;
        int len = 0;
        for(int i = 0;i < n;i++){
            if(s[i] == '('){
                count++;
                len++;
            }
            if(s[i] == ')') {
                count--;
                len++;
            }
            if(count == 0 && len > maxl){// one valid substring found
                maxl = len;
            }
            else if(count < 0){//invalid pre-fix 
                len = 0;
                count = 0;
            }
        }
        count = 0;
        len = 0;
        for(int i = n-1;i >= 0;i--){
            if(s[i] == ')'){
                count++;
                len++;
            }
            if(s[i] == '(') {
                count--;
                len++;
            }
            if(count == 0 && len > maxl){// one valid substring found
                maxl = len;
            }
            else if(count < 0){//invalid pre-fix 
                len = 0;
                count = 0;
            }
        }
        return maxl;
    }
};

ODF Denoising on SR Manifold

Noisy data before processing. delta=0.1

Smoothed data after processing. delta=0.1

Noisy data before processing. delta=0.2

Smoothed data after processing. delta=0.2

3 Sum

Given an array S of n integers, are there elements abc 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)
为了避免重复记录相同的三元组,在排序好的数组中搜索时每次移指针要跳过连续相同值的区块.
class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > output;
        if(num.size()<3) return output;
        sort(num.begin(),num.end());
        int i=0,j,k,n;
        n=num.size();
        while(i<n){
            if(num[i] > 0){//no solution
                break;
            }
            int temp = 0 - num[i];
            j = i+1;
            k = n-1;
            while(j<k){
                int sum2 = num[j] + num[k];
                if(sum2 == temp){//found one triplet
                    vector<int> triplet;
                    triplet.push_back(num[i]);
                    triplet.push_back(num[j]);
                    triplet.push_back(num[k]);
                    output.push_back(triplet);
                    //Be careful, we want to skip all the duplicate numbers, 
                    //so that no duplicate triplets are recorded
                    j++;
                    while(j<k && num[j-1] == num[j]) j++;
                    k--;
                    while(k>j && num[k+1] == num[k]) k--;
                }
                else if(sum2 > temp){
                    k--;
                    while(k>j && num[k+1] == num[k]) k--;
                }
                else{
                    j++;
                    while(j<k && num[j-1] == num[j]) j++;
                }
            }
            i++;
            while(i<n && num[i-1] == num[i]) i++;
        }
        return output;
    }
};

Remove N-th node from end of list

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.
/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode *p, *q, *pre;
        p=head; pre=p; q=head;
        for(int i=1;i<n;i++){
            if(q->next) q=q->next;
        }
        if(q->next == NULL){//head will be the one to be removed
            head = p->next;
            delete p;
            return head;
        }
        q=q->next;
        p=pre->next;
        while(q->next){
            p=p->next;
            q=q->next;
            pre=pre->next;
        }
        pre->next = p->next;
        delete p;
        return head;
    }
};

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:
    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 l,r;
        l=0; r=n-1;
        int newn = n;
        while(r>0 && A[r] == elem){
            r--; newn--;
        }
        if(A[r]==elem) return 0;

        while(l<r){
            while(A[l]!=elem && l<r) l++;
            if(l==r) break;
            A[l++] = A[r--];
            newn--;
            while(r>0 && A[r] == elem){
                r--; newn--;
            }
        }
        return newn;
    }
};

Merge k sorted lists

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) {}
 * };
 */
#include<priority_queue>
class comp{
public:
    bool operator() (const ListNode* a, const ListNode* b)    { 
        return (a->val > b->val);
    }
};

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int k = lists.size();
        if(k==0) return NULL;
        bool maxheap = false;
        priority_queue<ListNode*, vector<ListNode*>,comp> myheap;
        ListNode * output,*cur;
        for(int i=0;i<k;i++){
            if(lists[i]!=NULL) myheap.push(lists[i]);
        }
        if(myheap.empty()) return NULL;
        output = myheap.top();
        myheap.pop();
        cur = output;
        if(cur->next != NULL) myheap.push(cur->next);
        while(!myheap.empty()){
            cur->next = myheap.top();
            myheap.pop();
            cur = cur->next;
            if(cur->next != NULL) myheap.push(cur->next);
        }
        return output;
    }
};

Regular expression matching

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
class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function 
        if(*s == '' && *p == '') return true;
        if(*s != '' && *p == '') return false;
        while(*(p+1)!='*' && (*s == *p || (*p == '.' && *s!=''))){
            s++; p++;
            if(*s == '' && *p == '') return true;
        }
        if(*(p+1)=='*'){
            if(isMatch(s,p+2)) return true;
            while(*s == *p || (*p == '.' && *s!=''))
                if(isMatch(++s,p+2)) return true;
        }
        return false;
    }
};