反转字符串

LeetCode 344.反转字符串

问题

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

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

双指针

算法思想

  • 将 left 指向字符数组首元素，right 指向字符数组尾元素。

  • 当 left < right：

    • 交换 s[left] 和 s[right]；
    • left 指针右移一位，即 left = left + 1；
    • right 指针左移一位，即 right = right - 1。

  • 当 left >= right，反转结束，返回字符数组即可

1
2
3
4
5
6
7
8
public void reverseString(char[] s) {
    int n = s.length;
    for (int left = 0, right = n - 1; left < right; ++left, --right) {
        char tmp = s[left];
        s[left] = s[right];
        s[right] = tmp;
    }
}

反转字符串 Ⅱ

LeetCode 541.反转字符串 II

问题

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

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