Showing posts with label merge. Show all posts
Showing posts with label merge. Show all posts

Saturday, January 4, 2014

Day 74, ##, Sort List, Evaluate Reverse Polish Notation

Sort List
Sort a linked list in O(n log n) time using constant space complexity.
-----------------------------------------------------------------
Solution #1, recursive merge sort
wiki page has iterative buttom-up method
http://en.wikipedia.org/wiki/Merge_sort
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge (ListNode *&left, ListNode *&right) {
        ListNode* dummy = new ListNode(INT_MIN); // dummy
        ListNode* itr = dummy;
        while (left != NULL && right != NULL) {
            if (left->val <= right->val) {
                itr->next = left;
                itr = left;
                left = left->next;
            }else {
                itr->next = right;
                itr = right;
                right = right->next;
            }
        }
        if (right == NULL) itr->next = left;
        if (left == NULL) itr->next = right;
        return dummy->next;
    }

    ListNode *sortList(ListNode *head) {
        // divide
        if (head == NULL || head->next == NULL) {
            return head;
        }
        
        ListNode *slow = head, *fast = head->next;
        while (fast != NULL) {
            fast = fast->next;
            if (fast != NULL) {
                fast = fast->next;
                slow = slow->next;
            }
        }
        ListNode *second = slow->next;
        slow->next = NULL;
        
        head = sortList(head);
        second = sortList(second);
        
        // merge
        return merge(head,second);
    }
};
Update Jan-5-2015
dummy should be deleted in merge

Evaluate Reverse Polish Notation
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
----------------------------------------------------
post order, using stack
注意从stack出来时的顺序,RPN是最先进stack的在前面。
class Solution {
public:
    int arith (int op1, int op2, string opt) {
        if (opt == "+") {
            return op1 + op2;
        }else if (opt == "-") {
            return op1 - op2;
        }else if (opt == "*") {
            return op1 * op2;
        }else if (opt == "/") {
            return op1 / op2;
        }
    }

    int evalRPN(vector<string> &tokens) {
        stack<int> s;
        int num = 0;
        for (int i = 0; i < tokens.size(); i++) {
            if (isdigit(tokens[i][0]) || (tokens[i].length() > 1 && isdigit(tokens[i][1]))) {
                num = atoi(tokens[i].c_str());
            }else {
                int operand1 = s.top();
                s.pop();
                int operand2 = s.top();
                s.pop();
                num = arith(operand2,operand1,tokens[i]);
            }
            s.push(num);
        }
        return num;
    }
};

Saturday, December 21, 2013

Day 61, #56, #57, Merge Intervals, Insert Interval

Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
----------------------------------------------------------------
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    static bool comp (const Interval &i1, const Interval &i2) {
        return i1.start < i2.start;
    }

    vector<Interval> merge(vector<Interval> &intervals) {
        sort(intervals.begin(),intervals.end(),comp);
        vector<Interval> ret;
        
        if (intervals.size() == 0) {
            return ret;
        }
        
        ret.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i].start <= ret.back().end) {
                if (intervals[i].end > ret.back().end) {
                    ret.back().end = intervals[i].end;
                }
            }else {
                ret.push_back(intervals[i]);
            }
        }
        return ret;
    }
};
Insert Interval
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
------------------------------------------------------------ 
Solution#1
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> ret;
        int index = 0;
        int size = intervals.size();
        
        while (index < size && newInterval.start > intervals[index].end) {
            ret.push_back(intervals[index]);
            index++;
        }
        
        // deal with overlapping
        while (index < size && newInterval.end >= intervals[index].start ) {
            newInterval.start = min(newInterval.start,intervals[index].start);
            newInterval.end = max(newInterval.end,intervals[index].end);
            index++;
        }
        
        ret.push_back(newInterval);
        // push in the rest
        while (index < size) {
            ret.push_back(intervals[index]);
            index++;
        }
        return ret;
    }
};
Solution#2 -- in place
do it later

Monday, April 8, 2013

Day 12, 21 Merge Two Sorted Lists

Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
 ---------------------------------
Solution #1
handle 2 special cases at the beginning,
1) either l1 or l2 is NULL, or both are NULL
2) either l1 or l2 has only one element, or both have only one element

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (l1 == NULL) {
            return l2;
        }
        if (l2 == NULL) {
            return l1;
        }
        
        ListNode *saved, *pre;
        if (l1->val < l2->val) {
            saved = l1;
            pre = l1;
            l1 = l1->next;
            pre->next = l2;
        }else {
            saved = l2;
            pre = l2;
            l2 = l2->next;
            pre->next = l1;
        }
        
        while (l1 != NULL && l2 != NULL) {
            if (l1->val < l2->val) {
                pre->next = l1;
                pre = l1;
                l1 = l1->next;
                pre->next = l2;
            }else {
                pre->next = l2;
                pre = l2;
                l2 = l2->next;
                pre->next = l1;
            }
        }
        return saved;
    }
};

Solution #2
recursion
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (l1 == NULL) {
            return l2;
        }
        if (l2 == NULL) {
            return l1;
        }
        ListNode *re;
        if (l1->val < l2->val) {
            re = l1;
            re->next = mergeTwoLists(l1->next,l2);
        }else {
            re = l2;
            re->next = mergeTwoLists(l1,l2->next);
        }
        return re;
    }
};

Solution #3, from others
cur saves the address of the "next" in last node
class Solution {  
public:  
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {  
        ListNode* ret = NULL;  
        ListNode** cur = &ret;  
        while(NULL != l1 && NULL != l2)  
        {  
            if(l1->val < l2->val)  
            {  
                *cur = l1;  
                cur = &(l1->next);  
                l1 = l1->next;  
            }  
            else  
            {  
                *cur = l2;  
                cur = &(l2->next);  
                l2 = l2->next;  
            }  
        }  
        *cur = NULL == l1? l2: l1;  
        return ret;  
    }  
};  

update
Solution #4, using dummy head
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* itr = dummy;
        while (l1 != NULL && l2 != NULL) {
            if (l1->val < l2->val) {
                itr->next = l1;
                itr = l1;
                l1 = l1->next;
            }else {
                itr->next = l2;
                itr = l2;
                l2 = l2->next;
            }
        }
        if (l1 == NULL) {
            itr->next = l2;
        }else {
            itr->next = l1;
        }
        return dummy->next;
    }
};