链接：LeetCode
[Leetcode]5436. 一维数组的动态和
给你一个数组 nums 。数组「动态和」的计算公式为：(runningSum[i] = sum(nums[0]…nums[i]))。
请返回 nums 的动态和。
累加即可。
class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
res = []
cur = 0
for num in nums:
cur += num
res.append(cur)
return res
[Leetcode]5437. 不同整数的最少数目
给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。
哈希表，排序即可。
import collections
class Solution:
def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
dic = collections.Counter(arr)
n = len(set(arr))
vals = sorted(dic.values())
for val in vals:
if k<=0:break
if k>=val:
n-=1
k-=val
return n
[Leetcode]5438. 制作 m 束花所需的最少天数
给你一个整数数组 bloomDay，以及两个整数 m 和 k 。
现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。
花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。
请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。
如果mid天满足，那么mid+1天也满足，满足单调性，可以二分check。对于当前天数mid，贪心计算有多少个连续的小于等于mid的k天，假设有cnt个连续k天，判断cnt是否大于等于m即可
class Solution:
def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
def check(day):
n = len(bloomDay)
flower = [True if v <= day else False for v in bloomDay]
s, t = 0, 0
count = 0
while t < n:
if not flower[t]:
count += (t - s) // k
s = t+1
t += 1
count += (t - s) // k
return count >= m
left, right = min(bloomDay), max(bloomDay)
while left <= right:
day = (left + right) // 2
if check(day):
right = day-1
else:
left = day+1
return left if check(left) else -1
[Leetcode]5188. 树节点的第 K 个祖先
给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 (parent[i])是节点 i 的父节点。树的根节点是编号为 0 的节点。
请你设计并实现 getKthAncestor(int node, int k) 函数，函数返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点，返回 -1 。
树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。
DP倍增法，本质类似于二分法。假设状态(dp[node][j])，表示 node 的第 2^j 个祖先，则(dp[node][j] = dp[ dp[node][j-1] ][j-1])
class TreeAncestor:
def __init__(self, n: int, parent: List[int]):
self.cols = 20 # log(50000) < 20
self.dp = [[-1] * self.cols for _ in range(n)]
for i in range(n):
self.dp[i][0] = parent[i]
# 动态规划设置祖先, dp[node][j] 表示 node 往前推第 2^j 个祖先
for i in range(n):
for j in range(1, self.cols):
if self.dp[i][j-1] != -1:
self.dp[i][j] = self.dp[self.dp[i][j-1]][j-1]
return
def getKthAncestor(self, node: int, k: int) -> int:
for i in reversed(range(self.cols)):
if k & (1 << i):
node = self.dp[node][i]
if node == -1:
break
return node
参考：Leetcode