牛客真题编程——day1

发布时间:2022-08-18 18:47

环境:c++

1、连续最大和

一个数组有 N 个元素,求连续子数组的最大和。 例如:[-1,2,1],和最大的连续子数组为[2,1],其和为 3

首先使用穷举法,嵌套循环遍历出最大和,但是时间复杂度为n2,会有一个测试用例运行超时。

牛客真题编程——day1_第1张图片

采用动态规划思想:

分解问题为:sum(最大和)+a[i]

否则 sum+=a[i]

2、搬圆桌

现在有一张半径为r的圆桌,其中心位于(x,y),现在他想把圆桌的中心移到(x1,y1)。每次移动一步,都必须在圆桌边缘固定一个点然后将圆桌绕这个点旋转。问最少需要移动几步。

算法思想:

  根据题意画图,可知任意选择圆上一点画图,则圆心可移动范围为:初始圆心为圆心,r=2r的大圆内。且要想最少次数移动到(x1,y1),则移动方向只能为两圆心的连线。所以只需要求得最短距离和2r的倍数关系即可,余数自动舍入,结果即为移动步数。

需注意输入范围:一行五个整数r,x,y,x1,y1(1≤r≤100000,-100000≤x,y,x1,y1≤100000) 

采用longlongint声明整型

3、最大乘积

给定一个无序数组,包含正数、负数和0,要求从中找出3个数的乘积,使得乘积最大,要求时间复杂度:O(n),空间复杂度:O(1)

算法思想:题目要求时间复杂度n,所以不能用排序。其次需要对情况分类:当都为正数/负数时,选最大三值;当正负数同时存在时,需要max(最大正和两个最小负数,两个最大正数和一个最大负数)其一。

实现:INT_MIN,INT_MAX声明,循环判断输入i,排序出前三大,和两个最小。

输出:

 

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号