笔试强训 Day 42：最大差值、兑换零钱、小红的子串-北京尧图网络

Day 42最大差值解题思路股票问题 1 的思路代码实现importjava.util.*;publicclassSolution{publicintgetDis(int[]A,intn){intret0;intpreMinA[0];for(inti0;in;i){preMinMath.min(preMin,A[i]);retMath.max(ret,A[i]-preMin);}returnret;}}兑换零钱解题思路完全背包问题不需要关心选的钱的下标代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt(),aimin.nextInt();int[]arrnewint[n];for(inti0;in;i)arr[i]in.nextInt();int[]dpnewint[5010];Arrays.fill(dp,0x3f3f3f3f);dp[0]0;for(inti0;in;i){for(intj0;j5010;j){if(jarr[i])dp[j]Math.min(dp[j-arr[i]]1,dp[j]);}}System.out.println(dp[aim]0x3f3f3f3f?-1:dp[aim]);}}小红的子串解题思路前缀和思想滑动窗口滑动窗口统计字符种类不超过k的子串数量。子串总数可能达到n(n1)/2计数需使用long。固定right后合法子串的起点范围为[left, right]收集以 right 为结尾的子串个数。字符种类在[l,r]内的子串数为find(r) - find(l-1)。代码实现importjava.util.*;publicclassMain{privatestaticchar[]s;privatestaticintn;// 滑动窗口统计种类不超过 k 的个数// 关键滑动窗口不方便同时统计 [r,l], 只能先算 [0, r] 和 [0, l - 1], 否则会遗漏很多情况// 关键点计数可能达到约 n(n1)/2必须使用 longprivatestaticlongfind(intk){int[]hashnewint[26];intkind0;longcnt0;for(intleft0,right0;rightn;right){intinputs[right]-a;if(hash[input]0)kind;hash[input];while(kindk){intoutputs[left]-a;hash[output]--;if(hash[output]0)kind--;left;}// 对于每个 right窗口收缩到合法后所有起点位于 [left, right] 的子串都合法因此应增加// 关键固定 right只统计“以 right 位置结尾”的子串这种情况应该增加 right - left 1cnt(right-left1);}returncnt;}publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);nin.nextInt();intlin.nextInt(),rin.nextInt();sin.next().toCharArray();// 关键: 前缀和思路, 找 [l, r] - 找 [0, r] - [0, l - 1]System.out.println(find(r)-find(l-1));}}

笔试强训 Day 42：最大差值、兑换零钱、小红的子串

相关推荐

在gitea里把 pip 下载缓存全局持久化

Windows系统文件TrustedSignalCredProv.dll丢失找不到问题解决

目前的综合评价速度是前所未有的

更多资讯

AI服务响应异常排查实战：从告警到根因的分层定位方法

OpenCode与Claude Max插件集成解析及迁移方案

组态王6.55安装配置与避坑实战指南

Agent开发面试：MCP协议与工具生态治理实战解析

向量数据库在RAG系统中的核心作用与选型指南

提示工程架构师的心理健康管理与效能提升

今日更新

猫狗目标检测数据集：VOC/COCO/YOLO三格式一体化实战包

HDU2017多校标程复现：算法竞赛工程化真题沙盒

Codex Sandbox 隔离环境拆解：AI Agent 的临时实验室如何运作

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

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