春招秋招忆---斗鱼笔试

斗鱼的题目很简单，就几个字，反转字符串，其实看到这大家也就联想到剑指offer里面的题目翻转单词顺序与左旋转字符串了。那我们今天就来彻底的解决一下这类问题。

1.序

首先来看Trim()源码


public String trim() {
    int len = value.length;
    // 有效字符（不是空格）结束位置
    int st = 0;
    // 有效字符（不是空格）起始位置
    char[] val = value; 
    // 字符数组   /* avoid getfield opcode */
    while ((st < len) && (val[st] <= ' ')) { 
    // 从起始位置开始遍历，获取起始连续空格的最后空格位置
        st++;
        // st值发生变化，说明起始有空格，st就是起始需要截取的位置
    }

    while ((st < len) && (val[len - 1] <= ' ')) { 
    // 从末尾位置开始遍历，获取末尾连续空格的第一个空格位置
        len--;
        // len值发生变化，说明末尾有空格，len是末尾需要截取的位置
    }
    return ((st > 0) || (len < value.length)) ? 
     substring(st, len) : this;
     // 判断是否有空格需要截取，有截取，没有返回原String

}

2.翻转单词顺序序列

例如，“student. a am I”。句子单词的顺序翻转了，正确的句子应该是“I am a student.”。如何实现。

思路1

观察字符串变化规律，你会发现这道题很简单。只需要对每个单词做翻转，然后再整体做翻转就得到了正确的结果。

public String reverseWords(String s) {
    char[] data = s.toCharArray();
    if (data == null || data.length < 1) {
        return String.valueOf(data);
    }
    reverse(data, 0, data.length - 1);
    int start = 0;
    int end = 0;
    while (start < data.length) {
        if (data[start] == ' ') {
            start++;
            end++;
        } else if (end == data.length || data[end] == ' ') {
            reverse(data, start, end - 1);
            end++;
            start = end;
        } else {
            end++;
        }
    }
    return String.valueOf(data);
}
public static void reverse(char[] data, int start, int end) {
    if (data == null || data.length < 1 || start < 0 || end > data.length || start > end) {
        return;
    }
    while (start < end) {
        char tmp = data[start];
        data[start] = data[end];
        data[end] = tmp;
        start++;
        end--;
    }
}

思路2

//第二种思路，先将整个字符串反转，再逐个单词反转

public String ReverseSentence(String str) {
        if (str == null || str.length() == 0)
        {
            return str;
        }
        if (str.trim().length() == 0)
        {
            return str;
        }
        StringBuilder sb = new StringBuilder();
        String re = reverse(str);
        String[] s = re.split(" ");
        for (int i = 0; i < s.length - 1; i++) {
            sb.append(reverse(s[i]) + " ");
        }
        sb.append(reverse(s[s.length-1]));
        return String.valueOf(sb);
    }            
    public String reverse(String str) {
        StringBuilder sb = new StringBuilder();
        for (int i = str.length() - 1; i >= 0 ; i--) {
            sb.append(str.charAt(i));
        }
        return String.valueOf(sb);
    }

3.左旋转字符串

例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。

思路1

例如：输入字符串"abcdefg"和数字2，该函数将返回左旋转2位得到的结果"cdefgab";

第一步：翻转字符串“ab”，得到"ba"；

第二步：翻转字符串"cdefg"，得到"gfedc"；

第三步：翻转字符串"bagfedc"，得到"cdefgab"；

或者：

第一步：翻转整个字符串"abcdefg",得到"gfedcba"

第二步：翻转字符串“gfedc”，得到"cdefg"

第三步：翻转字符串"ba",得到"ab"

 public static void main(String[] args) {
        System.out.println(LeftRotateString("abcdefg",2));
    }
    public static String LeftRotateString(String pStr,int num){
        if(pStr == null ||pStr.length() <num){
            throw new RuntimeException();
        }
        String str1 = pStr.substring(0,2);
        String str2 = pStr.substring(2,pStr.length());
        StringBuilder stringBuilders = new StringBuilder();
        String str11 = help(str1);
        String str22 = help(str2);
        stringBuilders.append(str11);
        stringBuilders.append(str22);
        return help(stringBuilders.toString());
    }
    private static String help(String str1) {
        int start = 0;
        int end = str1.length()-1;
        char[] data = str1.toCharArray();
        while (start < end) {
            char tmp = data[start];
            data[start] = data[end];
            data[end] = tmp;
            start++;
            end--;
        }
        return new String(data);
    }

思路2

public String LeftRotateString(String str,int n) {
        if (str == null || str.trim().length() == 0) {
            return str;
        }
        int len = str.length();
        n = n % len;// 当len=3，n=4，其实相当于左旋转1位，所以需要取余
        char[] charstr = str.toCharArray();
        //先旋转前面的
        reverse(charstr, 0, n-1);
        //再旋转后面的字符串
        reverse(charstr, n, len -1);
        //最后整体反转
        reverse(charstr, 0, len-1);
        return String.valueOf(charstr);
    }
    //实现的是charstrs从i到j的反转，也可以使用上题中stringbuffer的反转方式
    private void reverse(char[] charStrs, int i, int j) {
        while(i<j) {
            char temp = charStrs[i];
            charStrs[i] =charStrs[j];
            charStrs[j] = temp;
            i++;
            j--;
        }
    }

4.LeetCode旋转字符串

给定两个字符串, A 和 B。

A 的旋转操作就是将 A 最左边的字符移动到最右边。例如, 若 A = 'abcde'，在移动一次之后结果就是'bcdea' 。如果在若干次旋转操作之后，A 能变成B，那么返回True。

示例 1:

输入: A = 'abcde', B = 'cdeab'

输出: true

示例 2:

输入: A = 'abcde', B = 'abced'

输出: false

注意：

A 和 B 长度不超过 100。

思路1：

首先确认两个字符串的长度要相等。其次只要保证A+A 的字符串中包含B就可以了。因为A+A已经包含了所有可移动的方案。

public static boolean rotateString(String A, String B) {
        return A.length() == B.length() && (A+A).contains(B);
    }
    public static void main(String[] args) {
        String a = "abcde";
        String b = "abced";
        boolean flag = rotateString(a,b);
        System.out.println(flag);
    }

思路2：KMP算法（不懂别用，一定要用自己擅长的算法实现题）

判断一个串是否为另一个串的子串的最优时间复杂度的算法是 KMP 算法。只需要用 KMP 算法判断 B 是否为 A + A 的子串即可。

软大神的KMP讲解

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

public boolean rotateString(String A, String B) {        int N = A.length();
        if (N != B.length())
            return false;
        if (N == 0) return true;
        //Compute shift table
        int[] shifts = new int[N+1];
        Arrays.fill(shifts, 1);
        int left = -1;
        for (int right = 0; right < N; ++right) {
            while (left >= 0 && (B.charAt(left) != B.charAt(right)))
                left -= shifts[left];
            shifts[right + 1] = right - left++;
        }
        //Find match of B in A+A
        int matchLen = 0;
        for (char c: (A+A).toCharArray()) {
            while (matchLen >= 0 && B.charAt(matchLen) != c)
                matchLen -= shifts[matchLen];
            if (++matchLen == N)
                return true;
        }
        return false;
    }

复杂度分析

时间复杂度：O(N)O(N)，其中 NN 是字符串 A 的长度。

空间复杂度：O(N)O(N)。