알고리즘 의 길 - 좌우 회전 문자열

문자열 의 왼쪽 회전 동작 을 정의 합 니 다: 문자열 앞 에 있 는 몇 개의 문 자 를 문자열 의 끝으로 이동 합 니 다.문자열 abcdef 를 왼쪽 으로 두 자리 회전 시 켜 문자열 cdefab 를 가 져 옵 니 다.문자열 의 왼쪽 회전 함 수 를 실현 하 십시오. 길이 가 n 인 문자열 에 대한 작업 시간 복잡 도 는 O (n) 이 고 공간 복잡 도 는 O (1) 입 니 다. 
 
 다음 알고리즘 은 회전 과 오른쪽 회전 을 할 수 있 습 니 다.
원리:
abcde123456
회전 할 자릿수 k 에 따라 배열 을 두 개의 문자열 로 나 누 었 습 니 다. 예 를 들 어 K = 6, 오른쪽 회전 을 하면 문자열 을 abcde 와 123456 (K 비트) 으로 나 누 었 습 니 다.
구분 기법: 오른쪽 회전, 뒤 면 꼬치 수 는 K 이 고 나머지 는 앞 면 꼬치 로 합 니 다.왼쪽 회전 이 라면 앞 면 꼬치 수 는 K 이 고 나머지 는 뒤 면 꼬치 로 한다.
                위 abcde 123456 에서 좌회전 K = 6 비트 를 진행 하면 문자열 의 구분 은 abcde 1 (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;

    }

}