算法题目-记hulu失败的实习面试

比眉伴天荒 2022-03-31 08:25 113阅读 0赞

1。对于数组A\[0,1,2,3,4,...,k\]，求得0<=i < j < k，且使得A\[j\] - A\[i\]为最大值。

最简单也最容易想到的搜索两遍，即可得到答案。i的位置从起始至倒数第二个位置，j的位置从末尾元素至i后一个位置，保存记录最大的差值即可。

不过最简单的方法复杂度为n的平方，其实令有一个时间复杂度很低的方法，及从前至后遍历，添加一个保存当前访问元素之前的最小的元素，最大值必定需要减去已访问过元素的最小值才能够获得，这样时间复杂度降至n。

class Solution {
         
    public:
    //i<j max(a[j]-a[i])
    	int arrayMaxGap(vector<int> &array) {
    		if(array.size() == 0 || array.size() == 1)
    			return -1;
    		if(array.size() == 2) {
    			return array[1] - array[0];
    		}
    		int maxres,premin;
    		maxres = array[1] - array[0];
    		premin = array[0];
    		for(int i = 1;i < array.size();i++) {
    			if (array[i] - premin > maxres)
    			    maxres = array[i] - premin;
    			if (array[i] < premin)
    				premin = array[i];
    		}
    		return maxres;
    	}
    }

