代码随想录算法训练营Day8|541. 反转字符串II、替换数字、151.翻转字符串里的单词、卡码网：55.右旋转字符串

1.这道题刚开始把题意理解错了，以为对于任意长度的字符串都只反转[0,k-1]以及[2k,3k-1]区间的值。
2.但实际上是要把一个字符串分成若干长度为2k的小区间，反转前[0,k-1]的字符串，[k,2k-1]保持不变;
3.如果有一个区间字符串字符个数小于k，则全部反转。
4.双指针法实现反转比用索引更方便

class Solution {public String reverseStr(String s, int k) {StringBuilder res = new StringBuilder(s);for(int i=0;i<=s.length()-1;i+=2*k){//每2k长度的区间操作一次if(s.length() >= i+k) reverse(res,i,i+k-1);//如果s字符串长度大于等于i+k，[i,i+k-1]区间反转，[i+k,i+2k-1]不变else reverse(res,i,s.length()-1);//如果s字符串长度小于i+k，在[i,s.length()-1]区间上全部反转}return  res.toString();}public StringBuilder reverse(StringBuilder s,int startIndex,int endIndex){//双指针法实现反转比用索引更方便int left = startIndex;int right = endIndex;while(left<right){char temp = s.charAt(left);s.setCharAt(left,s.charAt(right));s.setCharAt(right,temp);left++;right--;}return s;}
}

import java.util.*;
class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String target = scanner.nextLine();
System.out.print(method(target));
}
public static String method(String str){
StringBuilder sb = new StringBuilder();
for(int i=0;i<str.length();i++){
if(Character.isDigit(str.charAt(i))) sb.append(“number”);
else sb.append(str.charAt(i));
}
return sb.toString();
}
}

这道题是ACM格式的，趁这个机会练习一下。要注意以下几点：
1.类名必须为Main，同时要有主函数。
2.要有输入输出，输出要打印
3.需要自己导入必要的包

补充知识点：
Character.isDigit()判断字符是否为数字

import java.util.*;
class Main{public static void main(String[] args){Scanner scanner = new Scanner(System.in);String target = scanner.nextLine();System.out.print(method(target));}public static String method(String str){StringBuilder sb = new StringBuilder();for(int i=0;i<str.length();i++){if(Character.isDigit(str.charAt(i))) sb.append("number");else sb.append(str.charAt(i));}return sb.toString();}
}

方法一：自己想的方法，思路比较简单，但是调试了好久，贴在这里梳理一下思路。

class Solution {public String reverseWords(String s) {ArrayList<StringBuilder> list = new ArrayList<StringBuilder>();//存储遍历出来的一个个的无空格的单词StringBuilder sb = new StringBuilder(s);//先将String转为StringBuilder类型，便于操作StringBuilder res = new StringBuilder();//存储最终返回的结果int i = 0;//初始化指针while(sb.charAt(i) == ' ') i++;//将指针移动到有单词的位置上while(i < s.length()){//遍历sStringBuilder sbOne = new StringBuilder();//存储一个单词的StringBuilderwhile(s.charAt(i) != ' '){//不是空格的时候sbOne.append(s.charAt(i));//字符持续加入sbOne,直到遇到空格i++;if(i >= s.length()) break;//大于等于s.length()，也结束循环}list.add(sbOne);//此时指针i在空格上或者在最后一个字符的下一位，先保存sbOneif(i >= s.length()) break;//如果在最后一个字符的下一位，直接结束循环while(s.charAt(i) == ' '){//如果是空格就持续向下移动，直到遇到单词i++;if(i >= s.length()) break;//大于等于s.length()，也结束循环}}//此时list已经按序存储了所有满足条件的单词for(int j=list.size()-1;j >= 1;j--){res.append(list.get(j) + " ");}//除了第一个单词，其他都是一个单词一个空格地加入resres.append(list.get(0));//第一个单词直接加入，没有空格return res.toString();}
}

方法二：
卡哥的方法，先整体反转，再去除多余的空格，最后再对每一个单词反转。卡哥要求空间复杂度为O（1），那方法一就不符合要求了。

class Solution {public String reverseWords(String s) {int length = s.length();StringBuilder sb = new StringBuilder(s);reverse(sb,0,length-1);removeExtraSpace(sb);reverseOneWord(sb);return sb.toString();}public static void reverse(StringBuilder s,int startIndex,int endIndex){//双指针法实现反转int left = startIndex;int right = endIndex;while(left < right){char temp = s.charAt(left);s.setCharAt(left,s.charAt(right));s.setCharAt(right,temp);left++;right--;}}public static void reverseOneWord(StringBuilder s){//单个单词反转，对于除最后一个单词之外的单词//快指针下一个为空说明此时fast处于单词尾部，[slow,fast]之间的字符反转//slow变为fast+2,因为要跳过空格//最后一个单词直接[slow,s.length()-1]反转int slow = 0;for(int fast = 0;fast < s.length()-1;fast++){if(s.charAt(fast+1) != ' ') continue;else{reverse(s,slow,fast);slow = fast+2;}}reverse(s,slow,s.length()-1);}public static void removeExtraSpace(StringBuilder s){int slow = 0;boolean need=false;for(int fast = 0; fast < s.length();fast++){if(s.charAt(fast) != ' '){s.setCharAt(slow++,s.charAt(fast));//当快指针遇到了单词的第一个字母，说明slow指针放置完这个单词之后还要再放一个' 'need = true;}else if(need){//当遇到了空格(一个单词遍历结束)并且need为true，将slow指针指向的位置置为' 's.setCharAt(slow++,' ');   need = false;}}//但是如果原始字符串本身以空格结尾，倒数第一个单词遍历完之后need还是true的，因此新字符串还会添一个' '，这个时候应该长度置为slow-1if(s.charAt(s.length()-1) == ' ') s.setLength(slow-1);//如果原始字符串本身不以空格结尾，新字符串不会添' '，直接s.setLength(slow);else s.setLength(slow);}
}

方法三：
之前写的一个方法，用字符数组做的，时间复杂度和空间复杂度都很低。
这里的反转单个单词的方法非常棒：

