备战蓝桥杯————双指针技巧巧解数组3

利用双指针技巧来解决七道与数组相关的题目。

1. 两数之和 II - 输入有序数组： 给定一个按升序排列的数组，找到两个数使它们的和等于目标值。可以使用双指针技巧，在数组两端设置左右指针，根据两数之和与目标值的大小关系移动指针。
2. 删除有序数组中的重复项： 给定一个有序数组，原地删除重复出现的元素，使每个元素只出现一次，并返回新的长度。利用双指针技巧，一个指针用于遍历数组，另一个指针指向新数组的末尾。
3. 移除元素： 给定一个数组和一个值，原地移除数组中所有等于该值的元素，返回新数组的长度。同样利用双指针技巧，一个指针用于遍历数组，另一个指针用于记录非目标值的位置。
4. 移动零： 给定一个数组，将所有的 0 移动到数组的末尾，同时保持非零元素的相对顺序。使用双指针技巧，一个指针遍历数组，另一个指针记录非零元素的位置，并将非零元素依次移到前面。
5. 反转字符串： 反转给定的字符串。利用双指针技巧，一个指针从数组的开头向后移动，另一个指针从数组的末尾向前移动，依次交换两个指针指向的元素。
6. 最长回文子串： 找到给定字符串中的最长回文子串。作者通过介绍中心扩散法，结合双指针技巧，在遍历过程中寻找回文子串的中心点。
7. 删除排序链表中的重复元素： 删除排序链表中重复的元素，使得每个元素只出现一次。使用双指针技巧，一个指针遍历链表，另一个指针负责删除重复元素

一、反转字符串

题目描述

写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

• 1 <= s.length <= 105
• s[i] 都是 ASCII 码表中的可打印字符

解题技巧及代码

一般编程语言都会提供 reverse 函数，其实这个函数的原理非常简单可以利用双指针 从字符串两端开始先中间移动，依次交换字符串的每个字母即可。

class Solution {
    public void reverseString(char[] s) {
        int l=0,r=s.length-1;
        char temp;
        while(l<r){
            temp=s[l];
            s[l]=s[r];
            s[r]=temp;
            l++;
            r--;
        }
    }
}

结果展示

二、最长回文子串

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

解题思路及代码

寻找最长回文串的问题可以通过中心扩展法解决，其中双指针技巧是关键。思路可以总结为以下步骤：

• 对于每个字符 s[i]，以其为中心，利用 Pame(s, i, i) 寻找长度为奇数的回文串。此时，中心字符即为 s[i]。
• 对于相邻字符 s[i] 和 s[i+1]，以它们为中心，利用 Pame(s, i, i+1) 寻找长度为偶数的回文串。
• 在每次扩展中，更新最长回文串的长度和起始位置。

这样，通过遍历字符串，以每个字符及相邻字符为中心，不断扩展找到所有可能的回文串，最终得到最长回文串的长度和起始位置。 函数 Pame(s, l, r) 的作用是在给定字符串 s 中，以指定的左右指针 l 和 r 为中心，向两端扩展，寻找回文串。这个函数的具体实现应该考虑到奇数长度和偶数长度的情况。

class Solution {
    public String longestPalindrome(String s) {
        String res="";
        for(int i=0;i<s.length();i++){
            String res1=Pame(s,i,i);
            String res2=Pame(s,i,i+1);
            res=res.length() > res1.length() ? res:res1;
            res=res.length() > res2.length() ? res:res2;
        }
        return res;
    }

    public String Pame(String s,int l,int r){
        while(l>=0 && r<s.length() && s.charAt(l)==s.charAt(r) ){
            l--;
            r++;
        }
        return s.substring(l+1,r);
    }
}

结果展示