天池每周周赛 第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

目录
打赏
0
0
0
0
58
分享
相关文章
|
9月前
|
Leetcode第383场周赛
在LeetCode第383场周赛中,选手完成了3道题目。第一题是关于边界上的蚂蚁,蚂蚁根据非零整数数组nums的值移动,返回蚂蚁返回边界上的次数。解题方法是计算数组累加和为0的次数。第二题涉及计算网格的区域平均强度,给定一个灰度图像和阈值,返回每个像素所属区域的平均强度。解题关键在于理解相邻像素和区域定义,并计算平均强度。第三题是恢复单词初始状态的最短时间问题,通过移除前k个字符并添加k个字符,求恢复原词所需的最短时间。解题策略是检查去除前k个字符后的子串是否能作为原词的前缀。
43 1
Leetcode第383场周赛
|
9月前
|
Leetcode第382场周赛
```markdown 给定字符串`s`,计算按键变更次数,即使用不同键的次数,不考虑大小写差异。例如,`"aAbBcC"`变更了2次。函数`countKeyChanges`实现此功能。另外,求满足特定模式子集最大元素数,`maximumLength`函数使用`TreeMap`统计次数,枚举并构建子集,返回最大长度。最后,Alice和Bob玩鲜花游戏,Alice要赢需满足鲜花总数奇数、顺时针在[1,n]、逆时针在[1,m],返回满足条件的(x, y)对数,可通过奇偶性分类讨论求解。 ```
49 1
【蓝桥杯集训·周赛】AcWing 第96场周赛
文章目录 第一题 AcWing 4876. 完美数 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第二题 AcWing 4877. 最大价值 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第三题 AcWing 4878. 维护数组 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解
94 0
【蓝桥杯集训·最后一次周赛】AcWing 第 97 场周赛
文章目录 第一题 AcWing 4944. 热身计算 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第二题 AcWing 4945. 比大小 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第三题 AcWing 4946. 叶子节点 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解
152 0
【蓝桥杯集训·周赛】AcWing 第94场周赛
文章目录 第一题 AcWing 4870. 装物品 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第二题 AcWing 4871. 最早时刻 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第三题 AcWing 4872. 最短路之和 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解
86 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等