郑州建设工程信息网站,上海外贸网站建设找哪家,手机网页制作图片,济南住建网站day8:剩下的两题 151.翻转字符串里的单词卡码网#xff1a;55.右旋转字符串 151.翻转字符串里的单词 题目链接 状态#xff1a;不ok 文档#xff1a;programmercarl.com 思路#xff1a; 我们将整个字符串都反转过来#xff0c;那么单词的顺序指定是倒序了#xff0c;只不… day8:剩下的两题 151.翻转字符串里的单词卡码网55.右旋转字符串 151.翻转字符串里的单词 题目链接 状态不ok 文档programmercarl.com 思路 我们将整个字符串都反转过来那么单词的顺序指定是倒序了只不过单词本身也倒序了那么再把单词反转一下单词不就正过来了。
所以解题思路如下 1、移除多余空格 2、将整个字符串反转 3、将每个单词反转 整体反转局部反转
举个例子源字符串为 the sky is blue 移除多余空格 : “the sky is blue” 字符串反转“eulb si yks eht” 单词反转“blue is sky the”
首先在移除空格的操作上思路是遇到空格就去除没遇到空格的赋值给新的下标。这样一来和上面的替换思想类似所以还是使用双指针操作。
代码 第一步中 去除空格有两种方法 一种是分情况移除多余空格 – 前导空格、中间空格、尾随空格。 一种是自己手动加空格。
class Solution {
public:// 1.移除多余空格void removeExtraspace(string s){int fast 0,slow 0;//移除前导空格while(s.size() 0 fasts.size() s[fast] ){fast;}//用快指针移除中间重复空格for(;fasts.size();fast){if(fast-1 0 s[fast-1] s[fast] s[fast] ){//有两个空格不进行快慢赋值操作fast即可continue;}else{//快指针的值赋给慢指针s[slow] s[fast];}}//此时进行完slow就是新的数组的长度//移除尾随空格if(slow-1 0 s[slow-1] ){s.resize(slow-1);}else{s.resize(slow);}}//方法二同样是快慢指针移除多余空格但是是参考27题void removeExtraspace(string s){//慢指针slow指向新数组的下标快指针i一个个遍历元素int slow 0;for(int i0;is.size();i){//如果没遇到空格就进行以下操作如果遇到了就跳过iif(s[i] ! ){//此时s[i]是单词的第一个字母//既然空格都被处理掉了那么就得自己手动加空格//slow!0的时候说明不是第一个单词这个时候可以加空格if(slow ! 0){s[slow] ;}//把单词补上while(is.size() s[i] ! ){s[slow] s[i];}}}s.resize(slow);}第二步将整个字符串进行反转
//2.将整个字符串反转void reverseString(string s,int start,int end){for(int i start,j end;i j;i,j--){swap(s[i],s[j]);}}第三步单词反转
string reverseWords(string s) {//移除多余的空格前导、中间重复、尾随空格removeExtraspace(s);//2.反转整个字符串reverseString(s,0,s.size()-1);//3.将每个单词进行反转//首先确定哪些是一个单词里的根据空格来判断int start 0; //开始第一个字母一定是0的位置上for(int i 0;is.size();i){//01234567//blue sky//s 3 s 7 s:start//i到最后一个位置上 或者 i是空格 都可以判断 一个单词结束了if(i s.size() || s[i] ){//要判断 is.size() 而不是is.size()-1//因为要顾及下面的i-1如果is.size()-1的话那么i-1就是倒数第二个位置//照顾不到最后一个位置上的元素reverseString(s,start,i-1);start i1; //更新一个单词的开始位置}}return s;}注意 reverseString函数在实现的时候是左闭右闭的反转。
卡码网55.右旋转字符串 题目链接 状态ok 文档programmercarl.com 思路 依旧使用上一题的思路整体反转局部反转 但是局部反转是分两段进行的。 代码
#includeiostream
using namespace std;
#includestring
#includealgorithmint main()
{int k;string s;cink;cins;//int len s.size(); //获取长度//先整体反转再局部反转局部是分两段//1.整体反转reverse(s.begin(),s.end());//2.局部是分两段去反转 k 和 n-kreverse(s.begin(),s.begin()k); //kreverse(s.begin()k,s.end()); //n-kcoutsendl;return 0;}
