响应式网站和普通网站济南全包圆装修400电话

响应式网站和普通网站,济南全包圆装修400电话,营销网站开发选哪家,网络科技公司网站首页LeetCode 100天挑战 Day 3#xff1a;判断子序列与汇总区间 目录 前言题目一#xff1a;判断子序列问题 题目描述解题思路代码实现分析复杂度分析进阶优化#xff1a;批量处理方案 题目二#xff1a;汇总区间问题 题目描述解题思路代码实现分析复杂度分析边界情况处理 算…LeetCode 100天挑战 Day 3判断子序列与汇总区间目录前言题目一判断子序列问题题目描述解题思路代码实现分析复杂度分析进阶优化批量处理方案题目二汇总区间问题题目描述解题思路代码实现分析复杂度分析边界情况处理算法思想对比与总结实际应用场景参考资源前言在算法学习的过程中字符串处理和数组操作是两个非常重要的领域。今天的两道题目分别代表了这两个领域的经典问题判断子序列问题考察我们对字符串匹配的理解而汇总区间问题则训练我们对有序数组的处理能力。这两个问题虽然难度不同但都蕴含着重要的算法思想。今日题目统计信息题目难度知识点通过率核心思想判断子序列简单双指针、字符串匹配52.1%贪心算法汇总区间中等数组遍历、区间合并58.3%一次遍历题目一判断子序列问题题目描述给定字符串 s 和 t判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。进阶挑战如果有大量输入的 S称作 S1, S2, …, Sk 其中 k 10亿你需要依次检查它们是否为 T 的子序列。在这种情况下你会怎样改变代码示例 1输入s abc, t ahbgdc 输出true示例 2输入s axc, t ahbgdc 输出false解题思路这个问题的核心思想是贪心算法结合双指针技巧。我们需要在t中按顺序寻找s的每个字符基础思路使用两个指针一个指向s的当前位置一个指向t的当前位置在t中顺序查找s的当前字符找到后s的指针向前移动t的指针从找到位置的下一个位置继续查找如果s的所有字符都能在t中按顺序找到则s是t的子序列优化考虑如果s的长度大于t的长度直接返回false如果s为空字符串直接返回true如果s和t长度相等且内容相同返回true代码实现分析classSolution{publicbooleanisSubsequence(Strings,Stringt){intlen1s.length();intlen2t.length();// 边界情况处理if(len10){returntrue;}if(len20){returnfalse;}if(len1len2){returnst;}// 主逻辑双指针查找intindex0;// t中的查找起始位置for(inti0;ilen1;i){if(indexlen2){returnfalse;// t已经遍历完但s还有字符未匹配}// 从index开始在t中查找s.charAt(i)for(intjindex;jlen2;j){if(s.charAt(i)t.charAt(j)){indexj1;// 更新下次查找的起始位置break;}// 如果遍历到最后一个字符都没找到匹配if(jlen2-1){returnfalse;}}}returntrue;}}代码逐行解析长度获取与边界处理intlen1s.length();intlen2t.length();if(len10){returntrue;// 空字符串是任何字符串的子序列}if(len20){returnfalse;// 非空字符串不是空字符串的子序列}if(len1len2){returnst;// 长度相同时只有完全相等才是子序列}核心查找逻辑intindex0;// 记录在t中查找的起始位置for(inti0;ilen1;i){// 遍历s的每个字符for(intjindex;jlen2;j){// 在t中从index位置开始查找if(s.charAt(i)t.charAt(j)){indexj1;// 找到后更新下次查找位置break;}}}复杂度分析指标分析过程结果时间复杂度最坏情况下需要遍历整个t字符串O(m×n)其中mlen(s), nlen(t)空间复杂度只使用了常数个额外变量O(1)注意虽然时间复杂度看起来是O(m×n)但在实际运行中由于t的指针不会回退实际时间复杂度更接近O(mn)。进阶优化批量处理方案针对进阶挑战中提到的大量输入情况我们需要对t进行预处理classSolution{// 预处理t构建字符位置映射privateMapCharacter,ListIntegerpreprocess(Stringt){MapCharacter,ListIntegercharPositionsnewHashMap();for(inti0;it.length();i){charct.charAt(i);charPositions.computeIfAbsent(c,k-newArrayList()).add(i);}returncharPositions;}// 使用二分查找优化子序列检查publicbooleanisSubsequenceOptimized(Strings,Stringt){MapCharacter,ListIntegercharPositionspreprocess(t);intcurrentIndex-1;for(charc:s.toCharArray()){if(!charPositions.containsKey(c)){returnfalse;}ListIntegerpositionscharPositions.get(c);// 找到第一个大于currentIndex的位置intfoundIndexCollections.binarySearch(positions,currentIndex1);if(foundIndex0){foundIndex-foundIndex-1;}if(foundIndexpositions.size()){returnfalse;}currentIndexpositions.get(foundIndex);}returntrue;}}优化方案分析方法预处理时间单次查询时间适用场景原始方法O(1)O(mn)单次查询优化方法O(n)O(m×logk)大量查询题目二汇总区间问题题目描述给定一个无重复元素的有序整数数组nums。区间[a,b]是从a到b包含的所有整数的集合。返回恰好覆盖数组中所有数字的最小有序区间范围列表。也就是说nums的每个元素都恰好被某个区间范围所覆盖并且不存在属于某个区间但不属于nums的数字x。输出格式要求“a-b”如果a ! b“a”如果a b示例 1输入nums [0,1,2,4,5,7] 输出[0-2,4-5,7]示例 2输入nums [0,2,3,4,6,8,9] 输出[0,2-4,6,8-9]解题思路这个问题可以通过一次遍历解决核心思想是识别连续的数字序列主要思路遍历数组记录当前区间的起始位置检查当前数字与下一个数字是否连续如果不连续结束当前区间并开始新的区间处理最后一个区间的特殊情况关键判断条件nums[i] 1 ! nums[i 1]当前数字与下一个数字不连续i 1 nums.length已到达数组末尾代码实现分析classSolution{publicListStringsummaryRanges(int[]nums){ListStringresultnewArrayList();// 边界情况空数组if(nums.length0){returnresult;}intstart0;// 当前区间的起始位置for(inti0;inums.length;i){// 判断是否需要结束当前区间if(i1nums.length||nums[i]1!nums[i1]){if(starti){// 单个数字的区间result.add(String.valueOf(nums[start]));}else{// 多个数字的连续区间result.add(nums[start]-nums[i]);}starti1;// 开始新区间}}returnresult;}}代码详细解析初始化与边界处理ListStringresultnewArrayList();if(nums.length0){returnresult;// 空数组直接返回空列表}核心遍历逻辑intstart0;// 记录当前区间的起始索引for(inti0;inums.length;i){// 检查区间结束条件if(i1nums.length||nums[i]1!nums[i1]){// 处理区间结束}}区间格式化逻辑if(starti){// 单个元素区间result.add(String.valueOf(nums[start]));}else{// 多个元素的连续区间result.add(nums[start]-nums[i]);}starti1;// 更新下一个区间的起始位置复杂度分析指标分析结果时间复杂度只需要一次遍历O(n)空间复杂度存储结果列表最坏情况n个区间O(n)边界情况处理让我们分析各种可能的输入情况边界情况详细分析输入情况处理方式预期输出空数组[]直接返回空列表[]单元素[5]单个元素的区间[5]全连续[1,2,3,4]整个数组作为一个区间[1-4]全不连续[1,3,5,7]每个元素单独成区间[1,3,5,7]负数[-3,-2,-1,0]包含负数的连续区间[-3-0]算法思想对比与总结共同特点分析虽然这两道题目看似不同但它们都体现了几个重要的算法思想一次遍历原则子序列问题顺序查找不回退区间汇总问题线性扫描动态分组边界条件处理都需要仔细处理空输入等特殊情况都涉及循环结束条件的精确判断状态维护子序列问题维护当前查找位置区间汇总问题维护当前区间起始位置解题技巧总结技巧子序列问题应用区间汇总问题应用双指针✅ 在t中顺序查找s的字符✅ start和i形成区间边界贪心算法✅ 每次找到最早匹配的位置✅ 尽可能扩展连续区间状态机✅ 维护查找状态✅ 维护区间开始/结束状态边界处理✅ 多种特殊情况处理✅ 数组边界和连续性判断实际应用场景判断子序列的应用文本搜索与匹配搜索引擎的关键词匹配文本编辑器中的模式查找生物信息学中的DNA序列匹配数据验证输入格式验证协议解析中的字段顺序检查版本兼容性检查汇总区间的应用数据压缩连续数字范围的压缩存储日志文件的压缩记录网络地址范围表示数据分析时间序列数据的区间分析传感器数据的连续区间识别金融数据的连续涨跌区间统计性能优化建议// 子序列问题性能测试publicvoidperformanceTest(){Stringta.repeat(1000000)b.repeat(1000000);Stringsab;longstartTimeSystem.currentTimeMillis();booleanresultisSubsequence(s,t);longendTimeSystem.currentTimeMillis();System.out.println(结果: result, 耗时: (endTime-startTime)ms);}// 区间汇总问题扩展测试publicvoidrangeSummaryExtended(){// 测试大数据量int[]largeArraynewint[1000000];for(inti0;ilargeArray.length;i){largeArray[i]i*2;// 创建间隔为2的序列}ListStringresultsummaryRanges(largeArray);System.out.println(结果数量: result.size());}总结与思考通过今天对这两个算法题的深入分析我们可以得到以下几点重要启示算法思维的提升问题抽象能力将具体问题抽象为算法模型识别问题的核心本质选择合适的算法策略代码实现技巧边界条件的重要性状态维护的方法代码可读性与效率的平衡优化思考方式从暴力解法到最优解的思考路径时间复杂度与空间复杂度的权衡实际应用场景对算法选择的影响学习建议循序渐进先理解基本思路再考虑优化方案最后思考扩展应用举一反三总结通用的解题模式建立知识间的联系培养算法直觉实践验证编写代码验证思路测试各种边界情况分析性能瓶颈编程感悟算法学习不仅是掌握解题技巧更重要的是培养分析问题、解决问题的思维能力。每一道题目都是一个思维训练的机会通过深入思考和优化我们能够不断提升自己的编程水平。参考资源LeetCode官方题库 - 判断子序列LeetCode官方题库 - 汇总区间Java字符串处理官方文档Java集合框架文档算法与数据结构学习指南二分查找算法详解贪心算法原理与应用如果你觉得这篇文章对你有所帮助欢迎点赞、收藏和关注如有疑问或不同见解欢迎在评论区交流讨论。标签#LeetCode #算法 #Java #字符串 #数组 #双指针 #贪心算法 #数据结构