目录

转变日期格式

给你一个字符串 date ，它的格式为 Day Month Year ，其中：

  • Day 是集合 {“1st”, “2nd”, “3rd”, “4th”, …, “30th”, “31st”} 中的一个元素。
  • Month 是集合 {“Jan”, “Feb”, “Mar”, “Apr”, “May”, “Jun”, “Jul”, “Aug”, “Sep”, “Oct”, “Nov”, “Dec”} 中的一个元素。
  • Year 的范围在 ​[1900, 2100] 之间。

请你将字符串转变为 YYYY-MM-DD 的格式，其中：

  • YYYY 表示 4 位的年份。
  • MM 表示 2 位的月份。
  • DD 表示 2 位的天数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reformat-date

示例

输入：date = “20th Oct 2052”
输出：“2052-10-20”

思路1

字符串处理题，Python很好做。年份直接转字符串即可，月份用哈希表映射关系搞定，日期用isdigit()检查是否是数字且一位数字要在前面补0。

代码1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def reformatDate(self, date: str) -> str:
        date = date.split()
        tmp = {"Jan":"01", "Feb":"02", "Mar":"03", "Apr":"04", "May":"05", "Jun":"06", "Jul":"07", "Aug":"08", "Sep":"09", "Oct":"10", "Nov":"11", "Dec":"12"}
        res = ""
        res += str(date[2]) + "-"
        res += tmp[date[1]] + "-"
        day = ""
        for ch in str(date[0]):
            if ch.isdigit():
                day += ch
            else:
                break
        if len(day) < 2:
            day = "0" + day
        res += day
        return res

子数组和排序后的区间和

给你一个数组 nums ，它包含 n 个正整数。你需要计算所有非空连续子数组的和，并将它们按升序排序，得到一个新的包含 n * (n + 1) / 2 个数字的数组。

请你返回在新数组中下标为 left 到 right （下标从 1 开始）的所有数字和（包括左右端点）。由于答案可能很大，请你将它对 10^9 + 7 取模后返回。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/range-sum-of-sorted-subarray-sums

示例

输入：nums = [1,2,3,4], n = 4, left = 1, right = 5
输出：13
解释：所有的子数组和为 1, 3, 6, 10, 2, 5, 9, 3, 7, 4 。将它们升序排序后，我们得到新的数组 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 1 到 ri = 5 的和为 1 + 2 + 3 + 3 + 4 = 13 。

思路1

数据规模比较小，直接暴力模拟。双重循环求前缀和得到所有的子数组和，然后sort()排序，切片求和。前缀和数组长度为O(n^2)，则时间复杂度为O((n^2)log(n^2))

代码1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        tmp = []
        n = len(nums)
        for i in range(n):
            cur = 0
            for j in range(i, n):
                cur += nums[j]
                tmp.append(cur) 
        tmp.sort()    
        return sum(tmp[left-1:right])

三次操作后最大值与最小值的最小差

给你一个数组 nums ，每次操作你可以选择 nums 中的任意一个数字并将它改成任意值。

请你返回三次操作后， nums 中最大值与最小值的差的最小值。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves

示例

输入：nums = [5,3,2,4]
输出：0
解释：将数组 [5,3,2,4] 变成 [2,2,2,2]. 最大值与最小值的差为 2-2 = 0 。

思路1

暴力模拟。先对数组排序，分多种情况讨论。
1、数组少于等于4个，修改其中3个与另外一个一致，则差值为0
2、数组无重复数，且长度为5，则差值为相邻元素差值的最小值
3、数组无重复数，且长度为6，有两种情况，取其中的较小值：

  • 前3个数变为倒数第三个数，此时最小差值为最后一个数减去倒数第三个数
  • 后3个数变为第三个数，此时最小差值为第三个数减去第一个数

4、数组有重复数，如果除去重复最多的那个数以外的数字个数小于4个，则都变为重复最多的那个数字，此时差值为0
5、数组有重复数，如果除去重复最多的那个数以外的数字个数等于4个，其中3个变为重复最多的那个数，最小差值取与重复最多的数前后相邻的两个数与重复最多的数的差值的较小值。
6、数组有重复数，且除去重复最多的那个数以外的数字个数大于4个，先求重复最多的数的起止范围，如果起始索引前的数的数量或结束索引后的数的数量小于3个时，则小于3个的那个范围的数全变为重复最多的数，根据剩下的操作次数将最边缘的数变为能向里靠得最多的相邻的那个数。
7、不管数组是否有重复数，当数组长度很长，且重复最多的数的起止范围与数组边缘距离很远时，分4种情况讨论，取其中的最小值：

  • 后面三个数变为倒数第4个数，差值为倒数第4个数减去第1个数
  • 前面三个数变为第4个数，差值为倒数第1个数减去第4个数
  • 前面两个数变为第3个数，倒数第一个数变为倒数第2个数，差值为倒数第2个数减去第3个数
  • 后面两个数变为倒数第3个数，前面一个数变为第2个数，差值为倒数第3个数减去第2个数

