当然可以!以下是 LeetCode 1955. 统计特殊子序列的数目 的 Go(Golang)实现,使用与 Java 版本相同的动态规划思路。

✅ 题目简述

给定一个只包含 0、1、2 的整数数组 nums,求其中 “特殊子序列” 的数量:

- 特殊子序列 = 非空、递增顺序 的 0...0, 1...1, 2...2(每种至少出现一次)
- 子序列不要求连续,但 顺序必须是 0 → 1 → 2

✅ Go 实现

func countSpecialSubsequences(nums []int) int {
    const MOD = 1_000_000_007
    f0, f1, f2 := 0, 0, 0 // 分别表示以0、01、012结尾的合法子序列数量

    for _, x := range nums {
        if x == 0 {
            // 新开一个 "0",或在已有 f0 后加一个 0
            f0 = (f0*2 + 1) % MOD
        } else if x == 1 {
            // 在任意 f0 后加 1,或在已有 f1 后加 1
            f1 = (f1*2 + f0) % MOD
        } else if x == 2 {
            // 在任意 f1 后加 2,或在已有 f2 后加 2
            f2 = (f2*2 + f1) % MOD
        }
    }

    return f2
}

🔍 说明

- 所有运算都对 1e9+7 取模,防止整数溢出。
- 初始状态:f0 = f1 = f2 = 0
- 每次遇到数字,按规则更新对应状态。
- 最终答案是 f2 —— 完整的 0...1...2 特殊子序列总数。

🧪 示例

输入:
nums := []int{0,1,2,2}

输出:
3

解释:特殊子序列为 [0,1,2](选第一个2)、[0,1,2](选第二个2)、[0,1,2,2](两个2都选),共 3 个。

如有需要,也可以提供带注释版本或单元测试。是否要?

 

Logo

欢迎加入DeepSeek 技术社区。在这里,你可以找到志同道合的朋友,共同探索AI技术的奥秘。

更多推荐