刷题练习心法之双指针

Q1题目链接https://leetcode.com/problems/valid-palindrome-ii/leetcode 680看到题目的第一思路和之前做的125题类似 都是用双指针方法判断字符串是否回文但是解题思路略有差异代码随想录之后的想法和总结正确的解题思路第一步正常双指针往中间走如果s[left] s[right] 那就很简单leftright--继续。第二步什么时候才动用“删除一次”的机会只有在s[left] ! s[right]的时候。这时你不能随便继续走也不能直接 false。你要问如果删掉左边这个字符剩下的是不是回文或者如果删掉右边这个字符剩下的是不是回文第三步为什么要分成两种尝试因为你第一次不匹配时不知道问题出在左边这个字符多余还是右边这个字符多余例如abca当走到b和c时不相等你要分别想跳过b看aca是不是回文跳过c看aba是不是回文只要有一种成立就返回true。时间复杂度以及空间复杂度时间复杂度O(n)原因主循环走一遍最多调用一次子函数也是 O(n)Q2题目链接https://leetcode.com/problems/reverse-string/leetcode #344看到题目的第一思路双指针代码随想录之后的想法和总结注意原地交换交换的关键永远是先保存一边的旧值通常保存左边更自然temp 左边 左边 右边 右边 temp时间复杂度以及空间复杂度Q3题目链接https://leetcode.com/problems/reverse-words-in-a-string/leetcode #151看到题目的第一思路这个问题虽然也是用双指针但是不是之前的题目那样的左右夹击双指针反而是一种同向 / 扫描双指针大概思路从右往左扫描字符串每次找到一个完整单词按找到的顺序拼到结果里。代码随想录之后的想法和总结难点1怎么跳过多余空格2怎么确定一个单词的左右边界比如从右往左扫描时遇到d开始怎么知道world整个单词在哪里结束、从哪里开始这就会用到“指针移动”。需要用双指针来记录两个位置比如i用来扫描当找到单词尾部时记一个j思路像这样i 从右往左走 先跳过空格 如果 i 0结束 j i // j 先记住当前单词末尾 然后继续往左走直到遇到空格 这时单词范围就是 [i1 ... j]这个区间就是一个完整单词。完整的解题思路从右往左扫描跳过空格记录单词结尾j往左找到单词开头用substring(i1, j1)取出单词用StringBuilder拼结果中间只加一个空格时间复杂度以及空间复杂度今日收获学习时长第一题注意这里用到了两个双指针循环因此观察一下他们的区别主循环允许犯一次错误可以删一个字符子循环不允许犯错必须严格回文逻辑是否允许出错行为主循环✅ 允许一次不等 → 尝试删除子循环❌ 不允许不等 → 直接 false第二题数据类型不同 语法不同 为什么会混乱因为你做的题125 / 680 →String344 →char[]逻辑一样双指针但数据类型不同 → 访问方式不同判断方法考试/面试用你只需要看函数参数 如果是这样public boolean isPalindrome(String s) ✔ 用s.charAt(i) 如果是这样public void reverseString(char[] s) ✔ 用s[i]