🐛双指针🐛

19. 删除链表的倒数第N个节点
75.颜色分类
88.合并两个有序数组
167.两数之和II-输入有序数组
345.反转字符串中的元音字母
524.通过删除字母匹配到字典里最长单词
633.平方数之和
647.回文子串
680.验证回文字符串Ⅱ
5461.仅含1的子串数
977.有序数组的平方
11.盛最多水的容器
941.有效的山脉数组
31.下一个排列
922.按奇偶排序数组II
287.寻找重复数

删除链表的倒数第N个节点

leetcode给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

解题思路

使用快慢指针，让快指针提前先走n+1步，然后双指针再同时让前走，当快指针指到结尾时，慢指针指向要删除结点得前驱
为了让整个链表得删除操作都统一起来，所以加入了头节点dummy,因为删除某个结点得操作需要它得前驱，而第一个结点没有前驱，所以加入头结点会更方便，删除操作与其他结点统一。
链表所谓删除结点，即前一个结点得next指针越过此结点，指向下一结点

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* slow = dummy;
        ListNode* fast = dummy;
        n++;
        while (n--) {
            fast = fast->next;
        }
        while (fast) {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return dummy->next;
    }

颜色分类

Leetcode给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

解题思路

一共三个指针，p0一直指向0的后一位，p2一直指向2的前一位，cur是用于遍历的指针。
本题属于荷兰旗帜问题：思想是遇到0就跟p0所指的数交换位置，遇到2就跟p2所指的数交换位置，遇到1就跳过。
注意：遇到2交换完位置后，cur指针不前进，因为要再次判断交换过来的数是0还是1。
注意2：while结束是 cur <= p2而不是cur < nums.size() 因为p2之后的数都是交换过来的2，如果cur < nums.size()会再次判断交换，顺序就变成了021的顺序。

    void sortColors(vector<int>& nums) {
        int p0 = 0, p2 = nums.size() - 1;
        int cur = 0;
        while (cur < p2) {
            if (nums[cur] == 1) cur++;
            else if (nums[cur] == 0) swap(nums[p0++], nums[cur++]);
            else if (nums[cur] == 2) swap(nums[cur],nums[p2--]);
        }
    }

合并两个有序数组

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

解题思路

合并有两种写法：while结束条件不同可分为写在while里和while外。
注意：数组的边界条件,对于链表指针cur = NULL为结束，而数组是i = -1和i = size()为结束。
思路：从后往前插入num1，两个指针分别从后往前遍历两个数组，较大值插入num1中。

用&&与作为结束条件

意思是：当两个数组其中一个遍历结束时，结束while循环，所以还需要将另一个数组的剩余部分依次插入nums1。

  void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1, p2 = n - 1, cur = m + n - 1;
        while ( p1 >= 0 && p2 >= 0){
            nums1[cur--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
        }
        if (p1 < 0) {
            while (p2 >= 0)
                nums1[cur--] = nums2[p2--];
        }
    }

用||或作为结束条件

意思是，只要当两个数组全部遍历完后，才结束while循环，所以再循环体内就要考虑其中一个遍历结束后的操作。

    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1, p2 = n - 1, cur = n + m - 1;
        while(cur >= 0){
            if (p1 < 0) nums1[cur--] = nums2[p2--];
            else if (p2 < 0) nums1[cur--] = nums1[p1--];
            else nums1[cur--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
        }
    }

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

Leetcode给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

解题思路

双指针相向遍历，
因为是有序数组，所以left指向小的数，right指向大的数，当两指针所指的数之和大于target，就前移right指针缩小大的数，当和小于target，就后移left指针，增大小的数。

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

反转字符串中的元音字母

leetcode编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

解题思路

