代码随想录算法训练营第七天｜LeetCode 344. 反转字符串、541. 反转字符串 II

今天是开始新的篇章：字符串。

题目链接：344. 反转字符串

状态：一次性AC，第一题还是比较容易的。有前面反转链表的双指针思路的记忆，于是就尝试了一下。结果一次就成功了，不错不错～

看到题目时第一想法：双指针，left从头开始向后遍历，同时right从尾开始向前遍历，然后每次就两者交换元素直到left >= right的时候就不交换了。

344 反转字符串流程

具体的完整代码如下：

class Solution { // Java
    public void reverseString(char[] s) {
        // two pointers
        int left = 0;
        int right = s.length - 1;

        while(left < right){
            // swap
            char temp = 'a';
            temp = s[left];
            s[left] = s[right];
            s[right] = temp;

            left ++;
            right --;
        }
        
    }
}

时间复杂度：O(n)。因为字符串内的每个字符都会被访问一次。
空间复杂度：O(1)。因为只用了两个指针和一个临时变量来存储字符。

看到题目时第一想法：这道题应该是要用到上一题的交换方法。只不过呢，需要额外对遍历上做一些复杂的控制。根据题目的描述，很容易想到的是一个for循环遍历整个字符串，然后弄个count来计数，到了k就反转...但是也不难发现这种方法判断多，不仅麻烦还容易出错。于是进行画图思考🤔。思考过后发现他其实是每有2k个字符，就对前k个进行反转，最后不足2k的单独处理。于是我就想到了如下这种遍历方式：引入一个n来帮助控制i的位置。

        int i = 0, n = 0; // i = n * k
        for(i = n * k; i <= n * k + k - 1; i ++){
            // reverse 
            // ...
            // ...
            n = n + 2;
        }

这种做法确实能保证每次遍历的结果都是需要反转的部分，例如0 - (k-1), 2k - (3k-1), 4k - (5k-1) ... 但是每一小段反转之后还要拼接成最终的完整字符串，也是个很麻烦的。于是就看了解析，解析中给到的循环遍历的方式和反转的方式都非常的妙！
当循环遍历的时候，我们还是遍历整个字符串，但是由传统思维的 i++ 变成了 i+=2k，这样一来，每次就是对2k范围内对字符进行遍历了。然后reverse方法的参数也不同，不仅仅是传入一个char数组，同时还要传入反转的范围，即下标为i到下标为j的部分反转。由此，此题就引刃而解了，完整代码如下：

class Solution { // Java
    public String reverseStr(String s, int k) {
        char[] charAry = s.toCharArray();
        // Reverse the first k characters of every 2k characters
        for(int x = 0; x < charAry.length; x = x + 2 * k){
            // If the remaining characters are less than 2k, 
            // but greater than or equal to k, reverse the first k characters
            if(x + k <= charAry.length){
                reverse(charAry, x, x + k - 1);
                continue;
            }
            // If there are less than k characters left, reverse all the remaining characters.
            reverse(charAry, x, charAry.length - 1);
        }
        return new String(charAry);
    }

    public void reverse(char[] charArray, int m, int n){ 
        
        // reverse the charArray with the index from m to n

        if(charArray.length - 1 <= 0 || m == n) return;
        
        int i = Math.min(m,n);
        int j = Math.max(m,n);

        // char[] charArray = str.toCharArray();
        while(i < j){
            // swap
            char temp = 'a';
            temp = charArray[i];
            charArray[i] = charArray[j];
            charArray[j] = temp;

            i ++;
            j --;
        }
        

    }
}

时间复杂度：O(n)
空间复杂度：O(n)

代码随想录算法训练营第七天｜LeetCode 344. 反转字符串、541. 反转字符串 II