【LeetCode刷题日记】：344，541-字符串反转字符串反转技巧：双指针原地交换法

北极的代码

发布于 2026-04-22 13:58:01

720

前言：我们经过一段时间的学习，已经学习完了哈希表相关章节的算法，关于这些题目的思维导图之后会单独出一个专栏进行记录，下面我们继续学习字符串相关的算法题。

题目背景:LeetCode344

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。示例 1：输入：["h","e","l","l","o"] 输出：["o","l","l","e","h"] 示例 2：输入：["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]

题目答案：

class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while (l < r) {
            s[l] ^= s[r];  //构造 a ^ b 的结果，并放在 a 中
            s[r] ^= s[l];  //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
            s[l] ^= s[r];  //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换
            l++;
            r--;
        }
    }
}

// 第二种方法用temp来交换数值更多人容易理解些
class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while(l < r){
            char temp = s[l];
            s[l] = s[r];
            s[r] = temp;
            l++;
            r--;
        }
    }
}

题目解析：

对于这种题目，我们看到是很开心的，甚至是有点轻视的感觉，因为直接用直接使用封装好的库函数 reverse，调一下直接完事了，每一门编程语言都有这样的库函数。如果这么做题的话，这样大家不会清楚反转字符串的实现原理了。

但是也不是说库函数就不能用，是要分场景的。

如果在现场面试中，我们什么时候使用库函数，什么时候不要用库函数呢？

如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数。 毕竟面试官一定不是考察你对库函数的熟悉程度，如果使用python和java 的同学更需要注意这一点，因为python、java提供的库函数十分丰富。 如果库函数仅仅是解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数。 建议大家平时在leetcode上练习算法的时候本着这样的原则去练习，这样才有助于我们对算法的理解。不要沉迷于使用库函数一行代码解决题目之类的技巧，不是说这些技巧不好，而是说这些技巧可以用来娱乐一下。真正自己写的时候，要保证理解可以实现是相应的功能。

具体代码解析：

大家应该还记得，我们已经讲过了206.反转链表。在反转链表中，使用了双指针的方法。那么反转字符串依然是使用双指针的方法，只不过对于字符串的反转，其实要比链表简单一些。因为字符串也是一种数组，所以元素在内存中是连续分布，这就决定了反转链表和反转字符串方式上还是有所差异的。对于字符串，我们定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素。

如图：

题目背景：LeetCode541

给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。如果剩余字符少于 k 个，则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。示例: 输入: s = "abcdefg", k = 2 输出: "bacdfeg"

题目答案：

//解法一
class Solution {
    public String reverseStr(String s, int k) {
        StringBuffer res = new StringBuffer();
        int length = s.length();
        int start = 0;
        while (start < length) {
            // 找到k处和2k处
            StringBuffer temp = new StringBuffer();
            // 与length进行判断，如果大于length了，那就将其置为length
            int firstK = (start + k > length) ? length : start + k;
            int secondK = (start + (2 * k) > length) ? length : start + (2 * k);

            //无论start所处位置，至少会反转一次
            temp.append(s.substring(start, firstK));
            res.append(temp.reverse());

            // 如果firstK到secondK之间有元素，这些元素直接放入res里即可。
            if (firstK < secondK) { //此时剩余长度一定大于k。
                res.append(s.substring(firstK, secondK));
            }
            start += (2 * k);
        }
        return res.toString();
    }
}

//解法二（似乎更容易理解点）
//题目的意思其实概括为 每隔2k个反转前k个，尾数不够k个时候全部反转
class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        for(int i = 0; i < ch.length; i += 2 * k){
            int start = i;
            //这里是判断尾数够不够k个来取决end指针的位置
            int end = Math.min(ch.length - 1, start + k - 1);
            //用异或运算反转 
            while(start < end){
                ch[start] ^= ch[end];
                ch[end] ^= ch[start];
                ch[start] ^= ch[end];
                start++;
                end--;
            }
        }
        return new String(ch);
    }
}


// 解法二还可以用temp来交换数值，会的人更多些
class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        for(int i = 0;i < ch.length;i += 2 * k){
            int start = i;
            // 判断尾数够不够k个来取决end指针的位置
            int end = Math.min(ch.length - 1,start + k - 1);
            while(start < end){
                
                char temp = ch[start];
                ch[start] = ch[end];
                ch[end] = temp;

                start++;
                end--;
            }
        }
        return new String(ch);
    }
}

// 解法3
class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        // 1. 每隔 2k 个字符的前 k 个字符进行反转
        for (int i = 0; i< ch.length; i += 2 * k) {
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= ch.length) {
                reverse(ch, i, i + k -1);
                continue;
            }
            // 3. 剩余字符少于 k 个，则将剩余字符全部反转
            reverse(ch, i, ch.length - 1);
        }
        return  new String(ch);

    }
    // 定义翻转函数
    public void reverse(char[] ch, int i, int j) {
    for (; i < j; i++, j--) {
        char temp  = ch[i];
        ch[i] = ch[j];
        ch[j] = temp;
    }

    }
}

题目解析：

当需要固定规律一段一段去处理字符串的时候，要想想在for循环的表达式上做做文章，牢记这个，就是本题的思路。 首先我们要将字符串变成字符数组，因为在java中，字符串是不可变的。 char[] ch = s.toCharArray(); 然后，我们要在for循环中规定每次i移动的范围，也就是一段一段的移动，我们定义i+=2*k，即每次都移动2k步，也就是题目的条件。这样就已经实现了第一步的范围。然后我们具体把逻辑放在，移动2k之后反转前k个，关于这个操作，跟我们上面那题逻辑一样，就是用双指针来交换对应的位置来实现反转，这里就不细说。之后的逻辑就是题目最后说的条件了： 如果剩余字符少于 k 个，则将剩余字符全部反转。 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。 关于这两个条件，看起来很麻烦，不太好处理，其实也就是看最后的指针位置。我们这里进行的操作是对数组的长度ch.length和i+k-1取小值。至于为什么要这样，首先i+k-1代表每次指针移动完之后end的位置，第一次移动，end指针的位置就是k-1，因为数组是从0索引开始的，要减去1，然后第二次，2k+k-1，也就是第二次的end指针的位置，至于为什么要跟数组的长度进行比较，因为是为了防止越界，这样一来，如果越界了，自动把end指针放在数组的最后一个元素。因为我们的反转区间也就是【i，end】，所以也就实现了小于k遍历全部。

结语：如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的帮助！