天池每周周赛 第1场题解-阿里云开发者社区

开发者社区> 算法编程> 正文

天池每周周赛 第1场题解

简介: 在线编程限时内测赛第1场题目解析。

商品列表

算法:模拟

思路

依次计算L1、L2显示的商品区间。

复杂度

时间复杂度O(1),空间复杂度O(1)。
image.png
image.png
image.png

最大乘积

算法:思维

算法思路

无序数组中取三个数字的最大乘积,结果由两种情况构成:最大的三个数相乘或者最小的两个数相乘 (负数)再乘上最大数。
然后我们通过设五个变量代表上述五个数
遍历数组,通过ifelse判断五个变量和num的大小,不断更新上述五个变量
最后取两个情况的较大者即是答案

复杂度分析

  • 时间复杂度为O(n)

    • n为数组长度
  • 空间复杂度为O(1)

    • 常量级的空间消耗

image.png
image.png
image.png

会议室

算法:动态规划

算法思路

考虑到数据范围的时间戳 meetingi≤50000 ,我们可以以时间轴为核心建立动态规划。我们可以考虑 dpi 为到 i 时刻为止的最大价值。
我们可以先预处理一下每个时间点结束的会议有哪些。然后从对应的开始点进行状态转移。
状态转移方程为
dp[i]=max(dp[i-1], dp[startTime]+val)
image.png
image.png
image.png

幸运数

算法:dfs+思维

算法思路

由于 1≤l≤r≤10⁹ ,所以其实这个数字最多只有9位(10⁹不是幸运数)。我们仔细观察幸运数的定 义,由于其条件比较苛刻,所以其实幸运数数量不会很多,初步估计就在 6^8 以内(实际更少)。因此我们可以尝试生成出来所有的幸运数,然后判断范围。
生成的方法很简单,从 7 开始,进行扩展,变成 18, 81, 29, 92, 70等。这样一层层的拓展下去,得到所有的幸运数。
image.png
image.png
image.png
image.png
image.png

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接