当前位置:   article > 正文

LeetCode笔记:Biweekly Contest 70

LeetCode笔记:Biweekly Contest 70

1. 题目一

给出题目一的试题链接如下:

1. 解题思路

这一题直接使用贪婪算法即可实现。

首先我们将价格进行排序,然后价格最大的两个必然只能靠自费,而后我们就可以免费获得价格第三高的糖果,重复上述操作即可可到最终的答案。

2. 代码实现

给出python代码实现如下:

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        cost = sorted(cost, reverse=True)
        cost = [c for i, c in enumerate(cost) if i % 3 != 2]
        return sum(cost)
  • 1
  • 2
  • 3
  • 4
  • 5

提交代码评测得到:耗时40ms,占用内存14.4MB。

2. 题目二

给出题目二的试题链接如下:

1. 解题思路

这一题首先就是我们假设第一个元素为0,那么显然我们可以恢复出完整的序列。

此时,我们就可以得到这个序列当中最大元素与最小元素的差值,此时我们给出的范围与这个差值的差即为我们的答案。

2. 代码实现

给出python代码实现如下:

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        n = len(differences)
        nums = [0 for _ in range(n+1)]
        for i in range(n):
            nums[i+1] = nums[i] + differences[i]
        _min, _max = min(nums), max(nums)
        delta = _max - _min
        res = upper - lower - delta + 1
        return res if res >= 0 else 0
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

提交代码评测得到:耗时1943ms,占用内存28.8MB。

3. 题目三

给出题目三的试题链接如下:

1. 解题思路

这一题其实只需要通过一个bfs就能够获得能够走到的所有的格子,然后我们对其按照排序规则进行排序之后取前k个元素即可。

2. 代码实现

给出python代码实现如下:

class Solution:
    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:
        n, m = len(grid), len(grid[0])
        i, j = start
        q = [start + [0]]
        reachable = []
        seen = set([(i, j)])
        while q:
            i, j, s = q.pop(0)
            if pricing[0] <= grid[i][j] <= pricing[1]:
                reachable.append([s, grid[i][j], i, j])
            if i-1 >= 0 and grid[i-1][j] != 0 and (i-1, j) not in seen:
                q.append((i-1, j, s+1))
                seen.add((i-1, j))
            if i+1 < n and grid[i+1][j] != 0 and (i+1, j) not in seen:
                q.append((i+1, j, s+1))
                seen.add((i+1, j))
            if j-1 >= 0 and grid[i][j-1] != 0 and (i, j-1) not in seen:
                q.append((i, j-1, s+1))
                seen.add((i, j-1))
            if j+1 < m and grid[i][j+1] != 0 and (i, j+1) not in seen:
                q.append((i, j+1, s+1))
                seen.add((i, j+1))
        
        reachable = sorted(reachable)[:k]
        return [x[2:] for x in reachable] 
  • 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

提交代码评测得到:耗时3336ms,占用内存68.3MB。

4. 题目四

给出题目四的试题链接如下:

1. 解题思路

这一题其实相较上一题反而更加简单,我们只要以每两个位子为界,考察两个room之间的plant数目(不妨即为k),那么在这两个之间就有 k + 1 k+1 k+1种树立墙板的方法,而我们累乘所有的可能性即可得到我们最终的答案。

2. 代码实现

给出python代码实现如下:

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        MOD = 10**9 + 7
        corridor = corridor.strip("P")
        seat_num = len([ch for ch in corridor if ch == "S"])
        if seat_num == 0 or seat_num % 2 != 0:
            return 0
        i, cnt, n = 0, 0, len(corridor)
        res = 1
        while i < n:
            if corridor[i] == "P":
                i += 1
                continue
            cnt += 1
            if cnt % 2 == 0:
                j = i+1
                while j < n and corridor[j] == "P":
                    j += 1
                res = res * (j-i) % MOD
                i = j
            else:
                i += 1
        return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

提交代码评测得到:耗时1355ms,占用内存16MB。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/115977?site
推荐阅读
相关标签
  

闽ICP备14008679号