剑指offer58.2左旋转字符串（字符串思路）

题目描述

思路

这一篇与上一篇的区别是，上一篇使用栈来实现，效率非常的低，击败5%也就，这一篇用的是Java对字符串的种种操作来实现的，思路很简单，就是对字符串进行切片或者取余等等。

代码1

因为String类型属于不可变对象，所以使用StringBuilder进行单个字符的添加，将读取到的单个字符添加到StringBuilder中去，最后直接输出就好。

class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder res=new StringBuilder();
        for(int i=n;i<s.length();i++){
            res.append(s.charAt(i));
        }
        for(int i=0;i<n;i++){
            res.append(s.charAt(i));//这里遍历到并被添加的元素在StringBuilder中已经不存在了。
        }
        return res.toString();//根据返回类型将res强制转换成String类型
    }
}

代码2

这一部分比上面的要求更加苛刻，不允许使用StringBuilder方法，只能使用Strin数据类型，此时使用字符串遍历拼接，时间和空间复杂度都是O(N)，代码如下：

class Solution {
    public String reverseLeftWords(String s, int n) {
        // StringBuilder res=new StringBuilder();
        String res="";
        for(int i=n;i<s.length();i++){
            res+=s.charAt(i);
        }
        for(int i=0;i<n;i++){
            res+=s.charAt(i);
        }
        return res;
    }
}

可以通过取余操作简化代码，还是比较好用和巧妙的。

class Solution {
    public String reverseLeftWords(String s, int n) {
        // StringBuilder res=new StringBuilder();
        String res="";
        for(int i=n;i<n+s.length();i++){
            res+=s.charAt(i%s.length());
        }

        return res;
    }
}

三种方法分析

切片法

新建两个切片字符串，并将两切片拼接为结果字符串，无冗余操作，效率最高。

列表遍历拼接

列表(Python) 和 StringBuilder(Java) 都是可变对象，每轮遍历拼接字符时，只是向列表尾部添加一个新的字符元素。最终拼接转化为字符串时，系统仅申请一次内存。

字符串遍历拼接

在 Python 和 Java 中，字符串是 “不可变对象” 。因此，每轮遍历拼接字符时，都需要新建一个字符串；因此，系统 需申请 N次内存，数据量较大时效率低下。