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

Day 31, 23, Merge k Sorted Lists

Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
--------------------------------------------------------------
Solution #1 O(k*n)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *merge2Lists (ListNode *l1, ListNode *l2) {
        ListNode *ret,*cur;
        if (l1 == NULL) {
            return l2;
        }
        if (l2 == NULL) {
            return l1;
        }
        if (l1->val < l2->val) {
            ret = l1;
            cur = l1;
            l1 = l1->next;
        }else {
            ret = l2;
            cur = l2;
            l2 = l2->next;
        }
        while (l1 != NULL && l2 != NULL) {
            if (l1->val < l2->val) {
                cur->next = l1;
                cur = cur->next;
                l1 = l1->next;
            }else {
                cur->next = l2;
                cur = cur->next;
                l2 = l2->next;
            }
        }
        if (l1 == NULL) {
            cur->next = l2;
        }else {
            cur->next = l1;
        }
        return ret;
    }
    

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (lists.size() == 0) return NULL;
        ListNode *ret = lists[0];
        for (int i=1;i<lists.size();i++) {
            ret = merge2Lists(ret,lists[i]);
        }
        return ret;
    }
};

Solution #2, O（nlogk）, using Priority Queue
note struct of comparison function and declaration of priority queue

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    struct comp{
        bool operator()(const ListNode* n1, const ListNode* n2){
            return n1->val > n2->val;
        }
    };

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        priority_queue<ListNode*,vector<ListNode*>,comp> heap;
        ListNode *ret=NULL,*cur;
        for (int i=0;i<lists.size();i++) {
            if (lists[i] != NULL) {
                heap.push(lists[i]);
            }
        }
        
        while (!heap.empty()) {
            ListNode *min = heap.top();
            heap.pop();
            if (ret == NULL) {
                ret = min;
                cur = min;
            }else {
                cur->next = min;
                cur = cur->next;
            }
            if (min->next != NULL) {
                heap.push(min->next);
            }
        }
        return ret;
    }
};

Update on Sep-11-2014
Solution #3, push all nodes in priority_queue, then output will be in order

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    struct cmp {
        bool operator()(const ListNode* l1, const ListNode* l2) {
            return l1->val > l2->val;
        }
    };

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *dummy = new ListNode(INT_MIN);
        priority_queue<ListNode*,vector<ListNode*>,cmp> heap;
        bool flag = true;
        
        while (flag) {
            flag = false;
            for (int i = 0; i < lists.size(); i++) {
                if (lists[i] != NULL) {
                    flag = true;
                    heap.push(lists[i]);
                    lists[i] = lists[i]->next;
                }
            }
        }
        
        ListNode *head = dummy;
        while (!heap.empty()) {
            ListNode *t = heap.top();
            head->next = t;
            heap.pop();
            head = t;
        }
        head->next = NULL; // prevent infinite loop
        
        return dummy->next;
    }
};

Solution #4, merge all pairs of two adjacent lists for each iteration. O(nlog(k)), n is the total elements from all lists
Update on Nov-26-2014

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *merge2Lists (ListNode *l1, ListNode *l2) {
        ListNode *ret,*cur;
        if (l1 == NULL) {
            return l2;
        }
        if (l2 == NULL) {
            return l1;
        }
        if (l1->val < l2->val) {
            ret = l1;
            cur = l1;
            l1 = l1->next;
        }else {
            ret = l2;
            cur = l2;
            l2 = l2->next;
        }
        while (l1 != NULL && l2 != NULL) {
            if (l1->val < l2->val) {
                cur->next = l1;
                cur = cur->next;
                l1 = l1->next;
            }else {
                cur->next = l2;
                cur = cur->next;
                l2 = l2->next;
            }
        }
        if (l1 == NULL) {
            cur->next = l2;
        }else {
            cur->next = l1;
        }
        return ret;
    }

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (lists.size() == 0) return NULL;
        
        int size = lists.size();    
        while (size != 1) {
            
            for (int i = 0; i < size; i = i + 2) {
                if (i + 1 < size) {
                    lists[i / 2] = merge2Lists(lists[i],lists[i + 1]);
                }else{
                    lists[i / 2] = lists[i];
                }
            }
            size = size / 2 + size % 2;
        }
        
        return lists[0];
    }
};

与上面同样思路，但是用递归

