Merge k Sorted Lists

问题描述:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
分而治之的思想:   404ms

/**
 * 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) {
        if(lists.empty())
            return NULL;
        return dac(lists,0,lists.size()-1);
    }
private:
    ListNode* dac(vector<ListNode*>& lists,int low,int high)
    {
        int mid=(low+high)/2;
        if(low==high)
            return lists[low];
        ListNode* l1=dac(lists,low,mid);
        ListNode* l2=dac(lists,mid+1,high);
        return mergeTwoLists(l1,l2);
    }
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        if(l1->val<l2->val)
            l1->next=mergeTwoLists(l1->next,l2);
        else
            l2->next=mergeTwoLists(l1,l2->next);
    }
};

使用优先队列priority_queue找到最小的元素   436ms

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
struct cmp{
    bool operator()(const ListNode* l, const ListNode* r){
        return l->val > r->val;
    }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> q;
        for(auto l : lists){
            if(l) q.push(l);
        }
        if(q.empty())
            return NULL;
        ListNode* result = q.top();      // head
        q.pop();
        if(result->next)
            q.push(result->next);
        ListNode* pointer = result;
        while(!q.empty()){
            pointer->next = q.top();      // the min
            q.pop();
            pointer = pointer->next;
            if(pointer->next)             // the responding ListNode* is not empty
                q.push(pointer->next);
        }
        return result;
    }
};

使用make_heap 480ms

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
//struct cmp{
//   bool operator()(const ListNode* l, const ListNode* r){
//        return l->val > r->val;
//    }
//};
bool cmp(const ListNode* l, const ListNode* r){
    return l->val > r->val;
}
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
       ListNode head(0);
       ListNode *curr = &head;
       vector<ListNode*> v;
        for(auto l : lists){
            if(l) v.push_back(l);
        }
        make_heap(v.begin(), v.end(), cmp);
        while(v.size()>0){
            curr->next = v.front();      // the min
            pop_heap(v.begin(), v.end(), cmp);
            v.pop_back();
            curr = curr->next;
            if(curr->next){             // the responding ListNode* is not empty
                v.push_back(curr->next);
                make_heap(v.begin(), v.end(), cmp);
            }
        }
        return head.next;
    }
};

 

Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

思路:统计所有数中,各数位上1的个数。可以用循环的方式,从小达大对每个数位上1的个数进行统计。

class Solution {
public:
    int countDigitOne(int n) {
        if(n <= 0)
            return 0;
       int count = 0;
       for(long base = 1; base <= n; base *= 10)     // long, base*10 可能溢出
       {
           long data = n/base;
           long remain = n%base;
           count += (data+8)/10*base;               //  =0, =1, >1
           if(data%10 == 1)                        //  =1
              count += remain+1;
       }
       return count;
    }
};

Two Sum

题目1:Two Sum
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

题目意思是从给定一组数中,选出2个数,他们的和满足给定的一个目标值,按顺序输出这两个数对应的索引。(假设正好只有一个解)
思路:先按从小到大顺序数组排序,然后从小到大依次遍历,先确定一个较小的数,然后再其后面的数中使用二分查找的方式找另外一个数。

class Solution {
public:
    struct Item{
        int value;
        int index;
        Item(int pvalue, int pindex):value(pvalue), index(pindex){};
        bool operator<(const Item &it)
        {
            return value < it.value;
        }
    };
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        vector<Item> data;
        for(int i = 0; i <nums.size(); i++)
        {
            data.push_back(Item(nums[i], i));
        }
        sort(data.begin(), data.end());
        int lindex = 0, rindex = data.size() - 1;
        for( int lindex = 0; lindex <= rindex; lindex++){
            if((lindex > 0) && (data[lindex].value ==data[lindex+1].value) && (data[lindex].value * 2 == target)){
                result.push_back(min(data[lindex].index+1, data[lindex+1].index+1));
                result.push_back(max(data[lindex].index+1, data[lindex+1].index+1));
                return result;
            }
            else if((lindex > 0) && (data[lindex].value ==data[lindex+1].value) && (data[lindex].value * 2 == target))
                continue;
            int ret = -1;
            int remain = target - data[lindex].value;
            int left = lindex, right = rindex;
            while(left <= right){
                int mid = (left+right)/2;
                if(data[mid].value == remain){   // must compare the index
                    result.push_back(min(data[lindex].index+1, data[mid].index+1));
                    result.push_back(max(data[lindex].index+1, data[mid].index+1));
                    return result;
                }
                else if(data[mid].value < remain){
                    left = mid + 1;
                }
                else
                    right = mid - 1;
            }
        }
    }
};

时间复杂度为O(nlogn)
听说使用hashmap能将为O(n) 后续再探讨

Count Primes

问题:

找出不大于非负整数n的所有素数的个数

解答:
思路     先去掉偶数(n/2, 不包括2但包括1),然后从i=3开始的奇数进行扫描(以j=i*i为起点,step = 2*i为步长进行扫描)

class Solution {
public:
    int countPrimes(int n) {
        if(n <=2)
            return 0;
        int res = n>>1, m = sqrt(n-1);    // initilize res to n/2, remove all even number(not 2) and 1
        bool *table = new bool[n];
        for(int i = 3; i <= m; i +=2){
            if(!table[i]){                // odd prime
                for(int step = i<<1, j = i*i; j < n; j += step){   // start from i*i, step 2*i
                    if(!table[j]){
                        table[j] = 1;
                        res--;
                    }
                }
            }
        }
        return res;
    }
};

 

Sort List

问题描述:

Sort a linked list in O(n log n) time using constant space complexity.

解决代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode *first = head, *second = head->next, *mid= NULL;
        while(second->next != NULL && second->next->next != NULL){       // find the mid position
            first = first->next;
            second = second->next->next;
        }
        mid = first->next;
        first->next = NULL;
        ListNode *left = sortList(head);
        ListNode *right = sortList(mid);
        return MergeSort(left, right);
    }
    ListNode* MergeSort(ListNode *left, ListNode*right){
        ListNode* newNode = new ListNode(0);                             //
        ListNode* p = newNode;
        while(left != NULL && right != NULL){
            if(left->val <= right->val){
                p->next = left;
                p = p->next;
                left = left->next;
            }else{
                p->next = right;
                p = p->next;
                right = right->next;
            }
        }
        if(left != NULL)
            p->next = left;
        if(right != NULL)
            p->next = right;
        return newNode->next;
    }
};

有人采取自底向上的策略,给出了非递归解法,时间O(nlgn) 空间O(1):

/**
 * Merge sort use bottom-up policy,
 * so Space Complexity is O(1)
 * Time Complexity is O(NlgN)
 * stable sort
*/
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if(!head || !(head->next)) return head;
        //get the linked list's length
        ListNode* cur = head;
        int length = 0;
        while(cur){
            length++;
            cur = cur->next;
        }
        ListNode dummy(0);
        dummy.next = head;
        ListNode *left, *right, *tail;
        for(int step = 1; step < length; step <<= 1){
            cur = dummy.next;
            tail = &dummy;
            while(cur){
                left = cur;
                right = split(left, step);
                cur = split(right,step);
                tail = merge(left, right, tail);
            }
        }
        return dummy.next;
    }
private:
    /**
     * Divide the linked list into two lists,
     * while the first list contains first n ndoes
     * return the second list's head
     */
    ListNode* split(ListNode *head, int n){
        //if(!head) return NULL;
        for(int i = 1; head && i < n; i++) head = head->next;
        if(!head) return NULL;
        ListNode *second = head->next;
        head->next = NULL;
        return second;
    }
    /**
      * merge the two sorted linked list l1 and l2,
      * then append the merged sorted linked list to the node head
      * return the tail of the merged sorted linked list
     */
    ListNode* merge(ListNode* l1, ListNode* l2, ListNode* head){
        ListNode *cur = head;
        while(l1 && l2){
            if(l1->val > l2->val){
                cur->next = l2;
                cur = l2;
                l2 = l2->next;
            }
            else{
                cur->next = l1;
                cur = l1;
                l1 = l1->next;
            }
        }
        cur->next = (l1 ? l1 : l2);
        while(cur->next) cur = cur->next;
        return cur;
    }
};

https://leetcode.com/discuss/28594/bottom-recurring-with-space-complextity-time-complextity