leetcode——双指针

分手后的思念是犯贱 2022-10-31 00:43 201阅读 0赞

### leetcode——双指针 ###

*   *   *  1. 两数之和Ⅱ-输入有序数组（167）
         *  2.合并两个有序数组（88）
         *  3.快慢指针（142）
         *  4.滑动窗口（76最小覆盖子串）
         *  练习
         *   *  1.平方数之和（633）
             *  2.验证回文字符串（680）
             *  3.通过删除字母匹配到字典里最长单词（524）

### 1. 两数之和Ⅱ-输入有序数组（167） ###

给定一个已按照 **升序排列**的整数数组 *numbers* ，请你从数组中找出两个数满足相加之和等于目标数 *target 。*

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。*numbers* 的下标 从 1 开始计数 ，所以答案数组应当满足 *1 <= answer\[0\] < answer\[1\] <= numbers.length 。*

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例 1：

输入：numbers = \[2,7,11,15\], target = 9  
输出：\[1,2\]  
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。  
示例 2：

输入：numbers = \[2,3,4\], target = 6  
输出：\[1,3\]  
示例 3：

输入：numbers = \[-1,0\], target = -1  
输出：\[1,2\]

**题解：** i指向开头，j指向结尾，遍历一遍。

vector<int> twoSum(vector<int>& numbers, int target) {
        
        int i = 0, j = numbers.size() - 1, sum;
        while(i < j){
        
            sum = numbers[i] + numbers[j];
            if(sum == target) break;
            if(sum < target) i++;
            else j--;
    
        }
        return vector<int>{
        i+1,j+1};
    }

### 2.合并两个有序数组（88） ###

给你两个有序整数数组 *nums1* 和 *nums2*，请你将 *nums2* 合并到 *nums1* 中，使 *nums1* 成为一个有序数组。

初始化 *nums1* 和 *nums2* 的元素数量分别为 m 和 n 。你可以假设 *nums1* 的空间大小等于 m + n，这样它就有足够的空间保存来自 *nums2* 的元素。

示例 1：

输入：nums1 = \[1,2,3,0,0,0\], m = 3, nums2 = \[2,5,6\], n = 3  
输出：\[1,2,2,3,5,6\]  
示例 2：

输入：nums1 = \[1\], m = 1, nums2 = \[\], n = 0  
输出：\[1\]

**题解：** 因为两个数组都是有序的，直接从最后开始比较大小，然后赋给nums1。如果nums1复制完，nums2需要单独再复制剩下的。如果nums2复制完，nums1不需要改变，因为原来就是有序的。

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        
            int k = m + n - 1;
            m--;
            n--;
            while(m >= 0 && n >= 0){
        
                if(nums1[m] < nums2[n]){
        
                    nums1[k--] = nums2[n--];
                }else{
        
                    nums1[k--] = nums1[m--];
                }
             /**
             *  可改为
             *  nums1[k--] = nums1[m] < nums2[n] ? nums2[n--] : nums1[m--];
             * 
             * */
            }
            while(n >= 0){
        
                nums1[k--] = nums2[n--];
            }
        }

### 3.快慢指针（142） ###

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

为了表示给定链表中的环，我们使用整数 *pos* 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 *pos* 是 -1，则在该链表中没有环。注意，**pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。**

说明：不允许修改给定的链表。

示例 1：  
![在这里插入图片描述][20210220155012461.png]  
输入：head = \[3,2,0,-4\], pos = 1  
输出：返回索引为 1 的链表节点  
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：  
![在这里插入图片描述][20210220155021302.png]  
输入：head = \[1,2\], pos = 0  
输出：返回索引为 0 的链表节点  
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：![在这里插入图片描述][2021022015503485.png]  
输入：head = \[1\], pos = -1  
输出：返回 null  
解释：链表中没有环。

**提示：**

*  链表中节点的数目范围在范围 \[0, 104\] 内
 *  \-105 <= Node.val <= 105
 *  pos 的值为 -1 或者链表中的一个有效索引

