151. 翻转字符串里的单词_Java实现_空间O(1)详解

151. 翻转字符串里的单词_Java实现_空间O(1)详解

class Solution { /** * 151.翻转字符串里的单词 * 1、第一步去掉句子里的多余空格 * 2、翻转顺序 * 注：需要写一个方法，逆序指定范围的字符 * （1）整体逆序所有字符 * （2）再分别逆序每个单词 * @param s * @return */ /** * * //原地移动字符消除空格，i指针用来扫描，cur用来标识可以放字符的地方，每次放入cur位置之后，cur和i都要++（i在for循环条件里++） * //i经历过非空格后扫描到第一个空格，就放入cur位置，i连续第二次以后发现空格，就直接++，直到发现非空格字符，继续执行之前操作 * //space标记前一个字符是否为空格字符 * //i越界，扫描完成 */ public String reverseWords(String s) { //先保证s不为空 if(s == null) return null; char[] chars = s.toCharArray(); //标记最终有效字符串的长度 int len = 0; //当前用来存放字符的位置 int cur = 0; //前一个字符是否为空格字符 boolean space = true; //开头的空格会被忽略掉，cur不变，i持续++ （取值为true可理解为-1位置是空格） for (int i = 0; i < chars.length; i++) { if(chars[i] != ' '){ //非空格字符 chars[cur++] = chars[i]; space = false; }else if (space == false){ //chars[i]是空格字符，chars[i-1]是非空格字符 chars[cur++] = ' '; space = true; //标记前一个字符是空格字符 } } //cur有两种情况，第一种是，原字符串最后一个字符不是空格，则cur值就是有效串长 //第二种是，是空格，或者后面有多个空格，则cur只会比有效串长多1 len = space ? (cur - 1) : cur; /** * 1.对整一个有效字符串进行逆序 * 2. */ reverse(chars,0,len); //对每一个单词进行逆序 //前一个空格字符的位置（有-1位置有个假想的哨兵，就是一个假想的空格字符） int prevSpaceIdx = -1; for (int i = 0; i < len; i++) { if (chars[i] != ' ') continue; // i是空格字符的位置 reverse(chars,prevSpaceIdx + 1,i); prevSpaceIdx = i; } //翻转最后一个单词 reverse(chars,prevSpaceIdx+1,len); return new String(chars, 0, len); } //逆序，首尾交换 private static void reverse(char[] chars, int li, int ri){ ri--; while(li < ri){ char tmp = chars[li]; chars[li] = chars[ri]; chars[ri] = tmp; li++; ri--; } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。