从零学算法151

151.给你一个字符串 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”
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

• 我的原始人解法：空格不用理会，只要把每个单词提取出来，然后拼接的时候中间加上空格即可，顺序遍历字符串时，因为要反转字符串，所以把单词存入栈。

•   public String reverseWords(String s) {s=s.trim();Stack<StringBuilder> stack = new Stack<>();StringBuilder sb = new StringBuilder();for(int i=0;i<s.length();i++){// 遇到空格就结算一次单词，所以提前 trim 了if(s.charAt(i)==' '){stack.push(sb);sb=new StringBuilder();}// 把空格都清完while(s.charAt(i)==' '){i++;}sb.append(s.charAt(i));// 最后一个单词别忘了加入栈if(i==s.length()-1)stack.push(sb);}sb = new StringBuilder();while(!stack.isEmpty()){sb.append(stack.pop());sb.append(" ");}return sb.toString().trim();}
  

• 他人解法1：思路大致一致，但是截取手段高明不少，用双指针指向每个单词首尾，从尾部开始遍历，头指针从后往前移动到空格时，头指针后一位到尾指针就为一个单词，类似于遇到空格就结算一次单词，所以也提前 trim 了。然后直接把单词加个空格拼接起来（最后结果也 trim 就行）。然后也一样让头指针继续往前移动，直到遇到字母（或者说直到把空格都跳过），更新尾指针，重复操作即可。

•   public String reverseWords(String s) {s=s.trim();StringBuilder sb = new StringBuilder();int end = s.length()-1,start=end;while(start>=0){while(start>=0 && s.charAt(start)!=' ')start--;sb.append(s.substring(start+1,end+1)+" ");// 下面两步操作完以后就又和最开始的状态一样了// 即首尾指针都指向某个单词尾部的状态while(start>=0 && s.charAt(start)== ' ')start--;end=start;}return sb.toString().trim();}
  

• 他人解法2：api调用大师，直接 split 然后就能拼接了

•   public String reverseWords(String s) {String[] strs = s.trim().split(" ");        // 删除首尾空格，分割字符串StringBuilder res = new StringBuilder();for (int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表if(strs[i].equals("")) continue;        // 遇到空单词则跳过res.append(strs[i] + " ");              // 将单词拼接至 StringBuilder}return res.toString().trim();               // 转化为字符串，删除尾部空格，并返回}