DeepSeek LeetCode 3699. 锯齿形数组的总数 I Go实现-北京尧图网络

gopackage mainfunc zigZagArrays(n int, l int, r int) int {const MOD int64 1_000_000_007m : r - l 1if n 1 {return m}// up[i]: 以值 i 结尾且最后一步为上升的方案数// down[i]: 以值 i 结尾且最后一步为下降的方案数up : make([]int64, m)down : make([]int64, m)for i : 0; i m; i {up[i] 1down[i] 1}// 重复添加 n-1 个元素for step : 1; step n; step {// 前缀和prefixDown[i] sum(down[0..i-1])prefixDown : make([]int64, m1)for i : 0; i m; i {prefixDown[i1] (prefixDown[i] down[i]) % MOD}// 后缀和suffixUp[i] sum(up[i..m-1])suffixUp : make([]int64, m1)for i : m - 1; i 0; i-- {suffixUp[i] (suffixUp[i1] up[i]) % MOD}newUp : make([]int64, m)newDown : make([]int64, m)for x : 0; x m; x {// 上升前一步必须为下降且前一个值 xnewUp[x] prefixDown[x] // sum(down[0..x-1])// 下降前一步必须为上升且前一个值 xnewDown[x] suffixUp[x1] // sum(up[x1..m-1])}up, down newUp, newDown}var total int64for i : 0; i m; i {total (total up[i] down[i]) % MOD}return int(total)}复杂度分析· 时间复杂度O(n \cdot m)其中 m r - l 1。· 空间复杂度O(m)。关键点· 用 up 和 down 分别表示最后一步方向为上升/下降的方案数。· 使用前缀和和后缀和将状态转移优化为 O(m)整体 O(n \cdot m)。· 当 n1 时直接返回 m因为任意单元素数组都满足条件。· 所有计算取模 10^97。

DeepSeek LeetCode 3699. 锯齿形数组的总数 I Go实现

相关推荐

AI记忆框架对比：Mem0、MemOS与TiMem架构解析

基于兰姆波与深度学习的航空航天结构健康监测技术

AI时代提示词工程：从代码编写到需求描述的技能跃迁

更多资讯

Python+Playwright实战：破解Shopee弧形滑块验证码的完整方案

BrewUI：把 Homebrew 变成可视化应用，包管理与服务状态一目了然

osquery YARA 扫描实战指南：yara_events、yara_file 与 yara_process 的配置、查询与底层原理

10个GTweak高级技巧：这款Windows优化工具只有老用户才知道的隐藏功能

GitHub访问慢、下载失败怎么办？本周热点项目与新手上传全攻略

RAG查询路由技术：原理、实现与优化策略

今日更新

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？