2018头条笔试编程题 思路分享
第一题( 最优复杂度O(n) )
题干:在第一象限内,有一些(n个)离散的点(x,y均为自然数,且某一行、列都只有一个点)
代码需要输出一些“最大点”(设待考察点为x0,y0,如果存在x,y,满足x>x0且y>y0,则x0,y0不是最大点),输出顺序为x值递增顺序。
思路:
有点类似于凸包问题,但实际可以这么做->
(1)对于所有输入的点,按照x值递增排序。——因为x值没有重复,且已知x的范围,所以使用位图法排序,复杂度O(n)。直接sort就当做是nlog(n)咯!
(2)从最右侧的点(xn,yn)开始研究,他的右边没有点了,题干的条件被破坏,那么(xn,yn)是最大点;同时用max来表示当前研究点右侧(包含当前)点的最大y值。
(3)研究(x n-1,y n-1),因为x n-1的右侧已经有点x n,那么(x n-1,y n-1)是不是最大点的关键就在于,y n-1<max?如果小于,那x n-1不是最大点,否则他是最大点。更新max值
(4)循环第三步,直到待考察的点为空。——复杂度O(n)
感觉自我陶醉在O(n)的代码里~~~~~
第二题(O(n2))
题干:给定一个序列,如【6,2,1】,要求输出:在某一个区间上的最小值min 与这个区间上所有值的和sum的乘积,最终只输出最大的乘积值。
思路;肯定是用两个index来模拟区间范围,然后在区间里寻找min和sum了。
那么可以这么做:
int max=-1; for(int i=0;i<n;i++){ int sum = 0; int min = array[i]; for(int j=i;j<n;++){ if(array[j]<min)min=array[j];//更新min sum+=array[j];//更新sum if(min*sum>max)max=min*sum; } }复杂度应该是O(n2)
代码就不上了,因为鄙人第一题10%,第二题30%,上一次网易编程题也很惨。为什么本地调的好好的代码,交上去就不行呢?
#字节跳动#