SYSTEM
今日算法刷题笔记(只包含简单、中等,排除Hard)
src/content/notes/algorithm/字符串.md 今日算法刷题笔记(只包含简单、中等,排除Hard)
涉及题目:LC20有效的括号、LC125验证回文串、LC3无重复字符的最长子串、LC344反转字符串、LC541反转字符串II 分类:栈、相向双指针、滑动窗口、分段局部反转
一、LC20 有效的括号|栈
题意:判断括号字符串是否合法;左括号必须有对应右括号,顺序匹配。
核心思路
- 遇到左括号,压入栈;
- 遇到右括号,看栈顶是否匹配对应左括号,匹配则弹出;不匹配直接false;
- 遍历结束,栈必须为空才算合法。
模板代码
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for(char c : s.toCharArray()){
if(c == '(') stack.push(')');
else if(c == '[') stack.push(']');
else if(c == '{') stack.push('}');
else{
if(stack.isEmpty() || stack.pop() != c){
return false;
}
}
}
return stack.isEmpty();
}
代码细节
- 使用
Deque stack = new ArrayDeque<>()做栈,不推荐Stack类; - 技巧:压入对应的右括号,后续直接对比;
- 遇到右括号先判断栈是否为空,防止空栈pop报错;
- 最后不能直接return true,必须栈空,防止
"(()"这种残留左括号。
通用规律
括号匹配类:栈的经典场景,后进先出,最近打开最先闭合。
二、LC125 验证回文串|相向双指针
题意:只看字母数字,忽略大小写,判断是否回文。
核心思路
- left从最左,right从最右;
- left遇到非字母数字就右移;right遇到非字母数字就左移;
- 两边都跳到有效字符,统一转小写对比;不相等直接false;
- 相等则
left++、right--,直到指针相遇。
模板代码
public boolean isPalindrome(String s) {
int left = 0;
int right = s.length()-1;
while(left < right){
//跳过非字母数字
while(left < right && !Character.isLetterOrDigit(s.charAt(left))){
left++;
}
while(left < right && !Character.isLetterOrDigit(s.charAt(right))){
right--;
}
if(Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))){
return false;
}
left++;
right--;
}
return true;
}
代码细节
- 内层while必须带上
left < right,防止指针越界; Character.isLetterOrDigit()判断有效字符;toLowerCase()统一小写;- 不要修改原字符串,直接在原字符串下标操作,空间O(1)。
相向双指针固定格式
int left = 0;
int right = arr.length - 1;
while(left < right){
//业务逻辑
left++;
right--;
}
适用场景:回文、数组/字符串原地反转,从两头向中间靠拢。
三、LC344 反转字符串|原地双指针交换
题意:char数组,原地反转,O(1)额外空间。
核心思路
left在头部,right在尾部;交换两个下标字符,指针向中间靠拢;left >= right停止。
模板代码
public void reverseString(char[] s) {
int left = 0;
int right = s.length - 1;
while(left < right){
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
代码细节
- 返回值
void,直接修改原数组,不需要return; - 循环条件
left < right,不要写<=,中间元素无需自己交换; - 必须借助临时变量temp完成交换。
四、LC541 反转字符串II|分段+局部区间反转
题意:每2k字符,反转前k个;末尾不足做边界处理。
核心思路
- String不可变,转为
char[]数组; - 外层循环,步长
i += 2*k,按2k分段; - 每一段确定反转区间:
left=i,right = Math.min(i+k-1, n-1); - 在
[left,right]区间复用344的双指针交换逻辑。
模板代码
public String reverseStr(String s, int k) {
char[] arr = s.toCharArray();
int n = arr.length;
for(int i = 0; i < n; i += 2*k){
int l = i;
int r = Math.min(i + k - 1, n - 1);
while(l < r){
char t = arr[l];
arr[l] = arr[r];
arr[r] = t;
l++;
r--;
}
}
return new String(arr);
}
代码细节
Math.min(i+k‑1,n‑1)是本题核心,处理末尾字符不够k个的越界;- 字符串操作优先转char[]做原地修改,最后再转回String。
规律:分段处理字符串,每一段内部调用局部双指针反转。
五、LC3 无重复字符的最长子串|滑动窗口 HashSet
题意:找出字符串不含重复字符的最长子串长度。
核心思路
left窗口左边界;right窗口右边界,for循环不断向右扩大窗口;- HashSet保存当前窗口内全部字符;
- 如果即将加入的字符已经存在集合中:while循环不断移除left位置字符,left右移,直到集合无重复;
- 将right字符加入集合;更新窗口最大长度
right‑left+1。
模板代码
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int left = 0;
int maxLen = 0;
for(int right = 0; right < s.length(); right++){
char c = s.charAt(right);
while(set.contains(c)){
set.remove(s.charAt(left));
left++;
}
set.add(c);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
代码细节
char c = s.charAt(right)缓存右指针字符,简化代码;- while循环删除left位置字符,不是删除c;一步步收缩窗口保证窗口连续;
right‑left+1:闭区间窗口长度计算;Math.max(old, new)保存最大值。
滑动窗口通用骨架(字符串子串高频模板)
int left = 0;
for(int right = 0; right < s.length(); right++){
//扩大窗口,处理right字符
while(窗口不满足条件){
//收缩窗口,移动left
left++;
}
//窗口合法,更新结果:最大/最小长度,收集答案
}
适用:求最长子串、最短子串、子串计数类中等题。
📚整体总规律速记
1. 相向双指针模板(回文、反转)
int left = 0;
int right = len -1;
while(left < right){
//交换 / 判断
left++;
right--;
}
- 只比较不交换:LC125回文串
- 交换元素原地反转:LC344;LC541内部局部反转
2. 栈模板(括号匹配)
遇到成对匹配、后进先出优先考虑栈;
Deque<Character> stack = new ArrayDeque<>()
3. 滑动窗口模板(子串类)
right向外扩,while判断条件不满足就移动left向内缩;记录窗口结果。
4. Java字符串做题高频注意点
- String不可变,原地修改先转
char[] arr = s.toCharArray();处理完new String(arr)还原; s.charAt(index)获取单个字符;- 子串:必须连续;子序列可以不连续,读题注意区分;
- 字符工具:
Character.isLetterOrDigit()、Character.toLowerCase()。