#标签

本文介绍了四个字符串处理算法题解：1.计算字符串最后一个单词长度，使用getline读取整行并通过rfind定位空格；2.验证回文串，通过过滤非字母数字字符并转换大小写后双指针判断；3.寻找字符串中第一个唯一字符，利用数组统计字符出现次数；4.反转字符串，使用双指针交换首尾字符。每个解法都提供了详细思路和代码实现，涉及字符串常用操作和基础算法技巧。

给定一个二叉树的根节点root，返回它的中序遍历。中序遍历是三种主要的树遍历方法之一。左子树→根节点→右子树遍历左子树（递归）访问根节点遍历右子树（递归）树:123中序遍历:[1,3,2]-从1开始，向左（无）→处理1-向右到2，向左到3→处理3-回到2→处理2对于二叉搜索树（BST），中序遍历产生有序的值（升序），因为所有左子节点<根节点<所有右子节点。递归和迭代方法都实现了O(n)时间复杂度。

通过统计每个字符的出现次数，并检查出现次数为奇数的字符数量，我们可以有效地判断一个字符串是否能够通过重新排列字符形成一个回文串。这种方法的时间复杂度为O(n)，其中n是字符串的长度，空间复杂度为O(1)，因为hash数组的大小是固定的。

本文总结了四道动态规划进阶题目的解题思路，涵盖子序列、子数组、子串三类场景。每道题提供两种解法（基础DP和优化/非DP解法），并分析核心难点与易错点：最长递增子序列：基础DP解法O(n²)定义dp[i]为以i结尾的最长长度，优化解法O(nlogn)使用贪心+二分维护最小结尾数组；乘积最大子数组：需同时维护最大/最小乘积以处理负数反转情况，优化解法用变量代替数组降空间复杂度；分割等和子集：转化为01背包问题，注意总和奇偶判断和一维DP的倒序遍历；最长有效括号：DP解法分直接配对和嵌套配对两种情况，栈解

本文介绍了两个字符串处理问题及其滑动窗口解法。第一个问题要求找出无重复字符的最长子串长度，通过维护哈希集合和双指针实现，时间复杂度为O(n)。第二个问题需要找到字符串中所有字母异位词的起始索引，通过比较固定长度窗口内的字符频率数组来判定异位词。两个问题都利用了滑动窗口技术，通过动态调整窗口边界来高效解决问题，避免了暴力枚举的低效性。这些方法在处理字符串子串问题时具有通用性，能有效降低时间复杂度。

我们现在准备刷题了，时间紧、任务重，希望快速上手。只学对刷题最有用的20%Python知识，先能写题、跑通、过样例，再逐步变强。首先我们刷题前要知道的用list/dict（数组/哈希表）+循环+if，配合几个常用库（）和固定模板（双指针/栈/队列/BFS/二分/回溯/DP）就能解决：然后开始我们的新手LeetCode刷题入门指南。

