千问 LeetCode 1955.统计特殊子序列的数目 Go实现
以下是 LeetCode 1955. 统计特殊子序列的数目 的 Go(Golang)实现,使用与 Java 版本相同的动态规划思路。解释:特殊子序列为 [0,1,2](选第一个2)、[0,1,2](选第二个2)、[0,1,2,2](两个2都选),共 3 个。f0, f1, f2 := 0, 0, 0 // 分别表示以0、01、012结尾的合法子序列数量。// 在任意 f0 后加 1,或在已有 f1
当然可以!以下是 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 个。
如有需要,也可以提供带注释版本或单元测试。是否要?
更多推荐




所有评论(0)