反轉(zhuǎn)字符串
題目鏈接
https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html
思路
雙指針法摔笤，左右同時(shí)移動(dòng)
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--;
}
}
反轉(zhuǎn)字符串II
題目鏈接
https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html
思路
每隔2k交換前k個(gè)字符，重點(diǎn)在于如何處理最后一段字符串的交換
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();
}
翻轉(zhuǎn)字符串單詞
題目鏈接
思路
1、去掉空格霹菊，雙指針法
2近尚、翻轉(zhuǎn)整個(gè)字符串
3搜变、翻轉(zhuǎn)單詞
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;
}
左旋轉(zhuǎn)字符串
題目鏈接
思路
1艘蹋、局部旋轉(zhuǎn)
2车酣、整體旋轉(zhuǎn)
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);
}