从C语言到C++_11(string类的常用函数)力扣58和415(下)

简介: 从C语言到C++_11(string类的常用函数)力扣58和415

从C语言到C++_11(string类的常用函数)力扣58和415(中):https://developer.aliyun.com/article/1513667

8. string相关OJ

现在关于OJ题建议刷《剑指offer》和力扣上string的题,

用牛客一道题演示下上面提到的geline函数:看看IO型和接口型C++的区别

字符串最后一个单词的长度_牛客题霸_牛客网 (nowcoder.com)

简单  通过率:35.00%  时间限制:1秒  空间限制:32M


描述


计算字符串最后一个单词的长度,单词以空格隔开,字符串长度小于5000。(注:字符串末尾不以空格为结尾)


输入描述:


输入一行,代表要计算的字符串,非空,长度小于5000。


输出描述:


输出一个整数,表示输入字符串最后一个单词的长度。


示例1


输入:


hello nowcoder


输出:


8


说明:


最后一个单词为nowcoder,长度为8  

#include <iostream>
using namespace std;
 
int main() {
    int a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        cout << a + b << endl;
    }
}
// 64 位输出请用 printf("%lld")

代码解析:

这题直接用 cin 就不行,因为有空格,所以我们用 getline 输入一行字符,查文档:

虽然不包string头文件有些编译器也能过,但还是包上好:

#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string str;
    getline(cin,str);
    size_t pos = str.rfind(' ');
    if(pos != str.npos)
    {
        cout << str.size() - pos - 1 << endl;// -1是减去空格
    }
    else //找不到直接输出size
    {
        cout << str.size();
    }
    return 0;
}

看看力扣是这么写的:(力扣就检查用例较多,且此题多加了最后有空格的情况)

58. 最后一个单词的长度 - 力扣(LeetCode)

难度简单给你一个字符串 s,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1:

输入:s = "Hello World"

输出:5

解释:最后一个单词是“World”,长度为5。

示例 2:

输入:s = "   fly me   to   the moon  "

输出:4

解释:最后一个单词是“moon”,长度为4。

示例 3:

输入:s = "luffy is still joyboy"

输出:6

解释:最后一个单词是长度为6的“joyboy”。

提示:

  • 1 <= s.length <= 10^4
  • s 仅有英文字母和空格 ' ' 组成
  • s 中至少存在一个单词

代码解析:

只是比牛客的那题多了一个条件,所以直接放代码:

class Solution {
public:
  int lengthOfLastWord(string s) {
        while(s[s.size()-1] == ' ')
        {
            s.erase(s.size()-1,1);
        }
    size_t pos = s.rfind(' ');
    if (pos != s.npos)
    {
      return s.size() - pos - 1;// -1是减去空格
    }
    else //找不到直接输出size
    {
      return s.size();
    }
  }
};

力扣415. 字符串相加

415. 字符串相加 - 力扣(LeetCode)

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

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

示例 1:

输入:num1 = "11", num2 = "123"

输出:"134"

示例 2:

输入:num1 = "456", num2 = "77"

输出:"533"

示例 3:

输入:num1 = "0", num2 = "0"

输出:"0"

提示:

  • 1 <= num1.length, num2.length <= 10^4
  • num1num2 都只包含数字 0-9
  • num1num2 都不包含任何前导零
class Solution {
public:
    string addStrings(string num1, string num2) {
 
    }
};

代码解析:

这题首先想到从字符串末尾开始加,加后考虑进位后头插到一个新的字符串。需要用到头插接口:

查文档发现string没有头插,只有任意位置插入删除,凑合用用: 法一:头插

