leetcode-221周赛

Posted on Edited on In

leetcode 221周赛题解

leetcode 5637.判断字符串的两半是否相似

r57adJ.jpg
Solution: 理解题目了就可以, 字符串被分为前后两个部分, 两部分的元音字符个数 相同则为相似

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def halvesAreAlike(self, s):
        i = len(s) // 2
        return self.Count(s[:i]) == self.Count(s[i:])

    def Count(self, s):
        cache = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}
        count = 0
        for c in s:
            if c in cache:
                count += 1
        return count

leetcode 5638.吃苹果的最大数目

r5Hyhn.jpg
Solution: 迭代每一天, 如果该天的apple为0, 则只能吃 以前剩下的 && 没有过期的 苹果, 如果以前的也没有了, 则该天吃不到苹果。最后, n天之后如果还剩下没有过期的苹果则可以继续吃。可以使用优先级队列存储所有未过期的苹果, 吃的时候先吃马上要过期的苹果

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
class Solution:
    def eatenApples(self, apples, days):
        # 记录吃掉的苹果个数
        count = 0
        i = 0
        # 小顶堆, 按照 (过期日期, 苹果个数) 存储
        h = []
        while i < len(apples):
            # 该天有苹果, 先放到堆中
            if apples[i] != 0:
                heapq.heappush(h, (i + days[i], apples[i]))
            # 先把所有已经过期的苹果丢掉
            while h and (h[0][0] <= i or h[0][1] <= 0):
                heapq.heappop(h)
            # 有可以食用的苹果
            if len(h) != 0:
                # 先吃过期时间早的苹果
                apple = heapq.heappop(h)
                count += 1
                # 吃掉一个后, 在apple[0]天过期的苹果有剩余, 把剩下的再放到堆中
                if apple[1] > 1:
                    heapq.heappush(h, (apple[0], apple[1] - 1))
            i += 1
        # 如果有剩余的还可以继续吃 
        while h:
            if h[0][0] <= i or h[0][1] <= 0:
                heapq.heappop(h)
                continue
            apple = heapq.heappop(h)
            # 查看可以吃几天, days = apple[0] - i 为过期时间到该天的天数
            # days >= apple[1] 可以吃apple[1]个
            # days <  apple[1] 可以吃days个
            size = min(apple[1], apple[0] - i)
            count += size
            i += size
        return count

leetcode 5210.球会落何处

r5XsSA.jpg
Solution: 直接记录球的位置并且模拟球的运动即可

  • 可以使用(i, j)记录小球的位置, 当到达最后一行时小球顺利出去.
  • 当前位置的挡板必须和旁边的挡板相同, 比如 \ \, / /, 如果出现\/, \|, |/则被挡住。
  • 如果小球可以滑动, 则移动小球到旁边位置的下一行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def findBall(self, grid: List[List[int]]) -> List[int]:
        ans = []
        for j in range(len(grid[0])):
            ans.append(self.solve(grid, 0, j))
        return ans

    # 小球从位置(i, j)向下滑动, 返回最后滑动结果
    def solve(self, grid, i, j):
        # 获取旁边位置
        index = grid[i][j] + j
        # 走到了grid的两边
        if index < 0 or index >= len(grid[0]):
            return -1
        # 当前位置和旁边位置挡板方向相反
        if grid[i][j] + grid[i][index] == 0:
            return -1
        # 当前位置和旁边位置挡板方向相同, 可以继续滑动
        # 已经到达最后一行
        if i == len(grid) - 1:
            return index
        # 小球继续滑动
        return self.solve(grid, i + 1, index)

leetcode 5640.与数组中元素的最大异或值

r5xPIO.jpg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        ans = []
        nums = list(set(nums))
        nums.sort()
        for query in queries:
            x, m = query[0], query[1]
            tmp = float("-inf")
            for n in nums:
                if n > m:
                    break
                tmp = max(tmp, x ^ n)
            if tmp == float("-inf"):
                tmp = -1
            ans.append(tmp)
        return ans