反转字符串总结
1.反转字符串
这里是我们接触到的第一道反转字符串的例题
我们可以使用双指针来完成首位的反转
注意注意的是，这类题可能需要StringBulider这个容器
class Solution {
public void reverseString(char[] s) {
int left=0;
int right =s.length-1;
//快慢指针交换首位
while(left<right){//利用了a^b^b=a这一特性
s[left]^=s[right];
s[right]^=s[left];
s[left]^=s[right];
left++;
right--;
}
}
}
2.反转字符串 II
这道题只是增加了一些条件，实际上的思路还是不变的。
我们需要在for循环的条件上思考i变化的条件，以2k为一组，前k个我们反转，后k个保持不变即可。
严格把握住前k个的首位两项。
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();//将字符串转换为数组
for(int i = 0; i < ch.length; i += 2 * k){
int start = i;
//这里是判断尾数够不够k个来取决end指针的位置
int end = Math.min(ch.length - 1, start + k - 1);
//用异或运算反转
while(start < end){
ch[start] ^= ch[end];
ch[end] ^= ch[start];
ch[start] ^= ch[end];
start++;
end--;
}
}
return new String(ch);
}
}
3.替换空格
本题与前两道题有所不同，我们需要额外的辅助空间。然后遍历字符串，将空格替换为“%20”，其余的不变。全部塞进辅助空间内。
另外，我们需要注意equals的类型强转。
class Solution {
public String replaceSpace(String s) {
StringBuilder sb =new StringBuilder();
if(s==null) return null;
for(int i=0;i<s.length();i++){
//如果当前字符串时空格
if(" ".equals(String.valueOf(s.charAt(i)))){//注意将char类型转换位String类型
sb.append("%20");//将此位置添加为%20
}else{
sb.append(s.charAt(i));
}
}
return sb.toString();//注意：输出String类型，要将StringBuilder转换为String
}
}
4.翻转字符串里的单词
本题考查的知识点非常多
我们可以大体分为3步：
1.去掉空格
2.反转字符串（整体反转）
3.反转单词（局部反转）
class Solution {
/**
1.去掉空格(在前面、后面或者单词间包含多余的空格)
2.反转字符串
3.反转单词
*/
public String reverseWords(String s) {
StringBuilder sb= removeSpace(s);
reverseString(sb,0,sb.length()-1);
reverseEachWoed(sb);
return sb.toString();
}
//去掉空格
private StringBuilder removeSpace(String s){
StringBuilder sb =new StringBuilder();
int left =0;
int right = s.length()-1;
while(s.charAt(left)==' ') left++;//从前面去空格
while(s.charAt(right)==' ') right--;//从后面去空格
//去掉中间的空格
while(left<=right){
char ch = s.charAt(left);
if(ch!=' '||sb.charAt(sb.length()-1)!=' '){//核心代码
sb.append(ch);
}
left++;
}
return sb;
}
//反转字符串
private void reverseString(StringBuilder sb,int left,int right){
while(left<right){
char temp =sb.charAt(left);//临时存储
sb.setCharAt(left,sb.charAt(right));//将字符串中指定的位置的字符替换成目标字符
sb.setCharAt(right,temp);//将字符串中指定的位置的字符替换成目标字符
left++;
right--;
}
}
//反转单词
private void reverseEachWoed(StringBuilder sb){
int start = 0;
int end = 1;
int n = sb.length();
while (start < n) {
while (end < n && sb.charAt(end) != ' ') {
end++;
}
reverseString(sb, start, end - 1);
start = end + 1;
end = start + 1;
}
}
}
5.左旋转字符串
本题思路和上题大致相同
1.反转区间为前n的子串（局部）
2.反转区间为n到末尾的字串
3.反转整个字符串（整体）
class Solution {
/**
1.先局部反转（前n项）
2.再反转剩余的
3.再全体反转
*/
public String reverseLeftWords(String s, int n) {
StringBuilder sb =new StringBuilder(s);
int right=s.length()-1;
reverseString(sb,0,n-1);
reverseString(sb,n,right);
return sb.reverse().toString();
}
/**
反转字符串
*/
private void reverseString(StringBuilder sb,int left,int right){
while(left<right){
char temp = sb.charAt(left);//暂时存储当前第一个位置的字符
sb.setCharAt(left,sb.charAt(right));
sb.setCharAt(right,temp);
left++;
right--;
}
}
}