首尾各一个指针，当都指向元音字母时，交换字符串

    bool isVolew(char ch){
        if(ch=='a' || ch=='e'||ch=='i' || ch=='o'||ch=='u') return true;
        if(ch=='A' || ch=='E'||ch=='I' || ch=='O'||ch=='U') return true;
        return false;
    }
    string reverseVowels(string s) {
        int left=0, right=s.size() - 1;
        while (left < right) {
            if (!isVolew(s[left])) ++left;
            if (!isVolew(s[right])) --right;
            if (isVolew(s[left]) && isVolew(s[right])) {
                swap(s[left++], s[right--]);
            }
        }
        return s;
    }

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

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

示例

输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
输出: 
"apple"
输入:
s = "abpcplea", d = ["a","b","c"]
输出: 
"a"

解题思路

核心时判断一个字符串是不是另一个字符串的子序列，注意这里是子序列而不是子串，子序列是指每个字母在母串中的前后顺序不变。
使用双指针判断子序列，2各指针指向两个串，相同字母时指针后移，不同字母时只有母串指针后移，直到结束，看另一个指针是否指向结尾。
根据题意，要寻找最长的，所以一定要有一个变量储存当前最长值，然后不断进行比较。
compare()函数可以根据字典顺序比较，<0表示字典顺序在前

    string findLongestWord(string s, vector<string>& d) {
        string longest = "";
        for(int i = 0; i < d.size(); ++i){
            if(d[i].size() < longest.size()) continue;
            if(d[i].size() == longest.size() && longest.compare(d[i]) < 0) continue;
            if(isSub(s, d[i])) longest = d[i];
        }
        return longest;
    }
    
    bool isSub(string s,string d){
        int i=0, j=0;
        while(i < s.size() && j < d.size()){
            if(s[i] == d[j]){
                i++;
                j++;
            }else{
                i++;
            }
        }
        return j == d.size();
    }

平方数之和

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

解题思路

a,b可以为0，所以左指针从0开始而不是1，右指针sqrt(c)开始,效率高。
因为a和b可能是同一个数，所以while里的l可以=r。
考虑s可能溢出，所以用r使用long型。

为什么防止s溢出要将r设置为long型：

问题在于计算过程中溢出了，计算式完全是以int运算来执行的，并且只有在运算完成之后，其结果才被提升为 long，而此时已经太迟：计算已经溢出。
解决方法使计算表达式的其中一个因子明确为long型，这样可以强制表达式中所有的后续计算都用long运算来完成，防止溢出

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

回文子串

Leetcode给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例

输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

解题思路

双指针应用：中心扩展
回文串特性：对称相同
回文串：奇数个数和偶数个数，因此有两种扩展：当前字符向两边扩展笔记，当前字符和下一个字符向两边扩展比较。

   int countSubstrings(string s) {
        int cnt = 0;
        for (int i = 0; s[i] != '\0'; ++i){
            expand(s, i, i+1, cnt);
            expand(s, i, i, cnt);
        }
        return cnt;
    }
    void expand(string s,int left,int right,int& cnt){
        while (left >= 0 && right < s.size() && s[left] == s[right]){
            left--;
            right++;
            cnt++;
        }
    }

680.验证回文字符串Ⅱ

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

解题思路

传统思路：遍历每个结点，判断剩余结点能否形成回文，时间复杂度O(n^2)
因为回文对称相等，所以从两头开始遍历，当遇到不相同时，再删除其中一个再进行判断
优化：一开始就是从两头遍历的，所以已经遍历过的地方一定是相等，所以在isPalindrome()函数中不用从两头再重复遍历

    bool validPalindrome(string s) {
        int left = 0,right = s.size() - 1;
        while (left < right) {
            if (s[left] != s[right]) 
                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
            left++; right--;
        }
        return true;
    }
    bool isPalindrome(string s,int left,int right){
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }

仅含 1 的子串数

leetcode 给你一个二进制字符串 s（仅由 '0' 和 '1' 组成的字符串）。返回所有字符都为 1 的子字符串的数目。由于答案可能很大，请你将它对 10^9 + 7 取模后返回。

示例

输入：s = "0110111"
输出：9
解释：共有 9 个子字符串仅由 '1' 组成
"1" -> 5 次
"11" -> 3 次
"111" -> 1 次

