LeetCode 双指针练习题

原文链接（Go写的，换成C++实现了一遍，又加了一点题）
把这几个题练一下基本就可以掌握双指针的使用了，而且可以看出双指针的复杂度还是很低的。

--0--

455. 分发饼干

class Solution {
    public:
        int findContentChildren(vector<int>& g, vector<int>& s) {
            int res=0;
            sort(g.begin(),g.end());
            sort(s.begin(),s.end());
            int p1=0,p2=0;
            while(p1<g.size() && p2<s.size()) {
                if(s[p2]>=g[p1]) {
                    res++;
                    p2++;
                    p1++;
                }
                else{
                    p2++;
                }
            }
            return res;
        }
};

--1--

21. 合并两个有序链表

class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            ListNode *p=new ListNode(0);
            ListNode *head=p; 
            while(l1 && l2) {
                if(l1->val<l2->val) {
                    p->next=l1;
                    l1=l1->next;
                } else {
                    p->next=l2;
                    l2=l2->next;
                }
                p=p->next;
            }
            if(l1) 
                p->next=l1;
            if(l2) 
                p->next=l2;
            return head->next;
        }
};

--2--

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

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for(int i=0,j=numbers.size()-1;i<j;){
            if(numbers[i]+numbers[j]==target)
                return {i+1,j+1};
            else if(numbers[i]+numbers[j]>target)
                j--;
            else if(numbers[i]+numbers[j]<target)
                i++;
        }
        return {-1,-1};
    }
};

--3--

633. 平方数之和

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

--4--

345. 反转字符串中的元音字母

class Solution
{
public:
    bool is_aeiou(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)
    {
        int f = 0, l = s.size() - 1;
        while (f < l)
        {
            if (is_aeiou(s[f]) && is_aeiou(s[l]))
            {
                char tmp = s[f];
                s[f] = s[l];
                s[l] = tmp;
                f++;
                l--;
            }
            else if (!is_aeiou(s[f]))
                f++;
            else if (!is_aeiou(s[l]))
                l--;
        }
        return s;
    }
};

--5--

680. 验证回文字符串 Ⅱ

class Solution
{
public:
    bool validPalindrome(string s)
    {
        for (int i = 0, j = s.size() - 1; i < j; ++i, --j)
            if (s[i] != s[j])
                return (judge(s, i + 1, j) || judge(s, i, j - 1));
        return true;
    }
    int judge(string str, int i, int j)
    {
        while (i < j)
            if (str[i++] != str[j--])
                return false;
        return true;
    }
};

--6--

88. 合并两个有序数组

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

--7--

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

class Solution
{
public:
    string findLongestWord(string s, vector<string> &d)
    {
        size_t maxlen = 0;
        string res;
        for (int i = 0; i < d.size(); i++)
        {
            size_t p1 = 0, p2 = 0;
            while (p1 < s.size() && p2 < d[i].size())
            {
                if (s[p1] == d[i][p2])
                    p2++;
                p1++;
            }
            if (p2 == d[i].size() && (p2 > maxlen || (p2 == maxlen && d[i] < res)))
            {
                maxlen = p2;
                res = d[i];
            }
        }
        if (maxlen > 0)
            return res;
        return "";
    }
};

--8--

141. 环形链表

C++题解

--9--

142. 环形链表 II