1703天 博客通用头像 Edwiin

本人熟练掌握linux,windows的开关机,擅长nfs,samba,ftp,dhcp,bind,apache,mail等各项服务的安装与卸载,精通shell,mysql,iptables,selinux等单词的拼写,了解虚拟化,存储,集群等相关汉字的书写。

天池每周周赛 第1场题解

发布于 3个月前 / 50 次围观 / 0 条评论 / 技术学习 / Edwiin
本文最后更新于2020-8-4,已超过 1 个月没有更新,如果文章内容或图片资源失效,请【留言反馈】,我会及时处理,谢谢!

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

商品列表

算法:模拟

思路

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

复杂度

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

1.png2.png 3.png

最大乘积

算法:思维

算法思路

无序数组中取三个数字的最大乘积,结果由两种情况构成:最大的三个数相乘或者最小的两个数相乘 (负数)再乘上最大数。

然后我们通过设五个变量代表上述五个数

遍历数组,通过ifelse判断五个变量和num的大小,不断更新上述五个变量

最后取两个情况的较大者即是答案

复杂度分析

  • 时间复杂度为O(n)
    • n为数组长度
  • 空间复杂度为O(1)
    • 常量级的空间消耗

3.png 1.png 2.png

会议室

算法:动态规划

算法思路

考虑到数据范围的时间戳 meetingi≤50000 ,我们可以以时间轴为核心建立动态规划。我们可以考虑 dpi 为到 i 时刻为止的最大价值。

我们可以先预处理一下每个时间点结束的会议有哪些。然后从对应的开始点进行状态转移。

状态转移方程为

dp[i]=max(dp[i-1], dp[startTime]+val)

2.png 3.png 1.png

幸运数

算法:dfs+思维

算法思路

由于 1≤l≤r≤10⁹ ,所以其实这个数字最多只有9位(10⁹不是幸运数)。我们仔细观察幸运数的定 义,由于其条件比较苛刻,所以其实幸运数数量不会很多,初步估计就在 6^8 以内(实际更少)。因此我们可以尝试生成出来所有的幸运数,然后判断范围。

生成的方法很简单,从 7 开始,进行扩展,变成 18, 81, 29, 92, 70等。这样一层层的拓展下去,得到所有的幸运数。

1.png2.png3.png4.png5.png

全站顶部广告位

  • 支付宝赞助图片
  • 微信赞助图片
  • QQ赞助图片
头像
描述: 还好有你,再见如初。

Press Space to start