力扣算法系统刷题题解记录二（字符串、双指针法、栈与队列）

前言

参考顺序和资料：《代码随想录》
二刷要认真做笔记啦，加油！
笔记模板：

#### 解题思路
 #### 示意图
 #### 代码

四、字符串

344.字符串反转

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：
输入：[“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]

解题思路

如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数。

毕竟面试官一定不是考察你对库函数的熟悉程度， 如果使用python和java 的同学更需要注意这一点，因为python、java提供的库函数十分丰富。

如果库函数仅仅是 解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数。

建议大家平时在leetcode上练习算法的时候本着这样的原则去练习，这样才有助于我们对算法的理解。

不要沉迷于使用库函数一行代码解决题目之类的技巧，不是说这些技巧不好，而是说这些技巧可以用来娱乐一下。

真正自己写的时候，要保证理解可以实现是相应的功能。
在反转链表中，使用了双指针的方法。

那么反转字符串依然是使用双指针的方法，只不过对于字符串的反转，其实要比链表简单一些。

因为字符串也是一种数组，所以元素在内存中是连续分布，这就决定了反转链表和反转字符串方式上还是有所差异的。

示意图

代码

class Solution {
    public void reverseString(char[] s) {
         int left = 0;
         int right = s.length-1;    //left和right双指针是下标
         while(left<right){
             char temp = s[left];
             s[left] = s[right];
             s[right] = temp; 
             left++;
             right--;
         }
    }
}

541.字符串反转

给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例:
输入: s = “abcdefg”, k = 2
输出: “bacdfeg”

解题思路

每隔2k个字符的前k的字符，写了一堆逻辑代码或者再搞一个计数器，来统计2k，再统计前k个字符。
其实在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。
因为要找的也就是每2 * k 区间的起点，这样写，程序会高效很多。
所以当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。

示意图

代码

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);	
            //判断尾数的个数是否小于k个 尾数的个数和k-1个相比
            //用异或运算反转 
            while(start < end){
                ch[start] ^= ch[end];
                ch[end] ^= ch[start];
                ch[start] ^= ch[end];
                start++;
                end--;
            }
        }
        return new String(ch);
    }
}

以下是代码的具体分析：
char[] ch = s.toCharArray();：将字符串 s 转换为字符数组 ch，以便进行字符级别的操作。
for(int i = 0; i < ch.length; i += 2 * k)：通过循环遍历字符串 ch，每次递增 i 的值为 2k，以处理长度为 2k 的子串。
int start = i;：将 start 初始化为当前子串的起始索引 i。
int end = Math.min(ch.length - 1, start + k - 1);：计算子串的结束索引 end。这里使用 Math.min() 函数来判断子串是否不足 k 个字符，如果是，则将 end 设置为子串的最后一个字符索引，否则设置为 start + k - 1。
while(start < end)：进入一个循环，该循环通过异或运算来反转子串中的字符。
ch[start] ^= ch[end]; ch[end] ^= ch[start]; ch[start] ^= ch[end];：这三行代码使用异或运算来反转 ch[start] 和 ch[end] 两个字符的值，实现字符交换。
start++; end–;：递增 start，递减 end，用于处理下一对字符。
return new String(ch);：将字符数组 ch 转换回字符串，并作为方法的返回值。
总体而言，这段代码通过划分长度为 2k 的子串，然后使用异或运算反转子串中的字符，最终将整个字符串的一部分进行了反转操作。