反转字符串
题目链接
https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html
思路
双指针法，左右同时移动
public void reverseString(char[] s) {
int l = 0, r = s.length - 1;
while(l < r) {
char tmp = s[l];
s[l] = s[r];
s[r] = tmp;
l++;
r--;
}
}
反转字符串II
题目链接
https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html
思路
每隔2k交换前k个字符，重点在于如何处理最后一段字符串的交换
public String reverseStr(String s, int k) {
char[] str = s.toCharArray();
for(int i = 0; i < s.length();i = i +2*k) {
int l = i;
int r = Math.min(i + k -1,s.length() - 1);
while(l < r ) {
char tmp = str[l];
str[l] = str[r];
str[r] = tmp;
l++;
r--;
}
}
return new String(str);
}
替换空格
题目链接
https://programmercarl.com/%E5%89%91%E6%8C%87Offer05.%E6%9B%BF%E6%8D%A2%E7%A9%BA%E6%A0%BC.html
思路
从后往前遍历
public String replaceSpace(String s) {
char[] a = s.toCharArray();
StringBuilder str = new StringBuilder();
for(int i = 0;i< s.length() ;i++) {
if(a[i] == ' ') {
str.append("%20");
} else {
str.append(a[i]);
}
}
return str.toString();
}
翻转字符串单词
题目链接
思路
1、去掉空格，双指针法
2、翻转整个字符串
3、翻转单词
public String reverseWords(String s) {
char[] res = removeExtraSpaces(s.toCharArray());
reverse(res, 0, res.length - 1);
reverseEachWord(res);
return new String(res);
}
private void reverseEachWord(char[] res) {
int start = 0;
for(int i =0; i <= res.length;i++) {
if( i == res.length || res[i] == ' ') {
reverse(res, start, i - 1);
start = i + 1;
}
}
}
public void reverse(char[] chars, int left, int right) {
if (right >= chars.length) {
System.out.println("set a wrong right");
return;
}
while (left < right) {
chars[left] ^= chars[right];
chars[right] ^= chars[left];
chars[left] ^= chars[right];
left++;
right--;
}
}
public char[] removeExtraSpaces(char[] res) {
int l = 0,f = 0;
while(f < res.length) {
if(res[f] != ' ') {
if(l != 0) {
res[l++] = ' ';
}
while(f < res.length && res[f] != ' ') {
res[l++] = res[f++];
}
}
f++;
}
char[] newChars = new char[l];
System.arraycopy(res, 0, newChars, 0, l);
return newChars;
}
左旋转字符串
题目链接
思路
1、局部旋转
2、整体旋转
public String reverseLeftWords(String s, int n) {
char[] res = s.toCharArray();
int l = 0;
for(int i = n -1;i>l ;i--) {
res[i] ^= res[l];
res[l] ^= res[i];
res[i]^= res[l];
l++;
}
int h = s.length() - 1;
for(int i = n ;h > i ;i++) {
res[i] ^= res[h];
res[h] ^= res[i];
res[i]^= res[h];
h--;
}
h = s.length() - 1;
for(int i = 0 ;h > i ;i++) {
res[i] ^= res[h];
res[h] ^= res[i];
res[i]^= res[h];
h--;
}
return new String(res);
}