力扣算法系统刷题题解记录二(字符串、双指针法、栈与队列)
前言
参考顺序和资料:《代码随想录》
二刷要认真做笔记啦,加油!
笔记模板:
#### 解题思路#### 示意图#### 代码
四、字符串
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 的子串,然后使用异或运算反转子串中的字符,最终将整个字符串的一部分进行了反转操作。