【C++】string OJ练习（一)

我们来看几道string相关的OJ，来练习一下string的使用。

1. 仅仅反转字母

题目链接: link

我们一起来看一下题：

思路分析

我们来分析一下题目，这道题让我们干什么呢？

给我们一个字符串，该字符串中有英文字符也有非英文字符，要求我们去反转字符串中的所有英文字母，非英文字母的字符位置不动。

那是不是很简单啊，左右两个指针分别指向首尾，然后依次向中间移动寻找英文字母，找到后停下来，然后两个指针指向的英文字母进行交换，接着继续向中间移动，两者相遇结束。（是不是跟一趟快排的逻辑有点像啊）

代码实现

class Solution {
public:
    bool isletter(char x)
    {
        if((x>='a'&&x<='z')||(x>='A'&&x<='Z'))
            return true;
        return false;
    }
    string reverseOnlyLetters(string s) {
        int begin=0;
        int end=s.size()-1;
        while(begin<end)
        {
            while((begin<end)&&!isletter(s[begin]))
                begin++;
            while((begin<end)&&!isletter(s[end]))
                end--;
            swap(s[begin],s[end]);
            begin++;  
            end--;
        }
        return s;
    }
};

代码呢也比较简单，相信大家都能看懂，就不过多解释了。

2. 字符串中的第一个唯一字符

链接: link

题目分析

题目让我们找出字符串中第一个不重复的字符，那我们最容易想到的就是暴力求解，从头到尾遍历字符串，依次拿每一个字符与其他字符进行比较，如果没有与之重复的则当前字符就是要找的字符，返回其下标，有重复的就不是，继续看下一个，最终一个也没找到就返回-1。

当然这样的时间复杂度就是O(N^2)

那有没有好一点的方法呢？

🆗，其实呢我们可以考虑用计数排序的思想去搞：

题目说了只包含小写字母

所以字符串中字符的范围就是【a,z】，那我们就可以创建一个大小为26的整型数组，然后用一个相对映射去统计每个字母的出现次数，a就映射到下标为0的位置，b就映射到下标为1的位置，依次类推。

那怎么让这些字母映射到对应的位置呢？

减去’a’得到的值是不是就是它们映射的位置啊，然后遍历字符串，每个字母映射的值是几，就让下标为几的元素++，初值全为0，这样遍历过后每个字母出现的次数就统计出来了。（下标0的元素的值就是a出现的次数，1位置就是b出现的次数…）

但是现在有一个问题，那就是出现一次的字母可能不止一个，我们怎么判断那个是第一个只出现一次的字母呢？

🆗，这里我们不要去遍历统计次数的数组，还是从前往后去遍历字符串，然后看哪个字母的次数是1，第一个是1的就是第一个只出现一次的字母。

代码实现

class Solution {
public:
    int firstUniqChar(string s) {
        int count[26]={0};
        for(auto e:s)
        {
            count[e-'a']++;
        }
        for(int i=0;i<s.size();i++)
        {
            if(count[s[i]-'a']==1)
                return i;
        }
        return -1;
    }
};

大家结合上面的分析再看一看代码，相信就能理解了。

3. 《剑指offer》——替换空格

接下来我们来看一道《剑指offer》于string相关的题目——替换空格

解法一：寻找替换

思路分析

大家思考一下这道题可以怎么解？

是不是可以考虑用find+replace搞啊。

用find找的字符串中的所有空格，然后用replace将其替换成%20不就行了嘛。

代码实现

我们来实现一下代码：

class Solution {
public:
    string replaceSpace(string s) {
        size_t pos=s.find(' ');
        while(pos!=string::npos)//find找不到返回npos
        {
            s.replace(pos,1,"%20");
            pos=s.find(' ');
        }
        return s;
    }
};

🆗，就通过了。

优化

那大家看一下，我们刚才上面那样写好吗，或者说有没有可以优化的地方？

是可以做一些优化的。

来看find是不是可以指定开始查找的位置啊，如果我们不传pos的话它默认是从起始位置开始查找的，但是这里我们要查找所有的空格，并且对它们进行替换，那第一个空格被替换之后，我们往后查找第二个的时候，还有必要从头开始找吗，是不是就可以从替换之后的尾部开始往后找啊，这样效率是不是就高了一点会。

所以我们可以这样改进一下：

那大家再想，还可以再优化吗？

其实还有一个地方可以做一些优化，大家想，我们这里replace是把空格替换成%20，这样使用的空间是不是多了，那replace在替换的过程中是不是有可能空间不够进行扩容啊，那有没有什么办法可以避免replace的过程中可能会去频繁的扩容（扩容是有消耗的，特别是异地扩）。

🆗，我们是不是可以计算出需要多少空间，然后提前把空间开好啊。那大家说，这里应该用什么？

resize还是 reserve，reserve可以改变容量帮我们开空间，而resize除了开空间还可以初始化，但是这里有必要对开好的空间进行初始化吗？

是不是没必要啊，所以我们用reserve就行了。

那需要多少空间呢，空格替换成%20，所以每个空格多两个空间，那我们可以统计一下空格数，然后提前把空间开好

写一下代码：

class Solution {
public:
    string replaceSpace(string s) {
        int count=0;
        for(auto e:s)
        {
            if(e==' ')
                count++;
        }
        s.reserve(s.size()+2*count);
        size_t pos=s.find(' ');
        while(pos!=string::npos)
        {
            s.replace(pos,1,"%20");
            pos=s.find(' ',pos+3);
        }
        return s;
    }
};

解法二：空间换时间

那除了上面那种方法，其实还可以考虑另一种思路：

思路分析

我们可以创建一个新的string对象，然后遍历原串，不是空格，就直接+=到新串，是空格，就把"%20"+=到新串。

这样的好处是不需要像上面那样挪动数据了，只不过多开了一点空间。

代码实现

这个代码就非常简单：

class Solution {
public:
    string replaceSpace(string s) {
        string news;
        for(auto e:s)
        {
            if(e!=' ')
                news+=e;
            else
                news+="%20";
        }
        return news;
    }
};

当然这种方法在+=的过程中也有可能会扩容，所以我们也可以把reserve那一步加上。