小小码民刷算法——反转字符串

模板

经过一个下午的刷题时光,我发现力扣中字符串有关的题,可分为有空格和无空格的俩种类型,模板一记,直接开挂,秋名山的赛道,跑的飞起!!!

1、如果有前后置空格,那么必须判断临时字符串非空才能输出,否则会输出空串
`对应的代码如下:

void test01()
{
	s += " "; //这里在最后一个字符位置加上空格,这样最后一个字符串就不会遗漏
	string temp = "";  //临时字符串
	vector<string> res; //存放字符串的数组
	for (char ch : s)  //遍历字符句子
	{
		if (ch == ' ') //遇到空格
		{
			if (!temp.empty()) //临时字符串非空
			{
				res.push_back(temp);
				temp.clear();  //清空临时字符串
			}
		}
		else
			temp += ch;
	}
}

2、没有前后置的空格不需要判断空串

void text02()
{
	s += " ";
	string temp = "";
	vector<string> res;
	for (char ch : s)
	{
		if (ch == ' ')
		{
			res.push_back(temp);
			temp.clear();
		}
		else
			temp += ch;
	}
}

例题

反转字符串
直接用双指针来解

int n = s.size();
for (int left = 0, right = n - 1; left < right; ++left, --right) {
    swap(s[left], s[right]);//交换函数
}

反转字符串的前缀
需要判断是否为空

class Solution {
public:
    string reversePrefix(string word, char ch) {
    for(int i = 0; word[i] != ''; ++i) {
        if(word[i] == ch) {
            reverse(begin(word), begin(word) + i + 1);//反转字符串
            break;
        }
    }

    return word;
}
};

反转单词

class Solution {
public:
    string reverseWords(string s) {
        string ans;
        //i,j用于确定跳过首尾空格的下标范围
        int i=0,j=s.size()-1;
        //跳过s的首部空格
        while(i<=j&&s[i]==' ') i++;
        //跳过s的尾部空格
        while(i<=j&&s[j]==' ') j--;

        //k,w为用于确定每个单词范围的双指针,从非空格尾部开始往前扫描,i为前边界,j为后边界
        int k=j,w=j;
        //当输入全为空格时,跳过首尾空格后i>j
        while(i<=j&&k>=i){
            //k往前扫描直到遇到空格停下,或者超出i前边界停下
            while(k>=i&&s[k]!=' ') k--;
            //k+1到w为一个单词的范围,将每个字符按序加入string ans即可
            for(int idx=k+1;idx<=w;idx++) ans+=s[idx];
            //没超出前边界i时,k停下遇到的肯定是空格,可能是一个或多个,跳过
            if(k>=i&&s[k]==' '){
                while(k>=i&&s[k]==' ') k--;
                //跳过一个或多个空格后,ans加一个必要的空格
                ans+=' ';
            }
            //w跳到k位置继续扫描下一个单词范围
            w=k;
        }
        return ans;
    }
};

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>