LeetCode力扣刷题——玩转双指针

双指针

一、算法解释

int x;
int * p1 = &x; // 指针可以被修改，值也可以被修改
const int * p2 = &x; // 指针可以被修改，值不可以被修改（const int）
int * const p3 = &x; // 指针不可以被修改（* const），值可以被修改
const int * const p4 = &x; // 指针不可以被修改，值也不可以被修改

// addition是指针函数，一个返回类型是指针的函数
int* addition(int a, int b) {
    int* sum = new int(a + b);
    return sum;
}
int subtraction(int a, int b) {
    return a - b;
}
int operation(int x, int y, int (*func)(int, int)) {
    return (*func)(x,y);
}
// minus是函数指针，指向函数的指针
int (*minus)(int, int) = subtraction;
int* m = addition(1, 2);
int n = operation(3, *m, minus);

二、经典问题 

1. Tow Sum

167. 两数之和 II - 输入有序数组

167. Two Sum II - Input Array Is Sorted

        给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

        以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。你所设计的解决方案必须只使用常量级的额外空间。

        因为数组已经排好序，我们可以采用方向相反的双指针来寻找这两个数字，一个初始指向最 小的元素，即数组最左边，向右遍历；一个初始指向最大的元素，即数组最右边，向左遍历。

        如果两个指针指向元素的和等于给定值，那么它们就是我们要的结果。如果两个指针指向元 素的和小于给定值，我们把左边的指针右移一位，使得当前的和增加一点。如果两个指针指向元 素的和大于给定值，我们把右边的指针左移一位，使得当前的和减少一点。

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

2. 归并两个有效数组

88. 合并两个有序数组

88. Merge Sorted Array

        给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

        请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

        注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

        因为这两个数组已经排好序，我们可以把两个指针分别放在两个数组的末尾，即 nums1 的 m − 1 位和 nums2 的 n − 1 位。每次将较大的那个数字复制到 nums1 的后边，然后向前移动一位。 因为我们也要定位 nums1 的末尾，所以我们还需要第三个指针，以便复制。

        在以下的代码里，我们直接利用 m 和 n 当作两个数组的指针，再额外创立一个 pos 指针，起 始位置为 m + n − 1 。每次向前移动 m 或 n 的时候，也要向前移动 pos 。这里需要注意，如果 nums1 的数字已经复制完，不要忘记把 nums2 的数字继续复制；如果 nums2 的数字已经复制完，剩余 nums1 的数字不需要改变，因为它们已经被排好序。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int pos = m + n - 1;
        m--,n--;
        while(m >= 0 && n >= 0){
            nums1[pos--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
        }
        while(n >= 0){
            nums1[pos--] = nums2[n--];
        }
    }
};

 3. 快慢指针

142. 环形链表 II

142. Linked List Cycle II

        给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

        如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

        不允许修改链表。

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head,*fast = head;
        // 判断是否存在环路
        do{
            if(!fast || !fast->next)
                return nullptr;
            fast = fast->next->next;
            slow = slow->next;
        }while(fast != slow);
        // 如果存在，查找环路节点
        fast = head;
        while(fast != slow){
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

4. 滑动窗口

76. 最小覆盖子串

76. Minimum Window Substring

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

        本题使用滑动窗口求解，即两个指针 l 和 r 都是从最左端向最右端移动，且 l 的位置一定在 r 的左边或重合。注意本题虽然在 for 循环里出现了一个 while 循环，但是因为 while 循环负责移 动 l 指针，且 l 只会从左到右移动一次，因此总时间复杂度仍然是 O ( n ) 。本题使用了长度为 128 的数组来映射字符，也可以用哈希表替代；其中 chars 表示目前每个字符缺少的数量， flag 表示 每个字符是否在 t 中存在。

class Solution {
public:
    string minWindow(string s, string t) {
        vector<bool> flag(128,false);
        vector<int> chars(128,0);
        // 先统计t中的字符情况
        for(int i=0;isize();i++){
            flag[t[i]] = true;
            ++chars[t[i]];
        }
        // 移动滑动窗口，不断更改统计数据
        int cnt = 0,l = 0,min_l = 0,min_size = s.size() + 1;
        for(int r=0;rsize();++r){
            if(flag[s[r]]){
                if(--chars[s[r]] >= 0){
                    ++cnt;
                }
                // 若目前滑动窗口已包含t中全部字符，
                // 则尝试将l右移，在不影响结果的情况下获得最短子字符串
                while(cnt == t.size()){
                    if(r - l + 1 < min_size){
                        min_l = l;
                        min_size = r - l + 1;
                    }
                    if(flag[s[l]] && ++chars[s[l]] > 0){
                        --cnt;
                    }
                    ++l;
                }
            }
        }
        return min_size > s.size() ? "" : s.substr(min_l,min_size);
    }
};

三、巩固练习 

633. 平方数之和

633. Sum of Square Numbers

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

Two Sum 题目的变形题之一。

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

680. 验证回文串 II

680. Valid Palindrome II

        给你一个字符串 s，最多 可以从中删除一个字符。

        请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

两层双指针：
1. 外一层，寻找不相同的 begin 与 end 下标，如未找到，则 s 本身自己就是回文字符串
2. 找着了，则分两种情况，begin 后移 或者 end 前移，再进行一次双指针循环判断

class Solution {
public:
    bool validPalindrome(string s) {
        int begin = 0,end = s.length() - 1;
        while(begin < end){
            if(s[begin] != s[end]){
                return validHelper(s,begin + 1,end) || validHelper(s,begin,end - 1);
            }
            ++begin;
            --end;
        }
        return true;
    }
    bool validHelper(string s,int begin,int end){
        while(begin < end){
            if(s[begin] != s[end]){
                return false;
            }
            ++begin;
            --end;
        }
        return true;
    }
};

524. 通过删除字母匹配到字典里最长单词

524. Longest Word in Dictionary through Deleting

        给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

        如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

我们可以先对 dictionary 根据题意进行自定义排序：

1. 长度不同的字符串，按照字符串长度排倒序；
2. 长度相同的，则按照字典序排升序。                                                                               

然后我们只需要对 dictionary 进行顺序查找，找到的第一个符合条件的字符串即是答案。

class Solution {
public:
    string findLongestWord(string s, vector& dictionary) {
        sort(dictionary.begin(),dictionary.end(),[](string& a,string& b)
        {
            if(a.length() == b.length())
                return a < b;
            return a.length() > b.length();
        });
        for(auto ans : dictionary){
            int n = s.length();
            int m = ans.length();
            if(n < m)   continue;
            int i = 0,j = 0;
            while(i < n && j < m){
                if(s[i] == ans[j])  ++j;
                ++i;
                if(j == m)  return ans;
            }
        }
        return "";
    }
};

欢迎大家共同学习和纠正指教