跳转至

LCP 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'

解法

方法一：动态规划

我们定义 \(f[i][j]\) 表示对于第 \(i\) 片叶子，处于状态 \(j\) 时的最小操作次数，其中 \(j\) 表示：

  • 状态 \(0\) 表示第 \(i\) 片叶子处于左边的红色部分；
  • 状态 \(1\) 表示第 \(i\) 片叶子处于中间的黄色部分；
  • 状态 \(2\) 表示第 \(i\) 片叶子处于右边的红色部分。

初始时，如果第 \(0\) 片叶子为红色，那么 \(f[0][0] = 0\)，如果第 \(0\) 片叶子为黄色，那么 \(f[0][0] = 1\)。对于其余的状态，我们初始化为 \(+\infty\)，表示在这种状态下无法完成任务。

考虑 \(f[i][j]\)，其中 \(i \ge 1\)：

如果第 \(i\) 片叶子为红色，那么 \(f[i][0]\) 只能从 \(f[i-1][0]\) 转移而来，而 \(f[i][1]\) 可以从 \(f[i-1][0]\) 和 \(f[i-1][1]\) 转移而来，此时需要额外操作一次，而 \(f[i][2]\) 可以从 \(f[i-1][1]\) 和 \(f[i-1][2]\) 转移而来，此时不需要额外操作一次。

如果第 \(i\) 片叶子为黄色，那么 \(f[i][0]\) 只能从 \(f[i-1][0]\) 转移而来，并且需要额外操作一次，而 \(f[i][1]\) 可以从 \(f[i-1][0]\) 和 \(f[i-1][1]\) 转移而来，此时不需要额外操作一次，而 \(f[i][2]\) 可以从 \(f[i-1][1]\) 和 \(f[i-1][2]\) 转移而来，并且需要额外操作一次。

最终的答案即为 \(f[n-1][2]\)，其中 \(n\) 表示红叶和黄叶的总数。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minimumOperations(self, leaves: str) -> int:
        n = len(leaves)
        f = [[inf] * 3 for _ in range(n)]
        f[0][0] = int(leaves[0] == "y")
        for i in range(1, n):
            if leaves[i] == "r":
                f[i][0] = f[i - 1][0]
                f[i][1] = min(f[i - 1][0], f[i - 1][1]) + 1
                f[i][2] = min(f[i - 1][2], f[i - 1][1])
            else:
                f[i][0] = f[i - 1][0] + 1
                f[i][1] = min(f[i - 1][0], f[i - 1][1])
                f[i][2] = min(f[i - 1][2], f[i - 1][1]) + 1
        return f[n - 1][2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minimumOperations(String leaves) {
        int n = leaves.length();
        final int inf = 1 << 30;
        var f = new int[n][3];
        for (var g : f) {
            Arrays.fill(g, inf);
        }
        f[0][0] = leaves.charAt(0) == 'r' ? 0 : 1;
        for (int i = 1; i < n; ++i) {
            if (leaves.charAt(i) == 'r') {
                f[i][0] = f[i - 1][0];
                f[i][1] = Math.min(f[i - 1][0], f[i - 1][1]) + 1;
                f[i][2] = Math.min(f[i - 1][2], f[i - 1][1]);
            } else {
                f[i][0] = f[i - 1][0] + 1;
                f[i][1] = Math.min(f[i - 1][0], f[i - 1][1]);
                f[i][2] = Math.min(f[i - 1][2], f[i - 1][1]) + 1;
            }
        }
        return f[n - 1][2];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minimumOperations(string leaves) {
        int n = leaves.size();
        int f[n][3];
        memset(f, 0x3f, sizeof(f));
        f[0][0] = leaves[0] == 'y';
        for (int i = 1; i < n; ++i) {
            if (leaves[i] == 'r') {
                f[i][0] = f[i - 1][0];
                f[i][1] = min(f[i - 1][0], f[i - 1][1]) + 1;
                f[i][2] = min(f[i - 1][2], f[i - 1][1]);
            } else {
                f[i][0] = f[i - 1][0] + 1;
                f[i][1] = min(f[i - 1][0], f[i - 1][1]);
                f[i][2] = min(f[i - 1][2], f[i - 1][1]) + 1;
            }
        }
        return f[n - 1][2];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func minimumOperations(leaves string) int {
    n := len(leaves)
    f := make([][3]int, n)
    inf := 1 << 30
    for i := range f {
        f[i] = [3]int{inf, inf, inf}
    }
    if leaves[0] == 'y' {
        f[0][0] = 1
    } else {
        f[0][0] = 0
    }
    for i := 1; i < n; i++ {
        if leaves[i] == 'r' {
            f[i][0] = f[i-1][0]
            f[i][1] = min(f[i-1][0], f[i-1][1]) + 1
            f[i][2] = min(f[i-1][2], f[i-1][1])
        } else {
            f[i][0] = f[i-1][0] + 1
            f[i][1] = min(f[i-1][0], f[i-1][1])
            f[i][2] = min(f[i-1][2], f[i-1][1]) + 1
        }
    }
    return f[n-1][2]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function minimumOperations(leaves: string): number {
    const n = leaves.length;
    const inf = 1 << 30;
    const f: number[][] = new Array(n).fill(0).map(() => new Array(3).fill(inf));
    f[0][0] = leaves[0] === 'y' ? 1 : 0;
    for (let i = 1; i < n; ++i) {
        if (leaves[i] === 'r') {
            f[i][0] = f[i - 1][0];
            f[i][1] = Math.min(f[i - 1][0], f[i - 1][1]) + 1;
            f[i][2] = Math.min(f[i - 1][2], f[i - 1][1]);
        } else {
            f[i][0] = f[i - 1][0] + 1;
            f[i][1] = Math.min(f[i - 1][0], f[i - 1][1]);
            f[i][2] = Math.min(f[i - 1][2], f[i - 1][1]) + 1;
        }
    }
    return f[n - 1][2];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    func minimumOperations(_ leaves: String) -> Int {
        let n = leaves.count
        let inf = Int.max / 2
        var f = Array(repeating: [inf, inf, inf], count: n)
        let leavesArray = Array(leaves)

        f[0][0] = leavesArray[0] == "r" ? 0 : 1

        for i in 1..<n {
            if leavesArray[i] == "r" {
                f[i][0] = f[i - 1][0]
                f[i][1] = min(f[i - 1][0], f[i - 1][1]) + 1
                f[i][2] = min(f[i - 1][1], f[i - 1][2])
            } else {
                f[i][0] = f[i - 1][0] + 1
                f[i][1] = min(f[i - 1][0], f[i - 1][1])
                f[i][2] = min(f[i - 1][1], f[i - 1][2]) + 1
            }
        }

        return f[n - 1][2]
    }
}

评论