class Solution {
public:
  string addStrings(string num1, string num2) {
    int end1 = num1.size() - 1, end2 = num2.size() - 1;
    int next = 0;// 表示进位,这里只会是0或1
    string ret;// 把加后的字符弄到这
    while (end1 >= 0 || end2 >= 0)// 只要有一个没加完就继续,加完的看做数字0
    {
      int val1 = end1 >= 0 ? num1[end1] - '0' : 0;// -'0'转化为数字
      int val2 = end2 >= 0 ? num2[end2] - '0' : 0;
      int add = val1 + val2 + next;
      next = add > 9 ? 1 : 0;// 处理进位
      //写到这想到头插:查文档:
      ret.insert(0, 1, (add % 10) + '0');// 在ret第0个位置插入1个字符
      --end1;
      --end2;
    }
    if (next)// 提交后看测试用例有进位没处理到的处理一下
    {
      ret.insert(0, 1, '1');
    }
    return ret;
  }
};

提交通过后发现效率很低(虽然力扣效率不太准确,但是你网比较好且提交几次还是很慢就应该真是代码效率低了)哪里会低?string是连续的空间,所以任意位置插入需要挪动数据,效率就低了(O(N^2))。那能不能用效率高的尾插?而且 += 很方便。答案是可以的,头插和尾插最后的差别就是字符串反过来了,那我们以前写过逆置字符串就能派上用场,更方便的是C++已经提供了逆置字符串的函数,(string没提供,头文件algorithm提供了)在这个旧版网站搜一下:cplusplus.com - The C++ Resources Network

或者在msdn应用搜一下:(能搜到就行)

和我们以前写的差不多,左闭右开的区间,直接用,(法二,尾插+逆置):

class Solution {
public:
    string addStrings(string num1, string num2) {
        int end1 = num1.size() - 1, end2 = num2.size() - 1;
        int next = 0;// 表示进位,这里只会是0或1
        string ret;
        while(end1 >= 0 || end2 >= 0)// 只要有一个没加完就继续,加完的看做数字0
        {
            int val1 = end1 >= 0 ? num1[end1] - '0' : 0;// -'0'转化为数字
            int val2 = end2 >= 0 ? num2[end2] - '0' : 0;
            int add = val1 + val2 + next;
            next = add > 9 ? 1 : 0;// 处理进位
 
            //ret.insert(0,1,(add % 10) + '0');// 在ret第0个位置插入1个字符
            ret += (add % 10) + '0';// 尾插
            --end1;
            --end2;
        }
        if(next)// 提交后看测试用例有进位没处理到的处理一下
        {
            //ret.insert(0,1,'1');// 头插
            ret += '1';// 尾插
        }
 
        reverse(ret.begin(),ret.end());
        return ret;
    }
};

本章完。

学了这么多接口函数,又刷了两道OJ,后面也差不多就会刷了,

后面更一篇string相关的OJ题,再后一篇就模拟实现string,

后面的STL学习基本都是按照这个顺序走,只是内容少了点,因为接口函数都是类似的。

目录
相关文章
|
1天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
2天前
|
C++ 容器
【C++语言】String 类关键函数实现,手搓一个简单字符串类!
【C++语言】String 类关键函数实现,手搓一个简单字符串类!
|
2天前
|
C语言
C语言常用函数整理
C语言常用函数整理
|
2天前
|
编译器 C++
c++primer plus 6 读书笔记 第八章 函数探幽0
c++primer plus 6 读书笔记 第八章 函数探幽0
|
2天前
|
编译器 vr&ar C++
c++primer plus 6 读书笔记 第七章 函数--C++的编程模块
c++primer plus 6 读书笔记 第七章 函数--C++的编程模块
|
4天前
|
C++
C++中函数模版与类模版
C++中函数模版与类模版
18 4
|
8天前
|
C++
C++中的setprecision: fixed: scientific等函数
C++中的setprecision: fixed: scientific等函数
6 0
|
8天前
|
存储 程序员 C++
stoll函数和std::to_string函数
stoll函数和std::to_string函数
8 0
|
9天前
|
C语言
C语言进阶——文件的读写(文件使用方式、文件的顺序读写、常用函数、fprintf、fscanf)
C语言进阶——文件的读写(文件使用方式、文件的顺序读写、常用函数、fprintf、fscanf)
6 0