LeetCode-LCP19 秋叶收藏集

LeetCode-LCP19 秋叶收藏集 #

Solution 1 #

假设分割为 $leaves[:i], leaves[i:j], leaves[j:]$ , 记 $s[k]$ 为 $leaves[:k+1]$ 中 $‘r’$ 的数量. 那么一个分割 $0<i<j<n$ 的操作数为 $$ \begin{align*} cost&=(i-s[i-1]) + ((j-i)-((j-i)-(s[j-1]-s[i-1]))) + (n-j-(s[n-1]-s[j-1]))\ &=n-s[n-1]+(i-2s[i-1])-(j-2s[j-1]) \end{align*} $$ 遍历 $j$ 的同时维护 $\min_{0<i<j} (i-2s[i-1])$. 实现时需要注意下标的范围以及更新的逻辑关系.

代码如下:

class Solution:
    def minimumOperations(self, leaves: str) -> int:
        ans, s, m = inf, 0, inf
        n = len(leaves)
        for j in range(n - 1):
            s += leaves[j] == 'r' 
            ans = min(ans, -(j+1-2*s) + m) 
            m = min(m, j+1-2*s) 
        return ans + n - s - (leaves[-1] == 'r')