**题解：** 对于链表找环，通用的解法为：快慢指针（Floyd判圈法）。给定两个指针，一快每次走两步，一慢每次走一步，相遇则有环。  
![在这里插入图片描述][20210220161243177.png]  
随便拿个图，m为链表起点到圈起点的距离。n为环的周长。**设图中两段红线中间短的距离(即圈起点到相遇点的距离）为k。长的距离（即相遇点到圈起点的距离）为l。**

2slow = fast;  
    慢的走了m+k，快的走了m + k + xn（x圈环）
    则有2（m + k） = m + k + xn
    即m + k = xn
    得m = (x-1)n + l。
    
    所以在相遇之后，让快指针回到起点，并每次步伐大小改为1，慢指针继续走。一定会在圈起点相遇。

/**
     * 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 NULL;
                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最小覆盖子串） ###

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

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC”  
输出：“BANC”  
示例 2：

输入：s = “a”, t = “a”  
输出：“a”

提示：

*  1 <= s.length, t.length <= 105
 *  s 和 t 由英文字母组成

**题解：** 用长度128的数组来映射字符，也可用哈希表替代。其中chars表示目前每个字符缺少的数量，flag表示每个字符是否在t中存在。

string minWindow(string s, string t) {
        
        vector<int> chars(128,0);
        vector<bool> flag(128,false);
    
        //统计t中字符的情况
        for(int i = 0; i < t.size(); 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; r < s.size(); 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);
    }

### 练习 ###

#### 1.平方数之和（633） ####

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

示例 1：

输入：c = 5  
输出：true  
解释：1 \* 1 + 2 \* 2 = 5  
示例 2：

输入：c = 3  
输出：false  
示例 3：

输入：c = 4  
输出：true  
示例 4：

输入：c = 2  
输出：true  
示例 5：

输入：c = 1  
输出：true

提示：

0 <= c <= 2^31 - 1

**题解：** 这道题比较简单，但是要注意一点细节。因为它是a^2 + b ^ 2 = c,所以我们可以使用双指针遍历一遍到 0 ~ sqrt（c）即可。从测试用例c=2为true可以看出，两个数是可以重复的。

bool judgeSquareSum(int c) {
        
                long r = sqrt(c);
                long l = 0;
                while(l <= r){
        
                    if((l * l + r * r) == c)
                        return true;
                    else if((l * l + r * r) < c){
        
                        l++;
                    }else{
        
                        r--;
                    }
                }
                return false;
        }

#### 2.验证回文字符串（680） ####

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: “aba”  
输出: True  
示例 2:

输入: “abca”  
输出: True  
解释: 你可以删除c字符。  
注意:

字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

**题解：** 无

bool checkPalidrome(string s, int l, int r){
        
        for(int i = l, j = r; i < j; i++, j--){
        
            if(s[i] != s[j])
                return false;
        }
        return true;
    }
    
    bool validPalindrome(string s) {
        
        int l = 0;
        int r = s.length() - 1;
        while(l < r){
        
            if(s[l] == s[r]){
        
                l++;
                r--;
            }
            else return checkPalidrome(s,l,r-1) || checkPalidrome(s,l+1,r);
        }
        return true;
    }

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

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

示例 1:

输入:  
s = “abpcplea”, d = \[“ale”,“apple”,“monkey”,“plea”\]

输出:  
“apple”  
示例 2:

输入:  
s = “abpcplea”, d = \[“a”,“b”,“c”\]

输出:  
“a”

说明:

*  所有输入的字符串只包含小写字母。
 *  字典的大小不会超过 1000。
 *  所有输入的字符串长度不会超过 1000。

**题解：** 暴力法就是遍历比较集合里的字符串和s了。

string findLongestWord(string s, vector<string>& d) {
        
            string str = "";
            for(string strd : d){
        
                for(int i = 0,j = 0; i < s.length(); i++) {
        
                        if(s[i] == strd[j]) j++;
                        if(j == strd.length()) {
        
                            if(strd.length() > str.length() || (strd.length() == str.length() && strd.compare(str) < 0)) {
        
                                str = strd;
                            }
                        }
                    }
            }
                return str;
        }

[20210220155012461.png]: /images/20221024/309cf8ae1a1d40b5990311dc436eb0fc.png
[20210220155021302.png]: /images/20221024/5e69635f9070403f8be9bb85154fbfb9.png
[2021022015503485.png]: /images/20221024/43ca027e48a84e07ad8b8e68ea5ad703.png
[20210220161243177.png]: /images/20221024/bbf3cb8f1d804dd19e0fd81fa8fec109.png