c++:string相关的oj题(415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III)

这篇具有很好参考价值的文章主要介绍了c++:string相关的oj题(415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 415. 字符串相加

传送门

题目详情

c++:string相关的oj题(415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III),c语言题目分享,c++,java,开发语言,c语言,数据结构,学习

代码1

class Solution {
public:
    string addStrings(string num1, string num2) {
        int index1=num1.size()-1,index2=num2.size()-1;//找到最后一位
        int next=0;//进位
        string retStr;
        while(index1>=0||index2>=0)//还有一个没完就要进来:有可能一直进位
        {
            int val1=0,val2=0; 
            if(index1>=0)
            {
                val1=num1[index1--]-'0';
            }
            if(index2>=0)
            {
                val2=num2[index2--]-'0';
            }
            int ret=next+val1+val2;//两者相加后加上进位数
            next=ret/10;//需要进位就是1了,不需要就是0
            ret%=10;
            retStr.insert(0,1,'0'+ret);//头插到新string
        }
        //最后有可能有1+9的情况,现在只会有0
        if(next==1)
        {
            retStr.insert(0,1,'1');
        }
        return retStr;
    }
};

思路1

  1. 首先,定义两个指针 index1 和 index2 分别指向两个输入字符串的最后一位,用来从后往前遍历字符串。
  2. 然后定义一个变量 next 用来表示进位,初始化为 0。
  3. 接下来使用一个循环来遍历两个字符串,直到 index1 和 index2 都小于 0。在循环中,每次取出 index1 和 index2 对应位置的数字,并将它们与进位相加,得到一个临时的结果 ret。
  4. 然后更新进位 next 为 ret/10,并将 ret%10 插入到需要返回的字符串 retStr 的开头。
  5. 循环结束后,还需要检查最后是否有进位,如果有,需要将进位插入到结果字符串的开头。

但此时还是有一个问题的,那就是效率低(因为头插时间复杂度O(N^2));

代码2

class Solution {
public:
    string addStrings(string num1, string num2) {
        int index1=num1.size()-1,index2=num2.size()-1;//找到最后一位
        int next=0;//进位
        string retStr;
        while(index1>=0||index2>=0)//还有一个没完就要进来:有可能一直进位
        {
            int val1=0,val2=0; 
            if(index1>=0)
            {
                val1=num1[index1--]-'0';
            }
            if(index2>=0)
            {
                val2=num2[index2--]-'0';
            }
            int ret=next+val1+val2;//两者相加后加上进位数
            next=ret/10;//需要进位就是1了,不需要就是0
            ret%=10;
            //使用尾插效率更好,尾插有append,这里我们使用+=
            retStr+='0'+ret;
        }
        //最后有可能有1+9的情况,现在只会有0
        if(next==1)
        {
            retStr+='1';
        }
        reverse(retStr.begin(),retStr.end());//尾插后,最后翻转一下
        return retStr;
    }
};

思路2

整体思路都是一样的,只不过有头插换成了尾插+翻转

2. 125. 验证回文串

传送门

题目详情

c++:string相关的oj题(415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III),c语言题目分享,c++,java,开发语言,c语言,数据结构,学习

代码1(按照要求修改后放到新string里)

class Solution {
public:
    bool isPalindrome(string s) {
        string re;
        for(auto e:s)//按照要求修改好
        {
            if((e>='A'&&e<='Z')||(e>='a'&&e<='z')||(e>='0'&&e<='9'))
            {
               if(e>='A'&&e<='Z')
                {
                    re+=(e+32);
                }
                else
                {
                    re+=e;
                }
            }
        }
        string modified(re);
        reverse(re.begin(),re.end());       
        //看看是否相同
        for(int i=0;i<modified.size();i++)
        {
            if(re[i]!=modified[i])
            {
                return false;
            }
        }
        return true;
    }

思路1

  1. 遍历输入字符串 s 中的每个字符 e。
    如果字符 e 是字母或数字,则根据题目要求将大写字母转换为小写字母,并将其添加到新的字符串 re 中。

  2. 创建一个新的字符串 modified,它是字符串 re 的一个副本。

  3. 反转字符串 re。

  4. 比较反转后的字符串 re 和副本字符串 modified,如果它们不相等,则返回 false,表示不是回文字符串;如果它们相等,则返回 true,表示是回文字符串

代码2(利用双指针/索引)

bool isLetterOrNumber(char ch)
{
    return (ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z')||(ch>='0'&&ch<='9');
}

class Solution {
public:
    bool isPalindrome(string s) {
        for(auto& e:s)//大的变小的
        {
            if(e>='A'&&e<='Z')
            {
                e+=32;
            }
        }
        int begin=0;
        int end=s.size()-1;
        while(begin<end)
        {
            while(begin<end&&!isLetterOrNumber(s[begin]))
            {
                begin++;
            }
            while(begin<end&&!isLetterOrNumber(s[end]))
            {
                --end;
            }
            if(s[begin]!=s[end])
            {
                return false;
            }
            else
            {
                ++begin;
                --end;
            }
        }
        return true;
    }
};

思路2

  1. 创建一个辅助函数 isLetterOrNumber,用于判断一个字符是否是字母或数字。
  2. 遍历输入字符串 s 中的每个字符 e,将大写字母转换为小写字母。
  3. 初始化两个指针 begin 和 end,分别指向字符串的开头和结尾。
  4. 在一个 while 循环中,不断移动指针 begin 和 end,直到两个指针相遇。
    在移动指针的过程中,跳过非字母和数字的字符。
  5. 在二者都是数字或者字母后,比较指针指向的字符,如果不相等,则返回 false,表示不是回文字符串;如果相等,则继续移动指针。
  6. 如果循环结束后都没有返回 false,则说明是回文字符串,返回 true。

3. 541. 反转字符串 II

传送门

题目详情

c++:string相关的oj题(415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III),c语言题目分享,c++,java,开发语言,c语言,数据结构,学习

代码1

class Solution {
public:
    string reverseStr(string s, int k) {
        int len=s.size();
        for(int i=0;i<len;i+=2*k)
        {
            if(i+k<=len)//剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符
                      //同时前面的2k区域不用管,直接满足,只有最后那个不够2k的区间才讨论
            {
                reverse(s.begin()+i,s.begin()+i+k);
            }
            else{
                reverse(s.begin()+i,s.begin()+len);
            }
        }
        return s;
    }
};

思路1

利用每次要跳2k来处理:就直接i+=2k,这样每次直接跳到下一个区间,前面够2k的不用管,直接满足i+k<=len,只有那最后一个不够2k的需要讨论(毕竟s.begin()+len是最后元素的下个位置)

4. 557. 反转字符串中的单词 III

传送门

题目详情

c++:string相关的oj题(415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III),c语言题目分享,c++,java,开发语言,c语言,数据结构,学习

代码1(利用find)

class Solution {
public:
    string reverseWords(string s) {
        size_t pos=0;
        int i=0;
        while(i<s.size())
        {
            pos=s.find(' ',i);
            if(pos==string::npos)//只有一个单词了
            {
                reverse(s.begin()+i,s.end());
                break;
            }
            reverse(s.begin()+i,s.begin()+pos);
            i=(pos+1);
        }
        return s;
    }
};

思路1

总体思路是找到单词的左和右索引,在这个区间内进行翻转

  1. 利用一个i 对字符串进行遍历,pos来储存找到的' '的下标
  2. 那么从i到pos就是一个单词加上’ ',正好满足reserve()函数左闭右开的性质
  3. 然后i=pos+1(跳到空格后)
  4. 如果没找到空格,就说明只剩下一个,或者只有一个单词。 就直接iend()进行翻转了

代码2(利用双指针)

class Solution {
public:
    string reverseWords(string s) {
       int i=0;
       while(i<s.size())//直接进循环
       {
           int left=i;//存一下起始位置
           while(i<s.size()&&s[i]!=' ')//找空格
           {
               i++;
           }
           //现在要么找到了,要么到size处了
           int right=i-1;
           while(left<right)//开始换
           {
               swap(s[left],s[right]);
               left++;
               right--;
           }
           if(s[i]==' ')
           {
               i++;
           }
       }
       return s;
    }
};

思路2

总体思路是一样的,不过自己找,没有利用find


今天就到这里啦!文章来源地址https://www.toymoban.com/news/detail-819175.html

到了这里,关于c++:string相关的oj题(415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode_字符串_简单_415.字符串相加

    给定两个字符串形式的非负整数 num1 和num2,计算它们的和并同样以字符串形式返回。 你不能使用任何內建的用于处理大整数的库(比如 BigInteger), 也不能直接将输入的字符串转换为整数形式。 示例 1: 输入:num1 = “11”, num2 = “123” 输出:“134” 示例 2: 输入:num1 = “

    2024年02月01日
    浏览(43)
  • LeetCode·每日一题·415. 字符串相加·模拟

    作者:小迅 链接:https://leetcode.cn/problems/add-strings/solutions/2347085/mo-ni-zhu-shi-chao-ji-xiang-xi-by-xun-ge-fges/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。   题意 - 给定二个字符串,计算它们的和并同样以字符串形式返回。 直接从

    2024年02月16日
    浏览(42)
  • String类即字符串的相关方法

    文章目录 前言 一、字符串是什么? 二、使用方法 1.String类 2.字符串的相关方法 总结         众所周知,现主流的编程语言都是以英文为计算机所识别,所以当中国程序员想要创建一种,可以操纵中文的,数据类型时,String字符串类型,便有了极大的帮助。         字符串

    2024年02月08日
    浏览(58)
  • 【string题解 C++】字符串相乘 | 翻转字符串III:翻转单词

    目录 字符串相乘 题面 错误记录 Way1 拆分成“先乘后加” 思路 实现 时空复杂度分析 反思 Way2 用数组 思路 实现 时空复杂度分析 翻转字符串III:翻转字符串中的单词 题面 错误记录 思路1 遍历找单词 实现 思路2 暴力解法 实现 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平

    2024年02月07日
    浏览(62)
  • 【C++ OJ练习】5.字符串最后一个单词的长度

    字符串最后一个单词的长度_牛客题霸_牛客网 倒着找第一个空格的下标 用下标之间的差来计算  【C++ OJ练习】5.字符串最后一个单词的长度 完

    2024年02月13日
    浏览(63)
  • C++之string字符串比较方法

    📣📣📣📣📣📣📣📣 ✏️作者主页:枫霜剑客 📋 系列专栏:C++实战宝典 🌲 上一篇: C++之string字符串不同类型间转换 📣📣📣📣📣📣📣📣 🎍逐梦编程,让中华屹立世界之巅。 🎍简单的事情重复做,重复的事情用心做,用心的事情坚持做; 字符串可以和类型相同的字

    2024年02月03日
    浏览(69)
  • C++ string判断是否包含子字符串

    C++的string类提供了字符串中查找另一个字符串的函数find。 其重载形式为: 功能为在string对象中,查找参数string类型的字符串是否存在,如果存在,返回起始位置。不存在则返回 string::npos 。

    2024年02月02日
    浏览(52)
  • 【C++】string字符串查找替换、比较、提取、插入和删除

    Link 加油! 感谢! 努力!

    2024年02月12日
    浏览(44)
  • C++中求string类型字符串长度的三种方法

    length()函数是string的内置成员方,用于返回string类型字符串的实际长度。 length()函数声明: // 返回 string 长度,单位字节 size_t length() const noexcept; 示例1: size()函数与length()一样,没有本质区别。string类刚开始只有length()函数,延续了C语言的风格。引入STL之后,为了兼容又加入

    2024年02月07日
    浏览(64)
  • C++中如何将string(字符串)转换为int(整数)

    C++ 编程语言有一些内置数据类型: int , 对于整数(例如 10、150) double ,对于浮点数(例如 5.0、4.5) char ,对于单个字符(例如“D”、“!”) string ,对于字符序列(例如“Hello”) bool , 对于布尔值(true 或 false) C++ 是一种 强类型 编程语言,这意味着当您创建变量时,你

    2024年02月06日
    浏览(80)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包