算法之道--左右旋转字符串
? ? ? ? 定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。
如把字符串abcdef左旋转2位得到字符串cdefab。
请实现字符串左旋转的函数，要求对长度为n的字符串操作的时间复杂度为O(n)，空间复杂度为O(1)。???以下算法实现了可以做旋转和右旋转....原理：abcde123456根据要旋转的位数k，把数组分成两子串，例如K=6，进行右旋转，则把字符串分成 abcde 和 123456（K位）划分技巧：右旋转，后面子串位数为K，剩下做为前面子串；若是左旋转，前面子串位数为K，剩下做为后面子串????????????????如果上面 abcde123456 进行左旋转 K=6位，则字符串的划分是：abcde1（K位）? 和 23456接着对abcde和123456分别进行逆序操作结果：edcba和654321合并后成?edcba654321再整体逆序123456abcde?优点： 3个reverse 操作都是线性操作，前两个时间复杂度和为0（n/2）,最后一个整体逆序时间复杂度为0（n/2）,总时间复杂度是O(n)，比起普通的相同功能算法时间复杂度要低?
package 左旋转字符串;import java.util.Scanner;/** * 左旋转字符串 * * @author ccf * */public class test { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out.println("输入一行字符串："); Scanner input = new Scanner(System.in); char[] charArray = input.nextLine().toCharArray(); System.out.println("输入要移动的位数"); int shiftNum = Integer.parseInt(input.nextLine()); System.out.println("你输入的字符串为" + new String(charArray) + " 要移动问位数为" + shiftNum); // charArray = RightShift(shiftNum, charArray); charArray = LeftShift(shiftNum, charArray); System.out.println("移位结果为：" + String.valueOf(charArray)); } /** * 实现字符串的逆序 * * @param src * @param begin * @param end * @return */ private static char[] reverse(char[] src, int begin, int end) { char temp; for (; begin < end; end--, begin++) { temp = src[begin]; src[begin] = src[end]; src[end] = temp; } return src; } /** * * @param k * 偏移量 * @param src */ private static char[] RightShift(int k, char[] src) { src = reverse(src, 0, src.length - k - 1); src = reverse(src, src.length - k, src.length - 1); // 与左移位不同在于下标的选取，这里是取后面K位 src = reverse(src, 0, src.length - 1); return src; } private static char[] LeftShift(int k, char[] src) { src = reverse(src, 0, k - 1); // 与右移位不同在于下标的选取，这里是取前面K位 src = reverse(src, k, src.length - 1); src = reverse(src, 0, src.length - 1); return src; }}? /** * * <字符串逆序> * @param src * @param begin 起始位置 * @param end 结束位置 * @return */ public char[] reverseString(char src[],int begin,int end) { char temp; while(begin != end) { temp=src[begin]; src[begin]=src[end]; src[end]=temp; begin++; end--; } return src; } /** * * <字符串逆序> * @param src * @param begin 起始位置 * @param end 结束位置 * @return */ public char[] reverseString(char src[],int begin,int end) { char temp; while(begin != end) { temp=src[begin]; src[begin]=src[end]; src[end]=temp; begin++; end--; } return src; }