Leetcode——151.反转字符串中的单词
题解一
思路
最开始的想法是把一个字符串分为字符串数组,但是不知道一共有几个单词(当时没想起来split()),所以选择了用ArrayList储存字符串,在输出时没有考虑ArrayList可以存储空字符串,所以最开始的输出不正确,改进之后正确了。
代码
class Solution {
public String reverseWords(String s) {
List<String> list = new ArrayList<>();
int tag = 0;
for(int i = 0; i < s.length(); i++){
if(i == s.length() - 1 && s.charAt(i) != ' '){
list.add(s.substring(tag));
}
if(s.charAt(i) == ' '){
list.add(s.substring(tag,i));
tag = i + 1;
}
}
String res = "";
for(int i = list.size() - 1; i >= 0; i--){
if(!list.get(i).isEmpty()) res += list.get(i) + " ";
}
res = res.trim();
return res;
}
}
总结
对字符串还是不够熟练,有好多方法在用的时候想不起来
题解二
思路
首先用trim()方法将s前后的空格消掉,然后再用split()函数识别多个连续空格,在一个或多个连续空格处分开,用字符串数组存储,再用Collections.reverse()进行颠倒,然后再用join()函数用空格做间隔输出。
代码
class Solution {
public String reverseWords(String s) {
String[] str = s.trim().split("\\s+");
List<String> list = Arrays.asList(str);
Collections.reverse(list);
return String.join(" ",list);
}
}
总结
用到很多String的内置函数,非常简洁。
也学习到了很多新知识,比如trim()、split()、asList()、Collections类、\\s+正则表达式。其中trim()和split()就不多说了
asList()
通过asList()得到的列表,不能进行add()和remove()操作,但可以进行set()操作,这也是为什么虽然这个方法也新建了动态数组,但是并没有增加空间复杂度(是String[]增加了这个方法的空间复杂度)。Arrays.asList() 返回的 List 实际上是一个基于数组的视图(view),即它并没有复制数组的内容,而是直接操作原数组的引用。这也是为什么他不能进行add()和remove()操作,因为这里的List是固定大小的,
\\s+
第一次使用正则表达式,用的时候就搞不懂这里为什么是\\双反斜杠,说说我自己的理解。\n,\t 这种\是转义符。\\s里的第一个\代表转义符,告诉Java这里要转义,而第二个\是正则表达式里的\,和s是一起的,\s表示正则中的空白字符。而\n,\t并不是正则表达式,所以不需要用\\
题解三
思路
首先将整个字符串变成“标准”字符串(即前后无空格,相邻单词间只有一个空格),然后将整个字符串倒转,最后分别将字符串的每个单词再分别倒转。
代码
class Solution {
public String reverseWords(String s) {
StringBuilder sb = removeSpace(s);
reverseString(sb, 0, sb.length()-1);
reverseEachWord(sb);
return sb.toString();
}
//1.除去多余空白符
public StringBuilder removeSpace(String s){
int start = 0;
int end = s.length() - 1;
StringBuilder sb = new StringBuilder();
while(s.charAt(start) == ' '){
start++;
}
while(s.charAt(end) == ' '){
end--;
}
while(start <= end){
if(s.charAt(start) != ' ' || sb.charAt(sb.length() - 1) != ' '){
sb.append(s.charAt(start));
}
start++;
}
return sb;
}
//2.倒转整个字符串
public void reverseString(StringBuilder sb, int start, int end){
while(start <= end){
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
//3.分别倒转字符串中的每个单词
public void reverseEachWord(StringBuilder sb){
int start = 0;
int end = 1;
int length = sb.length();
while(start < length){
while(end < length && sb.charAt(end) != ' '){
end++;
}
reverseString(sb, start, end - 1);
start = end + 1;
end = start + 1;
}
}
}
总结
最后这种题解,只需新建一个新的StringBuilder类型对象,然后在该StringBuilder进行修改,不需要额外开辟数组或集合,空间复杂度低。
就是太复杂了!!学习过后复现都很难!!!
番外:
今天用了StringBuilder,昨天使用了StringBuffer,二者的区别是StringBuffer的方法使用synchronized修饰,具有线程安全的特点,但是相应的响应速度就更慢一些,看在哪里使用