解题思路

刚开始想到用双指针，类似于滑动窗口的思想，每次窗口把连续的1框住，计算窗口中最大子串数。
滑动窗口思想，左右指针从0开始，先移动右指针，当右指针达到要求后，再移动左子针，直到左指针也满足一定要求，最后处理中间的字符，处理完继续移动右指针。
这里右指针的要求指向连续1的最后一位，即当right指向1，而right+1指向0,然后开始移动左子针，直到做指针指向第一个1停，至此形成一个窗口，处理结束后记得更新左指针。

    int numSub(string s) {
        int left = 0, right = 0;
        long res = 0;
        while (right + 1 <= s.size()) {
            if (s[right] == '1' && s[right + 1] == '0' || 
                s[right] == '1' && s[right + 1] == '\0') {
                while (s[left] == '0') left++;
                long len = right - left + 1;
                res += (1 + len ) * len / 2;
                res %= 1000000007;
                left = right + 1;
            }  
            right++;
        }
        return res;
    }

如果仔细发现当中的规律，1个1有1个子串，2个连续的有3个子串，3个连续的1有6个子串，n个连续的1有1 + 2 + 3+...+n)个子串,即连续1每当增加一个1就会多加len(1)个子串。

    int numSub(string s) {
        int res = 0, len = 0;
        for (auto& ch : s) {
            if (ch == '1') {
                len++;
                res += len;
                res %= 1000000007;
            } else { 
                len = 0;
            }
        }
        return res;
    }

有序数组的平方

leetcode

解题思路

暴力

    vector<int> sortedSquares(vector<int>& A) {
        for (int i = 0; i < A.size(); ++i) {
            A[i] *= A[i];
        }
        sort(A.begin(), A.end());
        return A;
    }

双指针 + 归并排序
利用「数组 AA 已经按照升序排序」这个条件。显然，如果数组 A 中的所有数都是非负数，那么将每个数平方后，数组仍然保持升序；如果数组 A 中的所有数都是负数，那么将每个数平方后，数组会保持降序。
只要找到正负分界线，用双指针进行归并排序

    vector<int> sortedSquares(vector<int>& A) {
        int neg = 0;
        for (int i = 1; i < A.size(); ++i) {
            if ((A[i - 1] < 0 && A[i] > 0) || A[i] == 0) {
                neg = i;
                break;
            }
        }
        vector<int> res;
        int left = neg - 1, right = neg;
        while (left >= 0 || right < A.size()) {
            if (left < 0) {
                res.push_back(pow(A[right++], 2));
                continue;
            }
            if (right == A.size()) {
                res.push_back(pow(A[left--], 2));
                continue;
            }
            res.push_back(pow(A[left], 2) <= pow(A[right], 2) ? pow(A[left--], 2) : pow(A[right++], 2));
        }
        return res;
    }

盛最多水的容器

leetcode 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

解题思路

暴力双指针法计算所有面积，会超时

    int maxArea(vector<int>& height) {
        int MAX = INT_MIN;
        for (int i = 0; i < height.size(); ++i) {
            for (int j = i + 1; j < height.size(); ++j) {
                MAX = max(MAX, min(height[i], height[j]) * (j - i));
            }
        }
        return MAX;
    }

双指针: 起止位两个指针往中间遍历，因此宽在不断减小，为了让面积最大化，所以两个指针的高做比较，每次只移动最低的那个，保留高的，降低时间复杂度

    int maxArea(vector<int>& height) {
        int MAX = INT_MIN;
        int left = 0, right = height.size() - 1;
        while (left < right) {
            int h = min(height[left], height[right]);
            MAX = max(MAX, h * (right - left));
            if (height[left] < height[right]) ++left;
            else --right;
        }
        return MAX;
    }

有效的山脉数组

leetcode 给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组： A.length >= 3 在 0 < i < A.length - 1 条件下，存在 i 使得： A[0] < A[1] < ... A[i-1] < A[i] A[i] > A[i+1] > ... > A[A.length - 1]

