【OJ】string类刷题

zxctscl

发布于 2024-03-21 09:56:38

1580

文章被收录于专栏：zxctscl个人专栏zxctscl个人专栏

题目

1. 541 反转字符串 II
- 1.1 分析
- 1.2 代码
2. 557反转字符串中的单词 III
- 2.1 分析
- 2.2 代码
3. 43字符串相乘
- 3.1 分析
- 3.2 代码

1. 541 反转字符串 II

1.1 分析

题目给的是到2k就翻转前k个，那么循环的时候直接跳到2k处就行for (int i = 0; i < n; i += 2 * k) 。这里用 reverse翻转的时候区间选择与k有关，以例1为例：发现第一个翻转区间是[0,2)，也就从i=0到i+k,得注意区间是左闭右开的；第二个翻转区间是[4,6)，也就是i=4到n， reverse的结束就得取i+k和n中小的那一个。将区间写出来就是s.begin() + i, s.begin() + min(i + k, n)。

1.2 代码

class Solution {
public:
    string reverseStr(string s, int k) {
        int n = s.size();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(s.begin() + i, s.begin() + min(i + k, n));
        }
        return s;


    }
};

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

2.1 分析

定义一个变量记录一个单词开始的位置int a=0，遍历字符串，当遇到空格时候，进行reverse翻转，区间从开始记录单词的位置，到空格位置reverse(s.begin()+a,s.begin()+i);。然后将a跳过空格位置，又开始记录下一个单词开始位置 a=i+1;。遍历结束还剩下最后一个单词，直接进行翻转就行reverse(s.begin()+a,s.end())。

2.2 代码

class Solution {
public:
    string reverseWords(string s) {
        int n = s.size();
        int a=0;
        for(int i=0; i<n; ++i) 
        {
           if(s[i]==' ')
           {
            reverse(s.begin()+a,s.begin()+i);
             a=i+1;
           }
        }
        reverse(s.begin()+a,s.end());
        return s;



    }
};

3. 43字符串相乘

3.1 分析

用vector 存储num1和num2每个数相乘的值，就类似于列竖式做乘法的原理，来实现对相乘结果的存储，这里不进位相乘（num2[end2]-'0') * (num1[end1]-'0')。再将每一位结果相加存储到vector tmp里面。

vector tmp里面存储的是 4，13，28，27，18。

对 tmp里面存储的元素经行取模和取余就行，最后再倒序输出reverse(ret.begin(),ret.end())。

3.2 代码

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0";
         int m = num1.size(),n = num2.size();
         
        vector<int> tmp(m+n-1);
        // 1. 先无进位相乘再相加
        int end2 = n-1;
        while(end2 >= 0)
        {
            int end1 = m-1;
            while(end1 >= 0)
            {
                tmp[end1 + end2] += (num2[end2]-'0') * (num1[end1]-'0');
                end1--;
            }
            end2--;
        }
        // 2. 处理进位
        string ret;
        int i = m + n - 2,t = 0;
        while(i >= 0 || t)
        {
            if(i >= 0) t += tmp[i--];
            ret += t % 10 + '0';
            t /= 10;
        }
       reverse(ret.begin(),ret.end());
       return ret;


}
    
};

有问题请指出，大家一起进步！！！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-03-21，如有侵权请联系 cloudcommunity@tencent.com 删除

字符串