Reverse/Rotate类问题

reverse的模版

其实，reverse的操作和判断palindrome的操作近乎一摸一样。无非就是首尾两指针同时前进。 基本版如下：

  int start = 0;
  int end = array.length - 1;
  while (start < end) {
    char temp = array[start];
    array[start] = array[end];
    array[end] = temp;
    start++;
    end--;
  }

和palindrome问题一样，有时候我们在reverse的时候有条件限制，不是所有的char都需要操作。 反过来理解就是我们需要忽略一些char，那么就需要我们在while loop的内部再使用while loop 进行忽略。增强版如下：

  int start = 0;
  int end = array.length - 1;
  while (start < end) {
    while (start < end && start不满足条件) {
        start++;
    }
    while (start < end && end不满足条件) {
        end--;
    }
    if (start < end) {
        //swap
    }
    start++;
    end--;
}

reverse/rotate题目的类型

• reverse String/Array类。String/Array的题目的共性是我们可以从首尾两端同时前进。 而这类问题又有两种解决办法。第一是使用reverse的算法（有时要全局和局部各使用 一次）；第二是使用stack来辅助操作。

• rotate String/Array类。String/Array的题目的共性还是我们可以从首尾两端同时前进。 这类问题也有两种解法。第一是使用“三步反转法”，第二是使用queue。

• reverse Integer。这类问题和reverse bit最大的区别是reverse integer是把 integer作为signed number来对待的。也就是说java表示的就是我们想要的，所以我们可以直接 通过乘除运算来做进制转换。

• reverse bit。这类问题和reverse int的区别是reverse bits里面我们是把integer作为 unsigned number来对待的。也就是说java实际表示的不是我们想要的数。那我们就不能直接 进行乘除运算了。而要使用bitwise shift操作。

• reverse LinkedList。因为是单向链表，我们只能one direction traverse，这是 LinkedList反转和String/Array本质的区别。对于LinkedList的reverse问题，有他自己 的解法，详情请见LinkedList问题汇总章节。

题目

Reverse String/Array (reverse其实用到了栈的思想)

• Leetcode 151. Reverse Words in a String
• Leetcode 186. Reverse Words in a String II
• Leetcode 345. Reverse Vowels of a String
• Leetcode 344. Reverse String

Rotate String/Array (Rotate其实用到了queue的思想)

• Leetcode 189. Rotate Array
• Leetcode 61. Rotate List (这也是我们在LinkedList里面不用三步反转法，因为他天然就是一个queue)

Reverse Int/Bit

• Leetcode 7. Reverse Integer (这里我们把int作为signed integer，所以我们看到的int就是我们想要的)
• Leetcode 190. Reverse Bits (这里我们把int作为unsigned integer，所以我们看到的int不是我们想要的)