• 【LeetCode】string 类的几道简单题

    ​🌠 作者：@阿亮joy.
    🎆专栏：《阿亮爱刷题》
    🎇 座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根
    在这里插入图片描述

    👉仅反转字母👈

    给你一个字符串 s ，根据下述规则反转字符串：

    • 所有非英文字母保留在原有位置。
    • 所有英文字母（小写或大写）位置反转。

    返回反转后的 s 。

    在这里插入图片描述

    思路：这道题可以借助快排的思想，左边找出字母，右边找出字母，然后进行交换。如果不是字母，就继续找。

    class Solution 
{
public:
    string reverseOnlyLetters(string s) 
    {
        size_t begin = 0;
        size_t end = s.size() - 1;
        while(begin < end)
        {
            // isalpha是判断是否是字母的函数接口
            while(begin < end && !isalpha(s[begin]))
            {
                ++begin;
            }
            while(begin < end && !isalpha(s[end]))
            {
                --end;
            }

            swap(s[begin], s[end]);
            ++begin;
            --end;
        }
        return s;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    在这里插入图片描述

    👉字符串中的第一个唯一字符👈

    给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

    在这里插入图片描述

    思路：可以借助哈希映射的思想，用一个数组统计每个字母出现的次数，然后再遍历字符串就能够知道那个字母是第一个唯一字符。

    class Solution 
{
public:
    int firstUniqChar(string s) 
    {
        int count[26] = {0};
        // 统计字母出现的次数
        for(auto ch : s)
        {
            ++count[ch - 'a'];
        }

        // 顺序遍历字符串，找出第一个唯一字母
        for(int i = 0; i < s.size(); i++)
        {
            if(count[s[i] - 'a'] == 1)
                return i;            
        }
        return -1;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    在这里插入图片描述

    👉字符串相加👈

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

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

    在这里插入图片描述
    思路：这道题主要考察的就是竖式相加，我们可以从字符串的末尾依次往前相加，并保存进位信息。那如何将这个过程转换成代码呢？先定义两个变量end1和end2，并初始化为size - 1，如何利用 while 循环从后往前遍历字符串。当end1和end2都小于0时，while 循环结束。在while 循环里，定义三个变量val1、val2和ret，ret等于val1 + val2 + carry，其中carry为进位信息，其值为ret / 10。如果end小于0，则val的值为0。现在我们已经得到了相加的结果和进位信息了，就可以将数据插入到字符串。插入有两种方式，可以头插，也可以尾插。如果采用头插，效率会比较低，因为需要挪动数据。如果采用尾插，循环结束后需要将字符串逆置一下。

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

        while(end1 >= 0 || end2 >= 0)
        {
            int val1 = end1 >= 0 ? num1[end1] - '0' : 0;
            int val2 = end2 >= 0 ? num2[end2] - '0' : 0;
            int ret = val1 + val2 + carry;
            carry = ret / 10;
            ret %= 10;

            retStr.insert(0, 1, '0' + ret);
            --end1;
            --end2;
        }
		// 处理进位信息
        if(carry == 1)
            retStr.insert(0, 1, '1');

        return retStr;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    在这里插入图片描述

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

        while(end1 >= 0 || end2 >= 0)
        {
            int val1 = end1 >= 0 ? num1[end1] - '0' : 0;
            int val2 = end2 >= 0 ? num2[end2] - '0' : 0;
            int ret = val1 + val2 + carry;
            carry = ret / 10;
            ret %= 10;

            retStr += '0' + ret;
            --end1;
            --end2;
        }
		// 处理进位信息
        if(carry == 1)
            retStr += '1';
        // 逆置字符串
        reverse(retStr.begin(), retStr.end());
        return retStr;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    在这里插入图片描述

    👉字符串相乘👈

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

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

    在这里插入图片描述

    思路：首先将补零，将 num2 的每位数字和 num1 相乘的结果存到 ret1 里，再将 ret1 逆置就能得到 num2 的低位到高位与 num1 相乘的结果，最后将 ret1 加到结果 ret 上，ret 就是最终相乘的结果了。

    在这里插入图片描述

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

        while(end1 >= 0 || end2 >= 0)
        {
            int val1 = end1 >= 0 ? num1[end1] - '0' : 0;
            int val2 = end2 >= 0 ? num2[end2] - '0' : 0;
            int ret = val1 + val2 + carry;
            carry = ret / 10;
            ret %= 10;

            retStr += '0' + ret;
            --end1;
            --end2;
        }

        if(carry == 1)
            retStr += '1';
        
        reverse(retStr.begin(), retStr.end());
        return retStr;
    }

    string multiply(string num1, string num2) 
    {
        // 思路：首先将补零，将num2的每位数字和num1相乘的结果存到ret1里
        // 再将ret1逆置就能得到num2的个位、十位和百位与num1相乘的结果
        // 再将ret1加到结果ret上，ret就是最终相乘的结果了
        string ret("0");
        if(num1[0] == '0' || num2[0] == '0')
        {
            return ret;
        }
        int size1 = (int)num1.size();
        int size2 = (int)num2.size();
        for(int i = size2 - 1; i >=  0; i--)
        {
            string ret1;
            for(int j = 0; j < size2 - 1 - i; j++)
            {
                ret1.append(1, '0');
            }
            
            int carry = 0;
            for(int j = size1 - 1; j >= 0; j--)
            {
                int val1 = num1[j] - '0';
                int val2 = num2[i] - '0';
                int ret2 = val1 * val2 + carry;
                carry = ret2 / 10;
                ret1.append(1, '0' + ret2 % 10);
            }
            if(carry > 0)
            {
                ret1.append(1, '0' + carry);
            }
            reverse(ret1.begin(), ret1.end());
            ret = addStrings(ret, ret1);
        }

        return ret;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70

    在这里插入图片描述

    👉反转字符串中的单词 III👈

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

    在这里插入图片描述

    思路：定义两个变量pos和prevpos，pos的初始值为第一个空格所在的位置，prevpos的初始值为0。当pos != string::npos时，进入 while 循环，将prevpos到pos之间的字符逆置，逆置之后，prevpos = pos + 1，pos等于下一个空格的位置；while 循环结束，将prevpos到s.size()-1之间的字符逆置，然后字符串的单词都逆置过来了。

    class Solution 
{
public:
	// 逆置算法
    void reverse(string& s, size_t begin, size_t end)
    {
        while(begin < end)
        {
            swap(s[begin++], s[end--]);        
        }
    }

    string reverseWords(string s) 
    {
        size_t pos = s.find(' ', 0);
        size_t prevpos = 0;
        while(pos != string::npos)
        {
            reverse(s, prevpos, pos - 1);
            prevpos = pos + 1;
            pos = s.find(' ', pos + 1);
        }
        reverse(s, prevpos, s.size() - 1);
        return s;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    在这里插入图片描述

    👉反转字符串 II👈

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

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

    在这里插入图片描述

    思路：先定义一个逆置算法的函数，然后判断剩余的字符有多少，然后进行相应的操作就行了。

    class Solution 
{
public:
  //翻转start到end区间的字符串
  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 reverseStr(string s, int k) 
  {
    int len = s.size();
    for(int i = 0; i < len; i += 2 * k)
    {
        // 剩余字符大于k个
        if(i + k - 1 < len)
            Reverse(s, i, i + k - 1);
        else  // 剩余字符小于或等于k个
            Reverse(s, i, len - 1);
    }
    return s;
  }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    在这里插入图片描述

    👉总结👈

    好久没有写过刷题博客了，上次写的时候还是在上次。希望大家能够喜欢，那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️

  • 相关阅读:
    校园二手交易小程序,微信小程序二手交易系统毕设作品
    Windows重启时的电脑蓝屏怎么办？
    优维邀您共赴2022GOPS全球运维大会，探索精益IT运维方式
    昨天的面试官居然是位小姐姐，聊了半个多小时的异常处理
    10链表-单链表构造LinkedList
    无感验证案例：工商联人才中心
    String类的详解
    【深度学习】Python爬取豆瓣实现影评分析
    使用Redis将单机登录改为分布式登录
    【毕业季】平凡的求学生涯，回顾与启程
  • 原文地址：https://blog.csdn.net/m0_63639164/article/details/127926562