【算法】反转字符串中的单词151

题目描述

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

代码实现

//反转字符串中的单词151    
public class ReverseWordsInAString151 {
	public static void main(String[] args){
		System.out.println(new Solution().reverseWords("  hello world  "));
	}
}

class Solution {
    public String reverseWords(String s) {
    	StringBuilder res = removeSpace(s);
        System.out.println(res);
    	reverse(res,0,res.length() - 1);
        System.out.println(res);
        reverseEachWord(res);
    	return new String(res);
    }

    //1. 去多余空格
    public StringBuilder removeSpace(String oriStr){
    	StringBuilder res = new StringBuilder();
    	int left = 0;
    	int right = oriStr.length() - 1;
    	char[] oriChar = oriStr.toCharArray();
    	//把前后空格去了
    	while(oriChar[right] == ' ') right--;
    	while(oriChar[left] == ' ') left++;

    	while (left <= right) {
    		char c = oriChar[left];
    		//去中间空格
    		if (c != ' ' || res.charAt(res.length() - 1) != ' ') {
    			res.append(c);
    		}
    		left++;
    		
    	}
    	return res;
    }
    //2. 整个str 的反转
    public void reverse(StringBuilder oriStr, int start, int end){
    	while(start < end){
    		char temp = oriStr.charAt(start);
    		oriStr.setCharAt(start++, oriStr.charAt(end));
    		oriStr.setCharAt(end--,temp);
    	}
    }
    //3. 单词的恢复
    public void reverseEachWord(StringBuilder oriStr){
    	
    	int start = 0;
    	int end = 1;
    	int len = oriStr.length();
    	while(start < len){
    		//找last
            //这个地方end++不能放在判断式里面，因为放在里面就是只要判断了就会自增，实际上
            //只有同时满足条件了才会自增。
    		while(end < len && oriStr.charAt(end) != ' ') end++;
    		reverse(oriStr, start, end - 1);
    		start = end + 1;
    		end = start + 1;
    	}
    }
}

个人总结

解题关键：

1. 只使用 O(1) 的空间复杂度
2. 可以用 StringBuilder
3. 记得分好步骤：1. 去空格； 2. 全颠覆； 3. 恢复单词；

我对于++这个运算符的理解又上一层楼咯。

---

2023/04/01

我觉得这个题目有点东西的，所以第二天又刷了一次。

这次在++ 这种自增运算符处理更优雅了，但是我发现我还有两个弱点。

1. char老是写成chat
2. 对一下Java基础语法不太熟练。比如setCharAt()里面是两个参数，index 和 updataValue。