151. 反转字符串中的单词
151. 反转字符串中的单词
分析
其实这个题的思路很简单，先移除多余空格，然后反转整个字符串，再反转单词对应的字符串。思路不难想到，但是想在 20 分钟内，在没有 IDE 的情况下没有错误的写出来，还是有难度的。
反转整个字符串这一步我们就不说了，跟 344. 反转字符串 一模一样，移除多余空格和反转字符串中的单词写起来还是有一点难度的
移除空格
移除空格部分的代码跟 27. 移除元素 的方法其实是一样的，就是双指针法。
常规的方法是先移除头部的空格，再移除尾部的空格，最后移除中间部分的空格，去除中间空格的时候，首先判断当前 fast 指针指向的字符，是不是空格，如果不是，则说明是目标字符，同时移动快慢指针，如果是，则查看上一个确定的字符（slow 指向的字符）是不是空格，如果不是，则也是目标字符，同时移动快慢指针，如果是，说明当前是连续空格字符，不是目标字符。
// 移除空格
public String removeSpace(char[] chars){
// 还是用双指针法
int left = 0, right = chars.length-1;
// 移除头部的空格
while(chars[left]==' '){
left++;
}
// 移除尾部的空格
while(chars[right]==' '){
right--;
}
// 此时 left 和 right 指向的都是不为空格的字符
// slow 指的是下一个要插入的位置
int slow =left+1;
// fast 指向的是下一个需要检查的位置
int fast =left+1;
while(fast<=right){
// 如何移除中间的空格呢？
// 如果当前遍历字符不是空格，则同时移动快慢指针，
// 如果当前遍历字符是空格，而且上一个确定的字符不是空格，则同时移动快慢指针，
// 如果当前遍历字符是空格，而且上一个确定的字符也是空格，则仅移动快指针，即跳过此字符。
if(chars[fast]!=' '||chars[slow-1]!=' '){
chars[slow]=chars[fast];
slow++;
fast++;
}else{
fast++;
}
}
// 此时slow指的是下一个位置的索引，copyOfRange的第三个参数指向的索引刚好是排除的。
return new String(Arrays.copyOfRange(chars, left, slow));
}
其实也可以不用分三步，可以一步到位，但是比较难想
public String removeSpace(char[] chars){
int slow = 0, fast = 0;
while (fast < chars.length) {
// 如果当前字符是空格，而且
// 这是第一个字符或是最后一个字符，那肯定都是跳过
// 这个 ' ' == chars[fast + 1] 是为了处理末尾连续多个空格
if(' ' == chars[fast] && (fast == 0 || fast==chars.length-1 || ' ' == chars[fast + 1] || slow == 0 || ' ' == chars[slow - 1])){
fast++;
}else{
chars[slow] = chars[fast];
fast++;
slow++;
}
}
// 此时slow指的是下一个位置的索引，copyOfRange的第三个参数指向的索引刚好是排除的。
return new String(Arrays.copyOfRange(chars, 0, slow));
}
另一种方式，直接对比
public char[] clearSpace(char[] raw){
char[] result = new char[raw.length];
// 指向result中下一个插入的位置
int nextValIndex = 0;
for(int i=0;i<raw.length;i++){
if(nextValIndex==0 && raw[i]==' '){
continue;
}
//去除中间空格
if(raw[i]==' ' && result[nextValIndex-1] == ' '){
continue;
}
result[nextValIndex] = raw[i];
nextValIndex++;
}
// 去除末尾的空格
if(result[nextValIndex-1] == ' '){
nextValIndex--;
}
// 从 0 开始，不包含 nextValIndex
return Arrays.copyOfRange(result,0,nextValIndex);
}
其实去除空格
反转单词
反转单词最重要的是找到待反转的单词的起点和重点，
如果上一个字符没有或者上一个字符是空格，那么当前就是单词的起点
如果当前字符不为空格，但是是字符串的末尾，或者不是末尾且下一个字符是空格，那么当前就是单词的末尾
public String reverseWordInStr(char[] chars) {
char lastChar = 0;
int wordStart = 0, wordEnd = 0;
for (int i = 0; i < chars.length; i++) {
// 如果lastChar不存在或者lastChar是空格，当前就是单词的起点
if ((lastChar == 0 || ' ' == lastChar)) {
wordStart = i;
}
// 如果当前不是空格，下一个是空格，或者当前就是字符串的末尾了
if (' ' != chars[i] && (i == chars.length - 1 || ' ' == chars[i + 1])) {
wordEnd = i;
// 开始反转
for (; wordStart < wordEnd;) {
char temp = chars[wordStart];
chars[wordStart] = chars[wordEnd];
chars[wordEnd] = temp;
wordStart++;
wordEnd--;
}
wordStart = 0;
wordEnd = 0;
}
lastChar = chars[i];
}
return new String(chars);
}
然后我找到一种更简单的思路，
因为我们前面已经去掉了空格，所以现在字符串中的空格就都是单词间的空格，因此我们只需要记录空格的位置，就可以确定单词的范围了
public char[] reverseWords(char[] raw){
int lastSpaceIndex=-1;
for(int i=0;i<raw.length;i++){
if(raw[i]== ' ' || i==raw.length-1){
// 开始反转 left 到 right-1
int left = lastSpaceIndex!=-1?lastSpaceIndex+1:0;
int right = -1;
if(raw[i]== ' '){
right = i-1;
lastSpaceIndex = i;
}else if(i==raw.length-1){
right = i;
}
while(left<right){
char temp = raw[right];
raw[right] = raw[left];
raw[left] = temp;
left++;
right--;
}
}
}
return raw;
}
解题
class Solution {
public String reverseWords(String s) {
// 反转两次即可
// 先把整个字符串反转，然后再把单词反转
char[] chars = s.toCharArray();
String cleanStr = removeSpace(chars);
chars = cleanStr.toCharArray();
int left = 0, right = chars.length - 1;
for (; left < right;) {
char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
left++;
right--;
}
// 开始反转单词
return reverseWordInStr(chars);
}
public String removeSpace(char[] chars) {
// 还是用双指针法
int left = 0, right = chars.length - 1;
// 移除头部的空格
while (chars[left] == ' ') {
left++;
}
// 移除尾部的空格
while (chars[right] == ' ') {
right--;
}
// 此时 left 和 right 指向的都是不为空格的字符
// slow 指的是下一个要插入的位置
int slow = left + 1;
// fast 指向的是下一个需要检查的位置
int fast = left + 1;
while (fast <= right) {
// 如何移除中间的空格呢？
// 如果当前遍历字符不是空格，则同时移动快慢指针，
// 如果当前遍历字符是空格，而且上一个确定的字符不是空格，则同时移动快慢指针，
// 如果当前遍历字符是空格，而且上一个确定的字符也是空格，则仅移动快指针，即跳过此字符。
if (chars[fast] != ' ' || chars[slow - 1] != ' ') {
chars[slow] = chars[fast];
slow++;
fast++;
} else {
fast++;
}
}
// 此时slow指的是下一个位置的索引，copyOfRange的第三个参数指向的索引刚好是排除的。
return new String(Arrays.copyOfRange(chars, left, slow));
}
public String reverseWordInStr(char[] chars) {
char lastChar = 0;
int wordStart = 0, wordEnd = 0;
for (int i = 0; i < chars.length; i++) {
// 如果lastChar不存在或者lastChar是空格，当前就是单词的起点
if ((lastChar == 0 || ' ' == lastChar)) {
wordStart = i;
}
// 如果当前不是空格，下一个是空格，或者当前就是字符串的末尾了
if (' ' != chars[i] && (i == chars.length - 1 || ' ' == chars[i + 1])) {
wordEnd = i;
// 开始反转
for (; wordStart < wordEnd;) {
char temp = chars[wordStart];
chars[wordStart] = chars[wordEnd];
chars[wordEnd] = temp;
wordStart++;
wordEnd--;
}
wordStart = 0;
wordEnd = 0;
}
lastChar = chars[i];
}
return new String(chars);
}
}
新版的思路，感觉更简单
public String reverseWords(String s) {
// 先去除前后和中间的多余空格
// 然后再将整个字符串反转，
// 然后再将单个的单词反转
char[] result = s.toCharArray();
char[] trimSpace = clearSpace(result);
int left =0,right=trimSpace.length-1;
while(left<right){
char temp = trimSpace[right];
trimSpace[right] = trimSpace[left];
trimSpace[left] = temp;
left++;
right--;
}
char[] resultChar = reverseWords(trimSpace);
return new String(resultChar);
}
public char[] clearSpace(char[] raw){
char[] result = new char[raw.length];
// 指向result中下一个插入的位置
int nextValIndex = 0;
for(int i=0;i<raw.length;i++){
if(nextValIndex==0 && raw[i]==' '){
continue;
}
if(raw[i]==' ' && result[nextValIndex-1] == ' '){
continue;
}
result[nextValIndex] = raw[i];
nextValIndex++;
}
if(result[nextValIndex-1] == ' '){
nextValIndex--;
}
// 从 0 开始，不包含 nextValIndex
return Arrays.copyOfRange(result,0,nextValIndex);
}
public char[] reverseWords(char[] raw){
int lastSpaceIndex=-1;
for(int i=0;i<raw.length;i++){
if(raw[i]== ' ' || i==raw.length-1){
// 开始反转 left 到 right-1
int left = lastSpaceIndex!=-1?lastSpaceIndex+1:0;
int right = -1;
if(raw[i]== ' '){
right = i-1;
lastSpaceIndex = i;
}else if(i==raw.length-1){
right = i;
}
while(left<right){
char temp = raw[right];
raw[right] = raw[left];
raw[left] = temp;
left++;
right--;
}
}
}
return raw;
}