2017 携程 笔试编程题 1

简介: 前言正文题目要求思路n10n 18核心测试总结前言今天参加了携程的笔试,编程题第一题一开始想错了方向,花费了很多时间(虽然第二题就是给时间也不一定做得出来,(⊙﹏⊙)b)。

前言

今天参加了携程的笔试,编程题第一题一开始想错了方向,花费了很多时间(虽然第二题就是给时间也不一定做得出来,(⊙﹏⊙)b)。

下面记录一下这个小插曲。

正文

题目要求

将指定的正整数n分解成若干个互不相同的自然数的和,且使这些自然数的乘积最大

人家给了个输入输出的例子,如下:

输入15
输出 144

言下之意就是在自然数之和为15的这些数字中,乘积最大的一对是

2 3 4 6

思路

为了使得这些自然数之和的乘积最大,那么这些数字应该尽可能的接近。

下面举几个小例子:

n=10

2+3+4 = 9
// 剩下的那个1补到4上面
2+3+5 

这个时候最大的乘积变成了30

n = 18

2+3+4+5 = 14
//按照刚才的思路, 剩下的4 添加到5上面
2+3+4+9

此时最大的乘积结果为216

那么这时的结果是最大的吗?

答案是否定的,因为刚才是从下标为2开始的。如果下标从3,从4开始呢,我们来看下效果。

3+4+5+6 -->> 最大结果为:360
4+5+6+7>18则进行去尾加和
4+5+9  -->> 最大结果为: 180

剩下的其实就不用考虑了。

核心

经过刚才的铺垫,这下不难理解了。最笨的方法就是不断的递增下标,然后记录每一个下标对应的最大值。存储起来,然后找到这些最大值中最大的那个,就是我们要求的结果了。

代码如下:

def mutl(ls):
    result = 1
    for item in ls:
        result *= item
    return result

def compute(n, step):
    path = []
    cursum = 0
    for index in range(step, n):
        if cursum > n:
            last = path.pop()
            path.append(path.pop() + n - (cursum - last))
            break
        path.append(index)
        cursum += index
    return mutl(path)

def my(n):
    total = []
    maxvalue = 0
    for step in range(int(n/2)):
        item = compute(n, step)
        total.append(item)
    maxvalue = max(total)
    return maxvalue



n = 15
result= my(n)
print(result)

运行结果:

144

测试

再来多测几组数据。

  • n=10
30
  • n=18
360

这下,可以啦。需要注意的是:

递增下标到n的一半的位置就可以了,否则结果会不正确,这是因为计算每次的step的时候会把第一个给算进去,所以导致结果偏大。

总结

就携程的笔试题而言,前面部分的问答题和选择题还算是中规中矩,比较偏重于理论和实践。

编程题就真的是考验算法的了。大部分的笔试题都是动态规划类型的。我本人比较偏重于开发方向,所以参加这种笔试题真的是有点力不从心。

不管怎么说,算法是很有必要的。多学点,肯定没错,说不一定以后就用得到了。

我, 还有很长的路要走啊。

目录
相关文章
|
6月前
|
算法 Java Python
用友Java后端笔试2023-8-5
用友Java后端笔试2023-8-5
84 0
用友Java后端笔试2023-8-5
Java开发5年,复习1个月成功上岸京东物流,面试和复习思路分享
最近有很多小伙伴在后台私信我说,马上金九银十了,现在准备跳槽涨薪的同学越来越多了,想要一些速成的面试题和面试技巧,特地今天马老师为大家整理了这三套阿里巴巴2022年全年Java岗面试题总结+一线互联网大厂Java岗面经+一线互联网大厂Java岗面试题总结!
|
6月前
|
消息中间件 缓存 架构师
复习这份美团架构师的Java核心面试宝典,我四面阿里拿下offer
怎样才能拿到大厂的offer,没有掌握绝对的技术,那么就要不断的学习 他是如何拿下阿里等大厂的offer的呢,今天分享他的秘密武器,美团资深架构师整理的Java核心知识点,面试时面试官必问的知识点,篇章包括了很多知识点,其中包括了有基础知识、Java集合、JVM、多线程并发、spring原理、微服务、Netty 与RPC 、Kafka、日记、设计模式、Java算法、数据库、Zookeeper、分布式缓存、数据结构等等。
|
监控 算法 测试技术
携程2023算法开发岗 一面 二面 面经
携程2023算法开发岗 一面 二面 面经
82 0
|
缓存 算法 架构师
2023年秋招成功斩获offer秘籍:九大核心知识+1000道大厂面试真题
前言 如何在金九银十成功斩获Offer!BATJ大厂面经(成功关键:吃透九大核心知识+狂刷大厂面试真题) 第一轮:团队面试 第一轮基本上是你的团队成员面试你,是和你同级或者高你一个P的师兄来面你,我的话基本没问什么特别的,主要还是讲自己简历上的做的项目,这里需要你很熟悉自己的项目才行。 我个人觉得这里你要把项目里你的角色做了什么没做什么讲清楚,然后最好能把自己做的那部分重点展开来讲,然后面试官会从你讲的内容里挑一些具体来问你,这部分就因人而异了,知道的说不知道的别瞎说。 一些什么TCP/UDP啊、网络模型啊之类的基础知识。我是觉得这一面只要你项目靠谱、不吹牛逼、底子扎实,过一面应该都
|
存储 前端开发 JavaScript
🍪前端笔试系列 | 小米2020校招前端工程师笔试题
🍪前端笔试系列 | 小米2020校招前端工程师笔试题
529 9
🍪前端笔试系列 | 小米2020校招前端工程师笔试题
|
运维 Linux 网络协议
7大板块,200+面试题,助你拿下offer | 运维工程师面试宝典
在2020阿里云峰会上,阿里云智能总裁张建锋表示,阿里云今年再招5000人,大规模引进顶尖科技人才。7月9日 19:00-21:30 阿里云开发者社区首场“Offer 5000”直播开启!15位团队技术大牛在线招人,《阿里云技术面试红宝书》助你拿下Offer!马上投递简历: https://developer.aliyun.com/special/offerday01,在此,小编奉上运维工程师面试宝典,帮你拿下好工作!
13153 0
7大板块,200+面试题,助你拿下offer | 运维工程师面试宝典
|
SQL
爱奇艺后端笔试【完犊子了-选择20题+编程4道】
爱奇艺后端笔试【完犊子了-选择20题+编程4道】
111 0
|
NoSQL 算法 Java
程序员面试字节跳动,被怼了~
程序员面试字节跳动,被怼了~
208 0
程序员面试字节跳动,被怼了~
|
Android开发 Java
【面小易-面经10】阿里巴巴Android客户端开发实习生面试经验
又到了“金九银十”的招聘季,各位小伙伴们是不是也在忙着准备面试呢找工作呢?在接下来的一段时间里,面小易会为大家分享各种面试经验哦!请持续关注我。今天要和大家分享的是一位投递阿里巴巴Android开发实习生同学的面试经验,虽然他最终止步于二面,但是他的面试经验还是值得我们学习的,就让我们一起来看看吧。
4920 0