/**
 * 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), *itr = dummy;
        while (l1 != NULL && l2 != NULL) {
            if (l1->val > l2->val) {
                itr->next = l2;
                l2 = l2->next;
                itr = itr->next;
            }else {
                itr->next = l1;
                l1 = l1->next;
                itr = itr->next;
            }
        }
        
        if (l1 == NULL) {
            itr->next = l2;
        }
        if (l2 == NULL) {
            itr->next = l1;
        }
        return dummy->next;
    }

    ListNode* helper(vector<ListNode*> &lists,int start,int end) {
        if (start > end) return NULL;
        if (start == end) return lists[start];
        int mid = (start + end) / 2;
        ListNode *l1 = helper(lists,start,mid);
        ListNode *l2 = helper(lists,mid + 1,end);
        return mergeTwoLists(l1,l2);
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return helper(lists,0,lists.size() - 1);
    }
};

Java, 用priority queue
时间O(N * log k), 空间为O(k), N为总node的个数，k为list的数量。
先把所有的头指针插入到queue，然后一个个pop。把刚pop出来的node的一下个，推回queue

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue que = new PriorityQueue<>((a, b) -> {
            return a.val - b.val;
        });
                
        for (ListNode node : lists) {
            if (node != null) que.add(node);
        }
        
        ListNode dummy = new ListNode(0);
        ListNode itr = dummy;

        while (!que.isEmpty()) {
            ListNode next = que.poll();
            if (next.next != null) que.add(next.next);
            itr.next = next;
            itr = next;
        }
        
        return dummy.next;
    }
}

如果可以重复利用原来的array的话，空间可以算是O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        List rt = Arrays.asList(lists);
        while (rt.size() != 1) {
            rt = divide(rt);
        }
        
        return rt.get(0);
    }
    
    private List divide(List lists) {
        int n = lists.size();
        List rt = new ArrayList<>();
        for (int i = 0; i < n / 2; i++) {
            rt.add(mergeTwo(lists.get(i), lists.get(n - 1 - i)));
        }
        
        if (n % 2 == 1) rt.add(lists.get(n / 2));
        
        return rt;
    }
    
    private ListNode mergeTwo(ListNode node1, ListNode node2) {
        
        if (node1 == null) return node2;
        if (node2 == null) return node1;
            
        ListNode dummy = new ListNode(0);
        ListNode itr;
        if (node1.val > node2.val) {
            dummy.next = node2;
            node2 = node2.next;
        }else {
            dummy.next = node1;
            node1 = node1.next;
        }
        itr = dummy.next;
        
        while (node1 != null && node2 != null) {
            
            if (node1.val > node2.val) {
                itr.next = node2;
                itr = node2;
                node2 = node2.next;
            }else {
                itr.next = node1;
                itr = node1;
                node1 = node1.next;
            }
        }
        
        if (node1 != null) {
            itr.next = node1;
        }
        if (node2 != null) {
            itr.next = node2;
        }
        
        return dummy.next;
    }
}

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

Day 7, 7 Reverse Integer

Reverse Integer
Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321
Have you thought about this?

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

Solution #1

class Solution {
public:
    int reverse(int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        bool minus = false;
        if (x < 0) {
            x = -x;
            minus = true;
        }
        
        int rev=0;
        while (x > 0) {
            rev = rev * 10 + x%10;
            x = x/10;
        }
        
        if (minus) {
            return -1 * rev;
        }
        return rev;
        
    }
};

检测溢出

class Solution {
public:
    int reverse(int x) {
        int rt = 0,temp = x;
        int sign = 1;
        if (x < 0) {
            sign = -1;
            temp = abs(x);
        }
        
        while (temp > 0) {
            if (rt > INT_MAX / 10 || (rt == INT_MAX / 10 && temp % 10 > 7)) return 0;
            rt = rt * 10 + temp % 10;
            temp /= 10; 
        }
        return rt * sign;
    }
};

Day 6, 1, Two Sum

Two Sum
Solution #1, sort then look for match, O(nlogn)

struct Node {
  int val;
  int index;
  Node(){}
  Node(int v,int i):val(v),index(i) {}
};

bool comp (const Node &left, const Node &right) {
    return left.val < right.val;
}

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<Node> boo;
        for (int i=0;i<numbers.size();i++) {
            boo.push_back(Node(numbers[i],i+1));
        }
        sort(boo.begin(),boo.end(),comp);
        
        int frontI = 0;
        int backI = boo.size() - 1;
        while (frontI < backI) {
            int sum = boo[frontI].val + boo[backI].val;
            if (sum == target) {
                int minI = min(boo[frontI].index,boo[backI].index);
                int maxI = max(boo[frontI].index,boo[backI].index);
                vector<int> re;
                re.push_back(minI);
                re.push_back(maxI);
                return re;
            }
            else if (sum < target) {
                frontI++;
            }else {
                backI--;
            }
        }
    }
};

Solution #2, hashmap, O(n)

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        unordered_map<int,int> mapping;
        vector<int> result;
        for (int i=0;i<numbers.size();i++) {
            if (mapping.find(numbers[i]) == mapping.end()) {
                mapping[numbers[i]] = i + 1;
            }else if (numbers[i] * 2 == target) {
                result.push_back(mapping[numbers[i]]);
                result.push_back(i+1);
                return result;
            }
        }
         
        for (int i=0;i<numbers.size();i++) {
            int remainder = target - numbers[i];
            if (remainder * 2 != target && mapping.find(remainder) != mapping.end()) {
                result.push_back(i+1);
                result.push_back(mapping[remainder]);
                return result;
            }
        }
        
        return result;
    }
};

Added on Sep-02-2014 
Solution #3

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        vector<int> ret(2);
        unordered_map<int,int> mapping;
        unordered_map<int,int>::iterator itr;
        
        for (int i = 0; i < numbers.size(); i++) {
            itr = mapping.find(numbers[i]);
            if (itr == mapping.end()) {
                mapping.insert(make_pair(numbers[i],i + 1));
            }else {
                if (numbers[i] + itr->first == target) {
                    ret[0] = itr->second;
                    ret[1] = i + 1;
                    return ret;
                } 
            }
        }
        
        for (int i = 0; i < numbers.size(); i++) {
            itr = mapping.find(target - numbers[i]);
            if (itr != mapping.end() && itr->second != i + 1) {
                ret[0] = i + 1;
                ret[1] = itr->second;
                return ret;
            }
        }
        
        return ret;
    }
};