算法：数据结构之反转字符串

反转字符串

题目描述：将字符串 "##We###Are###Family!###" 反转为 "###!ylimaF###erA###eW##"。

分析与解答：这题我们的解答方法有很多，常见的方法是使用数组，下面来介绍用数据结构中的 Stack（栈）来完成反转。

Stack 的特点是 FILO（First In，Last Out）— 先进后出。此特点用于将字符串反转非常合适，以下是代码实现：

import java.util.Stack;

public class Demo {
    public static void main(String[] args) {
        System.out.println(ReverseAllStringWithStack("##We###Are###Family!###"));
    }

    public static String ReverseAllStringWithStack(String string) {
        // 如果 string 等于 null 或等于 "" 时，返回 string。
        if (string == null || string.length() == 0)
            return string;
        // 新建一个 Stack，用于存放 Character 类型。为什么存放 Character 而不是 char，
        // 因为泛型只能指定是类或接口类型，而不能是 primitive 主（基本）数据类型。
        Stack<Character> stringStack = new Stack<>();
        
        char[] array = string.toCharArray();//toCharArray() 将字符串转换成 char 类型数组
        // 使用 for-each 将数组中的元素 push（推）进 Stack
        for (Character c : array) {
            stringStack.push(c);
        }
        int length = string.length();// 数组的长度 length; 字符串的长度 length(); 集合的长度 size()
        // 利用 for 循环将元素从栈顶开始，依次弹出
        for (int i = 0; i < length; i++) {
            array[i] = stringStack.pop();
        }
        
        return new String(array);//String 的重载构造方法将 char[] 数组转换，返回一个实例化 String 对象
    }
}

多次反转字符串

题目描述：将字符串 "##We###Are###Family!###" 反转为 "###Family!###Are###We##"。

分析与解答：
此题和上题的区别是，单词不反转。解决思路有两个：

1. 将所有字符串反转后，再将反转结果中的单词再一次反转。
2. 先将字符串中的单词反转，再将整体反转。

两种方式的区别不大，下面代码是第一种方式的实现。

import java.util.Stack;

public class Demo {
    public static void main(String[] args) {
        System.out.println(ReverseAllStringWithStack("##We###Are###Family!###"));
    }

    public static String ReverseAllStringWithStack(String stringAll) {
        if (stringAll == null || stringAll.length() == 0)
            return stringAll;
        Stack<Character> stringAllStack = new Stack<>();
        char[] array = stringAll.toCharArray();
        for (Character c : array) {
            stringAllStack.push(c);
        }
        int length = stringAll.length();
        for (int i = 0; i < length; i++) {
            array[i] = stringAllStack.pop();
        }

        int from = 0, to = 0;//from 是单词在数组中的起始下标，to 是结束下标
        String string = null;// 存放排序后的字符串
        for (int i = 0; i < length; ) {
            while (array[i] == '#') {// 如果字符是 '#'，继续循环
                from = ++i;// 单词起始下标是循环结束时的下标 + 1，所以 from = i + 1;i++;->from = ++i
                if (i >= length)// 防止下标溢出
                    break;
            }
            if (i >= length)// 防止下标溢出
                break;
            while (array[i] != '#') {// 当字符是 '#'，循环结束
                to = i++;// 单词结束下标就是循环结束时的下标，所以 to = i;i++;->to = i++
            }
            string = ReverseStringWithStack(array, from, to);// 交换找到的单词顺序
        }
        return string;
    }

    public static String ReverseStringWithStack(char[] array, int from, int to) {
        if (array.length == 0)
            return null;
        for (int i = 0; i < from; i++) {
            while (from < to) {
                char t = array[from];
                array[from++] = array[to];//array[from++]->array[from] = array[to];from++;
                array[to--] = t;
            }
        }
        return new String(array);
    }
}

总结

不管是 # 还是空格等符号，反转方法均一样。顺序不变的部分经过两次反转就跟原来一样。

我们使用好 IDEA 的 dubug 功能能解决很多代码错误。建议多动手实践。

参考此资料

• julycoding— 旋转字符串