当前位置： 首页 > article >正文

C++string类相关OJ练习(2)

article 2024/9/21 14:52:17

个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

C++string类相关OJ练习(2)

收录于专栏【C++语法基础】
本专栏旨在分享学习C++的一点学习笔记，欢迎大家在评论区交流讨论💌

目录

1.反转字符串

2.反转字符串 II

3.反转字符串中的单词 III

4.字符串相乘

5.把字符串转换成整数 (atoi)

1.反转字符串

OJ链接:344. 反转字符串 - 力扣（LeetCode）

题目描述:

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

  • 1 <= s.length <= 105
  • s[i] 都是 ASCII 码表中的可打印字符

解题思路:

收尾交换，进行翻转

class Solution {
public:
  void reverseString(vector<char>& s) 
  {
    if(s.empty())
      return;

    int start = 0;
    int end = s.size()-1;
    while(start < end)
    {
      swap(s[start], s[end]);
      start++;
      end--;
    }
  }
};

2.反转字符串 II

OJ链接:541. 反转字符串 II - 力扣（LeetCode）

题目描述:

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

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

示例 1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2
输出："bacd"

提示：

  • 1 <= s.length <= 104
  • s 仅由小写英文组成
  • 1 <= k <= 104

解题思路:

写出反转函数,分情况讨论翻转 

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;
    }
};

3.反转字符串中的单词 III

题目描述:

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

示例 1：

输入：s = "Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

示例 2:

输入： s = "Mr Ding"
输出："rM gniD"

提示：

  • 1 <= s.length <= 5 * 104
  • s 包含可打印的 ASCII 字符。
  • s 不包含任何开头或结尾空格。
  • s 里 至少 有一个词。
  • s 中的所有单词都用一个空格隔开。

解题思路:

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())
        {
            //s.find(' ', start);从start位置开始找空格
            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;
    }
};

4.字符串相乘

OJ链接:43. 字符串相乘 - 力扣（LeetCode）

题目描述:

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

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

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

提示：

  • 1 <= num1.length, num2.length <= 200
  • num1 和 num2 只能由数字组成。
  • num1 和 num2 都不包含任何前导零，除了数字0本身。

解题思路:

1. 下翻转数据
2. 按位相乘
3. 将乘得的结果进行错位相加，模拟乘法的笔算过程

class Solution
{
public:
    void MulItem(string& tmp, string& num1, char a)
    {
        int i = 0, sign = 0;
        int mul = 0;

        while (i < num1.size())
        {
            mul = (num1[i] - '0') * (a - '0') + sign;
            if (mul >= 10)
            {
                sign = mul / 10;
                mul %= 10;
            }
            else
                sign = 0;

            tmp.push_back(mul + '0');
            i++;

        }
        if (sign > 0)
            tmp.push_back(sign + '0');
    }

    //对应为相加，sign进位采用引用传递
    int AddItem(int a, int b, int& sign)
    {
        int add = a + b + sign;

        if (add >= 10)
        {
            sign = 1;
            add -= 10;
        }
        else
            sign = 0;

        return add;
    }

    //错位相加
    void MoveAdd(string& result, string& tmp, int k)
    {
        int i, j;
        i = k;
        j = 0;

        int sign = 0;
        while (i < result.size() && j < tmp.size())
        {
            result[i] = AddItem(result[i] - '0', tmp[j] - '0', sign) + '0';
            i++;
            j++;
        }

        while (i < result.size() && sign)
        {
            result[i] = AddItem(result[i] - '0', 0, sign) + '0';
            i++;
        }

        while (j < tmp.size())
        {
            int v = AddItem(0, tmp[j] - '0', sign);
            result.push_back(v + '0');
            j++;
        }

        if (sign)
            result.push_back(sign + '0');
    }



    string multiply(string num1, string num2)
    {
        //先翻转数据，方便进位处理
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());

        string tmp, result;
        for (int i = 0; i < num2.size(); ++i)
        {
            //使用num2的每一个数据乘以num1
            MulItem(tmp, num1, num2[i]);
            //将乘得的结果进行错位相加
            MoveAdd(result, tmp, i);
            tmp.clear();
        }

        while (result.size() != 1 && result.back() == '0')
            result.pop_back();

        //翻转数据，恢复数据
        reverse(result.begin(), result.end());
        return result;
    }
};

5.把字符串转换成整数 (atoi)

OJ链接:LCR 192. 把字符串转换成整数 (atoi) - 力扣（LeetCode） 

题目描述:

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

  1. 读入字符串并丢弃无用的前导空格
  2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
  3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
  4. 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
  5. 如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
  6. 返回整数作为最终结果。

注意：

  • 本题中的空白字符只包括空格字符 ' ' 。
  • 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

示例 1：

输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："42"（读入 "42"）
           ^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。

