随想录Day8|344. 反转字符串、541. 反转字符串Ⅱ、LCR 122. 路径加密、151. 反转字符串里的单词、LCR182. 动态口令

题目越来越长了……

344. 反转字符串

文章&视频讲解

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

1 <= s.length <= 105
s[i] 都是 ASCII 码表中的可打印字符

第一想法

（愣了很久没想法）原地修改？那就是两面包抄的两两交换，我似乎明白了，用局部变量每次存两个，就不会给数组开额外空间。

如果长度为len，每次交换s[i]和s[len - 1 - i]，需要确定i的变化范围。如果len是偶数比如4，则最后i需要在1，所以是i < 2；如果len是奇数比如5，则最后i需要在1，也是i < 2，综上应该是i < len / 2。

用时12min~

void reverseString(vector<char> &s)
{
    int len = s.size();
    char left, right;
    for (int i = 0; i < len / 2; i++)
    {
        left = s[i];
        right = s[len - 1 - i];
        s[i] = right;
        s[len - 1 - i] = left;
    }
}

541. 反转字符串Ⅱ

文章&视频讲解

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

提示：

1 <= s.length <= 104
s 仅由小写英文组成
1 <= k <= 104

第一想法

和上面的整体思路差不多，但是需要多注意一些边界条件的细节。用i来代表这次翻转的起始点，每次增加2k步，翻转(s.begin() + i, s.begin() + i + k)区间内的元素。

用时13min~

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

LCR 122. 路径加密

原本剑指offer 05. 替换空格，文章讲解也是对原题的。

文章讲解

假定一段路径记作字符串 path，其中以 "." 作为分隔符。现需将路径加密，加密方法为将 path 中的分隔符替换为空格 " "，请返回加密后的字符串。

0 <= path.length <= 10000

第一想法

直接扫描替换就好了……啊……最简单的一集？

好吧！原题是需要把空格替换成%20，所以涉及到空间分配！我是说呢……

用时3min~

string pathEncryption(string path)
{
    int len = path.length();
    for (int i = 0; i < len; i++)
    {
        if (path[i] == '.')
            path[i] = ' ';
    }
    return path;
}

151. 反转字符串里的单词

文章&视频讲解

给你一个字符串 s ，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词

第一想法

需要注意很多细节啊，先写着吧……首先就是多个空格的情况需要跳过余下的，然后每次以单词为单位翻转，是否需要事先统计单词个数？原地如何实现，如果首尾单词不一样长，中间的部分如何放置？

看完随想录题解的想法

没错我偷看思路去了，不过我只看了最核心的那一句！先移除多余空格，再翻转整个数组，最后翻转每个单词。

移除多余空格的时候如果使用erase()，则本身操作的复杂度\(O(n)\)和字符串长度\(n\)，会导致最终整体复杂度\(O(n^2)\)，所以采用双指针法，一个指向原字符串正在处理的位置，一个指向新字符串要写入的位置，这也是原地的，因为新字符串的长度小于等于原来的，所以相当于把后面的内容搬运到前面来，原地也不会造成数据之间的干扰。

在翻转单词的时候，读到这个单词后面的空格则翻转刚刚的单词，通过每遇到一个字母就wordlen++记录下来的就是刚刚这个单词的长度，比如字符串为hello world时候，第一次遇到空格时wordlen = 5，此时也有i = 5，翻转范围应该是[0, 5)，所以最终应该是reverse(s.begin() + i - wordlen, s.begin() + i)。

初代目答案

耗时73min~

string reverseWords(string s)
{
    // 先除去多余的空格
    // fast指向原字符串正在处理的，slow指向搬运目的地
    int fast = 0, slow = 0;
    // 处理多个连续空格，遇到第一个时设为true，之后看见true则跳过剩下空格
    bool spaceflag = false;
    int len = s.length();

    // 去掉前导空格
    while (s[fast] == ' ')
        fast++;

    while (fast < len)
    {
        if (s[fast] == ' ')
        {
            // 如果flag是true，则跳过
            if (spaceflag)
            {
                fast++;
                continue;
            }
            else // 可能是正常空格，可能是一串空格的第一个
            {
                spaceflag = true;
                s[slow++] = ' '; // 也就是s[slow] = s[fast]; slow++;
                fast++;
            }
        }
        else // 正常字符，搬运，并且把flag重置
        {
            s[slow++] = s[fast++];
            spaceflag = false;
        }
    }

    // 去掉尾随空格
    while (s[slow - 1] == ' ')
        slow--;
    s.resize(slow);

    // 把整个字符串都翻转
    reverse(s.begin(), s.end());

    // 原地翻转每个单词
    int i = 0;
    int wordlen = 0;
    while (i < slow) // 注意slow才是新的len
    {
        if (s[i] == ' ') // 翻转上一个单词并重置wordlen
        {
            reverse(s.begin() + i - wordlen, s.begin() + i);
            wordlen = 0;
        }
        else
            wordlen++;
        i++;
    }
    // 翻转最后一个单词
    reverse(s.end() - wordlen, s.end());

    return s;
}

学习题解更简洁的答案

可以把第一部分（上面10~41行）替换为这样。

for (; fast < len; fast++)
{
    if (s[fast] != ' ') // 有效字母
    {
        // 不是第一个单词，则前面加空格
        if (slow != 0)
            s[slow++] = ' ';
        // 然后一次处理完一个单词直到遇到空格
        while (fast < len && s[fast] != ' ')
            s[slow++] = s[fast++];
    }
}
s.resize(slow);

LCR182. 动态口令

文章讲解

某公司门禁密码使用动态口令技术。初始密码为字符串 password，密码更新均遵循以下步骤：

设定一个正整数目标值 target
将 password 前 target 个字符按原顺序移动至字符串末尾

请返回更新后的密码字符串。

1 <= target < password.length <= 10000

第一想法

先把前target存起来，把后面的往前移？但是如果最坏的情况，target = password.length - 1，则空间复杂度过高。

可以采取上一题那种局部反转+整体反转的思路！如果分别反转前target个和后半段，再整体反转字符串即可。

用时8min~

string dynamicPassword(string password, int target)
{
    reverse(password.begin(), password.begin() + target);
    reverse(password.begin() + target, password.end());
    reverse(password.begin(), password.end());
    return password;
}

主要还是这个思路有点难想到，实现起来只需要三行！