喜刷刷: divide and conquer

Friday, November 21, 2014

[LeetCode] Merge k Sorted Lists

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

思路1：priority queue

将每个list的最小节点放入一个priority queue (min heap)中。之后每从queue中取出一个节点，则将该节点在其list中的下一个节点插入，以此类推直到全部节点都经过priority queue。由于priority queue的大小为始终为k，而每次插入的复杂度是log k，一共插入过nk个节点。时间复杂度为O(nk logk)，空间复杂度为O(k)。

注意C++的STL中的priority queue默认是max heap，定义一个新的比较函数。

class Solution {
public:
    struct compNode {
        bool operator()(ListNode *p, ListNode *q) const {
            return p->val>q->val;
        }  
    };

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode*, vector<ListNode*>, compNode> pq;
        ListNode *dummy = new ListNode(0), *tail = dummy;
        
        for(int i=0; i<lists.size(); i++) 
            if(lists[i]) pq.push(lists[i]);
            
        while(!pq.empty()) {
            tail->next = pq.top();
            tail = tail->next;
            pq.pop();
            if(tail->next) pq.push(tail->next);
        }
        
        return dummy->next;
    }
};

思路2：Merge two lists

利用合并两个list的方法，依次将每个list合并到结果的list中。这个方法的空间复杂度为O(1)，时间复杂度为：

2n + 3n + ... + kn = [(k+1)*k/2-1]*n = O(nk^2)

由于时间复杂度较大，大数据测试会超时。

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *ret = NULL;
        for(int i=0; i<lists.size(); i++) 
            ret = merge2Lists(ret, lists[i]);
        return ret;
    }
    
    ListNode* merge2Lists(ListNode *h1, ListNode *h2) {
        ListNode *dummy = new ListNode(0), *tail = dummy;
        while(h1 && h2) {
            if(h1->val<=h2->val) {
                tail->next = h1;
                h1 = h1->next;
            }
            else {
                tail->next = h2;
                h2 = h2->next;
            }
            tail = tail->next;
        }
        tail->next = h1 ? h1 : h2;
        return dummy->next;
    }
};

思路3：二分法

类似merge sort，每次将所有的list两两之间合并，直到所有list合并成一个。如果用迭代而非递归，则空间复杂度为O(1)。时间复杂度：
2n * k/2 + 4n * k/4 + ... + (2^x)n * k/(2^x) = nk * x
k/(2^x) = 1 -> 2^x = k -> x = log2(k)
所以时间复杂度为O(nk log(k))，与方法一相同。

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if(lists.empty()) return NULL;
        int end = lists.size()-1;
        while(end>0) {
            int begin = 0;
            while(begin<end) {
                lists[begin] = merge2Lists(lists[begin], lists[end]);
                begin++;
                end--;
            }
        }
        return lists[0];
    }
    
    ListNode* merge2Lists(ListNode *h1, ListNode *h2) {
        ListNode *dummy = new ListNode(0), *tail = dummy;
        while(h1 && h2) {
            if(h1->val<=h2->val) {
                tail->next = h1;
                h1 = h1->next;
            }
            else {
                tail->next = h2;
                h2 = h2->next;
            }
            tail = tail->next;
        }
        tail->next = h1 ? h1 : h2;
        return dummy->next;
    }
};

Thursday, November 13, 2014

[LeetCode] Pow(x, n)

Implement pow(x, n).

思路1：利用整数n的二进制表达
性质：(x^y)^z = x^(y*z)
例如：(5^3)^2 = 5^3 * 5^3 = 5^(3*2)

10: 二进制(1010)b = (2^3)*1 + (2^2)*0 + (2^1)*1 + (2^0)*0
3^10 = 3^[(2^3)*1] * 3^[(2^2)*0] * 3^[(2^1)*1] * 3^[(2^0)*0]
res = 1
res = res^2 * 3^1 = 3^(1)b
res = res^2 * 3^0 = 3^2 = 3^(10)b
res = res^2 * 3^1 = 3^5 = 3^(101)b
res = res^2 * 3^0 = 3^10 = 3^(1010)b
需要特殊处理 n<0的情况。

class Solution {
public:
    double pow(double x, int n) {
        bool negPow = n<0 ? true : false;
        n = abs(n);
        double res = 1;
        for(int i=31; i>=0; i--) {
            res = res*res;
            if(n & (1<<i))
                res = res*x;
        }
        if(negPow) res = 1/res;
        return res;
    }
};

思路2：分治递归

递归公式为：x^n = x^(n/2) * x^(n/2) * x^(n%2)

class Solution {
public:
    double pow(double x, int n) {
        if(n>=0)
            return powPositive(x,n);
        else
            return 1/powPositive(x,-n);
    }
    
    double powPositive(double x, int n) {
        if(n==0) return 1; // base case
        double res = powPositive(x, n/2);
        res *= res;
        if(n%2) res *= x;
        return res;
    }
};