leetcode151(翻转字符串里的单词)--Java语言实现

原创
07/09 15:49
阅读数 79

求:

给定一个字符串,逐个翻转字符串中的每个单词。

 

示例 1:

输入: "the sky is blue"
输出: "blue is sky the"
示例 2:

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
示例 3:

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。
 

说明:

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。
 

进阶:

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

 

题目链接: https://leetcode-cn.com/problems/reverse-words-in-a-string/

 

解:

1、使用库函数

字符串是一种ADT类型,底层实现是字符数组,如果使用C语言实现,这题会比较复杂。但是对于Java等高级语言来说,String是一种非常常用的类型,有很多的相关库函数可以直接调用。注意调用split函数时的正则匹配条件是:"\\s+",\\s表示空格、回车、换行等空白符,+号表示一个或多个,所以是对任意形式组成的空白的匹配。

时间复杂度:O(N)

空间复杂度:O(N)

public String reverseWords(String s) {
    StringBuilder retStrBuilder = new StringBuilder();
    String[] s1 = s.trim().split("\\s+");
    for (int i = s1.length - 1; i >= 0; i--) {
        retStrBuilder.append(s1[i].trim());
        if (i > 0) retStrBuilder.append(" ");
    }
    return retStrBuilder.toString();
}
public String reverseWords(String s) {
    String[] s1 = s.trim().split("\\s+");
    Collections.reverse(Arrays.asList(s1));
    return String.join(" ", s1);
}

2、双端队列

网上有看到使用Dequeue来做的,双端队列的思想很好,可以参考。

时间复杂度:O(N)

空间复杂度:O(N)

public String reverseWords(String s) {
    int left = 0, right = s.length() - 1;
    while (left <= right && s.charAt(left) == ' ') ++left;
    while (left <= right && s.charAt(right) == ' ') --right;
    Deque<String> d = new ArrayDeque();
    StringBuilder word = new StringBuilder();
    while (left <= right) {
        char c = s.charAt(left);
        if ((word.length() != 0) && (c == ' ')) {
            d.offerFirst(word.toString());
            word.setLength(0);
        } else if (c != ' ') {
            word.append(c);
        }
        ++left;
    }
    d.offerFirst(word.toString());
    return String.join(" ", d);
}

3、自定义函数实现

将字符串作为字符数组来处理,这种方式用C语言实现较好,能够看清字符串的底层逻辑,因为这题没什么意思,不在此给出相关代码。

时间复杂度:O(N)

空间复杂度:使用C语言等字符串可变的语言,最好可以达到O(1)。使用Java等字符串不可变的语言,最好可以达到O(N)

展开阅读全文
amp
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部