LeetCode题解——双指针(一)-蒲公英云

文章目录

- 1. 两数之和 II - 输入有序数组
- - 二分查找
  - 双指针
- 1. 平方数之和
- - 双指针
- 1. 反转字符串中的元音字母
- - 双指针
  - 双指针优化
- 1. 验证回文字符串 Ⅱ
- - 双指针

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

给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:

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

二分查找

x + y = target, 先设numbers[i] = x，二分查找target - y ，找到即成功

class Solution {
public:
    int binsearch(vector<int>& numbers, int target)
    {
        int left = 0, right = numbers.size() - 1;
        int ans = -1;
        while(left <= right)
        {
            int mid = left + ((right - left) >> 1);
            if(numbers[mid] < target)
                left = mid + 1;
            else if(numbers[mid] > target)
                right = mid - 1;
            else
            {
                ans = mid;
                break;
            }
        }
        return ans;
    }
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> ans;
        for(int i = 0; i < numbers.size(); ++i)
        {
            int y = target - numbers[i];
            int j = binsearch(numbers, y);
            if(j != -1 && i != j)
            {
                ans.push_back(min(i+1, j+1));
                ans.push_back(max(i+1, j+1));
                break;
            }
        }
        return ans;
    }
};

双指针

由于数组是有序的，只需要双指针即可。一个left首指针，一个right尾指针，如果left + right 值大于 target 则 right左移动，否则 left 右移。

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

633. 平方数之和

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

示例1:
输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5
示例2:
输入: 3
输出: False

双指针

首指针left = 0, 尾指针 right = sqrt©的整数，然后从两头遍历，left * left + right * right < c 则left++；否则，right–。防止越界特殊处理一下。

class Solution {
public:
    bool judgeSquareSum(int c) {
        if(c == 0)
            return true;
        double left = 0;
        double right = (int)sqrt(c);
        bool flag = 0;
        double eps = 1e-8;
        while(left <= right)
        {
            double tmp = c - left * left;
            if(fabs(tmp / right - right) < eps)
            {
                flag = 1;
                break;
            }
            else if((right - tmp / right) > eps)
                right--;
            else
                left++;
        }
        return flag;
    }
};

format_png

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

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

示例 1:

输入: “hello”
输出: “holle”
示例 2:

输入: “leetcode”
输出: “leotcede”
说明:
元音字母不包含字母”y”。

双指针

双指针，一个在头，一个在尾，两个都是元音就交换，遍历一遍即可

class Solution {
public:
    bool is_flag(char c)
    {
        if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' || c == 'E' || c == 'I' || c == 'O' || c =='U')
            return true;
        return false;
    }
    string reverseVowels(string s) {
        int left = 0, right = s.size() - 1;
        while(left < right)
        {
            bool f1 = is_flag(s[left]), f2 = is_flag(s[right]);
            if(f1 && f2)
            {
                char c = s[left];
                s[left] = s[right];
                s[right] = c;
                left++, right--;
            }
            else if(f1 && !f2)
                right--;
            else if(!f1 && f2)
                left++;
            else
                right--, left++;
        }
        return s;
    }
};

双指针优化

判断的次数少一点

class Solution {
public:
    string reverseVowels(string s) {
        unordered_map<char,int> map{
    {
     'a', 1}, {
    'e', 1}, {
    'i', 1},{
    'o', 1},{
    'u', 1},
                                    {
    'A', 1},{
    'E', 1},{
    'I', 1},{
    'O', 1},{
    'U', 1}};
        int i =0;
        int j = s.length()-1;
        char temp;
        while(i<j)
        {
            while(i<j&&map[s[i]]!=1) i++;
            while(i<j&&map[s[j]]!=1) j--;
            if(i<j)
            {
                temp = s[i];
                s[i] = s[j];
                s[j] = temp;
            }
            i++;j--;
        }
        return s;
    }
};

680. 验证回文字符串 Ⅱ

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

示例 1:

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

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

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

双指针

如果字符串的起始字符和结束字符相同（即 s[0]==s[s.length-1]），则内部字符是否为回文（s[1], s[2], …, s[s.length - 2]）将唯一地确定整个字符串是否为回文。

算法：
假设我们想知道 s[i],s[i+1],…,s[j] 是否形成回文。如果 i >= j，就结束判断。如果 s[i]=s[j]，那么我们可以取 i++;j–。否则，回文必须是 s[i+1], s[i+2], …, s[j] 或 s[i], s[i+1], …, s[j-1] 这两种情况。
见代码中注释

class Solution {
public:
    bool validPalindrome(string s) {
        int l = 0, r = s.length() - 1;
        int del_index = -1;
        while(l <= r)
        {
            if(s[l] == s[r])
                l++, r--;
            else
            {
                if(del_index == -1) // 第一次不等，先删除左边的，l++
                    del_index = l, l++;
                else if(del_index == s.length()) // 第三次不等，直接返回false
                    return false;
                else // 第二次不等，l返回到第一次不等的位置，r也回到对应的位置，删除右边的
                    l = del_index, r = s.length() - l - 2, del_index = s.length();
            }
        }
        return true;
    }
};