示例 2：

输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
            ^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
             ^
第 3 步："   -42"（读入 "42"）
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。

示例 3：

输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
             ^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。

解题思路:

1.首先除去不必要的字符

2.用sign存贮'-'和'+',以便后续进行正负判断

3.读取数字段字符,需要注意的是,我们使用border(INT_MAX/10)进行判断,作用为:

        i. 用低于int型数据长度一位的数据border判断了超过int型数据长度的值 
        ii. 将超过最大值和低于最小值的情况都包括了

 INT_MAX和INT_MIN

int main()
{
    int end = INT_MAX / 10;
    int end2 = INT_MIN;
    cout << end << endl; 
    cout << INT_MAX << " " << end2 << endl;
    return 0;
}

 

class Solution {
public:
    int myAtoi(string str)
    {
        bool sign = true;   //默认为正数
        // 跳过开头可能存在的空格
        int i = 0;
        while (i < str.size() && str[i] == ' ')
        {
            i++;
        }
        //接着判断首个字符是否为正负号
        if (str[i] == '-')
        {
            sign = false;  // 该字符串为负数，移至下一个字符接着判断
            i++;
        }
        else if (str[i] == '+')  // 字符串为正数，sign已经默认为true，直接移动到下一位即可
            i++;
        //下面开始对非正负符号位进行判断
        if (str[i] < '0' || str[i] > '9') // 正常数字第一位不能是0，必须为1~9之间的数字，否则就是非法数字
            return 0;
        int res = 0;   //这里res用的int型，需要更加仔细考虑边界情况，但如果用long的话可以省去一些麻烦
        int num = 0;
        //INT_MAX是int能达到的最大值2^31-1 = 2147483648
        int border = INT_MAX / 10;  // 用来验证计算结果是否溢出int范围的数据
        while (i < str.size())
        {
            // 遇到非数字字符，则返回已经计算的res结果
            if (str[i] < '0' || str[i] > '9')
                break;
            // 注意这句话要放在字符转换前，因为需要验证的位数比实际值的位数要少一位, 这里比较巧妙的地方在于
            // 1. 用低于int型数据长度一位的数据border判断了超过int型数据长度的值 
            // 2. 将超过最大值和低于最小值的情况都包括了
            if (res > border || res == border && str[i] > '7')
                return sign == true ? INT_MAX : INT_MIN;
            //开始对数字字符进行转换
            num = str[i] - '0';
            res = res * 10 + num;
            i++;
        }
        //最后结果根据符号添加正负号
        return sign == true ? res : -res;
    }
};


int main()
{
    int end = INT_MAX / 10;
    cout << end << endl; 
    cout << INT_MAX << endl;
    return 0;
}

 


http://www.kler.cn/news/290235.html

相关文章：

  • 【32项目】基于stm32f103c8t6的智能拐杖（文章末尾含完整代码）
  • MAC打开IDA Pro意外退出
  • 论文辅助笔记：LP_BERT
  • 【60天备战软考高级系统架构设计师——第一天：软件工程概述】
  • ListBox等控件的SelectedItem,SelectedValue,SelectedValuePath属性详解
  • 0904，关联式容器针对于自定义形式的写法（
  • 华为数据之道-读书笔记
  • 全能AI vs 专业AI：AI模型未来之路与市场潜力
  • Express Response类深度解析：全面掌握属性与方法，提升开发效率
  • Win 11补丁让AMD成亲儿子，性能最高提升35%
  • 神策SDK不支持Windows客户端全埋点，怎么实现用户统计分析？
  • JDK源码分析：HashMap
  • kubeadm部署 Kubernetes(k8s) 高可用集群【V1.28 】
  • net、udp、tcp
  • Linux之多线程概念
  • mongodb在Java中条件分组聚合查询并且分页(时间戳，按日期分组，年月日...)
  • OpenCV绘图函数（11）计算文本字符串在特定字体、尺寸和厚度下的大小的函数getTextSize()的使用
  • 模型从 HuggingFace 转存到 ModelScope
  • 【ubuntu使用笔记】Ubuntu Desktop 访问SMB共享文件夹
  • Spring声明式事务使用详情（知识点+案例）
  • 【Java】封装
  • 《Zookeeper 的监听机制及原理解析》
  • 后台使用Motionbuilder
  • 聚类算法-Kmeans聚类
  • 【60天备战软考高级系统架构设计师——第八天：设计模式概述】
  • Spring Boot项目中结合MyBatis详细使用
  • “智能化自动化” 架构之4：中间建模脑的软件设计三大原则-依赖倒置控制反转和依赖注入
  • 在react中利用three.js 渲染模型 让鼠标拖拽是模型转动
  • redhat7.9安装zsh以及常用插件
  • 具有平面规则性的单目视觉惯性里程计