OJ每日练习（3）

Posted on | In

题目名称

  1. Median of Two Sorted Arrays（Leetcode #4)
  2. Long Consecutive Sequence(Leetcode #128）
  3. 从尾到头打印链表（剑指offer #6）
  4. 重建二叉树（剑指offer #7）
  5. 二叉树的下一个节点(剑指offer #8)

Median of Two Sorted Arrays（Leetcode #4)

题目描述

There are two sorted arrays nums1 and nums2 of size m and n respectively.Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).You may assume nums1 and nums2 cannot be both empty.
Example 1:

1
2
3
nums1 = [1, 3]
nums2 = [2]
The median is 2.0

Example 2:
1
2
3
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

解题思路

笔者直接将问题改造为更一般的通用情况：已知两个有序数组，找到二者所有元素中第k大的元素。思路有以下三种：

  1. 归并排序，这是最显然的解法。但是无论时间还是空间均有较大消耗。
  2. 在1的基础上，采用一个计数器记录当前m大的元素，当m==k时终止算法。此时不再具备空间消耗，但时间复杂度不变。
  3. 在2的基础上我们发现，每一次比较都排除了一个在第k大元素之前的元素。我们可以充分利用数组有序的特性，每一次都删除一半的元素，如此则可实现O(log(m+n))的复杂度。

思路剖析

针对思路3，现有分析如下：
假设数组A与B元素个数均大于k/2，我们将A的第k/2个元素与B的第k/2个元素进行比较，即比较A[k/2-1]、B[k/2-1]，比较结果有三种可能（为了简化分析，假设k为偶数，所得结论对于k为奇数亦成立）：

  1. A[k/2-1]==B[k/2-1]
  2. A[k/2-1]>B[k/2-1]
  3. A[k/2-1]<B[k/2-1]

若A[k/2-1] < B[k/2-1]，则意味着区间[A[0],A[k/2-1]]内的所有元素必然不大于AUB的top k元素，则可直接舍弃这k/2个元素，对于<的情况亦是如此（证明很简单，令A[k/2-1]=P，则P至多为AUB的第k-1个元素）。若A[k/2-1]==B[k/2-1]，则表明已经找到了第k大的元素。

解题方案

思路二（计数器+归并）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        size_t sumsize=nums1.size()+nums2.size();
        bool evenflag = (sumsize&1)?true:false;
        size_t k = evenflag?(sumsize+1)/2:sumsize/2;
        return evenflag?findKth(nums1,nums2,k):(findKth(nums1,nums2,k)+findKth(nums1,nums2,k+1))/2;
    }
private:
    double findKth(const vector<int>& nums1,const vector<int>& nums2,size_t k){
        if(k==0)
            return -1;
        int count =0,i=0,j=0,current=-1;
        while(i!=nums1.size()&&j!=nums2.size()){
            current = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++],++count;
            if(count==k)
                return current;
        }
        return (i==nums1.size())?nums2[j+k-count-1]:nums1[i+k-count-1];
    }
};

思路三（二分）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int total=m+n;
        if(total&1) return aux(A,m,B,n,(total+1)/2);
        else return (aux(A,m,B,n,total/2)+aux(A,m,B,n,total/2+1))/2;
    }
private:
    double aux(int A[], int m, int B[], int n,int k){
        if(m>n) return aux(B,n,A,m,k);
        if(m==0) return B[k-1];
        if(k==1) return min(B[0],A[0]);
        int pa=min(k/2,m),pb=k-pa;
        if(A[pa-1]<B[pb-1])
            return aux(A+pa,m-pa,B,n,k-pa);
        else if(A[pa-1]>B[pb-1])
            return aux(A,m,B+pb,n-pb,k-pb);
        return A[pa-1];
    }
};

扩展

对于这种求第k个元素，很容易联想到大顶堆或小顶堆，笔者出于时间原因没有验证，但采用堆必然消耗空间，有兴趣的读者可以自行尝试。

Long Consecutive Sequence(Leetcode #128）

题目描述

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.Your algorithm should run in O(n) complexity.
Example:

1
2
3
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

解题思路

最长连续整数序列，第一反应必然是排序去重求解，但排序不满足O(n)的时间复杂度。因此可采用以空间换取时间的策略，将所有元素存入hashtable，对于每一个元素，以其为中心向两侧扩张，直到不再连续(当然亦可以采用hashset）。

解题方案

方案一（排序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
	    if (nums.size() <= 1) return nums.size();
	    sort(nums.begin(), nums.end());
	    nums.erase(unique(nums.begin(), nums.end()), nums.end());
	    size_t length = 1, maxlength = 1;
	    for (int i = 1; i != nums.size(); i++) {
		    if (nums[i] == nums[i - 1] + 1) 
		        length++;
		    else {
			    maxlength = maxlength > length ? maxlength : length;
			    length = 1;
		    }
	    }
	    maxlength = maxlength > length ? maxlength : length;
	    return maxlength;
    }
};

