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%，上一次网易编程题也很惨。为什么本地调的好好的代码，交上去就不行呢？
#字节跳动#
投递博世等公司7个岗位 >