本文主要是介绍面试经典算法150题系列-反转字符串中的单词,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
反转字符串中的单词
给你一个字符串 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" 解释:如果两个单词间有多余的空格,反转后的字符串需要将单词间的空格减少到仅有一个。
实现思路:
如果仅是实现字符串的反转比较容易,有两种实现思路:
第一种就是逆序输出。将字符串进行逆序遍历,每次遍历完一个单词后,则将其输出。边界条件就是字符串中间的空格。
第二种就是将字符串转换成列表。使用split进行分割,将每一个单词分隔开,构成一个字符串数组,然后逆序输出,即可得到反转的字符串。
然而,本题的难点在于对空格的处理,前后的空格,我们只需要使用trim()方法去掉,字符串中间的空格有的情况不只有有个,显然直接使用第一种思路和第二种思路都不太方便处理。这里我在堆字符串遍历前,对字符串进行了前后空格和中间的空格都进行了处理,将其分隔成为一个个规范的单词数组,然后逆序遍历数组,输出每一个单词并加上空格,遍历最后一个单词时不加空格。
实现代码:
public String reverseWords(String s) {// 1. 判空if (s == null || s.trim().isEmpty()) {return "";}// 2. 使用正则表达式去除空白字符并分割字符串String[] words = s.trim().split("\\s+");// 3. 使用StringBuilder来构建反转后的字符串StringBuilder reverseWords = new StringBuilder();// 4. 逆序遍历单词数组for (int i = words.length - 1; i >= 0; i--) {reverseWords.append(words[i]);// 在单词后添加空格,除了最后一个单词if (i > 0) {reverseWords.append(" ");}}// 5. 转换为String并去除尾部空格(如果有)return reverseWords.toString().trim();}
这里要注意的就是中间的空格处理,使用正则表达式`\\s+`将字符串分割成单词数组。`\\s+`表示匹配一个或多个空白字符,同时对于反转字符串操作使用了StringBuilder类,方便对字符串进行拼接操作(不懂这个类的可以在文章最后看知识补充)。
关于正则表达式,在最后一个单词的长度 一题中的最后有补充,大家可以看看,也可以顺便复习一下这一题。
实现思路2:多循环
首先将输入字符串转换为字符数组,然后从字符串的末尾开始向前遍历,找到每个单词的起始和结束位置,并将单词的字符逆序复制到结果数组中。如果遇到空格,则在逆序复制的单词后面添加一个空格。最后,使用new String
构造函数从结果数组中截取不包含最后一个空格的有效部分,作为最终的逆序字符串返回。
实现代码2:
public String reverseWords(String s) {// 将输入字符串转换为字符数组char[] s1 = s.toCharArray();// 创建一个新的字符数组,长度为原字符串长度加1,用于存储结果char[] s2 = new char[s1.length+1];// 初始化索引i为字符串的最后一个字符的位置int i = s.length() - 1;// 初始化num用于记录结果字符串中字符的数量int num = 0;// 外层循环,从字符串的末尾开始向前遍历while (i >= 0) {// 内层循环1,跳过前面的空格直到找到非空格字符while(i>=0 && s1[i] == ' ') i--;// 记录当前单词的末尾位置int r = i;// 内层循环2,找到当前单词的开始位置while (i >= 0 && s1[i] != ' ') i--;// 内层循环3,将当前单词的字符逆序复制到s2数组中for(int j = i+1; j<=r;j++){s2[num++] = s1[j];// 如果是单词的最后一个字符,则在逆序复制后添加一个空格if(j==r){s2[num++] = ' ';}}}// 如果num为0,说明原字符串只包含空格,返回原字符串if(num==0){return s;// 否则,使用substring方法从s2数组中截取结果字符串}else{return new String(s2,0,num-1); // 最后一个字符是空格,所以num-1}
}
第一种思路比较易于理解与实现,第二种思路执行效率相对高一些。
知识补充:
StringBuilder
StringBuilder
是一个在Java中用于操作字符串的类,它提供了一种可变的字符序列,可以高效地进行字符串的拼接、插入、删除等操作。与String
类相比,StringBuilder
的主要优点是它允许在字符序列上进行修改,而不需要每次修改都创建一个新的字符串对象。
以下是StringBuilder
的一些关键特性和常用方法:
-
可变性:
StringBuilder
对象的内容可以被修改,这与String
类形成对比,后者是不可变的。 -
线程安全性:
StringBuilder
不是线程安全的。如果多个线程同时访问一个StringBuilder
对象,而至少有一个线程写入该对象,那么应该通过同步或者使用StringBuffer
(它是StringBuilder
的线程安全版本)来确保线程安全。 -
构造函数:
StringBuilder
提供了多种构造函数,可以创建一个空的StringBuilder
对象,或者包含一个初始字符串的StringBuilder
对象。 -
常用方法:
append(Object obj)
:将指定对象的字符串表示形式追加到此字符序列的末尾。insert(int offset, Object obj)
:在指定位置插入指定对象的字符串表示形式。delete(int start, int end)
:删除从start到end(不包括end)的子序列。reverse()
:将字符序列反转。substring(int start)
或substring(int start, int end)
:返回一个新字符串,它是此序列的子序列。toString()
:返回一个新字符串,它包含此序列的字符。
-
性能:由于
StringBuilder
是可变的,因此在执行大量字符串操作时,它通常比String
更高效。 -
使用场景:当你需要在循环中构建字符串或者需要频繁修改字符串内容时,使用
StringBuilder
是一个很好的选择。
这篇关于面试经典算法150题系列-反转字符串中的单词的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!