Fork me on GitHub
image frame

EightyNinth

力扣 322. 零钱兑换

leetcode 
1
2
3
4
5
6
7
8
def coinChange(coins, amount):
    # 无限背包最大变最小问题
    dp = [float("inf") for _ in range(amount + 1)]
    dp[0] = 0
    for i in range(len(coins)):
        for j in range(coins[i], amount + 1):
            dp[j] = min(dp[j], dp[j - coins[i]] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1

力扣 862. 和至少为k的最短子数组

leetcode

解法：前缀和+单调双端队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def shortestSubarray(nums, k):
    # 前缀和+单调双端队列
    sums = [0]
    for num in nums:
        sums.append(num + sums[-1])
    
    queue, ret = deque(), float("inf")
    for i in range(len(sums)):
        while queue and queue[-1][1] >= sums[i]:
            queue.pop()
        
        while queue and sums[i] - queue[0][1] >= k:
            ret = min(ret, i - queue.popleft()[0])
        
        queue.append((i, sums[i]))
    
    return ret if ret != float("inf") else -1

力扣 312. 戳气球

leetcode

解法：dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
def maxCoins(nums):
    @lru_cache(None)
    def solve(left, right):
        if left >= right - 1:
            return 0
        best = 0
        for i in range(left + 1, right):
            cur = new[left] * new[i] * new[right]
            cur += solve(left, i) + solve(i, right)
            best = max(best, cur)
        return best
    new = [1] + nums + [1]
    return solve(0, len(nums) + 1)

解法二：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
def maxCoins(nums):
    # 动态规划
    n = len(nums)
    dp = [[0 for _ in range(n + 2)] for _ in range(n + 2)]
    new = [1] + nums + [1]
    for i in range(n - 1, -1, -1):      # 左边缘气球
        for j in range(i + 2, n + 2):   # 右边缘气球
            for k in range(i + 1, j):   # 戳爆的气球
                total = new[i] * new[k] * new[j]
                total += dp[i][k] + dp[k][j]
                dp[i][j] = max(dp[i][j], total)
    return dp[0][n + 1]

力扣 309. 最佳买卖股票时期含冷冻期

leetcode

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def maxProfit(prices):
    # 动态规划
    """
    dp_0表示手中持有股票的状态
    dp_1表示手中没有股票，但处于冷冻期的状态
    dp_2表示手中没有股票，也没有处于冷冻期的状态
    """
    dp_0, dp_1, dp_2 = -prices[0], 0, 0
    for i in range(1, len(prices)):
        cur_0 = max(dp_0, dp_2-prices[i])
        cur_1 = dp_0 + prices[i]
        cur_2 = max(dp_1, dp_2)
        dp_0, dp_1, dp_2 = cur_0, cur_1, cur_2
    return max(dp_1, dp_2)

力扣 934. 最短的桥

leetcode

解法

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
from collections import deque
def shortestBridge(grid):
    n = len(grid)
    queue, island = deque(), set()
    # 第一次bfs查找第一个岛
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                queue.append((i, j, 0))
                island.add((i, j))
                break
        if queue:
            break
    
    # 第二次bfs查找扩展岛边界直到两岛接触
    while queue:
        x, y, step = queue.popleft()
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            cx, cy = x + dx, y + dy
            if 0 <= cx < n and 0 <= cy < n and (cx, cy) not in island:
                island.add((cx, cy))
                if grid[cx][cy] == 1:
                    if step:
                        return step
                    queue.appendleft((cx, cy, 0))
                else:
                    queue.append((cx, cy, step + 1))
    return 0

力扣 301. 删除无效的括号

leetcode

思路1：回溯 + dfs

  1. 首先判断需要最少删除的左括号和右括号
  2. 进行回溯

解法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 removeInvalidParentheses(self, s: str) -> List[str]:
        # 1. 确定最小删除的左括号数量和右括号数量
        left_del, right_del = self.get_ld_rd(s)

        ret, path = set(), []

        # 2. dfs回溯
        def dfs(i, ld, rd, score):
            nonlocal ret, path
            # 回溯终止条件
            if i >= len(s):
                # 判断结果是否合法，能够加入到结果中
                if ld == 0 and rd == 0 and score == 0:
                    ret.add("".join(path))
                return
            
            # 剪枝条件,也可是说是到目前为止能够确保下一步结果一定合法的值
            if score < 0:
                return 
            
            if s[i] == "(":
                # 删除
                if ld > 0:
                    dfs(i + 1, ld - 1, rd, score)
                # 不删除
                path.append(s[i])
                dfs(i + 1, ld, rd, score + 1)
                path.pop()
            elif s[i] == ")":
                # 删除
                if rd > 0:
                    dfs(i + 1, ld, rd - 1, score)
                # 不删除
                path.append(s[i])
                dfs(i + 1, ld, rd, score - 1)
                path.pop()
            else:
                path.append(s[i])
                dfs(i + 1, ld, rd, score)
                path.pop()
        
        dfs(0, left_del, right_del, 0)
        return list(ret)
            

    def get_ld_rd(self, s: str) -> List[int]:
        ld, rd = 0, 0
        for i in s:
            if i =="(":
                ld += 1
            elif i == ")":
                if ld > 0: ld -= 1
                else: rd += 1
            else:
                continue
        return ld, rd

思路2：bfs

就粗暴解法
逐层判断合法值，保留进行下一层，直至遍历完毕。

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def removeInvalidParentheses(s):
    def isValid(s):
        score = 0
        for i in s:
            if i == "(":
                score += 1
            elif i == ")":
                if score <= 0:
                    return False
                else:
                    score -= 1
        return score == 0

    cur = {s}
    while True:
        valid = list(filter(isValid, cur))
        if valid:
            return valid
        cur = {c[:i] + c[i + 1:] for c in cur for i in range(len(c)) if c[i] in "()"}

力扣 915. 分割数组

leetcode

思路1：两次遍历

可以说是接雨水的简化版。

从右向左遍历数组，得到当前子数组的最小值

再从左向右遍历数组拿到当前子数组最大值的同时，找到满足左连续子数组的所有值小于等于又连续子数组的位置。

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
def partitionDisjoint(nums):
    # 两次遍历
    min_right = [0 for _ in range(len(nums))]
    min_right[-1] = nums[-1]
    for i in range(len(nums) - 2, -1, -1):
        min_right[i] = min(min_right[i + 1], nums[i])
    
    max_left = nums[0]
    for i in range(1, len(nums)):
        if max_left <= min_right[i]:
            return i
        else:
            max_left = max(max_left, nums[i])

思路2：一次遍历

只需要维护左连续子数组即可。

cur_max 维护当前左连续子数组的最大值
left_max 维护左连续最短子数组的最大值

解法2

1
2
3
4
5
6
7
8
def partitionDisjoint(nums):
    # 一次遍历
    cur_max, left_max, ret = nums[0], nums[0], 0
    for i in range(1, len(nums)):
        cur_max = max(cur_max, nums[i])
        if nums[i] < left_max:
            left_max, ret = cur_max, i
    return ret + 1

力扣 901. 股票价格跨度

leetcode

思路

可以转化为背包问题

dp[i]表示做到第i份工作后的最大利益

因此在面对第i件工作时有两种情况

  1. 不做第i件工作：dp[i] = dp[i - 1]
  2. 做第i件工作，利益承接和第i件工作不冲突的dp：dp[i] = dp[k] + profit[i]
    1. 查找和第i件不冲突的工作k: bisect_right(data, starttime[i], hi=i, key=endtime[i])
    2. 完成第k件工作，还可以完成第i件工作

综合上述情况 dp[i] = max(dp[i - 1], dp[k] + profit[i])

解法

1
2
3
4
5
6
7
8
9
def jobScheduling(startTime, endTime, profit):
    # 背包问题 + 二分查找
    n = len(profit)
    dp = [0 for _ in range(n + 1)]
    data = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
    for i in range(1, n + 1):
        k = bisect_right(data, data[i - 1][0], hi=i, key=lambda x: x[1])
        dp[i] = max(dp[i - 1], data[i - 1][-1] + dp[k])
    return dp[-1]

力扣 901. 股票价格跨度

leetcode

思路

分别保存每日股价以及每日股票跨度，

对每日股价倒叙查找，判断查找的股价小于等于当日股价，则根据他的股票跨度进行倒退，再次判断直到查找的股价大于当日股价，

得到最终当日股价的跨度。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class StockSpanner:

    def __init__(self):
        self.prices = []
        self.dp = []


    def next(self, price: int) -> int:
        cur, dp = len(self.prices) - 1, 1
        while cur > -1 and self.prices[cur] <= price:
            dp += self.dp[cur]
            cur -= self.dp[cur]
        self.prices.append(price)
        self.dp.append(dp)
        return self.dp[-1]
  • Copyrights © 2022 eightyninth
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信