由于人比较蠢，只能想到暴力模拟，但是情况太多，遗漏了很多情况（最后是第7中情况的后两种情况没考虑到），最后没来得及在比赛结束前AC掉，导致没有AK。

代码1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

class Solution:
    def minDifference(self, nums) -> int:
        n = len(nums)
        if n <= 4:
            return 0
        res = float("inf")
        nums.sort()
        tmp = collections.defaultdict(int)
        for num in nums:
            tmp[num] += 1
        cnt = 0
        maxKey = -1
        for k, v in tmp.items():
            if v > cnt:
                cnt = max(cnt, v)
                maxKey = k
        tmp = list(set(tmp))
        tmp.sort()
        if cnt > 1:
            ind = tmp.index(maxKey)
            if n - cnt < 4:
                return 0
            if n - cnt == 4:
                try:
                    res = min(res, tmp[ind] - tmp[ind-1])
                except:
                    pass
                try:
                    res = min(res, tmp[ind+1] - tmp[ind])
                except:
                    pass
                return res
            start, end = -1, -1
            for i in range(n):
                if nums[i] == maxKey:
                    start = i
                    break
            for i in range(start+1, n):
                if nums[i] != maxKey:
                    end = i - 1
                    break
            if end == -1:
                end = n-1
            back = n-1-end
            gg = min(start, back)
            if gg < 3:
                if back < start:
                    return maxKey - nums[3-back]
                else:
                    return nums[-(1+3-start)] - maxKey
        if n == 5:
            for i in range(1, n):
                res = min(res, nums[i] - nums[i-1])
            return res
        if n == 6:
            return min(nums[2] - nums[0], nums[-1] - nums[-3])
        return min(nums[-4] - nums[0], nums[-1] - nums[3], nums[-2] - nums[2], nums[-3] - nums[1])

思路2

实际上，思路1中第7种情况的讨论包含了前面6种情况的所有可能性。
即，不管数组是否有重复数，当数组长度很长，且重复最多的数的起止范围与数组边缘距离很远时，分4种情况讨论，取其中的最小值：

  • 后面三个数变为倒数第4个数，差值为倒数第4个数减去第1个数
  • 前面三个数变为第4个数，差值为倒数第1个数减去第4个数
  • 前面两个数变为第3个数，倒数第一个数变为倒数第2个数，差值为倒数第2个数减去第3个数
  • 后面两个数变为倒数第3个数，前面一个数变为第2个数，差值为倒数第3个数减去第2个数

代码2

1
2
3
4
5
6
7

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 3:
            return 0
        nums.sort()
        return min(nums[-4] - nums[0], nums[-1] - nums[3], nums[-2] - nums[2], nums[-3] - nums[1])

石子游戏IV

Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。

一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。

如果石子堆里没有石子了，则无法操作的玩家输掉游戏。

给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True ，否则返回 False 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/stone-game-iv

示例

输入：n = 7
输出：false
解释：当 Bob 采取最优策略时，Alice 无法赢得比赛。
如果 Alice 一开始拿走 4 个石子， Bob 会拿走 1 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 3 -> 2 -> 1 -> 0）。
如果 Alice 一开始拿走 1 个石子， Bob 会拿走 4 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 6 -> 2 -> 1 -> 0）。

思路1

记忆化搜索，用dp[i]记录石头个数为i时先手取是否可以获胜。当i是平方数时dp[i]设为True; 否则用i减去先手可取的平方数，看是否会落在一个先手取会失败的dp[j]上，这样先收取到剩下j个石头后轮到对手先手取必可使对手失败，这样在原先数量的石头上先手取必可取胜。

代码1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        if int(n**0.5) == n**0.5:
            return True
        if n == 1:
            return True
        if n == 2:
            return False
        dp = [False] * (n+1)
        dp[1] = True
        dp[2] = False
        for i in range(3, n+1):
            if int(i**0.5) == i**0.5:
                dp[i] = True
                continue
            ind = 1
            while i - ind*ind > 0:
                if dp[i - ind*ind] == False:
                    dp[i] = True
                    break
                ind += 1
        return dp[n]

总结

除了第3题没AC，其余AC。比赛结束一分钟内通过了第3题，差点AK。不过这次题目很简单，就算AK了也只能拿600名左右，太菜了。
目前全国排名 2424 ，全球排名 11421 。
得分13/18，完成时间0:55:26，全国排名 647 / 2545，全球排名 1682 / 8174。
1、0:04:52，字符串处理题，Python很好做。
2、0:10:59，暴力模拟通过（甚至答案最后忘了取模），比赛时想不出更优解。
3、暴力模拟，要讨论的情况比较多，最后最后的return没考虑min()里的后两种情况，在比赛结束后一分钟内才通过，比较可惜。复盘一遍后发现很多情况不需要讨论，浪费了时间。
4、0:55:26，石子游戏一般使用动态规划做的，我这里算是用了记忆化搜索把n内所有的情况都讨论了，因为n的情况可以基于n前的情况决定。