网站网速慢,单位做核酸检测简报,郑州网站开发公司哪家好,wordpress 数据表打卡记录 相邻字符不同的最长路径#xff08;树状DP#xff09;
链接
若节点也存在父节点的情况下#xff0c;传入父节点参数#xff0c;若是遍历到父节点#xff0c;直接循环里 continue。
class Solution:def longestPath(self, parent: List[int], s: str) - in…打卡记录 相邻字符不同的最长路径树状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 0def dfs(x):nonlocal ansmax_len 0for y in g[x]:length dfs(y) 1if s[x] ! s[y]:ans max(ans, max_len length)max_len max(max_len, length)return max_lendfs(0)return ans 1三个无重叠子数组的最大和滑动窗口
链接
分段处理类似于股票问题的一种解法把前面出现的最大值保存下来留给后面计算来使用这样可以避免重叠出现。
class Solution:def maxSumOfThreeSubarrays(self, nums: List[int], k: int) - List[int]:ans []sum1, maxSum1, maxSum1Idx 0, 0, 0sum2, maxSum12, maxSum12Idx 0, 0, ()sum3, maxTotal 0, 0for 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 sum1maxSum1Idx i - k * 3 1if maxSum1 sum2 maxSum12:maxSum12 maxSum1 sum2maxSUm12Idx (maxSum1Idx, i - k * 2 1)if maxSum12 sum3 maxTotal:maxTotal maxSum12 sum3ans [*maxSUm12Idx, i - k 1]sum1 - nums[i - k * 3 1]sum2 - nums[i - k * 2 1]sum3 - nums[i - k 1]return ans三个无重叠子数组的最大和动态规划
链接 DP解法的难点在于如何回溯动态规划后的坐标而且要保持字典序最小。
class Solution:def maxSumOfThreeSubarrays(self, nums: List[int], k: int) - List[int]:n len(nums)s list(accumulate(nums, initial0))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] * 3i, j, idx 1, 3, 0while j 0:if f[i 1][j] f[i k][j - 1] s[i k - 1] - s[i - 1]: i 1else:ans[idx] i - 1idx 1i kj - 1return ans
