Leetcode-19 秋叶收藏集

描述

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

示例 1

输入：leaves = "rrryyyrryyyrr"

输出：2

解释：调整两次，将中间的两片红叶替换成黄叶，得到 "rrryyyyyyyyrr"

示例 2

输入：leaves = "ryr"

输出：0

解释：已符合要求，不需要额外操作

提示

3 <= leaves.length <= 10^5 leaves 中只包含字符 'r' 和字符 'y'

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/UlBDOe 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 

解题1

//前缀性问题 //分类关键是前缀所属节数（1r，1y，2r） //状态变量：i // 提示： // 整个leaves可分为三段：第一段红色，第二段黄色，第三段红色 // f代表某片叶子位于某一段，最少调整次数， // f[i][0] : 第i片叶子 位于第一段 // f[i][1] : 第i片叶子 位于第二段 // f[i][2] : 第i片叶子 位于第三段 const inf = math.MaxInt32 func minimumOperations(leaves string) int { n := len(leaves) // init runes := []rune(leaves) f := make([][]int, n) for i:=0;i<n;i++{ f[i]=make([]int, 3) } f[0][0] = isRed(runes, 0) f[0][1] = inf f[0][2] = inf // dp for j:=0;j<3;j++{ for i:=1;i<n;i++ { if j == 0 { f[i][j] = f[i-1][0] + isRed(runes, i) } if j == 1 { if i < 1 { f[i][j] = inf } else { f[i][j] = min(f[i-1][0], f[i-1][1]) + isYellow(runes, i) } } if j == 2 { if i < 2 { f[i][j] = inf } else { f[i][j] = min(f[i-1][1], f[i-1][2]) + isRed(runes, i) } } } } return f[n-1][2] } func isYellow(s []rune,i int) int { if s[i] == 'y' { return 0 } else { return 1 } } func isRed(s []rune,i int) int { if s[i] == 'r' { return 0 } else { return 1 } } func min(i, j int) int { if i < j { return i } return j }

优化

//前缀性问题 //分类关键是前缀所属节数（1r，1y，2r） //状态变量：i // 提示： // f的状态转移方程中 // 第i片叶子 仅依赖 第i-1片叶子 // 因此去除记忆化数组 func minimumOperations(leaves string) int { isYellow := func(i int) int { if leaves[i] == 'y' { return 0 } else { return 1 } } isRed := func(i int) int { if leaves[i] == 'r' { return 0 } else { return 1 } } min := func (i, j int) int { if i < j { return i } return j } // dp n := len(leaves) dp0, dp1, dp2 := isRed(0), inf, inf for i:=1; i < n ;i++{ dp2 = min(dp1, dp2) + isRed(i) dp1 = min(dp0, dp1) + isYellow(i) dp0 = dp0 + isRed(i) } return dp2 }