Leetcode 刷题笔记-Leetcode 101 第3章 双指针

Leetcode 刷题笔记-Leetcode 101 第3章 双指针

双指针

双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延伸到多个数组的多个指针。

若两个指针指向同一数组，遍历方向相同且不会相交，则也称为滑动窗口（两个指针包围的区域即为当前的窗口），经常用于区间搜索。

若两个指针指向同一数组，但是遍历方向相反，则可以用来进行搜索，待搜索的数组往往是排好序的。

Two Sum

Leetcode 167

在一个增序的整数数组里找到两个数，使它们的和为给定值。已知有且只有一对解。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> result;
        int left = 0;
        int right = numbers.size() - 1;
        while(left < right){
            if(numbers[left] + numbers[right] < target){
                ++left;
            }
            else if(numbers[left] + numbers[right] > target){
                --right;
            }
            else{
                result.push_back(left+1);
                result.push_back(right+1);
                break;
            }
        }
        return result;
    }
};

分析：左右两个指针分别进行移动，加和小了就把左边的指针往右移动一下，加和大了就把右边的指针往左移动一下。这道题比较特殊，限定了一定有答案而且答案只会有一个，因此不需要添加任何其他的额外条件。

错误：没看清下标的表示方式，直接输出数组下标了。

归并两个有序数组

Leetcode 88

给定两个有序数组，把两个数组合并为一个。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        if(n == 0){
            return;
        }
        if(m == 0){
            nums1 = nums2;
            return;
        }
        int mi = m - 1;
        int ni = n - 1;
        int numIndex = m+n-1;
        while(numIndex >= 0){
            if(mi >= 0 && ni >= 0){
                if(nums1[mi] > nums2[ni]){
                    swap(nums1[mi],nums1[numIndex]);
                    --mi;
                }
                else{
                    swap(nums2[ni],nums1[numIndex]);
                    --ni;  
                }
          
            }
            else if(mi == -1){
                while(ni != -1){
                    nums1[numIndex] = nums2[ni];
                    --ni;
                    --numIndex;
                }
                break;
            }
            --numIndex;
        }

    }
};

分析：从后边开始安排数字，填充0的空位

错误：挺简单的一道题，首先是刚开始没有想到非常好的解法，看了答案后双指针又有一些问题。。真的是生疏了。

快慢指针

Leetcode 142

给定一个链表，如果有环路，找出环路的开始点。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        do{
            if(fast == nullptr || fast->next == nullptr){
                return nullptr;
            }
            slow = slow->next;
            fast = fast->next->next;
        }while(slow != fast);
        fast = head;
        while(slow != fast){
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};

分析：有一个通用的解法——快慢指针（Floyd判圈法）。给定两个指针，分别命名为slow和fast，起始位置在链表的开头。每次fast前进两步，slow前进一步。如果fast可以走到尽头，那么说明没有环路；如果fast可以无限走下去，那么说明一定有环路，且一定存在一个时刻slow 和fast 相遇。当slow和fast第一次相遇时，我们将fast重新移动到链表开头，并让slow和fast每次都前进一步。当slow和fast第二次相遇时，相遇的节点即为环路的开始点。

错误：算法忘记了，没有思路。

滑动窗口

Leetcode 76

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""

class Solution {
public:
    string minWindow(string s, string t) {
        size_t s_size = s.size();
        size_t t_size = t.size();
        map<char,int> mp1;
        for(size_t i=0;i<t_size;i++){
            if(mp1.count(t[i])){
                mp1[t[i]] += 1;
            }
            else{
                mp1[t[i]] = 1;
            }
        }
        int left = 0,cnt = 0,min_l = 0,min_size = s_size+1;
        for(int r=0;r<s_size;++r){
            if(mp1.count(s[r])){
                --mp1[s[r]];
                if(mp1[s[r]] >= 0){
                    ++cnt;
                }
                while(cnt == t_size){
                    if(r - left + 1 < min_size){
                        min_size = r - left + 1;
                        min_l = left;
                    }
                    if(mp1.count(s[left]) && ++mp1[s[left]] > 0){   
                        --cnt;
                    } 
                    ++left;
                }
            }
        }
        return min_size > s_size ? "" : s.substr(min_l,min_size);
    }
};

