侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【模拟, 双指针】反转字符串中的单词

GabrielxD
2022-10-11 / 0 评论 / 0 点赞 / 16 阅读 / 903 字 / 正在检测是否收录...

题目

151. 反转字符串中的单词


给你一个字符串 s ,请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

**注意:**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。

示例 1:

输入:s = "the sky is blue"
输出:"blue is sky the"

示例 2:

输入:s = "  hello world  "
输出:"world hello"
解释:反转后的字符串中不能存在前导空格和尾随空格。

示例 3:

输入:s = "a good   example"
输出:"example good a"
解释:如果两个单词间有多余的空格,反转后的字符串需要将单词间的空格减少到仅有一个。

提示:

  • 1 <= s.length <= 10^4
  • s 包含英文大小写字母、数字和空格 ' '
  • s至少存在一个 单词

**进阶:**如果字符串在你使用的编程语言中是一种可变数据类型,请尝试使用 O(1) 额外空间复杂度的 原地 解法。

解题

方法一:API

思路

直接上 API,对字符串去除前后空格,根据空字符分割,翻转,最后拼接。

代码

class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ", wordList);
    }
}

方法二:模拟 双指针

思路

先把整个字符串翻转,然后再把每个单词翻转,翻转后去除多余空格,具体操作见代码注释。

代码

class Solution {
    char[] chs;

    public String reverseWords(String s) {
        int n = s.length();
        // 准备一个长度为 n+1 的字符数组
        chs = new char[n + 1];
        chs[0] = ' '; // 把第一个字符置为空格
        // 把字符串放进剩下的区域
        System.arraycopy(s.toCharArray(), 0, chs, 1, n);
        // 这样做的目的是: 在字符数组翻转后 空格就去到了末尾
        // 这样在给定字符串没有前导零时 循环处理单词的时候最后一个单词不用额外处理
        ++n;
        // 翻转字符串
        reverse(0, n - 1);
        int begin = 0, end = n - 1;
        // 找到第一个单词开始位置
        while (chs[begin] == ' ') ++begin;
        int oughtToEnd = n; // 每个单词应该结束的位置(只隔一个空格)
        // wordBegin: 每个单词现在的开始索引; oughtToBegin: 每个单词应该开始的位置
        for (int i = begin + 1, wordBegin = begin, oughtToBegin = 0; i < n; ++i) {
            // 遇到空格 单词结束
            if (chs[i] == ' ') {
                // 该单词现在的结尾索引
                int wordEnd = i - 1;
                // 翻转该单词
                reverse(wordBegin, wordEnd);
                // 根据oughtToBegin以及单词长度算出oughtToEnd
                oughtToEnd = oughtToBegin + wordEnd - wordBegin;
                // 把单词向前移动(去除多余空格)
                for (int offset = 0; offset <= wordEnd - wordBegin; ++offset) {
                    chs[oughtToBegin + offset] = chs[wordBegin + offset];
                }
                // 把单词原来的位置置为空格
                for (int j = oughtToEnd + 1; j <= wordEnd; ++j) chs[j] = ' ';
                oughtToBegin = oughtToEnd + 2;
                // 找到下一个单词的开头
                while (i < n && chs[i] == ' ') ++i;
                wordBegin = i;
            }
        }
        // 返回截断后面空格后的字符串
        return String.valueOf(chs).substring(0, oughtToEnd + 1);
    }

    void reverse(int left, int right) {
        for (; left < right; ++left, --right) {
            char tmp = chs[left];
            chs[left] = chs[right];
            chs[right] = tmp;
        }
    }
}
0

评论区