自学内容网 自学内容网

代码随想录算法训练营第九天 |LeetCode151.翻转字符串里的单词 卡码网:55.右旋转字符串

代码随想录算法训练营

Day 9 代码随想录算法训练营第九天 |LeetCode151.翻转字符串里的单词 卡码网:55.右旋转字符串



前言

LeetCode151.翻转字符串里的单词

讲解文档

卡码网:55.右旋转字符串

讲解文档


一、LeetCode151.翻转字符串里的单词

1.题目链接

LeetCode151.翻转字符串里的单词

2.思路

(1)如何反转
先反转整个字符串,再逐个反转单词
如何反转单词:双指针
i作为单词起点,j作为单词终点,如果j遇到空格或j为n(到末尾),则说明i与j夹住一个单词,反转
(2)处理空格:双指针
(这里按照空间复杂度O(1)做的)
快指针fast指向要获取的元素,慢指针slow指向元素的新位置
1)字符串首的空格:如果为空格则fast++,直到fast遇到第一个不是空格的字符为止
2)去除单词间的多余空格:
连续空格则移动fast
不是连续空格则将s[fast]放进s[slow],slow和fast同时移动
3)去掉末尾空格
检查s[0]到s[slow-1]字符串末尾有无空格,若有,则左移slow
4)修改字符串大小

3.题解

class Solution {
public:
    void reverse(string& s, int i, int j) {
        while (i < j) {
            swap(s[i], s[j]);
            i++;
            j--;
        }
    }
    string cut(string s) {
        int slow = 0;
        int fast = 0;
        int n = s.size();
        while (fast < n && s[fast] == ' ') {
            fast++;
        }
        while (slow < n && fast < n) {
            if (fast > 0 && s[fast] == ' ' && s[fast - 1] == ' ') {
                fast++;
            } else {
                s[slow] = s[fast];
                slow++;
                fast++;
            }
        }

        while (s[slow - 1] == ' ' && slow > 0) {
            slow--;
        }
        s.resize(slow);
        return s;
    }
    string reverseWords(string s) {
        s = cut(s);
        int n = s.size();
        reverse(s, 0, n - 1);
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && s[j] != ' ') {
                j++;
            }
            reverse(s, i, j - 1);
            i = j + 1;
        }
        return s;
    }
};

二、卡码网:55.右旋转字符串

1.题目链接

卡码网:55.右旋转字符串

2.思路

先整体反转,再将n-k和k各自反转
示意图示意图

也可以先反转局部,再反转整体

3.题解

先整体后局部

#include<bits/stdc++.h>
using namespace std;
void reverse(string &s,int l,int r)
{
    while(l<r)
    {
        swap(s[l],s[r]);
        l++;
        r--;
    }
}
int main()
{
    int k ;
    string s;
    cin>>k;
    cin>>s;
    int n=s.size();
    reverse(s,0,n-1);
    reverse(s,0,k-1);
    reverse(s,k,n-1);
    cout<<s;
    return 0;
}

先局部后整体

#include<bits/stdc++.h>
using namespace std;
void reverse(string &s,int l,int r)
{
    while(l<r)
    {
        swap(s[l],s[r]);
        l++;
        r--;
    }
}
int main()
{
    int k ;
    string s;
    cin>>k;
    cin>>s;
    int n=s.size();
    reverse(s,0,n-k-1);
    reverse(s,n-k,n-1);
    reverse(s,0,n-1);
    cout<<s;
    return 0;
}

字符串总结

1、字符串基础:字符串可以用字符数组或string类实现,一般用string类,因为相关接口更完备
2、双指针
(1)双指针实现反转字符
(2)填充问题:先给字符串扩容,再从后向前操作(例如:替换数字为number)
(3)双指针移除元素
快指针指向要获取的元素,慢指针指向元素的新位置
3、反转字符串:设计反转策略,可以先用纸笔写出反转的情况
先反转整体,再反转局部:LeetCode151.翻转字符串里的单词 卡码网:55.右旋转字符串
先反转局部,再反转整体:卡码网:55.右旋转字符串


原文地址:https://blog.csdn.net/2301_79647020/article/details/140583303

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!