← 返回学习路线

SYSTEM

今日算法刷题笔记(只包含简单、中等,排除Hard)

LeetCode题解
src/content/notes/algorithm/字符串.md

今日算法刷题笔记(只包含简单、中等,排除Hard)

涉及题目:LC20有效的括号、LC125验证回文串、LC3无重复字符的最长子串、LC344反转字符串、LC541反转字符串II 分类:栈、相向双指针、滑动窗口、分段局部反转

一、LC20 有效的括号|栈

题意:判断括号字符串是否合法;左括号必须有对应右括号,顺序匹配。

核心思路

  1. 遇到左括号,压入栈;
  2. 遇到右括号,看栈顶是否匹配对应左括号,匹配则弹出;不匹配直接false;
  3. 遍历结束,栈必须为空才算合法。

模板代码

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();
}

代码细节

  1. 使用Deque stack = new ArrayDeque<>()做栈,不推荐Stack类;
  2. 技巧:压入对应的右括号,后续直接对比;
  3. 遇到右括号先判断栈是否为空,防止空栈pop报错;
  4. 最后不能直接return true,必须栈空,防止"(()"这种残留左括号。

通用规律

括号匹配类:栈的经典场景,后进先出,最近打开最先闭合。


二、LC125 验证回文串|相向双指针

题意:只看字母数字,忽略大小写,判断是否回文。

核心思路

  1. left从最左,right从最右;
  2. left遇到非字母数字就右移;right遇到非字母数字就左移;
  3. 两边都跳到有效字符,统一转小写对比;不相等直接false;
  4. 相等则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;
}

代码细节

  1. 内层while必须带上left < right,防止指针越界;
  2. Character.isLetterOrDigit()判断有效字符;toLowerCase()统一小写;
  3. 不要修改原字符串,直接在原字符串下标操作,空间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--;
    }
}

代码细节

  1. 返回值void,直接修改原数组,不需要return;
  2. 循环条件left < right,不要写<=,中间元素无需自己交换;
  3. 必须借助临时变量temp完成交换。

四、LC541 反转字符串II|分段+局部区间反转

题意:每2k字符,反转前k个;末尾不足做边界处理。

核心思路

  1. String不可变,转为char[]数组;
  2. 外层循环,步长 i += 2*k,按2k分段;
  3. 每一段确定反转区间:left=i,right = Math.min(i+k-1, n-1);
  4. 在[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);
}

代码细节

  1. Math.min(i+k‑1,n‑1)是本题核心,处理末尾字符不够k个的越界;
  2. 字符串操作优先转char[]做原地修改,最后再转回String。

规律:分段处理字符串,每一段内部调用局部双指针反转。


五、LC3 无重复字符的最长子串|滑动窗口 HashSet

题意:找出字符串不含重复字符的最长子串长度。

核心思路

  1. left窗口左边界;right窗口右边界,for循环不断向右扩大窗口;
  2. HashSet保存当前窗口内全部字符;
  3. 如果即将加入的字符已经存在集合中:while循环不断移除left位置字符,left右移,直到集合无重复;
  4. 将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;
}

代码细节

  1. char c = s.charAt(right)缓存右指针字符,简化代码;
  2. while循环删除left位置字符,不是删除c;一步步收缩窗口保证窗口连续;
  3. right‑left+1:闭区间窗口长度计算;
  4. 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字符串做题高频注意点

  1. String不可变,原地修改先转char[] arr = s.toCharArray();处理完new String(arr)还原;
  2. s.charAt(index)获取单个字符;
  3. 子串:必须连续;子序列可以不连续,读题注意区分;
  4. 字符工具:Character.isLetterOrDigit()、Character.toLowerCase()。