今天是开始新的篇章：字符串。
题目链接：344. 反转字符串
状态：一次性AC，第一题还是比较容易的。有前面反转链表的双指针思路的记忆，于是就尝试了一下。结果一次就成功了，不错不错 ～
看到题目时第一想法：双指针，left从头开始向后遍历，同时right从尾开始向前遍历，然后每次就两者交换元素 直到left >= right的时候就不交换了。
344 反转字符串 流程
具体的完整代码如下：
class Solution { // Java
public void reverseString(char[] s) {
// two pointers
int left = 0;
int right = s.length - 1;
while(left < right){
// swap
char temp = 'a';
temp = s[left];
s[left] = s[right];
s[right] = temp;
left ++;
right --;
}
}
}
时间复杂度：O(n)。因为字符串内的每个字符都会被访问一次。
空间复杂度：O(1)。因为只用了两个指针和一个临时变量来存储字符。
题目链接：541. 反转字符串 II
状态：没有一次性AC，关于循环的部分还是卡了半天。但是最终还是做到AC了。
看到题目时第一想法：这道题应该是要用到上一题的交换方法。只不过呢，需要额外对遍历上做一些复杂的控制。根据题目的描述，很容易想到的是一个for循环遍历整个字符串，然后弄个count来计数，到了k就反转...但是也不难发现这种方法判断多，不仅麻烦还容易出错。于是进行画图思考🤔。思考过后发现他其实是每有2k个字符，就对前k个进行反转，最后不足2k的单独处理。于是我就想到了如下这种遍历方式：引入一个n来帮助控制i的位置。
int i = 0, n = 0; // i = n * k
for(i = n * k; i <= n * k + k - 1; i ++){
// reverse
// ...
// ...
n = n + 2;
}
这种做法确实能保证每次遍历的结果都是需要反转的部分，例如0 - (k-1), 2k - (3k-1), 4k - (5k-1) ... 但是每一小段反转之后还要拼接成最终的完整字符串，也是个很麻烦的。于是就看了解析，解析中给到的循环遍历的方式和反转的方式都非常的妙！
当循环遍历的时候，我们还是遍历整个字符串，但是由传统思维的 i++ 变成了 i+=2k，这样一来，每次就是对2k范围内对字符进行遍历了。然后reverse方法的参数也不同，不仅仅是传入一个char数组，同时还要传入反转的范围，即下标为i到下标为j的部分反转。由此，此题就引刃而解了，完整代码如下：
class Solution { // Java
public String reverseStr(String s, int k) {
char[] charAry = s.toCharArray();
// Reverse the first k characters of every 2k characters
for(int x = 0; x < charAry.length; x = x + 2 * k){
// If the remaining characters are less than 2k,
// but greater than or equal to k, reverse the first k characters
if(x + k <= charAry.length){
reverse(charAry, x, x + k - 1);
continue;
}
// If there are less than k characters left, reverse all the remaining characters.
reverse(charAry, x, charAry.length - 1);
}
return new String(charAry);
}
public void reverse(char[] charArray, int m, int n){
// reverse the charArray with the index from m to n
if(charArray.length - 1 <= 0 || m == n) return;
int i = Math.min(m,n);
int j = Math.max(m,n);
// char[] charArray = str.toCharArray();
while(i < j){
// swap
char temp = 'a';
temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
i ++;
j --;
}
}
}
时间复杂度：O(n)
空间复杂度：O(n)
