day08 - 字符串 part01-526互联

day08 - 字符串 part01

力扣344. 反转字符串

超级简单，双指针，swap

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

}

力扣541. 反转字符串II

重点在于，for循环中， i += (2 * k)； 所以当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。

代码

string reverseStr(string s, int k) {
    for (int i = 0; i < s.size(); i += 2*k)
    {
        if (i + k <= s.size())
        {
            reverse(s.begin() + i, s.begin() + i + k);
        }
        else
        {
            reverse(s.begin() + i, s.end());
        }
    }
    return s;
}

剑指offer05. 替换空格

思路：直接新建字符串进行替换是可行的，但是如果空间想压缩，就要扩容现在的字符串，然后，从后往前进行遍历。因为从前往后会覆盖掉原字符串。

代码

string replaceSpace(string s) {
    int count = 0;
    for (char c : s)
    {
        if (c == ' ')
        {
            count++;
        }
    }
    int oldSize = s.size();
    s.resize(s.size() + 2 * count);


    for (int i = s.size() - 1, j = oldSize - 1; j < i; i--, j--)
    {
        if (s[j] == ' ')
        {
            s[i] = '0';
            s[i - 1] = '2';
            s[i - 2] = '%';
            i -= 2;
        }
        else
        {
            s[i] = s[j];
        }
    }
    return s;
}

力扣151. 翻转字符串里的单词

思路：先去掉多余空格，然后把整体全部翻转，然后翻转每个单词

第一步，去掉多余空格

void removeSpace(string& s)
{
    //快慢指针法，同移除元素
    int slow = 0;
    for (int i = 0; i < s.size(); i++)
    {
        //如果当前不是空格，那么就是单词咯，就要输出到下一个空格为止
        if (s[i] != ' ')
        {
            //如果慢指针不是0，就说明不是开头第一个，就要输出一个空格分隔单词
            if (slow != 0)
            {
                s[slow++] = ' ';
            }
            //然后循环输出整个单词
            while (i < s.size() && s[i] != ' ')
            {
                s[slow++] = s[i++];
            }
        }
    }
    //重新调整大小，去掉多余的空间
    s.resize(slow);
}

第二部，整体翻转

直接

reverse(s.begin(), s.end());

第三部，翻转每个单词

//设置每个单词的起始位置
int start = 0;
for (int i = 0; i <= s.size(); i++)
{	
    //如果i到了末尾，或者遇见了空格，此时就应该翻转整个单词
    if (i == s.size() || s[i] == ' ')
    {
        //翻转从start开始，到i结束。注意翻转时候是左闭右开区间，因此主要i最后要==s.size()的，因此i一直比索引大1
        reverse(s.begin() + start, s.begin() + i);
        //重置，因为i比索引大1， 因此i指向空格，start继续指向空格的下一个，就是单词开始的位置
        start = i + 1;
    }
}

剑指Offer58-II.左旋转字符串

思路：1申请额外空间，先赋值k到最后，再加上0到k

思路：2 不需额外空间，先全部翻转，再翻转前面k个

总结：当需要翻转部分字符串的时候，应该想到，两次翻转的方法