167 Two Sum-Input array is sorted， 125 Valid Palindrome，344-白红宇的个人博客

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

发布日期：2021-10-22 14:27:08 浏览次数：3 分类：技术文章

本文共 2478 字，大约阅读时间需要 8 分钟。

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

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

时间复杂度：O(nlongn)

class Solution {public:    vector
     
       twoSum(vector
      
       & numbers, int target) {        //二分查找        vector
       
         result;        int n = numbers.size();        for(int i=0; i
        
          numbers[mid]){                    //在右半部分                    l = mid+1;                }                else{                    //返回索引，从1开始                    result.push_back(i+1);                    result.push_back(mid+1);                    break;                }            }            if(result.size()==2) break;        }        return result;    }};

解法三：对撞指针

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

时间复杂度：O(n)

class Solution {public:    vector
     
       twoSum(vector
      
       & numbers, int target) {        int n = numbers.size();        int l = 0, r = n-1;        while(l

(res, res+2); } else if(numbers[l] + numbers[r] < target) l++; else r--; } throw invalid_argument("The input has no solution."); }};

对撞指针的另一个题目：

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

#include 
     
      class Solution {public:    bool isPalindrome(string s) {        int l = 0, r = s.size()-1;        while(l

344 Reverse String

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

class Solution {public:    string reverseString(string s) {        int l = 0, r = s.size()-1;        int mid = (l+r)/2;        for(int i=0;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 = 0, r = n-1;                while(l

class Solution {public:int maxArea(vector
     
       &height) {    int m = 0;    int i = 0, j = height.size() - 1;    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;}};

转载于:https://www.cnblogs.com/Bella2017/p/10146882.html

转载地址：https://blog.csdn.net/weixin_30361641/article/details/95882067 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Android开发艺术探索笔记—— View(一)

下一篇：用python导出csv文件

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章