文档章节

左旋转字符串

datacube
 datacube
发布于 2016/06/22 17:45
字数 717
阅读 12
收藏 1
public class LeftRotateString {
    /**
     * Q 26 左旋转字符串
     * 题目:定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。
     * 如把字符串abcdef左旋转2位得到字符串cdefab。
     * 请实现字符串左旋转的函数。要求时间对长度为n的字符串操作的复杂度为O(n),辅助内存为O(1)。
     */
    public static void main(String[] args) {
        String data = "abcdef";
        String re = leftRotateString(data, 2);
        System.out.println(re);
    }

    /*
     * abcdef->ab.cdef->ba.fedc->cdefab
     */
    public static String leftRotateString(String str, int n) {
        if (str == null || str.length() == 0) {
            return str;
        }
        if (n <= 0 || n >= str.length()) {
            return str;
        }
        int begin = 0;
        int end = str.length() - 1;
        char[] letters = str.toCharArray();#考虑引用传递可以修改值
        reverseString(letters, begin, n - 1);
        reverseString(letters, n, end);
        reverseString(letters, begin, end);
        return new String(letters);

    }

    public static void reverseString(char[] letters, int begin, int end) {
        /*
         * of course we can do it like this: StringBuilder sb=new
         * StringBuilder(str); sb.reverse().toString(); but we are learning
         * algorithm so let's 'reinvent the wheel'.
         */
        if (begin >= end) {
            return;
        }
        for (int i = begin, j = end; i < j; i++, j--) {
            char tmp = letters[i];
            letters[i] = letters[j];
            letters[j] = tmp;
        }
        System.out.println("---"+new String(letters)+"---");
        /**
         *
         ---bacdef---
         ---bafedc---
         ---cdefab---
         cdefab
         *
         */
    }
}

================================
public class ShiftLeft {

    static String str;

    public ShiftLeft(String str){
        this.str = str;
    }

    public static void main(String[] args) {
        ShiftLeft sl = new ShiftLeft("abcdefghi");
        System.out.printf(sl.shift(12));


    }

    /**
     * abcdef循环左移两位得到cdefab
     *1 暴力求解,将左移字母的暂存临时变量中,将其他字母移位,再将临时变量,补充到移位后字符串的后面
     *2 ba ihgfedc  -> cdefghiab
     *
     *
     */
    private String shift(int digits) {
        if (digits == 0){
            return str;
        } else if (digits > 0){
            digits = digits % str.length();     //是保证循环移位的关键,可以输入大于字符串长度的移位
            String left = reverse(str.substring(0,digits));
            String right = reverse(str.substring(digits));
            System.out.println("left:"+left);
            System.out.println("right:"+right);
            return reverse(left + right);
        } else {   // < 0
            digits = -digits;
            digits = digits % str.length();     //同上
            return shift(str.length() - digits);
        }
    }

    private static String reverse(String s) {
        int start = 0;
        int end = s.length() - 1;
        char[] temp = new char[s.length()];
        for (int i = 0; i< temp.length; i++){
            temp[start] = s.charAt(end);
            temp[end] = s.charAt(start);
//          s.charAt(start) = s.charAt(end);  这样写是有问题的
            start++;
            end--;
        }

        return String.valueOf(temp);
    }

}
=====================
package com.lifeibigdata.algorithms.blog;


public class LeftRotateString {
    /**
     * Q 26 左旋转字符串
     * 题目:定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。
     * 如把字符串abcdef左旋转2位得到字符串cdefab。
     * 请实现字符串左旋转的函数。要求时间对长度为n的字符串操作的复杂度为O(n),辅助内存为O(1)。
     */
    public static void main(String[] args) {
        String data = "abcdef";
        String re = leftRotateString(data, 2);
        System.out.println(re);
    }

    /*
     * abcdef->ab.cdef->ba.fedc->cdefab
     */
    public static String leftRotateString(String str, int n) {
        if (str == null || str.length() == 0) {
            return str;
        }
        if (n <= 0 || n >= str.length()) {
            return str;
        }
        int begin = 0;
        int end = str.length() - 1;
        char[] letters = str.toCharArray();
        reverseString(letters, begin, n - 1);
        reverseString(letters, n, end);
        reverseString(letters, begin, end);
        return new String(letters);

    }

    // public static String reverseString(String str,int begin,int end){
    public static void reverseString(char[] letters, int begin, int end) {
        /*
         * of course we can do it like this: StringBuilder sb=new
         * StringBuilder(str); sb.reverse().toString(); but we are learning
         * algorithm so let's 'reinvent the wheel'.
         */
        if (begin >= end) {
            return;
        }
        for (int i = begin, j = end; i < j; i++, j--) {
            char tmp = letters[i];
            letters[i] = letters[j];
            letters[j] = tmp;

        }
        System.out.println("---"+new String(letters)+"---");
        /**
         *
         ---bacdef---
         ---bafedc---
         ---cdefab---
         cdefab
         *
         */
    }
}


本文转载自:

上一篇: 求树的直径
datacube
粉丝 9
博文 607
码字总数 152394
作品 0
海淀
程序员
私信 提问

暂无文章

使用TensorFlow的AI程序运行报错AttributeError: module 'tensorflow' has no attribute 'xxx'

使用TensorFlow的AI程序,在运行时报错AttributeError: module 'tensorflow' has no attribute 'xxx',首先检查是否是包路径不对,一般是版本变化所致。...

织梦之魂
33分钟前
2
0
提示浏览器版本低

本文转载于:专业的前端网站➭提示浏览器版本低 网站网页在遇到浏览器低版本(尤其是IE浏览器)时,提示浏览器版本低(如IE8以及以下),建议用户升级浏览器以获得最好体验。以下是代码: 1...

前端老手
35分钟前
5
0
CentOS 7系统增加swap

转载请注明文章出处:CentOS 7系统增加swap swap是位于磁盘上的特殊文件(或分区),属于“虚拟内存”的一部分。通俗点就是内存的备胎,内存充足的情况下,基本上没swap什么事(和设置有关)...

tlanyan
58分钟前
6
0
基于Prometheus和Grafana的监控平台 - 环境搭建

相关概念 微服务中的监控分根据作用领域分为三大类,Logging,Tracing,Metrics。 Logging - 用于记录离散的事件。例如,应用程序的调试信息或错误信息。它是我们诊断问题的依据。比如我们说...

JAVA日知录
今天
6
0
PHP运行时全局构造体

struct _php_core_globals { zend_bool magic_quotes_gpc; // 是否对输入的GET/POST/Cookie数据使用自动字符串转义。 zend_bool magic_quotes_runtime; //是否对运行时从外部资源产生的数据使...

冻结not
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部