MyException - 我的异常网
当前位置:我的异常网» 编程 » 算法之道-上下旋转字符串

算法之道-上下旋转字符串

www.MyException.Cn  网友分享于:2013-02-19  浏览:3次
算法之道--左右旋转字符串
        定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。
如把字符串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;
    }
}
 
1 楼 dsjt 前天  
2 楼 clz2008wan 昨天  
你逆序字符串的方法可以进一步优化
    /**
     * 
     * <字符串逆序>
     * @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;
    }
3 楼 chenchuangfeng 昨天  
clz2008wan 写道
你逆序字符串的方法可以进一步优化
    /**
     * 
     * <字符串逆序>
     * @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;
    }



这个效率不是差不不多一样???请问有哪些巧妙之处??

文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有