    public void keyReverse(char[] chars){//start索引是随着end索引移动而移动的int start = 0;//这里end <= chars.length，end最大可以到chars.length，对应的是reverse(chars,start,end-1);for(int end = 0;end <= chars.length;end++){if(end == chars.length || chars[end] == ' '){reverse(chars,start,end-1);start = end+1;}}}

class Solution {public String reverseWords(String s) {char[] chars = s.toCharArray();char[] charsNew = trim(chars,chars.length);reverse(charsNew,0,charsNew.length-1);keyReverse(charsNew);return String.valueOf(charsNew);}public void keyReverse(char[] chars){//start索引是随着end索引移动而移动的int start = 0;//这里end <= chars.length，end最大可以到chars.length，对应的是reverse(chars,start,end-1);for(int end = 0;end <= chars.length;end++){if(end == chars.length || chars[end] == ' '){reverse(chars,start,end-1);start = end+1;}}}//该方法用于反转指定索引的字符串public void reverse(char[] chars,int start,int end){while(start < end){char temp = chars[start];chars[start] = chars[end];chars[end] = temp;start++;end--;}}public char[] trim(char[] chars,int length){//该方法用于去除字符串两头的空格以及单词之间多余的空格int slow = 0;for(int fast = 0;fast< length;fast++){if(chars[fast] != ' '){//遇到非空说明slow后面要加空格了if(slow != 0) chars[slow++] = ' ';//直到找到下一个单词首字母（非空）while(fast < chars.length && chars[fast] != ' '){chars[slow++] = chars[fast++];}}}//创建一个用于存储信数组的newChars，可以将多余部分去除char[] newChars = new char[slow];//chars为复制源，起始索引，目标数组，起始索引，要复制的元素数量System.arraycopy(chars, 0, newChars, 0, slow); return newChars;}
}

这道题目很简单，但是解决了我长久以来关于ACM模式的一个困惑：连续用scanner向系统键入两个量的时候，会报错。
因为：如下面代码所示， int num = scanner.nextInt();输入一个整数之后还要键入一个回车，这个回车会被当成紧接着要输入的scanner.nextLine();导致在执行下面代码中出错。因此需要键入一个scanner.nextLine();消耗掉回车。
scanner.nextLine(); // 消耗掉nextInt后的换行符

import java.util.*;
class Main{public static void main(String[] args){Scanner scanner = new Scanner(System.in);int num = scanner.nextInt();scanner.nextLine();//消耗掉回车String str = scanner.nextLine();int len = str.length();StringBuilder sb = new StringBuilder();for(int i = len-num;i < len;i++){sb.append(str.charAt(i));}for(int i = 0;i<len-num;i++){sb.append(str.charAt(i));}System.out.print(sb.toString());}
}