方案二（hashtable)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.size() <= 1) 
            return nums.size();
        unordered_map<int, bool> used;
        for(auto i:nums)
            used[i]=false;
        size_t maxlength = 1;
        for (auto i : nums) {
            if (used[i]) continue;
            used[i]=true;
            size_t length=1;
            for (int j = i + 1; used.find(j) != used.end();++j) 
                used[j] = true,++length;
            for (int j = i - 1; used.find(j) != used.end(); --j)
                used[j] = true,++length;
            maxlength = maxlength > length ? maxlength : length;
        }
        return maxlength;
    }
};

从尾到头打印链表（剑指offer #6）

解题思路

没什么好说的，从尾到头是标准的先进后出，自然想到了栈。此外，本题采用递归也能实现。

解题方案

方案一（栈）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        if(!head)
            return vector<int>();
        vector<int> res;
        stack<ListNode*> aux;
        while(head){
            aux.push(head);
            head=head->next;
        }
        while(!aux.empty()){
            ListNode* temp = aux.top();
            res.push_back(temp->val);
            aux.pop();
        }
        return res;
    }
};

方案二(递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        print_aux(head,res);
        return res;
    }
    
    void prints_aux(ListNode* head,vector<int>& res){
        if(!head) return;
        if(head->next)
            prints_aux(head->next,res);
        res.push_back(head->val);
    }
};

重建二叉树（剑指offer #7）

题目描述

以下将探讨如何从前序遍历、中序遍历序列还原二叉树。

解题思路

思路很简单：前序的第一个Node为root，在中序序列中找到root，其左右分别为左子树和右子树。再对左右子树执行递归构建即可。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.empty())
            return nullptr;
        if(pre.size()==1)
            return new TreeNode(pre[0]);
        return construct_aux(pre,vin,0,pre.size(),0,vin.size());
    }
    
private:
    TreeNode* construct_aux(vector<int> &pre,vector<int> &vin,
                            size_t pb,size_t pe,size_t ib,size_t ie){
        if(pb==pe)
            return nullptr;
        else{
            int rootvalue = pre[pb];
            TreeNode* root = new TreeNode(rootvalue);
            size_t pos=ib;
            while(pos!=ie)
                if(vin[pos]==rootvalue) break;
                else pos++;
            root->left = construct_aux(pre,vin,pb+1,pb+1+pos-ib,ib,pos);
            root->right = construct_aux(pre,vin,pb+1+pos-ib,pe,pos+1,ie);
            return root;
        }       
    }
};

扩展

利用中序与后序还原二叉树也是类似的思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.empty())
			return nullptr;
		if (inorder.size() == 1)
			return new TreeNode(inorder[0]);
		return construct_aux(inorder, postorder, 0, inorder.size(), 0, postorder.size());
    }
    
private:
    TreeNode * construct_aux(vector<int> &vin, vector<int> &post,
                            size_t ib, size_t ie, size_t pb, size_t pe) {
	    if (ib == ie)
		    return nullptr;
	    else {
		    int rootvalue = post[pe-1];
		    TreeNode* root = new TreeNode(rootvalue);
		    size_t pos = ib;
		    while (pos != ie)
			    if (vin[pos] == rootvalue) break;
			    else pos++;
		    root->left = construct_aux(vin, post, ib, pos, pb, pb+pos-ib);
		    root->right = construct_aux(vin, post, pos+1, ie, pb+pos-ib, pe-1);
		    return root;
	    }
    }    
};

二叉树的下一个节点(剑指offer #8)

题目描述

求解某二叉树在中序遍历下的下一个节点，struct TreeNode内含有指向父亲的指针。

解题思路

该问题可按照以下步骤求解：

  1. 若该节点存在右子树，则下一个节点必为其右子树的最左侧节点。
  2. 在不满足1的条件下，若该节点为左子，则其父为下一节点。
  3. 在不满足1的条件下，若该节点为右子，上溯至其第一个不为右子的祖先之父。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode){
        if(!pNode)
            return nullptr;
        else{
            if(pNode->right){
                pNode=pNode->right;
                while(pNode->left)
                    pNode=pNode->left;
                return pNode;
            }
            else{
                while(pNode->parent){
                    if(pNode->parent->left==pNode)
                        return pNode->parent;
                    pNode=pNode->parent;
                }
                return nullptr;
            }
        }
    }
};