《程式設計珠玑2》讀書筆記1---翻轉代碼

第二章 ”啊哈，算法“ P11

問題B：将一個n元一維向量向左旋轉i個位置（循環移位）,例如abcdefgh左循環移位3個位置變成defghabc

 要求：使用一個n元的中間向量在n步内完成，能否僅适用數十個額外位元組的存儲空間，在正比于n的時間内完成？

"啊哈，靈機一動"：

貼個照片，不侵權吧，呵呵，手我加了指甲，分辨手掌正反面

代碼：

package org.test.algorithm;



/**
 * 翻轉算法
 * 目标: 把n元一維向量"abcdefg"左旋轉3個位置，既字元串循環移位變成"defgabc"
 * 限制:時間，僅适用n元的中間向量在n步内完成，在正比于n的時間内完成，空間，僅适用數十個額外位元組的存儲空間  
 * @author Administrator
 *
 */
public class FingerTranslate {
    private static String srcStr = "abcdefg";
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("input: "+srcStr+" 左移位3次後:");
        System.out.println("output: "+moveFor(srcStr,3));
    }
    /**
     * 翻轉 一個字元數組
     * {a,b,c} to {c,b,a}
     * 
     * @param charArr 
     */
    public static char[] reverseArray(char[] charArr ){
        int len = charArr.length;
        int changeTimes = len/2;
        
        char charTmp = 0;
        for(int i=0;i<changeTimes;i++){
            charTmp = charArr[i];
            charArr[i] = charArr[len-i-1];
            charArr[len-i-1] = charTmp;
        }
        return charArr;
    }
    /**
     * 把srcStr向左循環移位moveTimes次
     * @param _srcStr
     * @param moveTimes
     * @return
     */
    public static String moveFor(String _srcStr,int moveTimes){
        int lenInput = _srcStr.length();
        /**
         * 把整個串截斷兩部分head(abc) 和tail(defg)
         * 步驟：
         * 1，翻轉head
         * 2,翻轉tail
         * 3,翻轉{head,tail}
         */
        //構造head 承裝abc
        char[] arrHead = new char[moveTimes];
        arrHead = _srcStr.substring(0, moveTimes).toCharArray();
        //構造tail 承裝defg
        char[] arrTail = new char[lenInput-moveTimes];
        arrTail = _srcStr.substring(moveTimes, lenInput).toCharArray();
        //構造total承裝所有字元(各自翻轉後的 head+tail :cba gfed)
        char[] arrTotal = new char[lenInput];
        
        //1
        reverseArray(arrHead);
        //2
        reverseArray(arrTail);
        //3
        /**
         * head并入
         */
        System.arraycopy(arrHead, 0, arrTotal, 0, arrHead.length);
        /**
         * tail并入
         */
        System.arraycopy(arrTail, 0, arrTotal, moveTimes, arrTail.length);
        reverseArray(arrTotal);
        return new String(arrTotal);
    }

}

           

package org.test.algorithm;

import junit.framework.TestCase;

public class FingerTranslateTest extends TestCase {
    FingerTranslate ft =new FingerTranslate();
    String tmp = "abcdefgh";
    public void testReverseArray() {
        char[] chars = {'a','b','c','d'};
        assertEquals("", "dcba", new String(ft.reverseArray(chars)));
    }

    public void testMoveFor() {
        String result = ft.moveFor(tmp, 4);
        assertEquals("", "efghabcd", result);
    }

}