leet代码1816。截断句子
#java #leetcode #字符串 #interviewquestions

这是一个简单的problem on leet代码,说明为:

句子是单个单词的列表,这些单词被没有前导或尾随空间的单个空间隔开。每个单词仅由大写和小写英文字母组成(没有标点符号)。

例如,“ Hello World”,“ Hello”和“ Hello World Hello World”都是句子。

您得到了一个句子,还有一个整数k。您想截断s,以便仅包含第一个k的单词。截断后返回s。

约束:

1 <= s.length <= 500
k在范围内[1,s中的单词数]。
S仅由小写和大写英文字母和空间组成。
s中的单词被一个空间分开。
没有领先或落后的空间。

完成此操作有很多不同。您可以通过建造者或使用收集器来拆分字符串并连接所需的内容。

如果您不想将其拆分,没有太多的内存,并且希望更快地向前,您只需迭代字符串并添加字符串构建器,添加一个计数器并在完成后离开。让我们尝试第一个示例,然后与第二个示例进行比较:

class Solution {
    public String truncateSentence(String s, int k) {

        final String[] splittedS = s.split(" ");
        final StringBuilder response = new StringBuilder();

        response.append(splittedS[0]);

        for(int i=1;i<k;i++){
            response.append(" " + splittedS[i]);
        }

        return response.toString();
    }
}

运行时:2毫秒,截短句子的Java在线提交的50.49%的速度更快。

内存使用量:41.2 MB,不到Java在线提交的截短句子的41.55%。

在第一个示例中,我确实拆分了字符串,创建了一个字符串构建器,该构建器比仅串联多个字符串(由于字符串实例创建每个串联)更快,添加了第一个字符串,然后迭代了拆分和附加的空间。

在第二个示例中,我做了相同的操作

class Solution {
    public String truncateSentence(String s, int k) {


        // splitting the string
        final String[] splittedS = s.split(" ");

        // trimming the items that will not be used
        final String[] trimmedArray = Arrays.copyOfRange(splittedS, 0, k);

        // adding as stream and joining using space
        return Stream.of(trimmedArray).collect(Collectors.joining(" "));

        /* 
            one liner would be: 
            return Stream.of(Arrays.copyOfRange(s.split(" "), 0, k)).collect(Collectors.joining(" "));
        */        
    }
}

运行时:3毫秒,截短句子的Java在线提交的35.12%快。

内存用法:40.9 MB,不到Java在线提交的截短句子的71.04%。

您可以看到,看起来更简单,可以在一行中完成,但性能是不同的。

我将显示的最后一个示例基本上是没有分裂的,并且使用字符串构建器,我认为是最快的,因为没有记忆过多,但是这个想法是相同的。

class Solution {
    public String truncateSentence(String s, int k) {

        final StringBuilder response = new StringBuilder();
        int count = 0;

        for(int i=0;i<s.length();i++){
            final char c = s.charAt(i);
            if(' ' == c) {
                count++;
                if(count==k) break;
            }
            response.append(c);
        }
        return response.toString();
    }
}

运行时:1 ms,截短句子的Java在线提交的84.40%快。

内存用法:40.6 MB,不到Java在线提交的截短句子的91.06%。

所有示例均为o(n),由于列表的一次迭代,结果表明最后一个的速度更快,使用较少的内存。


就是这样!如果还有其他事情要讨论,请随时发表评论,直到下一篇文章! :)