在对字符串进行反转操作时，要使时间复杂度为O(n)，那么就需要在本串上操作，也就是双指针法。

模板

使用此模板后，只需要在反转的区间做做文章。

  1. public char[] reverse(char[] array, int left, int right) {
  2.     for (; left < right; left++, right--) {
  3.         char temp = array[left];
  4.         array[left] = array[right];
  5.         array[right] = temp;
  6.     }
  7.     return array;
  8. }

541.反转字符串 II

其实在遍历字符串的过程中，只要让 i += (2 k)，i 每次移动 2 k 就可以了，然后判断是否需要有反转的区间。

  1. public String reverseStr(String s, int k) {
  2.     char[] array = s.toCharArray();
  3.     int i = 0;
  4.     for (; i < array.length; i += 2 * k) {
  5.         if (i + k <= array.length) {
  6.             array = reverse(array, i, i + k - 1);
  7.             continue;
  8.         }
  9.         array = reverse(array, i, array.length - 1);
  10.     }
  13.     return new String(array);
  14. }
  16. public char[] reverse(char[] array, int left, int right) {
  17.     for (; left < right; left++, right--) {
  18.         char temp = array[left];
  19.         array[left] = array[right];
  20.         array[right] = temp;
  21.     }
  22.     return array;
  23. }

151.翻转字符串里的单词

不要使用辅助空间，空间复杂度要求为O(1)。
不能使用辅助空间之后，那么只能在原字符串上下功夫了。
想一下，我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。
所以解题思路如下：

  • 移除多余空格
  • 将整个字符串反转

  • 将每个单词反转 ```java class Solution { /**

    1.   * 水题做法
    2.   *
    3.   * @param s
    4.   * @return
    5.   */

    /* public String reverseWords(String s) {

    1.   String[] strings = s.trim().split(" ");
    2.   StringBuffer stringBuffer = new StringBuffer();
    3.   for (int k = strings.length - 1; k >= 0; k--) {
    4.       if (strings[k] != "") {
    5.           if (k > 0) {
    6.               stringBuffer.append(strings[k]).append(" ");
    7.           } else {
    8.               stringBuffer.append(strings[k]);
    9.           }
    10.       }
    11.   }
    12.   return String.valueOf(stringBuffer);

    }

    1.   */

    public String reverseWords(String s) {

    1.   // 去除首尾空格
    2.   StringBuilder sb = removeSpace(s);
    3.   // 反转所有字符
    4.   reverseString(sb, 0, sb.length() - 1);
    5.   // 反转其中单词
    6.   reverseEachWord(sb);
    7.   return String.valueOf(sb);

    }

    /**

    1.   * 去掉空格
    2.   *
    3.   * @param s
    4.   * @return
    5.   */

    private StringBuilder removeSpace(String s) {

    1.   StringBuilder sb = new StringBuilder();
    2.   int start = 0, end = s.length() - 1;
    3.   // 去掉首尾空格
    4.   while (s.charAt(start) == ' ') start++;
    5.   while (s.charAt(end) == ' ') end--;
    7.   while (start <= end) {
    8.       // 不存在空格追加进去
    9.       char c = s.charAt(start);
    10.       if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
    11.           sb.append(c);
    12.       }
    13.       start++;
    14.   }
    15.   return sb;

    }

    /**

    1.   * 反转字符串指定区间[start, end]的字符
    2.   *
    3.   * @param sb
    4.   * @param start
    5.   * @param end
    6.   */

    public void reverseString(StringBuilder sb, int start, int end) {

    1.   for (; start < end; start++, end--) {
    2.       char temp = sb.charAt(start);
    3.       sb.setCharAt(start, sb.charAt(end));
    4.       sb.setCharAt(end, temp);
    5.   }

    }

  1. /**
  2.     * 反转每个单词
  3.     *
  4.     * @param sb
  5.     */
  6. private void reverseEachWord(StringBuilder sb) {
  7.     int start = 0, end = 1;
  8.     int n = sb.length();
  9.     while (start < n) {
  10.         // 搜索一个单词
  11.         while (end < n && sb.charAt(end) != ' ') {
  12.             end++;
  13.         }
  15.         // 反转这个单词
  16.         reverseString(sb, start, end - 1);
  18.         // 重新开始下一个单词
  19.         start = end + 1;
  20.         end = start + 1;
  21.     }
  22. }

}

  1. <a name="cgPJE"></a>
  2. # 剑指Offer58-II.左旋转字符串
  3. 这道题目也非常类似，依然可以通过局部反转+整体反转 达到左旋转的目的。<br />具体步骤为：
  5. 1. 反转区间为前n的子串
  6. 1. 反转区间为n到末尾的子串
  7. 1. 反转整个字符串
  9. ![image.png](https://cdn.nlark.com/yuque/0/2022/png/26393840/1653833850671-0429cbc7-01a9-468b-a7d6-793e1c500e7f.png#clientId=u48d02f85-e327-4&crop=0&crop=0&crop=1&crop=1&from=paste&id=uf2ba93bf&margin=%5Bobject%20Object%5D&name=image.png&originHeight=760&originWidth=1034&originalType=url&ratio=1&rotation=0&showTitle=false&size=59921&status=done&style=none&taskId=u3fe94c65-d044-478b-a956-105cb9edf32&title=)
  10. ```java
  11. class Solution {
  12.     public String reverseLeftWords(String s, int n) {
  13.         s = reverse(s, 0, n - 1);
  14.         s = reverse(s, n, s.length() - 1);
  15.         s = reverse(s, 0, s.length() - 1);
  16.         return s;
  17.     }
  19.     public String reverse(String s, int i, int j) {
  20.         char[] chars = s.toCharArray();
  21.         for (; i < j; i++, j--) {
  22.             char temp = chars[i];
  23.             chars[i] = chars[j];
  24.             chars[j] = temp;
  25.         }
  26.         return String.valueOf(chars);
  27.     }
  28. }