LCP-19 秋叶收藏集

题目回顾

解法思路

这题有两种解法,先着重写一下前缀和+动态规划的解法。

要将树叶分成红-黄-红三部分,关键就是要找到2个分界点。不妨将这两个点设为x,y.

[0,x-1] 红

[x,y-1] 黄

[y,n-1] 红

那么我们需要操作的次数,就是第一段中黄色的个数、第二段中红色的个数以及第三段中黄色的个数之和,我们的目标就是要找到这个和的最小值

为了更方便的表示每段中不同颜色的个数,我们可以定义一个前缀和数组

所以需要进行的操作次数可表示为:

$n-sumR\left[ n-1 \right] $是常数不用管,而观察到x,y相关的表达式形式是统一的,因此不妨令

要求op的最小值,就转化为求$t[x]-t[y]$的最小值,或者说,求$t[y]-t[x],(y>x)$的最小值。那么问题就转化成求股票最大差价的问题了,就是一个典型的动态规划问题。

下面需要关心一下x,y的取值范围。

那么x的范围就是$[1,n-2]$.

因此只需一次遍历t[n]数组,就能得到最大差值。

总体来说,时间复杂度为O(n),空间复杂度也为O(n)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def minimumOperations(self, leaves: str) -> int:
n=len(leaves)
sumR = [0]*n
sumR[0]=int(leaves[0]=='r')
# 计算 sumR
for i in range(1,n):
sumR[i]=sumR[i-1]+int(leaves[i]=='r')
# 计算 t
for i in range(n):
t[i]=i+1-2*sumR[i]
minT=float("inf")
max_delta=-float("inf")
# 计算 max(t[x]-t[y])
for i in range(1,n-1):
minT=min(t[i-1],minT)
max_delta=max(max_delta,t[i]-minT)
return n-sumR[n-1]-max_delta
作者

江风引雨

发布于

2020-10-03

更新于

2020-10-03

许可协议

CC BY 4.0

评论