[数据结构与算法]第9周 算法思想-双指针

Leetcode 题解 - 双指针

• 有序数组的 Two Sum 167. Two Sum II - Input array is sorted(Easy)
• 两数平方和 633.Sum of Square Numbers(Medium)
• 反转字符串中的元音字符345. Reverse Vowels of a String(Easy)
• 回文字符串680. Valid Palindrome II(Easy)
• 归并两个有序数组 88. Merge Sorted Array(Easy)
• 判断链表是否存在环 141. Linked List Cycle(Easy)
• 最长子序列524.Longest Word in Dictionary through Deleting(Medium)

双指针法小结：
双指针法个人理解也可称为哨兵法，当遍历的每一步都能根据题目直接定义好时，我们只需要两个指针然后按规则进行移动即可。这个方法主要用于：

• 排好序的数组：由于数组的特殊性，对数组值进行搜索
• 链表找环：经典应用
• 字符串匹配：找子串

有序数组的 Two Sum

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        /*
        思路：典型的双指针法
        时间复杂度：O(n)
        空间复杂度：O(1)
        */
        int i = 0, j = numbers.size() - 1;
        vector<int> ans;
        
        while(i < j){
            if(numbers[i] + numbers[j] == target){
                ans.push_back(i+1);
                ans.push_back(j+1);
                break;
            }
            else if(numbers[i] + numbers[j] > target)
                j -= 1;
            else if(numbers[i] + numbers[j] < target)
                i += 1;
        }
        return ans;
    }
};

两数平方和

class Solution {
public:
    bool judgeSquareSum(int c) {
        /*
        思路：双指针法搜索[1,sqrt(c)+1]，寻找平方和为c的数值对，注意i，j的初始取值非常重要
        时间复杂度：O(log(n))
        空间复杂度：O(1)
        */
        long long i = 0, j = sqrt(c);
        long long cL = c;
        
        while(i <= j){
            if(i*i + j*j == cL)
                return true;
            else if(i*i + j*j < cL)
                i += 1;
            else if(i*i + j*j > cL)
                j -= 1;
        }
        return false;
    }   
};

反转字符串中的元音字符

class Solution {
public:
    bool isVowel(char c){
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
    }
    string reverseVowels(string s) {
        /*
        思路：双指针法，两个指针寻找到元音后交换
        时间复杂度：O(n)
        空间复杂度：O(n)
        */
        int i = 0, j = s.size()-1;
        while(1){
            while(i < s.size()-1 && !isVowel(s[i]))
                i += 1;
            while(j > 0 && !isVowel(s[j]))
                j -= 1;
            if(i >= j)
                break;
            else{
                swap(s[i], s[j]);
                i += 1;
                j -= 1;
            }
                
        }
        return s;
    }
};

回文字符串

class Solution {
public:
    bool validPalindrome(string s) {        
        /*
        思路：双指针法，遍历构成中如果遇到不对称的字符，则考虑两种删掉一个字符的情况，如果存在删掉后是回文则满足条件，否则不满足
        */
        int i = 0, j = s.size() - 1;
        while(i < j){
            if(s[i] != s[j])
                return isPalindrome(s, i+1, j) || isPalindrome(s, i, j-1);
            i += 1;
            j -= 1;
        }
        return true;
        
    }
    bool isPalindrome(string s, int start, int end){
        while(start < end){
            if(s[start] != s[end])
                return false;
            start += 1;
            end -= 1;
        }
        return true;
    }
};

归并两个有序数组

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> merge;
        int i = 0, j = 0;
        while(i < m || j < n){
            if(i == m){
                merge.push_back(nums2[j]);
                j += 1;
            }
            else if(j == n){
                merge.push_back(nums1[i]);
                i += 1;
            }
            else{
                if(nums1[i] <= nums2[j]){
                    merge.push_back(nums1[i]);
                    i += 1;
                }
                else{
                    merge.push_back(nums2[j]);
                    j += 1;
                }
            }
        }
        for(int k = 0;k < m+n; k++)
            nums1[k] = merge[k];
        
    }
};

判断链表是否存在环

class Solution {
public:
    bool hasCycle(ListNode *head) {
        /*
        思路：快慢指针
        */
        if(head == NULL)
            return false;
        
        ListNode* fast = head, *slow = head;
        
        while(1){
            if(fast->next != NULL && fast->next->next != NULL){
                fast = fast->next->next;
                slow = slow->next;
            }
            else
                return false;
            
            if(fast == slow)
                return true;
        }
        return false;
    }
};

最长子序列

class Solution {
public:
    bool match(string s1, string s2){
        // 判断s2是不是s1的子串
        int i = 0, j = 0;
        while(i < s1.size()){
            if(s1[i] == s2[j]){
                j += 1;
                if(j == s2.size())
                    return true;
            }
            i += 1;
        }
        return false;
    }
    string findLongestWord(string s, vector<string>& dictionary) {
        string ans = "";
        for(int i = 0;i < dictionary.size(); i++){
            bool isMatch = match(s, dictionary[i]);
            if(isMatch){
                if(dictionary[i].size() > ans.size())
                    ans = dictionary[i];
                else if(dictionary[i].size() == ans.size() && dictionary[i] < ans)
                    ans = dictionary[i];
            }
        }
        return ans;
    }
};