解题思路：

先扫描左侧是否单调递增，并记录最高点下标，再扫描右边判断是否单调递减

    bool validMountainArray(vector<int>& A) {
        if (A.size() < 3) return false;
        int idx = 0;
        for (int i = 1; i < A.size(); ++i) {
            if (A[i] < A[i - 1]) {
                idx = i - 1;
                break;
            }
        }
        
        if (idx == 0) return false;

        for (int i = idx; i + 1 < A.size(); ++i) {
            if (A[i] <= A[i + 1]) {
                return false;
            }
        }
        return true;
    }

双指针，左指针递增就+1，右指针递增也+1，最后判断左右指针能否相遇，且相遇点不是起止位。

    bool validMountainArray(vector<int>& A) {
        if (A.size() < 3) return false;
        int left = 0, right = A.size() - 1;
        while (left + 1 < A.size() && A[left] < A[left + 1]) left++;
        while (right > 0 && A[right] < A[right - 1]) right--;
        if (left == right  && left != 0 && right != A.size() - 1) return true;
        return false;
    }

下一个排列

leetcode 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解题思路：

我们需要将一个左边的「较小数」与一个右边的「较大数」交换，以能够让当前排列变大，从而得到下一个排列。
同时我们要让这个「较小数」尽量靠右，而「较大数」尽可能小。当交换完成后，「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小。

    void nextPermutation(vector<int>& nums) {
        if (nums.empty() || nums.size() == 1) return;
        int i = nums.size() - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i < 0) {
            sort(nums.begin(), nums.end());
            return;
        }
        int j = nums.size() - 1;
        while (j > i && nums[j] <= nums[i]) {
            j--;
        }
        swap(nums[i], nums[j]);
        reverse(nums.begin() + i + 1, nums.end());
    }

922.按奇偶排序数组II

leetcode 给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。你可以返回任何满足上述条件的数组作为答案。

解题思路

双指针法，一个专门指向偶数下标，另一个专门指向奇数下标

    vector<int> sortArrayByParityII(vector<int>& A) {
        vector<int> res(A.size(), 0);
        int oddIdx = 1;
        int evenIdx = 0;
        for (auto num : A) {
            if (num & 1) {
                res[oddIdx] = num;
                oddIdx += 2;
            } else {
                res[evenIdx] = num;
                evenIdx += 2;
            }
        }
        return res;
    }

寻找重复数

leetcode 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有一个重复的整数，找出这个重复的数。

输入：nums = [1,3,4,2,2]
输出：2

解题思路

用set的方法时间复杂度太高
使用快慢指针的方式，基本类似与链表中找环
把数组中的值当作下一个节点的索引
找还的算法思路：快指针每次走两步，慢指针走一步，直到快指针追上慢指针，然后让快指针从头开始走，和慢指针同样的速度，当再次相遇时即为环的起点。

    int findDuplicate(vector<int>& nums) {
        int fast = 0, slow = 0;
        do {
            fast = nums[nums[fast]];
            slow = nums[slow];
        } while (fast != slow);

        fast = 0;
        while (fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }

刘文韬 / leetcode-note .gitee-modal { width: 500px !important; }

🐛双指针🐛

删除链表的倒数第N个节点

解题思路

颜色分类

解题思路

合并两个有序数组

解题思路

用&&与作为结束条件

用||或作为结束条件

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

解题思路

反转字符串中的元音字母

解题思路

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

示例

解题思路

平方数之和

解题思路

为什么防止s溢出要将r设置为long型：

回文子串

示例

解题思路

680.验证回文字符串Ⅱ

解题思路

仅含 1 的子串数

示例

解题思路

有序数组的平方

解题思路

盛最多水的容器

解题思路

有效的山脉数组

解题思路：

下一个排列

解题思路：

922.按奇偶排序数组II

解题思路

寻找重复数

解题思路

简介

发行版

贡献者

近期动态

搜索帮助

刘文韬 / leetcode-note