秋叶收藏集"/>

秋叶收藏集

秋叶收藏集

小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves， 字符串 leaves 仅包含小写字符 r 和 y， 其中字符 r 表示一片红叶，字符 y 表示一片黄叶。
出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。

示例 1：

输入：leaves = "rrryyyrryyyrr"输出：2解释：调整两次，将中间的两片红叶替换成黄叶，得到 "rrryyyyyyyyrr"

示例 2：

输入：leaves = "ryr"输出：0解释：已符合要求，不需要额外操作

提示：

1. 3 <= leaves.length <= 10^5
2. leaves 中只包含字符 ‘r’ 和字符 ‘y’

解题思路：

一 ：r是令字符串都是‘r’所需要的步骤

则字符串里面，有n个y就需要修改n次，就记作n
举例：r(‘rrrry’)=1
r(‘ryryr’)=2

二： ry 是将字符串变作r y 形式

那么连续的r后面加一个y，或者在已有的ry形式后面再加一个y就可以满足

想要得到最优解，就要：

​ 令之前为r形式,令最后一位是y

​ 或者令之前为ry形式，令最后一位是y

​ ry(n位) = min(r(n-1位)，ry(n-1位))+1-int(第六位是否为‘y’）

​ 举例：现有’r r r r y r’，前五位是‘rrrry’ 第六位是‘r’

​ 两种情况

​ 令之前为r形式,令最后一位是y

​ r(‘rrrry’)+ 1-int(第六位是否为y)=1+1-0=2 变为 rrrrr y

​ 令之前为ry形式，令最后一位是y

​ ry(‘rrrry’) + 1-int(第六位是否为y)=0+1-0=1 变为 rrrr y y

​ 使用min()判断r形式与ry形式优劣，获得最优解

三：ryr将字符串变为ryr形式

​ 令之前为ry形式 令最后一位为r

​ 或令之前为ryr形式，令最后一位为r

​ ryr(n位) = min(ry(n-1位)，ryr(n-1位)) + int(第六位是否为‘y’）

​ 与 二：ry 同理不再举例

四：代码实现

def demo(leaves):  r , ry , ryr = int(leaves[0]=="y") , float("inf") , float("inf")  for i in range(1,len(leaves)):  x = int(leaves[i]=='y')  r , ry , ryr = r+x , min(r,ry)+(1-x) , min(ry,ryr)+x return ryr