【LeetCode】【C++】string OJ必刷题

这篇具有很好参考价值的文章主要介绍了【LeetCode】【C++】string OJ必刷题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【LeetCode】【C++】string OJ必刷题,LeetCode刷题笔记,C++,c++,开发语言

👀樊梓慕:个人主页

 🎥个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》

🌝每一个不曾起舞的日子,都是对生命的辜负


目录

前言

【LeetCode】415.字符串相加

【LeetCode】43.字符串相乘 

 【LeetCode】125.验证回文字符串

【LeetCode】541.反转字符串Ⅱ

【LeetCode】557.反转字符串中的单词Ⅲ


前言

利用string的一些常用方法解题,本篇文章不乏有你眼前一亮的优秀方法,欢迎大家订阅。

欢迎大家📂收藏📂以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。

=========================================================================

GITEE相关代码:🌟fanfei_c的仓库🌟

=========================================================================


【LeetCode】415.字符串相加

=================================原题链接=================================

415. 字符串相加https://leetcode.cn/problems/add-strings/

 =========================================================================

题目:

给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库(比如 BigInteger), 也不能直接将输入的字符串转换为整数形式。

【LeetCode】【C++】string OJ必刷题,LeetCode刷题笔记,C++,c++,开发语言


实际应用中,可能会有一些非常大的数字要求进行计算,甚至long long类型都无法容纳。

那么此时我们就需要利用字符串,简称“大数运算”。

思路:

实际上就是简单的加法的思路,主要难点在于如何控制进位。

代码实现(未优化):

class Solution {
public:
    string addStrings(string num1, string num2) {
        int end1=num1.size()-1,end2=num2.size()-1;
        string retStr;
        int next=0;
        
        while(end1>=0 || end2>=0)
        {      
            int val1=0,val2=0;   
            if(end1>=0)
                val1=num1[end1--]-'0';//拿到末尾数字
            if(end2>=0)
                val2=num2[end2--]-'0';//拿到末尾数字

            int ret=val1+val2+next;
            next=ret/10;//得到进位
            ret%=10;//得到该位计算结果
            retStr.insert(retStr.begin(),'0'+ret);
        }
        if(next==1)//如果进位有剩余,不要忘记进位补充到数字中
        {
            retStr.insert(retStr.begin(),'1');
        }
        return retStr;
    }
};

【LeetCode】【C++】string OJ必刷题,LeetCode刷题笔记,C++,c++,开发语言


 为什么时间复杂度会这么高呢?

实际上是因为insert方法,整个算法最后的时间复杂度为O(N^2),insert为头插,每次头插都需要挪动后面的元素,这也是导致了时间复杂度偏高的原因,那么如何解决呢?

优化思路:

  • 我们知道尾插在这里的效率肯定是强于头插的,唯一需要解决的问题就是尾插得到的字符串是“反”的,那我们只需要调用reverse方法翻转字符串即可。

代码实现(优化):

class Solution {
public:
    string addStrings(string num1, string num2) {
        int end1 = num1.size() - 1, end2 = num2.size() - 1;
        string retStr;
        int next = 0;

        while (end1 >= 0 || end2 >= 0)
        {
            int val1 = 0, val2 = 0;
            if (end1 >= 0)
                val1 = num1[end1--] - '0';
            if (end2 >= 0)
                val2 = num2[end2--] - '0';

            int ret = val1 + val2 + next;
            next = ret / 10;
            ret %= 10;
            retStr += (ret + '0');
        }
        if (next == 1)//如果有剩余进位则尾插剩下的进位数字
        {
            retStr += '1';
        }
        reverse(retStr.begin(), retStr.end());
        return retStr;
    }
};

【LeetCode】【C++】string OJ必刷题,LeetCode刷题笔记,C++,c++,开发语言


【LeetCode】43.字符串相乘 

=================================原题链接=================================

43.字符串相乘 https://leetcode.cn/problems/multiply-strings/description/

 =========================================================================

题目:

给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。

注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

【LeetCode】【C++】string OJ必刷题,LeetCode刷题笔记,C++,c++,开发语言


 思路:

乘法的进位与加法有相似之处,但不好控制的是被乘数乘以乘数的每一位所得到的结果需要错位相加。

比如:

【LeetCode】【C++】string OJ必刷题,LeetCode刷题笔记,C++,c++,开发语言

代码实现:

class Solution {
public:
    //乘方法
    string multiply(string num1, string num2) {
        int end1 = num1.size() - 1, end2 = num2.size() - 1;
        string reg;
        int next = 0;
        string retStr;

        //判断是否有字符串为0,如有直接输出0
        if(num1=="0")
        {
            return num1;   
        }
        if(num2=="0")
        {
            return num2;
        }

        while (end2 >= 0)//双层循环,因为根据乘法,我们知道被乘数每个数字都要被乘数乘
        {
            while (end1 >= 0)//内层循环得到的reg是被乘数乘个/十/百/···的结果
            {
                int val1 = 0, val2 = 0;
                if (end1 >= 0)
                    val1 = num1[end1--] - '0';
                val2 = num2[end2] - '0';

                int ret = val1 * val2 + next;
                next = ret / 10;
                ret %= 10;
                reg += (ret + '0');
            }

            if (next != 0)//将未加的进位补上
            {
                reg += (next + '0');
            }

            reverse(reg.begin(), reg.end());//由于之前在尾插,数字为反着的,所以这里反转回来
            //之前采用尾插是因为尾插的复杂度低于头插
            
            //这步是为了错位相加用,比如当被乘数乘乘数的十位得到的数字,应该比被乘数乘乘数的个位多一位0,才能保证乘法逻辑的正确
            for (int i = 0; i < count - end2; i++)
            {
                reg += '0';
            }

            retStr = addStrings(retStr, reg);//调用加方法,利用实现好的加方法将乘完的结果加在一起
            //调整参数
            end2--;
            end1 = num1.size() - 1;
            next=0;
            reg.clear();
        }

        return retStr;
    }
};

 【LeetCode】125.验证回文字符串

=================================原题链接=================================

125.验证回文字符串https://leetcode.cn/problems/valid-palindrome/description/

 =========================================================================

题目:

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s,如果它是 回文串 ,返回 true ;否则,返回 false 

【LeetCode】【C++】string OJ必刷题,LeetCode刷题笔记,C++,c++,开发语言


判断回文是我们的老朋友了,利用左右指针即可轻松解决,需要注意的无非就是字符的转化。

代码实现:

class Solution {
public:
    bool isDigtalOrWord(char ch)
    {
        if ((ch >= '0' && ch <= '9')
            || (ch >= 'A' && ch <= 'Z')
            || (ch >= 'a' && ch <= 'z'))
            return true;
        return false;
    }
    bool isPalindrome(string s)
    {
        if (s.empty())
            return true;
        for (int i = 0; i < s.size(); ++i)
        {
            s[i] = tolower(s[i]); //忽略大小写      
        }
        int left = 0;
        int right = s.size() - 1;
        while (left < right)
        {
            //找到左边第一个未比较的字母
            while (left < right && !isDigtalOrWord(s[left]))
                left++;
            //找到右边第一个未比较的字母
            while (left < right && !isDigtalOrWord(s[right]))
                right--;
            //左右两边字母若不相等,则不是回文
            if (s[left] != s[right])
                return false;
            left++;
            right--;
        }
        return true;
    }
};

【LeetCode】541.反转字符串Ⅱ

=================================原题链接=================================

541. 反转字符串 IIhttps://leetcode.cn/problems/reverse-string-ii/description/

 =========================================================================

题目:

给定一个字符串 s 和一个整数 k,从字符串开头算起,每计数至 2k 个字符,就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个,则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。

【LeetCode】【C++】string OJ必刷题,LeetCode刷题笔记,C++,c++,开发语言


代码实现:

class Solution {
public:
    //翻转start到end区间的字符串
    void Reverse(string& s, int start, int end)
    {
        char tmp;
        end--;
        while (start < end)
        {
            tmp = s[start];
            s[start] = s[end];
            s[end] = tmp;
            start++;
            end--;
        }
    }
    string reverseStr(string s, int k)
    {
        int len = s.size();
        for (int i = 0; i < len; i += 2 * k)
        {
            if (i + k < len)
                Reverse(s, i, i + k);
            else
                Reverse(s, i, len);
        }
        return s;
    }
};

【LeetCode】557.反转字符串中的单词Ⅲ

=================================原题链接=================================

557. 反转字符串中的单词 IIIhttps://leetcode.cn/problems/reverse-words-in-a-string-iii/description/

 =========================================================================

题目:

给定一个字符串 s ,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。 

【LeetCode】【C++】string OJ必刷题,LeetCode刷题笔记,C++,c++,开发语言


思路:

  • 1. 通过查找空格,分割单词
  • 2. 针对分割的单词进行翻转

代码实现:

class Solution {
public:
    void Reverse(string& s, int start, int end)
    {
        char tmp;
        while (start < end)
        {
            tmp = s[start];
            s[start] = s[end];
            s[end] = tmp;
            start++;
            end--;
        }
    }
    string reverseWords(string s)
    {
        size_t start = 0;
        size_t end = 0;
        while (start < s.size())
        {
            end = s.find(' ', start);
            if (end == string::npos)
            {
                end = s.size();
                break;
            }
            Reverse(s, start, end - 1);
            start = end + 1;
        }
        Reverse(s, start, end - 1);
        return s;
    }
};

