LeetCode Biweekly 30 题解

正文索引 [隐藏]

5177. 转变日期格式

题目链接

给定一个形如 “20th Oct 2052” 的日期,将其转化为形如 “2052-10-20″(即YYYY-MM-DD) 的日期。

题意非常明确,我们直接做对应的转换即可。将输入按照空格切分成三段,顺次为日期、月份、年份,将日期和月份转化为数字,再拼接即可。
一个比较简单的字符串处理题,没有什么坑。

5445. 子数组和排序后的区间和

题目链接

给定一个长度为 n 的数组 nums,计算所有子段和得到长度为 n\cdot (n-1)/2 的新数组 sum。对 sum 数组的 [left, right] 位置继续求和。
数据范围 n \leq 1000-1e9 \leq nums[i] \leq 1e9,i=0, 2, \ldots, n-1

直接按照题目的意思生成 sum 数组,对其进行排序,然后对应位置求和即可。
时间复杂度:O(n^2 \log n)

5445. 子数组和排序后的区间和

题目链接

给你一个数组 nums ,每次操作你可以选择 nums 中的任意一个数字并将它改成任意值。请你返回三次操作后, nums 中最大值与最小值的差的最小值。
数据范围:n \leq 1e5

非常显然,如果数字个数不超过 4 个的时候,我们可以将所有数字改成一样的,这样答案一定最小,为 0。
如果超过 4 个的话,我们要改的话,每次一定是将最大值改小,或者将最小值改大。因为这样才有可能让差值缩小才有意义。而一共只进行 3 次操作,所以直接枚举这三次中改最小值改大做几次,最大值改小做几次就可以了。
时间复杂度:O(1)

5447. 石子游戏 IV

题目链接

Alice 和 Bob 两个人轮流玩一个游戏,Alice 先手。
一开始,有 n 个石子堆在一起。每个人轮流操作,正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。
如果石子堆里没有石子了,则无法操作的玩家输掉游戏。
给你正整数 n ,且已知两个人都采取最优策略。问 Alice 是否会赢得比赛。
数据范围:n\leq 1e5

这是一个典型的 SG 博弈,我们用记忆化搜索来处理所有的状态(必输/必胜)。
dp\left[n\right] 表示当前剩余 n 个石子时,先手的状态。

由题意,当前剩余 n 石子的时候,我们可以拿走一个平方数 x, x\leq n,之后就剩余 n-x 枚石子。此时,如果我们发现 dp\left[n-x\right] 是必败态,那么我们此步选择 x 个石子就可以让对手陷入必败态,那么我们就必胜了,故 dp\left[n\right] 是必胜态。如果 dp\left[n-x\right] 是必胜态,那么我们可以尝试其他的 x^{‘}

换句话说,对于 dp\left[n\right],我们枚举所有可能的 x 检查其后继状态 dp\left[n-x\right]。如果所有后继状态都是必胜态,则 dp\left[n\right] 为必败态,否则我们就可以主动转移到后继中的必败态,令 dp\left[n\right] 为必胜态。

处理 dp 数组,我们使用记忆化搜索即可。

时间复杂度:O(n)