8.Rotate String-旋转字符串（容易题）

旋转字符串

题目

给定一个字符串和一个偏移量，根据偏移量旋转字符串(从左向右旋转)

样例

对于字符串 “abcdefg”.

offset=0 => “abcdefg” offset=1 => “gabcdef” offset=2 => “fgabcde” offset=3 => “efgabcd”

挑战

在数组上原地旋转，使用O(1)的额外空间

题解

先前一部分逆序，再把后一部分逆序，最后整体逆序，重点掌握数组逆序的方法。注意从左向右旋转时offset应从字符数组的尾部算起。

public class Solution { /** * @param str: an array of char * @param offset: an integer * @return: nothing */ public void rotateString(char[] str, int offset) { if (str == null || str.length <=1) { return; } int n = str.length; offset %= n;//处理offset大于n的情况 reverse(str,0,n-offset-1); reverse(str,n-offset,n-1); reverse(str,0,n-1); } //将数组的部分元素进行逆序操作 public void reverse(char[] str,int start,int end) { for (int i=start,j=end;i<j;i++,j--) { char temp = str[i]; str[i] = str[j]; str[j] = temp; } } }

Last Update 2016.8.15