Day50力扣打卡

打卡记录

三个无重叠子数组的最大和

链接

滑动窗口

class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        n, ans = len(nums), []
        sum1 = sum2 = sum3 = 0
        maxsum1idx, maxsum12idx = 0, ()
        maxsum1 = maxsum12 = total = 0
        
        for i in range(2 * k, n):
            sum1 += nums[i - 2 * k]
            sum2 += nums[i - k]
            sum3 += nums[i]
            if i >= 3 * k - 1:
                if sum1 > maxsum1:
                    maxsum1 = sum1
                    maxsum1idx = i - 3 * k + 1
                if maxsum1 + sum2 > maxsum12:
                    maxsum12 = maxsum1 + sum2
                    maxsum12idx = (maxsum1idx, i - 2 * k + 1)
                if maxsum12 + sum3 > total:
                    total = maxsum12 + sum3
                    ans = [*maxsum12idx, i - k + 1]
                sum1 -= nums[i - 3 * k + 1]
                sum2 -= nums[i - 2 * k + 1]
                sum3 -= nums[i - k + 1]
        return ans

动态规划 + 回溯

class Solution:
    def maxSumOfThreeSubarrays(self, nums, k):
        n = len(nums)
        sums = list(accumulate(nums, initial=0))
        dp = [[0] * 4 for _ in range(n + 10)]
        for i in range(n - k + 1, 0, -1):
            for j in range(1, 4):
                dp[i][j] = max(dp[i + 1][j], dp[i + k][j - 1] + sums[i + k - 1] - sums[i - 1])
        
        ans = [0] * 3
        i, j, idx = 1, 3, 0
        while j > 0:
            if dp[i + 1][j] > dp[i + k][j - 1] + sums[i + k - 1] - sums[i - 1]:
                i += 1
            else:
                ans[idx] = i - 1
                i += k
                j -= 1
                idx += 1
        return ans

T 秒后青蛙的位置（树状DP）

链接

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        g = [[] for _ in range(n + 1)]
        g[1].append(-1)
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
        ans = 0
        def dfs(x, fa, time, k):
            if x == target and (time == 0 or len(g[x]) == 1):
                nonlocal ans
                ans = 1 / k
                return True
            if x == target or time == 0:
                return False
            for y in g[x]:
                if y == fa:
                    continue
                if dfs(y, x, time - 1, k * (len(g[x]) - 1)):
                    return True
        dfs(1, -1, t, 1)
        return ans

树上最大得分和路径（树状DP）

链接

class Solution:
    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
        n = len(amount)
        g = [[] for _ in range(n)]
        g[0] = [-1]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
        
        Bob_times = [n] * n
        def dfs1(x, fa, time):
            if x == 0:
                Bob_times[0] = time
                return True
            for y in g[x]:
                if y == fa:
                    continue
                if dfs1(y, x, time + 1):
                    Bob_times[x] = time
                    return True
            return False
        dfs1(bob, -1, 0)
        
        def dfs2(x, fa, time, score):
            if time < Bob_times[x]:
                score += amount[x]
            elif time == Bob_times[x]:
                score += amount[x] // 2
            if len(g[x]) == 1:
                return score
            res = -inf
            for y in g[x]:
                if y == fa:
                    continue
                res = max(res, dfs2(y, x, time + 1, score))
            return res
        return dfs2(0, -1, 0, 0)