=========================================================================

如果你对该系列文章有兴趣的话,欢迎持续关注博主动态,博主会持续输出优质内容

🍎博主很需要大家的支持,你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏+关注 ~🌟

========================================================================= 文章来源地址https://www.toymoban.com/news/detail-751661.html

到了这里,关于【LeetCode】【C++】string OJ必刷题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【C语言必刷题】2. 9*9乘法表

    📚博客主页:爱敲代码的小杨. ✨专栏:《Java SE语法》 | 《数据结构与算法》 | 《C生万物》 ❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️ 🙏小杨水平有限,欢迎各位大佬指点,相互学习进步! 使用C语⾔写⼀个程序打印9*9乘法⼝诀表,如下

    2024年02月19日
    浏览(32)
  • 【C语言必刷题】1.打印1~100之间的奇数

    📚博客主页:爱敲代码的小杨. ✨专栏:《Java SE语法》 | 《数据结构与算法》 | 《C生万物》 ❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️ 🙏小杨水平有限,欢迎各位大佬指点,相互学习进步! 使用C语言写一个程序打印1~100之间的奇数,要

    2024年02月21日
    浏览(75)
  • Leetcode刷题笔记题解(C++):203. 移除链表元素

    思路:不同的情况出现了,就是第一个节点要是为等于val的节点,可以新建一个节点,并next指向head,这样就可以遍历新的链表来删除节点

    2024年02月22日
    浏览(52)
  • Leetcode刷题笔记题解(C++):83. 删除排序链表中的重复元素

    思路:链表相关的问题建议就是画图去解决,虽然理解起来很容易,但就是写代码写不出来有时候,依次去遍历第二节点如果与前一个节点相等则跳过,不相等则遍历第三个节点

    2024年02月22日
    浏览(57)
  • 【C++】---string的OJ题

    解题思路: 根据题意,有以下四种字符需要考虑: 首部空格: 删除之即可; 符号位: 三种情况,即 ‘’+‘’ , ‘‘−’’ , \\\'\\\'无符号\\\" ;新建一个变量(sign)保存符号位,返回前判断正负即可; 非数字字符: 遇到首个非数字的字符时,应立即返回; 数字字符: 字符转数字

    2024年04月13日
    浏览(70)
  • oj刷题-C语言版

    输入两个整数,求这两个整数的和是多少。 输入格式 输入两个整数A,B ,用空格隔开 输出格式 输出一个整数,表示这两个数的和 数据范围 0≤A,B≤108 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。 栈有两种最重要的操作,即 pop(

    2024年02月05日
    浏览(29)
  • C语言——oj刷题——杨氏矩阵

    目录 1. 理解杨氏矩形的特点 2. 实现杨氏矩形查找算法 3. 编写示例代码 当我们谈到杨氏矩形时,我们指的是一种在二维数组中查找目标元素的高效算法。它是由杨氏(Yan Shi)教授提出的,因此得名为杨氏矩形。 杨氏矩形问题的场景是这样的:给定一个有序的二维数组,每一

    2024年02月20日
    浏览(39)
  • C语言——oj刷题——获取月份天数

    KiKi想获得某年某月有多少天,请帮他编程实现。输入年份和月份,计算这一年这个月有多少天。 输入描述: 多组输入,一行有两个整数,分别表示年份和月份,用空格分隔。 输出描述: 针对每组输入,输出为一行,一个整数,表示这一年这个月有多少天。 题目要求通过输

    2024年02月20日
    浏览(29)
  • 【C++ • STL • 力扣】详解string相关OJ

    ヾ(๑╹◡╹)ノ\\\" 人总要为过去的懒惰而付出代价 ヾ(๑╹◡╹)ノ\\\" 力扣链接 代码1展示 :【下标】 代码2展示 :【迭代器】 思路 :快速排序中的单趟排序 知识点 :C++库提供了swap的函数,可以直接调用。 力扣链接 代码展示 : 思路 :计数排序的思想 牛客链接 代码展示 :

    2024年02月09日
    浏览(41)
  • C语言——oj刷题——回文字符串

    问题: 实现一个函数,判断一个字符串是否为回文字符串。 回文字符串是指正读和反读都相同的字符串。例如,\\\"level\\\"、\\\"radar\\\"和\\\"madam\\\"都是回文字符串。 要解决这个问题,我们可以使用两个指针分别指向字符串的首尾字符,然后逐步向中间移动,同时比较指针所指向的字符是

    2024年02月21日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包