剑指Offer（四十四）-- 翻转单词序列（不调用API）

秦怀杂货店

发布于 2022-02-15 14:00:31

2630

发布于 2022-02-15 14:00:31

文章被收录于专栏：技术杂货店

Github仓库地址：https://github.com/Damaer/CodeSolution 笔记地址：https://damaer.github.io/CodeSolution/ 仓库介绍：刷题仓库：CodeSolution

题目描述

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

示例注意：引号内部才是输入的内容

输入

"You are a cool boy."

输出

"boy. cool a are You"

思路以及解答

前面已经讲过使用JDK的api切割字符串，以及使用堆栈实现倒序的方法，这里介绍的，是一个原生的方法。

首先判断字符串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;
    }
}

上面的做法，在遍历寻找单词的时候，相当于遍历完了一次字符串，将字符串拼接到结果字符串的时候，也相当于遍历完了一次字符串，假设字符串的长度为n，则需要2n次处理，也就是时间复杂度为O(n)。

【作者简介】：

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

平日时间宝贵，只能使用晚上以及周末时间学习写作 - END -

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-02-24，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法