每天一道leetcode151-反转字符串里的单词
- 2019 年 10 月 4 日
- 筆記
昨天的题解
题目
每天一道leetcode151-反转字符串里的单词 分类：字符串
题目详述
给定一个字符串，逐个翻转字符串中的每个单词。
示例:
输入: "the sky is blue", 输出: "blue is sky the". 说明:
无空格字符构成一个单词。 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
题目详解
思路
- 见到这道题，我第一思想就是先剔除掉空格，然后反转整个字符串，abc hef反转完就是feh cba 然后在依次反转每个字符串feh反转完就hef cba反转完就是abc,然后连接起来就是def abc完成反转
- 剔除空格的思路，是先剔除首部和尾部的空格，然后对于中间的空格，找到的话只添加一个空格，直到找到下一个单词；abc def(隔了3个空格),abc不是空格，就加到result字符串里，然后直到了第一个空格，result就加一个空格，然后循环一直往下遍历，直到找到不是空格的d然后再把d加到字符串里面（ef不是空格也依次加到result里面），最后就得到了abc def剔除掉了空格
代码(安卓机代码可以移动，苹果机不行，最近我在寻找一个新的代码排版，PC端打开没有问题）
先放个图片，代码排版有问题的看图片
test.png
public class Solution { public String reverseWords(String s) { if(s.equals("")) return s; if(s.equals(" ")) return ""; s = deleteSpace(s); s = reverse(s); String [] list = s.split(" "); String result = ""; for(int i=0;i<list.length-1;i++) { result += reverse(list[i]) + " "; } result += reverse(list[list.length - 1]); return result; } public String reverse(String s) { char [] charArray = s.toCharArray(); int i=0;int j=charArray.length - 1; while(i < j) { char temp = charArray[i]; charArray[i] = charArray[j]; charArray[j] = temp; i++; j--; } return String.valueOf(charArray); } public String deleteSpace(String s1) { char [] charArray = s1.toCharArray(); int begin = 0;int end = s1.length() - 1; while(begin < charArray.length && charArray[begin] == ' ') begin++; while(end >= 0 && charArray[end] == ' ') end--; String temp = ""; while (begin <= end) { if(charArray[begin] != ' ') { temp += charArray[begin]; begin++; }else { temp += ' '; while (charArray[begin] == ' ') { begin++; } } } return temp; } }
代码讲解
- 32-55行就是思路上说的剔除空格的实现。
- 18-31行就是反转字符串
- 7-8行就是先剔除空格，然后反转字符串，11-14行就是对于每个字符串都依次反转，然后拼接起来
结果
结果.png 超时了尴尬
AC代码
public class Solution { public String reverseWords(String s) { if (s == null || s.length() == 0) { return ""; } String[] array = s.split(" "); String str = ""; for (int i = array.length - 1; i >= 0; --i) { if (!array[i].equals("")) { if (str.length() > 0) { str += " "; } str += array[i]; } } return str; } }
代码讲解
- 不AC就换种思路，不反转字符串了！
- 6行先按照“ ”空格分开（这个很强，会把所有的空格变成一个“”空字符串！，然后把一个个单词分开，abc dgh fgh 分成abc和dgh和fgh）
- 然后从后往前依次遍历，9行就是判断是不是空白字符串，因为split会把空格变成空字符串。所以会把空白字符串跳过！
- 13行就是不是空字符串加上分开的字符串，（abc和dgh和fgh这些）
- 最后AC了