分析：滑动窗口典型题目

首先对子字符串进行计数，记录是否出现，以及出现的次数。然后采取滑动窗口的策略，两个指针都从左开始滑动，以右指针为基准构成外侧的大循环。右指针滑动的过程中，对之前的计数进行更改，滑动到了一个字符就减小1。等到0的时候，说明右指针滑动过了的字符串一定包含子字符串的全部字符，然后将左指针向右滑动来减小这个字符串的长度。左指针碰到了某个子字符串内部的字符，就会将计数+1，从而不满足这个字符串包含整个子字符串的要求，因此重新开始移动右字符串，以尝试再次包含整个子字符串。

错误：算法忘记了，没有思路。

练习

Leetcode 633

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a^2 + b^2 = c 。

class Solution {
public:
    bool judgeSquareSum(int c) {
        long long left = 0;
        long long right = sqrt(c);
        while(left <= right){
            if(left * left + right * right < c){
                ++left;
            }
            else if(left * left + right * right > c){
                --right;
            }
            else{
                return true;
            }
        }
        return false;
    }
};

分析：仍然是双指针的问题，多了一点点细节问题。

错误：left = right，right的范围考虑的不太好。

Leetcode 680

给你一个字符串 s，最多可以从中删除一个字符。请你判断 s是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

class Solution {
public:
    bool judge(string &s,int left,int right){
        while(left <= right){
            if(s[left] == s[right]){
                ++left;
                --right;
            }
            else{
                return false;
            }
        }
        return true;
    }
    bool validPalindrome(string s) {
        size_t s_size = s.size();
        int left = 0;
        int right = s_size - 1;
        while(left <= right){
            if(s[left] == s[right]){
                ++left;
                --right;
            }
            else{
                return judge(s,left+1,right) || judge(s,left,right-1);
            }
        }
        return true;
    }
};

分析：双指针移动就好

错误：没有考虑到删除一个字符后有两种情况，应该共同考虑而不是仅仅使用某一种情况进行判断。

Leetcode 524

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

class Solution {
public:
    static bool cmp(string &a,string &b){
        if(a.size() != b.size()){
            return a.size() > b.size();
        }
        return a < b;
    }
    string findLongestWord(string s, vector<string>& dictionary) {
        sort(dictionary.begin(),dictionary.end(),cmp);
        size_t s_size = s.size();
        for(auto t : dictionary){
            size_t t_size = t.size();
            int si = 0,ti = 0;
            while(si != s_size){
                if(s[si] == t[ti]){
                    ++ti;
                }
                ++si;
                if(ti == t_size){
                    return t;
                }
            }
        }
        return "";
    }
};

分析：先排序，然后双指针进行移动匹配，如果子字符串的指针移动到字符串的末尾了，说明已经匹配成功了，可以直接输出这个字符串。如果原始的字符串的指针移动到末尾了，说明没有匹配成功，因此转为匹配下一个字符串。

错误：题目要求的排序条件没有看好，返回了长度比较短的字符串。

Leetcode 340

给定一个字符串 s，找出至多包含 k个不同字符的最长子串 T

分析：还是滑动窗口的策略，以右边指针为基准，滑动一下就记录一下最长的长度，滑动到不满足条件了，就将左边的指针收回来，收到满足条件了就继续放右边的指针去滑动。

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        size_t s_size - s.size();
        map<char,int> mp;
        int maxlen = 0;
        int l = 0;
        for(int r=0;r<s_size;r++){
            if(mp.size() <= k){
                ++mp[s[r]];
            }
            while(mp.size() > k){
                if(--mp[s[l]] == 0){
                    mp.erase(s[l]);
                }
                l++;
            }
            maxlen = max(maxlen,r-l+1);
        }
        return maxlen;
    }
};

错误：会员题，无法提交。

总结

双指针的题目还可以，感觉重要的是判断条件。滑动窗口的题目比较困难，可能也是做的题目比较少。后面还需要加强练习。