文章目录无重复字符的最长子串滑动窗口算法算法思路时间复杂度空间复杂度代码实现示例执行流程使用集合滑动窗算法思路时间复杂度空间复杂度代码实现回文数字符串法代码实现数学反转法具体步骤代码实现复杂度分析无重复字符的最长子串滑动窗口算法滑动窗口算法是一种常用的解决字符串/数组子串问题的方法。其核心思想是使用两个指针表示窗口的左右边界右指针不断向右移动扩展窗口当窗口中不满足条件时出现重复字符左指针向右移动缩小窗口记录满足条件时的最大窗口大小算法思路使用两个指针start和end表示窗口的左右边界使用字典char_index_map记录字符最近出现的位置遍历字符串对于每个字符如果字符已经在当前窗口中出现过移动窗口起始位置到重复字符的下一个位置更新字符的最新位置计算当前窗口长度更新最大长度时间复杂度O(n)其中 n 是字符串的长度空间复杂度O(min(m, n))其中 m 是字符集的大小代码实现classSolution:deflengthOfLongestSubstring(self,s:str)-int: 滑动窗口解法 - 最优解 时间复杂度: O(n)其中 n 是字符串的长度 空间复杂度: O(min(m, n))其中 m 是字符集的大小 算法思路 1. 使用滑动窗口技术窗口包含当前无重复字符的子串 2. 使用字典记录字符最近出现的位置 3. 当遇到重复字符时移动窗口起始位置到重复字符的下一个位置 4. 每次迭代更新最大长度 # 字符到索引的映射记录字符最近出现的位置char_index_map{}max_length0# 最大长度start0# 窗口的起始位置forendinrange(len(s)):# 如果当前字符已经在窗口中出现过ifs[end]inchar_index_mapandchar_index_map[s[end]]start:# 移动窗口起始位置到重复字符的下一个位置startchar_index_map[s[end]]1# 更新字符的最新位置char_index_map[s[end]]end# 更新最大长度max_lengthmax(max_length,end-start1)returnmax_length示例执行流程!使用集合滑动窗算法思路使用集合来存储当前窗口中的字符使用两个指针表示窗口的左右边界右指针不断向右移动直到遇到重复字符遇到重复字符时左指针向右移动直到窗口中没有重复字符时间复杂度O(n)其中 n 是字符串的长度空间复杂度O(min(m, n))其中 m 是字符集的大小代码实现deflengthOfLongestSubstring(self,s:str)-int: 使用集合的滑动窗口解法 时间复杂度: O(n)其中 n 是字符串的长度 空间复杂度: O(min(m, n))其中 m 是字符集的大小 算法思路 1. 使用集合来存储当前窗口中的字符 2. 使用两个指针表示窗口的左右边界 3. 右指针不断向右移动直到遇到重复字符 4. 遇到重复字符时左指针向右移动直到窗口中没有重复字符 char_setset()max_length0left0right0whilerightlen(s):# 如果当前字符不在集合中添加到集合并移动右指针ifs[right]notinchar_set:char_set.add(s[right])right1max_lengthmax(max_length,right-left)else:# 如果当前字符在集合中移除左指针指向的字符并移动左指针char_set.remove(s[left])left1returnmax_length回文数字符串法优点简单直观缺点使用了额外的空间代码实现classSolution:defisPalindrome(self,x:int)-bool:sstr(x)returnss[::-1]数学反转法不将整数转为字符串而是通过数学方法反转数字的后半部分然后与前半部分比较。具体步骤特殊情况处理负数不可能是回文数因为前面有负号如果数字的最后一位是0但数字不是0那么它不可能是回文数如10、100等反转数字的后半部分初始化一个变量revertedNumber为0循环将数字的最后一位添加到revertedNumber中同时从原数字中去掉这一位循环条件是x revertedNumber这样我们只反转数字的一半比较前后半部分对于偶数长度的数字直接比较x和revertedNumber对于奇数长度的数字通过revertedNumber // 10去除中间的数字后再比较代码实现classSolution:defisPalindrome(self,x:int)-bool: 判断一个整数是否是回文数 参数: x: 要判断的整数 返回: bool: 如果是回文数返回True否则返回False 解题思路: 1. 负数不可能是回文数因为前面有负号 2. 0是回文数 3. 如果数字的最后一位是0但数字不是0那么它不可能是回文数 4. 我们将数字的后半部分反转然后与前半部分比较 5. 这样可以避免整数溢出问题并且不需要额外的空间 # 特殊情况处理# 1. 负数不可能是回文数# 2. 如果数字的最后一位是0但数字不是0那么它不可能是回文数ifx0or(x%100andx!0):returnFalserevertedNumber0whilexrevertedNumber:revertedNumberrevertedNumber*10x%10xx//10# 当数字长度为奇数时我们可以通过 revertedNumber//10 去除中间的数字# 例如当输入为12321时在while循环的末尾x 12revertedNumber 123# 由于处于中位的数字不影响回文它总是与自己相等所以我们可以简单地将其去除returnxrevertedNumberorxrevertedNumber//10复杂度分析时间复杂度O(log n)其中n是数字的大小空间复杂度O(1)只使用了常数空间