Day35力扣打卡

打卡记录

相邻字符不同的最长路径（树状DP）

链接

若节点也存在父节点的情况下，传入父节点参数，若是遍历到父节点，直接循环里 continue。

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(parent)
        g = [[] for _ in range(n)]
        for i in range(1, n): g[parent[i]].append(i)
        ans = 0
        def dfs(x):
            nonlocal ans
            max_len = 0
            for y in g[x]:
                length = dfs(y) + 1
                if s[x] != s[y]:
                    ans = max(ans, max_len + length)
                    max_len = max(max_len, length)
            return max_len
        dfs(0)
        return ans + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

三个无重叠子数组的最大和（滑动窗口）

链接

分段处理，类似于股票问题的一种解法，把前面出现的最大值保存下来留给后面计算来使用，这样可以避免重叠出现。

class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        ans = []
        sum1, maxSum1, maxSum1Idx = 0, 0, 0
        sum2, maxSum12, maxSum12Idx = 0, 0, ()
        sum3, maxTotal = 0, 0
        for i in range(k * 2, len(nums)):
            sum1 += nums[i - k * 2]
            sum2 += nums[i - k]
            sum3 += nums[i]
            if i >= k * 3 - 1:
                if sum1 > maxSum1:
                    maxSum1 = sum1
                    maxSum1Idx = i - k * 3 + 1
                if maxSum1 + sum2 > maxSum12:
                    maxSum12 = maxSum1 + sum2
                    maxSUm12Idx = (maxSum1Idx, i - k * 2 + 1)
                if maxSum12 + sum3 > maxTotal:
                    maxTotal = maxSum12 + sum3
                    ans = [*maxSUm12Idx, i - k + 1]
                sum1 -= nums[i - k * 3 + 1]
                sum2 -= nums[i - k * 2 + 1]
                sum3 -= nums[i - k + 1]
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

三个无重叠子数组的最大和（动态规划）

链接
DP解法的难点在于如何回溯动态规划后的坐标，而且要保持字典序最小。

class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        s = list(accumulate(nums, initial=0))
        f = [[0] * 4 for _ in range(n + 2)]
        for i in range(n - k + 1, 0, -1):
            for j in range(1, 4):
                f[i][j] = max(f[i + 1][j], f[i + k][j - 1] + s[i + k - 1] - s[i - 1])
        ans = [0] * 3
        i, j, idx = 1, 3, 0
        while j > 0:
            if f[i + 1][j] > f[i + k][j - 1] + s[i + k - 1] - s[i - 1]: i += 1
            else:
                ans[idx] = i - 1
                idx += 1
                i += k
                j -= 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18