剑指offer-44、翻转单词序列

Java资料网推荐剑指offer-44、翻转单词序列这篇文章给大家，欢迎收藏Java资料网享受知识的乐趣

题⽬描述

给定⼀个句⼦，将句⼦中的单词进⾏翻转，注意，单词内部的字符顺序不改变，改变的是单词与单词之间的顺序，⽐如“ I am a coder. ”,翻转之后变成“ coder. a am I ”。

示例
注意：引号内部才是输⼊的内容
输⼊："You are a cool boy."
输出："boy. cool a are You"

思路及解答

Java内置函数分割反转

Java ⾥⾯有切割字符串的⽅法，直接⽤空格进⾏分隔，分隔成为多个单词，然后从字符串数组的后⾯开始，每⼀个字符拼接上⼀个空格，但是，值得注意的⼀点是，当只剩下⼀个字符串的时候，也就是索引为 0 的时候，不需要再拼接空格。代码实现如下：

public class Solution {
    public String ReverseSentence(String str) {
        if (str == null || str.length() == 0 || str.equals(" ")) {
	        return "";
        }
        
        //去除首尾空格后，按照空格分隔
        String[] strs = str.trim().split(" ");
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = strs.length - 1; i >= 0; i--) {
            stringBuilder.append(strs[i]);
            stringBuilder.append(i == 0 ? "" : " ");
        }
        return stringBuilder.toString();
    }
}

• 时间复杂度：O(n)，分割和拼接各需线性时间
• 空间复杂度：O(n)，存储单词数组和结果字符串

借助栈

借助栈，栈是先进后出，也就是我们切割完字符串之后，全部放到栈中，再全部取出来拼接，就可以完成逆序的操作。有⼀个值得注意的点，就是空格的问题，我们压栈的时候，跟随着拼接上空格即可，最后⼀个字符不压⼊空格。

public String ReverseSentence(String str) {
    if (str == null || str.length() == 0)
        return str;
    StringBuilder stringBuilder = new StringBuilder();
    String[] strs = str.split(" ");
    if (strs.length == 0)
        return str;
    Stack < String > stack = new Stack < > ();
    for (int i = 0; i < strs.length - 1; i++) {
        stack.push(strs[i]);
        stack.push(" ");
    }
    stack.push(strs[strs.length - 1]);
    while (!stack.isEmpty()) {
        stringBuilder.append(stack.pop());
    }
    return stringBuilder.toString();
}

双指针法(推荐)

⾸先判断字符串 str 是否为空或者为空字符，如果 str 不为空，则初始化 start ，和 end 指针指向字符串的尾部， start 从尾部向头部遍历

针对每⼀个字符，如果字符为空字符：

• 如果 start 和 end 不是出于同⼀个位置，说明已经遍历完⼀个单词，那么将 start+1 ~ end 之间的字符，拼接到结果后，并且添加上⼀个空格。将 start-1 ，并且 end 指向 start 的位置
• 否则，说明是多余的空格，直接跳过， start-1 ， end=start

如果字符不是空字符：可以把 start 索引前移，也就是 start--

最后，剩下最后⼀个单词的时候，需要特殊处理最后⼀个单词，拼接到字符串后⾯就可以了。

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.ReverseSentence("nowcoder. a am I"));
    }
    public String ReverseSentence(String str) {
        if (str != null && str.length() != 0 && !str.equals(" ")) {
            int start = str.length() - 1, end = start;
            StringBuffer stringBuffer = new StringBuffer();
            for (; start > 0;) {
                // 如果为空格
                if (str.charAt(start) == ' ') {
                    // 且开始索引和结束索引不⼀致的情况
                    if (start != end) {
                        // 遍历start+1~end的字符，加到
                        for (int i = start + 1; i <= end; i++) {
                            stringBuffer.append(str.charAt(i));
                        }
                        // 每⼀个单词的后⾯加上⼀个空格
                        stringBuffer.append(" ");
                    }
                    start--;
                    end = start;
                } else {
                    start--;
                }
            }
            // 处理最后⼀个单词
            for (int i = 0; i <= end; i++) {
                stringBuffer.append(str.charAt(i));
            }
            return stringBuffer.toString();
        }
        return str;
    }
}

• 时间复杂度：O(n)，每个字符被访问常数次
• 空间复杂度：O(n)，StringBuilder存储结果

三次反转法（空间最优）

通过字符级操作实现O(1)空间复杂度（假设字符数组可修改）。

先反转整个字符串，再逐个反转每个单词

三次反转的数学原理：

对于句子 "A B C"（A、B、C为单词）：

1. 整体反转： "C' B' A'"
2. 单词反转： "C'"反转→ "C", "B'"反转→ "B", "A'"反转→ "A"
3. 结果： "C B A" → 正是期望的顺序

public class Solution {

    public String reverseWords(String s) {
        if (s == null || s.length() == 0) return "";
        
        char[] chars = s.toCharArray();
        int n = chars.length;
        
        // 步骤1：反转整个字符串
        reverse(chars, 0, n - 1);
        
        // 步骤2：反转每个单词
        reverseWords(chars, n);
        
        // 步骤3：清理多余空格
        return cleanSpaces(chars, n);
    }
    
    /**
     * 反转字符数组的指定区间
     */
    private void reverse(char[] chars, int left, int right) {
        while (left < right) {
            char temp = chars[left];
            chars[left++] = chars[right];
            chars[right--] = temp;
        }
    }
    
    /**
     * 反转每个单词
     */
    private void reverseWords(char[] chars, int n) {
        int i = 0, j = 0;
        
        while (i < n) {
            // 跳过前导空格
            while (i < j || (i < n && chars[i] == ' ')) i++;
            // 找到单词结尾
            while (j < i || (j < n && chars[j] != ' ')) j++;
            // 反转单词
            reverse(chars, i, j - 1);
        }
    }
    
    /**
     * 清理多余空格，返回最终字符串
     */
    private String cleanSpaces(char[] chars, int n) {
        int i = 0, j = 0;
        
        while (j < n) {
            // 跳过前导空格
            while (j < n && chars[j] == ' ') j++;
            // 保留单词间的一个空格
            while (j < n && chars[j] != ' ') {
                chars[i++] = chars[j++];
            }
            // 添加单词间空格
            while (j < n && chars[j] == ' ') j++;
            if (j < n) {
                chars[i++] = ' ';
            }
        }
        
        return new String(chars, 0, i);
    }
}

• 时间复杂度：O(n)，三次线性遍历
• 空间复杂度：O(1)（如可修改原数组）或 O(n)（需创建新数组）

文章来源:https://www.cnblogs.com/sevencoding/p/19285761
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！