字符串第一天，加油！
344.反转字符串
解题思路：
设置两个指针在字符串的首尾，分别交换指针指向的字符串元素即可
Tipp：
java中交换数值有两种方法
- temp交换，常规，solution中的
- 位运算交换(异或运算)
可交换性：ab=ba
可结合性：abc=(ab)c=a(bc)
自身进行异或运算值为零：a^a=0
与 0 异或时结果不变：a^0=a
实现：
a ^=b;
b ^=a;
a ^=b;
class Solution {
public void reverseString(char[] s) {
int l = 0;
int r = s.length - 1;
char temp;
while (l < r) {
temp = s[l];
s[l] = s[r];
s[r] = temp;
l++;
r--;
}
}
}
541. 反转字符串II
解法一：
运用双指针进行翻转
1.左指针的位置为每次间隔2k
1.需要判断右指针的位置
·当 k<= 剩余字符串长度 <= 2k时，右指针在i+k-1；
·当 剩余字符串长度 <k 时，右指针直接在字符串末尾，因为将剩余的字符串都反转
class Solution {
public String reverseStr(String s, int k) {
int n = s.length();
char[] arr = s.toCharArray();
for (int i = 0; i < n; i += (2 * k)) {
//如果剩余字符大于等于k，但是小于2k时，右指针的点在i+k-1上
if (i + k <= n) {
reverse(arr, i, (i+k)-1);
} else {
reverse(arr, i, n-1);
}
}
// for (int i = 0; i < n; i += (2 * k)) {
// reverse(arr, i, Math.min(i + k, n) - 1);
// }
return new String(arr);
}
public void reverse(char[] s, int left, int right) {
//位运算实现翻转函数
while (left < right) {
s[left] ^= s[right];
s[right] ^= s[left];
s[left] ^= s[right];
left++;
right--;
}
}
}
/*复杂度分析：
时间复杂度为O(n)，n为s长度
空间复杂度为O(n)，因为将字符串转为了数组，变成了可以修改的字符串;java中String不可修改
*/
题目：剑指Offer 05.替换空格
解题思路：
依次读取s中的字符，检测是否为空格，如果是就添加%20；不是就读原字符
class Solution {
public String replaceSpace(String s) {
StringBuilder res = new StringBuilder();
for (char c : s.toCharArray()) {
if (c == ' ') {
res.append("%20");
} else {
res.append(c);
}
}
return res.toString();
}
}
/*
时间复杂度为O(n)，n为字符串长度
空间复杂度为O(n)，n为原字符长度+2*空格数量
*/
题目：剑指Offer58-II.左旋转字符串
解题思路：双指针
实现三次反转，运用自己写的reverse函数
1.先将0到n的字符翻转
2.再将n+1到末尾的字符反转
3.最后将整个字符翻转
其中翻转函数还是用双指针
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder res = new StringBuilder(s);
reverseString(res, 0, n-1);
reverseString(res, n, s.length()-1);
return res.reverse().toString();
}
public void reverseString(StringBuilder res, int left, int right) {
char temp;
while (left < right) {
temp = res.charAt(left);
res.setCharAt(left, res.charAt(right));
res.setCharAt(right, temp);
left++;
right--;
}
}
}
