尧图网站建设 尧图网络
  • 首页
  • 关于我们
  • 服务项目
  • 案例展示
  • 建站流程
  • 资讯中心
  • 联系我们
首页/资讯中心/详情

Kimi LeetCode 3351. 好子序列的元素之和 Python3实现

Kimi    LeetCode 3351. 好子序列的元素之和 Python3实现
📅 发布时间:2026/6/24 4:31:10

```python
class Solution:
def sumOfGoodSubsequences(self, nums: List[int]) -> int:
MOD = 10**9 + 7
mx = max(nums) if nums else 0

# f[i] = 以值 i 结尾的所有好子序列的元素和
f = [0] * (mx + 1)
# g[i] = 以值 i 结尾的所有好子序列的数量
g = [0] * (mx + 1)

for x in nums:
# 1. 单独作为一个子序列
f[x] = (f[x] + x) % MOD
g[x] = (g[x] + 1) % MOD

# 2. 接在以 x-1 结尾的好子序列后面
if x > 0:
f[x] = (f[x] + f[x - 1] + g[x - 1] * x) % MOD
g[x] = (g[x] + g[x - 1]) % MOD

# 3. 接在以 x+1 结尾的好子序列后面
if x + 1 <= mx:
f[x] = (f[x] + f[x + 1] + g[x + 1] * x) % MOD
g[x] = (g[x] + g[x + 1]) % MOD

return sum(f) % MOD
```

核心思路:

- 好子序列要求相邻元素差的绝对值恰好为 1。处理数字 x 时,它可以:
1. 单独作为一个好子序列。
2. 接在所有以 x-1 结尾的好子序列后面。
3. 接在所有以 x+1 结尾的好子序列后面。

- `f[x]` 记录以值 x 结尾的所有好子序列的元素和,`g[x]` 记录对应的数量。
- 从 x-1 转移时,新增贡献为 `f[x-1] + g[x-1] * x`(原有子序列和 + 每个子序列末尾新增 x)。
- 最终答案为 `sum(f) % MOD`。

复杂度:
- 时间 O(n + M),M = \max(\text{nums})。
- 空间 O(M)。

相关新闻

  • CY5-amine Cy5标记氨基 花菁染料Cy5-氨基 CY5-NH2 结构说明
  • Web安全面试指南:从SQL注入到业务逻辑漏洞的攻防实战解析
  • 台积电CoPoS封装取代CoWoS-玻璃基板产业化-AI芯片封装革命

最新新闻

  • 10分钟掌握Swift-Verge状态管理:面向初学者的实用入门教程
  • WinBoat:在Linux上无缝运行Windows应用的终极方案,你还在用虚拟机吗?
  • 发现 VS Code 的隐藏宝藏:7 个你或许不知道却能让效率翻倍的功能
  • 【工具优化】Windows工具MobaXterm_Personal_20.3解除最多保存14个Session的限制_20260505
  • 如何让喜欢的角色住进桌面?5分钟快速上手DyberPet桌宠系统
  • 项目实训博客(四)从Vulkan到D3D12:注入与拦截架构演变

日新闻

  • 终极指南:如何用shadPS4在电脑上免费畅玩PS4游戏
  • 打造个性化Instagram Clone:主题定制与用户体验优化技巧
  • 未来展望:RoseTTAFold-All-Atom的发展路线图与社区支持资源汇总

周新闻

  • Visual C++运行库修复终极指南:5分钟快速解决Windows软件启动错误
  • 手把手教你构建统计局地区经济数据爬虫:从环境搭建到数据持久化全指南
  • 2026多Agent深度解析:用AI团队替代单一模型,四种架构实战落地

月新闻

  • 【总结】入门篇:50句话让你记住架构核心概念
  • WeChatMsg技术方案解析:实现Mac微信数据自主管理的完整解决方案
  • WeChatMsg:革新性微信数据备份方案,打造你的专属数字记忆库

关于尧图

  • 公司简介
  • 团队介绍
  • 企业文化
  • 荣誉资质

服务项目

  • 定制开发
  • 电商建站
  • UI 设计
  • 运维服务

快速链接

  • 案例展示
  • 建站流程
  • 常见问题
  • 资讯中心

联系方式

  • 📍北京市朝阳区互联网产业园 A 座 10 层
  • 📞400-888-8888
  • ✉️contact@rkmt.cn
  • 🕐周一至周日 9:00-21:00

© 2024 北京尧图网络科技有限公司 版权所有 | 京 ICP 备 XXXXXXXX 号