2。对于递增的数组A\[0,1,2,3,4,...,k\]，数组B\[0,1,2,3,4,...k'\]，对于0<=i<k,0<=j<k'，对于计算出的A\[i\]+B\[j\]，求其前k小个元素。

对于这个题目最先想到的思路，构造一个集合计算出所有的A\[i\]+B\[j\]，然后求取前k小个元素就比较简单了，但是如果k相对于构造出的集合比较小，这样就比较浪费空间了。

对于任意一个元素A\[i\]+B\[j\]，我们可以指导A\[i+1\]+B\[j\]和A\[i\]+B\[j+1\]是其接下来可确定的最近邻的两个大于其的元素，首先A\[0\]+B\[0\]，接下来就是A\[1\]+B\[0\]，A\[0\]+B\[1\]之中小的元素为第二小的元素，接下来继续扩展第二小的元素得到A\[2\]+B\[0\]，A\[1\]+B\[1\]，或者A\[0\]+B\[2\]，A\[1\]+B\[1\]，所以如果用指针的话这样无法保存，求取最小的结合不断的膨胀，所以这里考虑利用最小堆每次得到多个元素中最小的元素。

//class for minKsum
    struct Point {
    	int x;
    	int y;
    	int sum;
    };
    bool operator<(Point a,Point b){
    	return a.sum > b.sum;
    }
    class Solution {
    public:
    //array A,arrayB, obtain the minest k a[i]+b[j]. that a[0]+b[0] is the minest
    	vector<int> minKsum(vector<int> i_A,vector<int> i_B,int k) {
    		vector<int> res;
    		priority_queue<Point> priorityq;
    		if(i_A.size() == 0&&i_B.size() == 0) {
    			return res;
    		}
    		if(i_A.size() == 0) {
    			if (i_B.size() > k)
    			{
    				return res;
    			}
    			return vector<int>(i_B.begin(),i_B.begin()+k);
    		}
    		if(i_B.size() == 0) {
    			if(i_A.size() > k)
    			{
    				return res;
    			}
    			return vector<int>(i_A.begin(),i_A.begin()+k);
    		}
    		Point first;
    		first.x = 0;
    		first.y = 0;
    		first.sum = i_A[0] + i_B[0];
    		priorityq.push(first);
    		while (!priorityq.empty()&&res.size() != k)
    		{
    			Point tmpoutput = priorityq.top();
    			priorityq.pop();
    			res.push_back(tmpoutput.sum);
    			if(tmpoutput.y == 0) {
    				if (tmpoutput.x + 1 < i_A.size())
    				{
    					Point tmp;
    					tmp.x = tmpoutput.x + 1;
    					tmp.y = tmpoutput.y;
    					tmp.sum = i_A[tmpoutput.x + 1] + i_B[tmpoutput.y];
    					priorityq.push(tmp);
    				}
    				if (tmpoutput.y + 1 < i_B.size()) {
    					Point tmp;
    					tmp.x = tmpoutput.x;
    					tmp.y = tmpoutput.y + 1;
    					tmp.sum = i_A[tmpoutput.x] + i_B[tmpoutput.y + 1];
    					priorityq.push(tmp);
    				}
    			}
    			else {
    				if(tmpoutput.y + 1 < i_B.size()) {
    					Point tmp;
    					tmp.x = tmpoutput.x;
    					tmp.y = tmpoutput.y + 1;
    					tmp.sum = i_A[tmpoutput.x] + i_B[tmpoutput.y + 1];
    					priorityq.push(tmp);
    				}
    			}
    		}
    		return res;
    	}
    }

3。实现带有重复元素的二分查找，如果查找的元素重复，返回重复元素的起始位置。

类似二分查找，但是结束条件有些不同，结束条件为当前节点=目标元素并且当前节点为起始节点或者前一个节点不等与目标元素。

class Solution {
         
    public:
    	int binarySearch(vector<int> &array, int target) {
    		if(array.size() == 1) {
    			if (array[0] == target)
    			    return 0;
    			else
    				return -1;
    		}
    		int start = 0,end = array.size() - 1,mid;
    		while(start <= end) {
    			mid = (start + end)/2;
    			if(array[mid] == target && (mid == 0 || array[mid-1] != target)) {
    				return mid;
    			}
    			else if(target <= array[mid]) {
    				end = mid - 1;
    			}
    			else {
    				start = mid + 1;
    			}
    		}
    		return -1;
    	}
    }

4。对于链表表示的完全二叉树，给出根节点的指针，统计其节点的数量。

完全遍历需要O(n)时间的复杂度。但是这样没有完全利用完全二叉树的特性。

计算节点数量转换为计算最后一层节点数量，计算最后一层节点数量可以这样计算，左子树，右子树，如果深度相同，计算右子树最后一层数量+满的左子树。如果深度不同，计算左子树的最后一层节点数量，这样问题规模可以直接减半。

#include <algorithm>
    #include <time.h>
    #include <iostream>
    using namespace std;
    struct TreeNode {
    	TreeNode *left;
    	TreeNode *right;
    	int value;
    	TreeNode(int v) {value = v;}
    };
    class Solution {
    public:
    	int recurseTree(TreeNode *root) {
    		if (root == NULL)
    		    return 0;
    		int tdepth = depth(root);
    		return (int)pow((double)2,tdepth-1) - 1 + recuseNode(root,tdepth);
    	}
    	//递归统计完全二叉树的最后一层节点个数
    	int recuseNode(TreeNode *root,int depth) {
    		if(root == NULL)
    			return 0;
    		//最后一层才进行统计，depth == 1
    		if(root->left == NULL && root->right == NULL && depth == 1)
    			return 1;
    		return recuseNode(root->left,depth-1)+recuseNode(root->right,depth-1);
    	}
    	int dc(TreeNode *root) {
    		if(root == NULL)
    			return 0;
    		int treedepth = depth(root);
    		if(treedepth == 1)
    			return 1;
    		else
    		    return (int)pow((double)2,treedepth-1) - 1 + devide_conquer(root);
    	}
    	//分治统计完全二叉树的最后一层节点个数
    	int devide_conquer(TreeNode *root) {
    		int tdepth = depth(root);
    		//如果只有两层，直接可以得到最后一层节点个数
    		if(tdepth == 2) {
    			if(root->right == NULL)
    				return 1;
    			return 2;
    		}
    	    int leftdepth = depth(root->left);
    		int rightdepth = depth(root->right);
    		//right side
    		if (leftdepth == rightdepth) {
    			return (int)pow((double)2,tdepth-1-1) + devide_conquer(root->right);
    		}
    		//left side
    		else if(leftdepth > rightdepth) {
    			return devide_conquer(root->left);
    		}
    		else {
    			//error
    		}
    	}
    	//计算深度
    	int depth(TreeNode *root) {
    		int depth = 0;
    		TreeNode *cur = root;
    		while(cur != NULL) {
    			cur = cur->left;
    			depth++;
    		}
    		return depth;
    	}
    };
    int main(int argc,char **argv) {
    	TreeNode *_1root = new TreeNode(1);
    	_1root->left = NULL;
    	_1root->right = NULL;
    
    	TreeNode *_2root1 = new TreeNode(1);
    	TreeNode *_2root2 = new TreeNode(2);
    	TreeNode *_2root3 = new TreeNode(3);
    	TreeNode *_2root4 = new TreeNode(4);
    	TreeNode *_2root5 = new TreeNode(5);
    	TreeNode *_2root6 = new TreeNode(6);
    	TreeNode *_2root7 = new TreeNode(7);
    	TreeNode *_2root8 = new TreeNode(8);
    	TreeNode *_2root9 = new TreeNode(9);
    	TreeNode *_2root10 = new TreeNode(10);
    	TreeNode *_2root11 = new TreeNode(11);
    	TreeNode *_2root12 = new TreeNode(12);
    
    	_2root1->left = _2root2;
    	_2root1->right = _2root3;
    
    	_2root2->left = _2root4;
    	_2root2->right = _2root5;
    
    	_2root3->left = _2root6;
    	_2root3->right = _2root7;
    
    	_2root4->left = _2root8;
    	_2root4->right = _2root9;
    
    	_2root5->left = _2root10;
    	_2root5->right = _2root11;
    
    	_2root6->left = _2root12;
    	_2root6->right = NULL;
    
    	_2root7->left = NULL;
    	_2root7->right = NULL;
    
    	_2root8->left = NULL;
    	_2root8->right = NULL;
    
    	_2root9->left = NULL;
    	_2root9->right = NULL;
    
    	_2root10->left = NULL;
    	_2root10->right = NULL;
    
    	_2root11->left = NULL;
    	_2root11->right = NULL;
    
    	_2root12->left = NULL;
    	_2root12->right = NULL;
    
    	Solution s;
    	int s11,s12,s21,s22;
    
    	clock_t start,finish;
    	start = clock();
    	for(int i = 0;i < 1000000;i++)
    	    s11 = s.dc(_1root);
    	finish = clock();
    	double t11 = double(finish - start);
    	start = clock();
    	for(int i = 0;i < 1000000;i++)
    	    s12 = s.recurseTree(_1root);
    	finish = clock();
    	double t12 = double(finish - start);
    
    	start = clock();
    	for(int i = 0;i < 1000000;i++)
    	    s21 = s.dc(_2root1);
    	finish = clock();
    	double t21 = double(finish - start);
    	start = clock();
    	for(int i = 0;i < 1000000;i++)
    	    s22 = s.recurseTree(_2root1);
    	finish = clock();
    	double t22 = double(finish - start);
    
    	cout<<"s11:"<<s11<<"time:"<<t11<<"ms"<<endl;
    	cout<<"s12:"<<s12<<"time:"<<t12<<"ms"<<endl;
    	cout<<"s21:"<<s21<<"time:"<<t21<<"ms"<<endl;
    	cout<<"s22:"<<s22<<"time:"<<t22<<"ms"<<endl;
    }

5。给出一串数字，判断是否为有效二叉查找树的后序遍历序列（及是否能够通过这串后序遍历序列构造出二叉查找树）。

最先想到的思路，将当前序列排序，有序的假设为中序遍历序列，这样可以类似还原BST。利用后序的序列不断的分割中序。有序的序列是否能够在后序中为一串连续的空间，如果连续即可构造出BST。这种方法的时间复杂度可以从O(n2)优化至O(nlgn)，利用hash表。

有一个更好的思路，不利用中序，直接利用后序，首先利用最后的根节点，利用二分查找nlgn得到分割点，当前元素小于根，下一个元素大于根，考虑一些边界情况。

然后，根节点之前的为左子树，其上界为根节点；根节点之后的为右子树，其下界为根节点，递归下去，递归至一个元素，如果符合上下界的条件，即可形成BST。

class Solution {
         
    public:
    //postorder sequece and checkout if it can be construct BST
    	bool validBST(vector<int> &postorder) {
    		return validBST_recurse(postorder, 0, postorder.size() - 1, INT_MIN, INT_MAX);
    	}
    	bool validBST_recurse(vector<int> &postorder, int start, int end, int min, int max) {
    		if(end < start) {
    			return true;
    		}
    		if(end == start) {
    			return postorder[end] > min && postorder[end] < max;
    		}
    		int partition = binaryPartition(postorder,start,end);
    		bool left = validBST_recurse(postorder, start, partition, min, postorder[end]);
    		bool right = validBST_recurse(postorder, partition+1, end-1, postorder[end], max);
    		return left&&right;
    	}
    	//partition to two part, postorder[p] < postorder[end] && portorder[p+1] > postorder[end]
    	int binaryPartition(vector<int> &postorder, int start, int end) {
    		int target = postorder[end];
    		int mid;
    		end = end - 1;
    		if(start == end)
    			return start;
    		while(start < end) {
    			mid = (start + end)/2;
    			if(postorder[mid] < target && (mid == end || postorder[mid+1] > target)) {
    				return mid;
    			}
    			else if(postorder[mid] > target && (mid == start || postorder[mid-1] < target)) {
    				return mid-1;
    			}
    			else if(postorder[mid] < target) {
    				start = mid + 1;
    			}
    			else {
    				end = mid - 1;
    			}
    		}
    		return -1;
    	}
    }