day08打卡

发布时间:2024年01月18日

day08打卡

344. 反转字符串

时间复杂度:O(N),空间复杂度:O(1)

第一想法:遍历,交换元素

class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i = 0, j = s.size()-1; i < j; ++i, --j)
        {
            swap(s[i], s[j]);
        }
    }
};

541. 反转字符串 II

时间复杂度:O(N),空间复杂度:O(1)

第一想法:单调栈,遍历一遍,每k个进行反转

困难:空间复杂度高,实现麻烦

看了题解:每次过2*k个元素,每次判断i+k是否小于等于size进行反转前k个即可,如果大于则不足k个元素全部反转

class Solution {
public:
    string reverseStr(string s, int k) {
        for(int i = 0; i < s.size(); i += 2*k)
        {
            //字符小于等于k个,反转k个
            if(i + k <= s.size())
            {
                reverse(s.begin()+i, s.begin()+i+k);
            }
            else //字符少于k个,全部反转
                reverse(s.begin()+i, s.begin()+s.size());
        }
        return s;
    }
};

54.替换数字

时间复杂度:O(N),空间复杂度:O(N)

第一想法:遍历,遇到数字插入“number”即可,

#include <iostream>
using namespace std;

int main()
{
    string s = "";
    getline(cin, s);
    string ans = "";
    for(int i = 0; i < s.size(); ++i)
    {
        if(s[i] >= '0' && s[i] <= '9')
        {
            ans += "number";
        }
        else
            ans += s[i];
    }
    cout << ans << endl;
    return 0;
}

151. 反转字符串中的单词

时间复杂度:O(N),空间复杂度:O(1)

第一想法:反转全部单词,去除空格,反转部分单词

看了题解:去重空格+添加空格、反转全部单词、反转部分单词

class Solution {
public:
    void resversePartWord(string& s, int start, int end)
    {
        for(int i = start, j = end; i < j; ++i, --j)
        {
            swap(s[i], s[j]);
        }
    }
    void eraseExtraSpace(string& str)
    {
        int slow = 0;
        for(int i = 0; i < str.size(); ++i)
        {
            if(str[i] != ' ')
            {
                //如果slow不为0,说明一个单词补完了,要加空格了
                if(slow != 0) str[slow++] = ' ';
                //补单词,直到遇到空格
                while(i < str.size() && str[i] != ' ') str[slow++] = str[i++];
            }
        }
        str.resize(slow);
    }
    string reverseWords(string s) {
        //去除全部空格+添加空格
        eraseExtraSpace(s);
        //全部反转
        reverse(s.begin(), s.end());
        //部分反转
        int start = 0;//记录单词的起始位置
        for(int i = 0; i <= s.size(); ++i)
        {
            if(i == s.size() || s[i] == ' ')
            {
                resversePartWord(s, start, i-1);
                start = i+1;//设置下一个单词起始位置
            }
        }
        return s;
    }
};

55.右旋字符串

时间复杂度:O(N),空间复杂度:O(1)

第一想法:三步反转法

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    //输入
    int k = 0;
    cin >> k;
    string s = "";
    cin >> s;
    //旋转
    
    //反转
    reverse(s.begin(), s.end());
    reverse(s.begin(), s.begin()+k);
    reverse(s.begin()+k, s.end());
    cout << s << endl;
    return 0;
}
文章来源:https://blog.csdn.net/dev1cce/article/details/135660768
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。