【每日一题】151. 反转字符串中的单词

151. 反转字符串中的单词 - 力扣（LeetCode）

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

提示：

• 1 <= s.length <= 104
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

class Solution {
    public String reverseWords(String s) {
        StringBuffer sb = new StringBuffer(s);
        sb.reverse();
        int len = sb.length()+1;
        sb.append(" ");
        int right = 0;
        int left = 0;
        int flag = 0;
        while(right < len) {
            left = right;
            while(sb.charAt(right) != ' ' ) right++;
            if(right-flag == 1 && sb.charAt(flag)==' ') {
                sb.delete(flag,right);
                right--;
                len--;
                flag = right;
                continue;
            }
            int tmp = right-1;
            while(left <= tmp) {
                char ch = sb.charAt(left);
                sb.setCharAt(left,sb.charAt(tmp));
                sb.setCharAt(tmp,ch);
                left++;
                tmp--;
            }
            flag = right;
            right++;
        }
        System.out.println(sb.toString());
        return sb.toString().trim();
    }
}

         每日一题，今天是中等题。

        读完题。首先要说明一下，在Java中String类是常量，不能修改，所以博主这里不能使用O（1）的算法，但实际上思路是一样的，因为除了开了一个StringBuffer其他的没有使用其他多余的数据量（除了单个常量，但单个常量在大O渐进表示中是O（1））。所以思路其实是一样的。接下来就开始说吧。

        第一种思路就是通过空格，将每个单词分开，并反转每个单词，最后再合并起来。这个是可以的，但没有办法做到O（1）的空间复杂度，需要空间来存储每个单词。

        第二种思路就是先将整个字符串反转，而后逐个反转单词。博主采用的是整个方法。先将整个字符串反转。之后，给字符串最后再添加一个空格，防止最后没有空格，便于处理。而后就是处理反转的问题了。right用来先行，left用于后面，right一旦碰到空格，就说明这个单词结束了，需要对这个单词反转，而left由于等于还没出发的right，所以，此时的left指向的就是需要反转单词的首字母，反转的最后就是right-1，空格不反转，但不能改right的值，所以需要一个tmp来标识，再对去修改。但有可能一个单词之间不止一个空格，这时候就需要另一个标记量flag，在循环的最后，right会+1，就是下一个单词的开头，所以使用flag记录right还没+1的状态，也就是处于空格时的状态。right+1之后再进入循环，如果循环完，right-flag==1并且flag位置是空格，那么就说明此时两个单词之间空格多出来了，直接删除，但删除完len和right并不会改变。所以需要手动减，并且此时空格的情况就无需往后了，直接continue即可。

        大致思路既是如此，运行结果如下：