遍历源数组，当前遍历到的数字为nums[i]，如果Map中存在以target-nums[i]为key值的元素，说明找到了两个数字加起来等于target的值，这时候返回当前索引和Map中以target-nums[i]为key值对应的value值即可。输入:strs=[“eat”,“tea”,“tan”,“ate”,“nat”,“bat”]输出:[[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]●value的该数字在数组中的位置。

数组&&矩阵理论基础

该题解使用快速选择算法在O(n)时间复杂度内找到数组中第k个最大元素。通过随机选择基准值将数组分为大于、小于和等于基准值三部分，然后递归地在相应分区中查找。如果k小于大于基准值的元素个数，则在较大分区继续查找；否则调整k值后在较小分区查找。这种分治策略平均时间复杂度为O(n)，最坏情况下为O(n²)。示例中对于输入[3,2,1,5,6,4]和k=2，算法正确返回第二大元素5。

本文解析了LeetCode160题"相交链表"的解法。通过长度差对齐法，先计算两链表长度差，让较长链表的指针先走差值步，使两指针处于同一起跑线后再同步前进，最终找到交点或确认无交点。该方法时间复杂度O(N+M)，空间复杂度O(1)，避免了复杂边界条件，体现了预处理思想。关键点包括指针复位、节点对象比较而非值比较，以及无需特殊处理无交点情况。

本文介绍了一种稳定分区链表的算法。给定单链表和目标值x，要求将小于x的节点排在前面且保持相对顺序。核心思路是使用四个指针维护两个区间（小于x和大于等于x），通过尾插法分别构建两个子链表，最后拼接并处理边界情况。关键点包括：1）尾插法保持稳定性；2）拼接后必须断开原链表的残留指针；3）处理全小或全大的边界情况。该算法时间复杂度O(n)，空间复杂度O(1)，适用于多种链表重排问题。建议在遍历时先断开当前节点以避免指针污染。

本文全面解析二叉树前序遍历的多种实现方法，包括递归辅助函数、简洁递归、迭代法、统一迭代法和Morris遍历，分析各方法的时间/空间复杂度及适用场景。重点推荐递归辅助函数作为面试首选方案，并详细讲解迭代法的栈实现过程。文章还提供面试实战技巧，包括边界条件处理、常见错误规避和进阶问题应对策略，强调理解"根左右"遍历顺序的核心思想。通过对比不同解法优劣，帮助读者掌握基础算法并应对不同面试场景要求。

可以用递归的方式向下遍历这颗树，定义一个s，表示目前路径的和，每走一个节点就把节点值加入s，然后判断哈希表中是否存在s-targetSum，如果存在说明找到了和为targetSum的路径，不存在就把更新哈希表。本题和“和为k的子数组有异曲同工之妙”，思路也相似。可以用一个哈希表去存储每条路径的和，两条路径和只差即为中间路径的和。需要注意的是，左右叶子节点递归完之后要回溯哈希表，以免对其他分支的技术产生问题。

摘要：本文提出了一种基于二分查找的算法，用于计算多辆公交车完成指定旅途数所需的最少时间。算法首先确定时间范围[0,最慢车×总趟数]，然后通过二分查找寻找满足条件的最小时间。每次验证时计算当前时间内所有车辆能完成的趟数总和，若不足则增大时间，否则尝试减小时间。算法利用提前退出优化和开区间二分查找提高效率，时间复杂度为O(nlogT)。示例表明该算法能正确找到最优解，如输入[1,2,3]和5趟时输出3。

给你一个正整数n，表示一个nxn的城市，同时给定一个二维数组buildings，其中buildings[i]=[x,y]表示位于坐标[x,y]的一个唯一建筑。输入:n=3,buildings=[[1,2],[2,2],[3,2],[2,1],[2,3]]输入:n=5,buildings=[[1,3],[3,2],[3,3],[3,5],[5,3]]输入:n=3,buildings=[[1,1],[1,2],[2,1],[2,2]]

给你一个单链表的头结点head，请将其按升序排序，并返回排序后的链表头结点。链表长度范围为[0,5*10^4]，节点值在[-10^5,10^5]之间。进阶要求是时间复杂度O(nlogn)，额外空间复杂度O(1)。leetcode​。

之后我们就可以遍历整个2维数组，不难发现，如果两个区间可以合并，那么第二个子数组的起点值一定小于第一个数组的终点，至于合并区间的终点，自然是第一个子数组和第二个子数组的终点的最大值。数组按区间的起始位置进行排序。排序后，区间的开始位置会按照从小到大的顺序排列。这是因为，区间的合并操作需要按顺序进行，所以首先要确保每个区间的起始位置从小到大排列。不断遍历数组即可求出所有的子区间。

动态规划算法-回文子串问题：40.让字符串成为回文串的最小插入次数解析

我们可以枚举所有a>b的平方和三元组(a,b,c)。由于a^2+b^2=b^2+a^2，所以(b,a,c)也是平方和三元组。所以只需统计a>b的情况，最后把统计结果乘以2，即为答案。是整数，那么我们找到了一个平方和三元组(a,b,c)，计数器加一。枚举a,b，如果a^2+b^2≤n*n(c<=n)且c=1925:统计平方和三元组的数目。（向0取整，不是四舍五入），这是“隐式类型转换”，

力扣（LeetCode）-542.01矩阵

本文介绍了判断括号字符串有效性的算法。通过使用栈结构来匹配括号对，当遇到左括号时入栈，遇到右括号时与栈顶元素匹配。算法首先检查字符串首字符是否为左括号，然后使用栈辅助处理，确保每个右括号都能与最近的左括号正确匹配。最终栈中应仅剩初始占位符，否则视为无效。该算法时间复杂度为O(n)，空间复杂度为O(n)，能高效处理各种括号组合的验证问题。

本文提出了一种高效算法，用于统计咒语与药水成功组合的数量。算法首先对药水数组排序，然后对每个咒语使用二分查找确定满足条件的最小药水强度。通过计算p_len-lower_bound位置，快速统计成功组合数。时间复杂度为O(mlogm+nlogm)，其中m为药水数量，n为咒语数量。该方案通过预处理和二分查找优化了组合统计效率，适合大规模数据处理。示例验证了算法的正确性，同时指出了潜在的除零和精度问题及改进方向。

请你找出nums中元素和最小的山形三元组，并返回其元素和。如果不存在满足条件的三元组，返回-1。如果nums的大小为n，则此算法时间复杂度为O(n)，空间复杂度为O(n)。nums[i]<nums[j]且nums[k]<nums[j]给你一个下标从0开始的整数数组nums。输入：nums=[5,4,8,7,10,2]输入：nums=[6,5,4,3,4,5]解释：可以证明nums中不存在山形三元组。输入：nums=[8,6,1,5,3]

先排序，引用次数从小到大排序，例如[3,0,6,1,5]引用X大于等于1的有Y个，5-1=4个。引用X大于等于3的有Y个，5-2=3个。引用X大于等于5的有Y个，5-3=2个。引用X大于等于6的有Y个，5-4=1个。引用X大于等于0的有Y个，5-0=5个。->[0,1,3,5,6],遍历数组。X>=Y时,Y即为H-index。