167 Two Sum-Input array is sorted， 125 Valid Palindrome，344

Two sum:

哈希表解法；

class Solution {

public:

    vector<int> twoSum(vector<int>& nums, int target) {

        //只有唯一的一个解,且nums里的数不能重复使用

        //hash

        unordered_map<int, int> index;

        for(int i=; i<nums.size(); i++)

            index[nums[i]] = i;

        for(int i=; i<nums.size(); i++){

            int left = target - nums[i];

            if(index.count(left) && index[left]!=i)

                //能在index中找到另一个数与nums[i]相加为target

                return {i, index[left]};    //返回索引

        }

        return {};  //找不到解，返回空vector

    }

};

注意这两个元素不能是相同的。

解法一：二分查找法，逐一取数组中的值，然后second = target - numbers[i] , 用二分查找法求第二个值。

时间复杂度：O(nlongn)

class Solution {

public:

    vector<int> twoSum(vector<int>& numbers, int target) {

        //二分查找

        vector<int> result;

        int n = numbers.size();

        for(int i=; i<n;i++){

            int second = target - numbers[i];

            int l = i+, r = n-;

            while(l<=r){

                int mid = (l+r)/;

                if(second < numbers[mid]){

                    //在左半部分

                    r = mid-;

                }

                else if(second > numbers[mid]){

                    //在右半部分

                    l = mid+;

                }

                else{

                    //返回索引，从1开始

                    result.push_back(i+);

                    result.push_back(mid+);

                    break;

                }

            }

            if(result.size()==) break;

        }

        return result;

    }

};

解法三：对撞指针

使用两个指针，若nums[i] + nums[j] > target 时，i++; 若nums[i] + nums[j] < target 时，j -- 。

时间复杂度：O(n)

class Solution {

public:

    vector<int> twoSum(vector<int>& numbers, int target) {

        int n = numbers.size();

        int l = , r = n-;

        while(l<r){

            if(numbers[l] + numbers[r] == target){

                int res[] = {l+, r+};

                return vector<int>(res, res+);

            }

            else if(numbers[l] + numbers[r] < target)

                l++;

            else

                r--;

        }
        throw invalid_argument("The input has no solution.");

    }

};

class Solution {

public:

    vector<int> twoSum(vector<int>& nums, int target) {

        //只有唯一的一个解,且nums里的数不能重复使用

        //hash

        unordered_map<int, int> index;

        for(int i=; i<nums.size(); i++)

            index[nums[i]] = i;

        for(int i=; i<nums.size(); i++){

            int left = target - nums[i];

            if(index.count(left) && index[left]!=i)

                //能在index中找到另一个数与nums[i]相加为target

                return {i, index[left]};    //返回索引

        }

        return {};  //找不到解，返回空vector

    }

};

Two sum's follow up :

//

//  main.cpp

//  Two sum 的follow up

// 在数组中找两个元素使它们的和大于9，返回元素对的个数

// sort + 双指针

// ans = ans + (j-i);   当前有j-i个元素对大于target

//

#include<bits/stdc++.h>

using namespace std;

int main() {

    // insert code here...

    vector<int> nums{,,,,,,};

    int target = ;

    sort(nums.begin(), nums.end());

    int left = , right = nums.size()-;

    int ans = ;

    while(left < right){

        if(nums[left] + nums[right] > target){

            ans += (right - left);

            right--;

        }

        else{

            left++;

        }

    }

    cout << "ans: "<<ans<<endl;;

    return ;

}

对撞指针的另一个题目：

空串也认为是回文串。若 isalnum() == true，则为字母或数字；使用toupper()将其转换为大写。

#include <ctype.h>

class Solution {

public:

    bool isPalindrome(string s) {

        int l = , r = s.size()-;

        while(l<r){

            //跳过非字母和数字的字符

            while(!isalnum(s[l]) && l<r)

               l++;

            while(!isalnum(s[r]) && l<r)

               r--;

            //将字母或数字都转化为大写来比较是否相同

            if(toupper(s[l]) != toupper(s[r]))

               return false;

            l++;

            r--;

        }

        return true;

    }

};

344 Reverse String

还蛮简单的，用了对撞指针的思想，交换首尾对应指针所指的元素的值。

class Solution {

public:

    string reverseString(string s) {

        int l = , r = s.size()-;

        int mid = (l+r)/;

        for(int i=;i<=mid;i++){

            swap(s[l], s[r]);

            l++;

            r--;

        }

        return s;

    }

};

345

翻转元音字母：aeiouAEIOU

class Solution {

public:

    bool is_vowel(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;

        else

            return false;

    }

    string reverseVowels(string s) {

        int n = s.size();

        int l = , r = n-;

        while(l<r){

            while(!is_vowel(s[l]) && l<r)

                l++;

            while(!is_vowel(s[r]) && l<r)

                r--;

            swap(s[l], s[r]);

            l++;

            r--;

        }

        return s;

    }

};

class Solution {

public:

int maxArea(vector<int> &height) {

    int m = ;

    int i = , j = height.size() - ;

    while (i < j) {

        //m = max(m, (j - i) * min(height[i], height[j]));

        //height[i] < height[j] ? i++ : j--;

        if(height[i] < height[j]){

            m = max(m, (j - i) * height[i]);

            i++;

        }

        else{

             m = max(m, (j - i) * height[j]);

             j--;

        }

    }

    return m;

}

};

巴特西

167 Two Sum-Input array is sorted， 125 Valid Palindrome，344

最新文章

热门文章