刷题挑战链接

链表

题号 题目名称 核心思路 时间复杂度 空间复杂度 代码亮点 牛客原题链接
BM1 反转链表 三指针迭代（pre/cur/next） O(n) O(1) 循环不变式清晰，边界处理简洁 🔗 直达
BM2 链表内指定区间反转 虚拟头节点 + 局部头插反转 O(n) O(1) 两次遍历，定位后原地翻转 🔗 直达
BM3 每 k 个一组翻转 递归 + 尾插反转 O(n) O(1) tail 指针定位每组末尾，递归剩余 🔗 直达
BM4 合并两个排序链表 双指针归并 O(n) O(1) 哑节点统一头结点处理 🔗 直达
BM5 合并 k 个排序链表 分治法两两合并 O(n log k) O(log k) 复用 BM4，分治思想 🔗 直达
BM6 判断链表是否有环 快慢指针 / 哈希表 O(n) O(1) / O(n) 快慢指针相遇判环，空间可选 🔗 直达
BM7 链表中环的入口 哈希表记录首次出现 O(n) O(n) 再次遇到即入口，写法直观 🔗 直达
BM8 链表中倒数第 k 个节点 快慢指针 O(n) O(1) 快指针先走 k 步，再同步 🔗 直达
BM9 删除倒数第 n 个节点 快慢指针 / 长度法 O(n) O(1) 虚拟头节点避免头结点特判 🔗 直达
BM10 两个链表的第一个公共节点 哈希表存访问记录 O(n) O(n) 先存一条链，再扫另一条 🔗 直达
BM11 链表相加(二) 翻转相加再翻转 O(n) O(1) 两次翻转省去逆序存储 🔗 直达
BM12 单链表的排序 归并排序（链表版） O(n log n) O(log n) 快慢指针找中点，递归合并 🔗 直达
BM13 判断回文结构 快慢指针 + 后半翻转 O(n) O(1) 翻转后半段后双指针比对 🔗 直达
BM14 链表的奇偶重排 双指针分离再拼接 O(n) O(1) 一次遍历，奇偶指针交替 🔗 直达
BM15 删除有序链表中重复元素-I 单指针跳过重复 O(n) O(1) 有序特性，直接 next 跳过 🔗 直达
BM16 删除有序链表中重复元素-II 虚拟头节点 + 一次遍历 O(n) O(1) 出现重复值整段删除，保证无重复 🔗 直达

✅ 建议复习顺序（由易到难）：

BM1 → BM4 → BM8 → BM9 → BM2 → BM3 → BM14 → BM15 → BM16 → BM6 → BM7 → BM10 → BM11 → BM12 → BM13 → BM5

BM1反转链表

反转链表_牛客题霸_牛客网
https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=295&tqId=23286&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;
public class Solution {
    public ListNode ReverseList (ListNode head) {
        if(head == null) return null; // 1.判断链表是否为空
        ListNode pre = null;// 2. 创建pre反转后的节点，初始化为空
        ListNode cur = head;// 3. 创建cur指向当前节点
        while(cur != null){// 4. 循环 直至最后一个
            ListNode nextNode = cur.next;// 创建nextNode指向当前的下一个节点
            cur.next = pre;// 当前节点的下一个节点指向pre
            pre = cur;// pre再更新指向cur 前移
            cur = nextNode;// cur 复原指向下一个未反转的节点
        }
        return pre;// pre 指向的是最后一个反转了的节点，即反转之后的头节点
    }
}

BM2链表内指定区间反转

链表内指定区间反转_牛客题霸_牛客网
https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=295&sfm=html&channel=nowcoder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;
public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        ListNode res = new ListNode(-1); // 1. 加个表头
        res.next = head;// 2. 前序节点
        ListNode pre = res;// 3. 当前节点
        ListNode cur = head;// 4. cur指向当前节点
        for (int i = 1; i < m; i++) {// 5. 找到m
            pre = cur;// 6. 更新指向当前的上一个节点 
            cur = cur.next;// 7. 向后移动一个
        }
        for (int i = m; i < n; i++) {// 8. 从m反转到n 同题BM1反转
            ListNode nextNode = cur.next;
            cur.next = nextNode.next;
            nextNode.next = pre.next;
            pre.next = nextNode;
        }
        return res.next;//返回去掉表头
    }
}

BM3链表中的节点每k个一组翻转

链表中的节点每k个一组翻转_牛客题霸_牛客网
https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;
public class Solution {
    public ListNode reverseKGroup (ListNode head, int k) {
        ListNode tail = head;// 1. 每次反转的尾部
        for(int i = 0; i < k ; i ++){// 2. 每次反转K次
            if(tail == null){// 如果不足K则直接返回
                return head;
            }
            tail = tail.next;
        }
        ListNode pre = null;// 3. 前序节点
        ListNode cur = head;// 4. 当前节点
        while(cur != tail){// 再到达前段节点尾之前都要进行翻转
            ListNode nextNode = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nextNode;
        }
        head.next = reverseKGroup(tail,k);//当前的末尾指向下一段要反转的节点
        return pre;
    }
}

BM4 合并两个排序的链表

https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;
public class Solution {
    public ListNode Merge (ListNode l1, ListNode l2) {
       if(l1 == null) return l2;// 1 l1空 则直接返回l2
       if(l2 == null) return l1;// 2 l2空 则直接返回l1
       ListNode head = new ListNode(-1);// 3 创建一个新的头节点 初始值为-1        
       ListNode cur = head;// 4 记录当前节点
       while(l1 != null && l2 != null){// 如果两个都不空 则开始合并
            if(l1.val < l2.val){// l1 小，则l1跟着当前节点 
                cur.next = l1;// 下一个节点
                l1 = l1.next;
            }else{
                cur.next = l2;// 同上
                l2 = l2.next;
            }
            cur = cur.next;// 移动到下一个要处理的节点
       }

       if(l1 != null) cur.next = l1;// 有一个列表空了 如果表1没空，则表1继续跟着当前节点
       else  cur.next = l2;// 反之
       return head.next;// 返回的是我们虚拟的头节点的下一个节点
    }
}

BM5 合并k个已排序的链表

https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=295&tqId=724&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;

public class Solution {
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        return divideMerge(lists, 0, lists.size() - 1); // 1.使用分治
    }
    ListNode divideMerge(ArrayList<ListNode> lists, int l, int r) {// 2.划分合并区间函数
        if (l > r) return null;// 2.1 非法情况
        else if (l == r) return lists.get(l);// 2.2 中间只用一个的情况
        int mid = (l + r) / 2;// 2.3 二分成两段处理
        return Merge(divideMerge(lists, l, mid), divideMerge(lists, mid + 1, r));// 2.4 记得右端是mid + 1 开始
    }
    ListNode Merge(ListNode list1, ListNode list2) {//3 合并两个链表的函数
        if (list1 == null) return list2;// 3.1 list1空 则直接返回list2
        if (list2 == null) return list1;// 3.2 list2空 则直接返回list1
        ListNode head = new ListNode(0);// 3.3 创建一个新的头节点 初始值为0        
        ListNode cur = head;// 3.4 记录当前节点
        while (list1 != null && list2 != null) {// 如果两个都不空 则开始合并
            if (list1.val <= list2.val) {
                cur.next = list1;// list1 小，则list1跟着当前节点 
                list1 = list1.next;// 下一个节点
            } else {
                cur.next = list2;// 同上
                list2 = list2.next;
            }
            cur = cur.next;// 移动到下一个要处理的节点
        }
        if (list1 != null) cur.next = list1;// 有一个列表空了 如果表1没空，则表1继续跟着当前节点
        else cur.next = list2;// 反之
        return head.next;// 返回的是我们虚拟的头节点的下一个节点
    }


}

BM6 判断链表中是否有环

https://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9?tpId=295&tqId=605&sourceUrl=%2Fexam%2Foj

  1. 双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;
public class Solution {
    public boolean hasCycle(ListNode head) {
       if(head == null) return false;// 1. 列表非空
       ListNode f = head;// 2 快指针
       ListNode s = head;// 3 慢指针
       while(f != null && s != null){
            s = s.next;// 4 慢指针每次移动一个
            if(f.next != null){
                f = f.next.next;// 5 快指针每次移动两个
            }else{
                return false;// 6 如果快指针指向空 则已经到了末尾 则无环 
            }
            if(s == f) return true;// 7 如果相等则有环
       }
       return false;// 8 空链表也无环
    }
}
  1. 哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode pos = head;// pos 用来遍历
        Set<ListNode> vis = new HashSet<ListNode>();// 1.创建一个set记录访问过的结点
        while (pos != null) {// 2. 循环整个列表
            if (vis.contains(pos)) {// 3. 如果set中有，则有环
                return true;
            } else {// 4. 没有则加入set中
                vis.add(pos);
            }
            pos =  pos.next;//5. 下一个
        }
        return false;// 6. 没找到环则无环
    }
}

BM7 链表中环的入口结点

链表中环的入口结点_牛客题霸_牛客网
https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode pos = pHead;// 1. 创建一个pos来遍历
        Set<ListNode> cur = new HashSet<ListNode>();// 2. 创建哈希表来查找环
        while(pos != null){
            if(cur.contains(pos)){// 3. 找到环的结合点就是入口，或者说遍历时出现两次的节点
                return pos;
            }else{
                cur.add(pos);
            }
            pos = pos.next;
        }
        return null;// 4. 没找到则判空
    }
}

BM8 链表中倒数最后k个结点

链表中倒数最后k个结点_牛客题霸_牛客网 https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj
2025年7月28日19:04:44 —— 2025年7月28日19:09:22

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        ListNode s = pHead;// 1. 快指针
        ListNode f = pHead;// 2. 慢指针
        int i = 0;
        for(; i < k ; i ++){// 3. 找到头后面的第K个
            if(f == null){ return null;}
            f = f.next;
        }
        if(i == k && f == null) return s;// 4. 如果头后面第k个刚好是空，则头就是倒数最后k个结点
        while(s != null && f != null){// 5. 头和第K个都不是空
            if(s.next != null && f.next == null){// 6. 慢指针不空，快指针刚好空，则快指针刚刚好到末尾
                return s.next;
            }
            s = s.next;// 7. 遍历下一个
            f = f.next;// 8. 遍历下一个
        }
        return null;    
    }
}

BM9 删除链表的倒数第n个节点

删除链表的倒数第n个节点_牛客题霸_牛客网
https://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj
2025年7月28日19:15:17 2025年7月28日19:31:54

  1. 双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;
public class Solution {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        if(head == null) return null;
        ListNode s = head;
        ListNode f = head;
        for(int i = 0 ; i < n ; i ++){// 1. 找到第N个
            f = f.next;
        }
        if( f == null) return head.next;// 2. 如果刚好是结尾 则把头节点删掉 新的头节点则是旧的头节点的下一个
        while(f.next != null){// 3. 遍历到结尾
            f = f.next;
            s = s.next;
        }
        s.next = s.next.next;// 4. 删除倒数第N个
        return head;
    }
}
  1. 计算长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.*;
public class Solution {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        int lens = 0;// 1. 初始化长度
        ListNode p = head;// 2. 用来删除节点
        ListNode q = head;// 3. 用来遍历长度
        while(q != null){// 4. 计算总长度
            lens ++;
            q = q.next;
        }
        if(lens < 2){// 5. 特判只有一个节点的
            return null;
        }
        if( n == lens){// 6. 如果n和长度一样则刚好吧原来的头节点删掉了  新的头节点则是旧的头节点的下一个
            return head.next;
        }
        int i = 0;
        while(p != null){
            i ++;
            if(i == lens - n){// 7. 找到倒数第n个
                p.next = p.next.next;// 8. 删除操作
            }
            p = p.next;
        }
        return head;// 9. 头结点不变
    }
}

BM10 两个链表的第一个公共结点

两个链表的第一个公共结点_牛客题霸_牛客网
https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        Set<ListNode> p1 = new HashSet<ListNode>();// 1. 哈希表存储pHead1
        while(pHead1 != null){ // 2.哈希表存储pHead1
            p1.add(pHead1);
            pHead1 = pHead1.next;
        }
        while(pHead2 != null){
            if(p1.contains(pHead2)){// 3.遍历pHead2找到相同节点
                return pHead2;
            }else{
                pHead2 = pHead2.next;
            }
        } 
        return null;// 4.没有公共节点 ,返回null
    }
}

BM11 链表相加(二)

链表相加(二)_牛客题霸_牛客网
https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=295&tqId=1008772&sourceUrl=%2Fexam%2Foj
2025年7月30日22:32:01 2025年7月30日22:58:52

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;

public class Solution {
	// ReverseList 同上BM1
    public ListNode addInList (ListNode head1, ListNode head2) {
        if(head1 == null) return head2;// 1. 判空如果另外一个是空则不用处理了
        if(head2 == null) return head1;
        head1 = ReverseList(head1);// 2. 翻转列表 不用对齐 方便处理进位33
        head2 = ReverseList(head2);
        ListNode res = new ListNode(-1);// 3. 新建虚拟头节点
        ListNode head = res;// 4. 添加表头
        int carry = 0;// 5. 借助一个进位
        while(head1 != null || head2 != null || carry != 0){// 5. 链表 进位 任意一个不为空则进行处理
            int v1 = (head1 == null ? 0 : head1.val);// 6. 表空的话就为 0
            int v2 = (head2 == null ? 0 : head2.val);
            int temp = v1 + v2 + carry;// 7. 当前位的累加
            carry = temp / 10;// 8. 处理进位
            head.next = new ListNode(temp % 10);// 9. 添加数据到链表中
            head = head.next;// 10. 遍历下一个
            if(head1 != null) head1 = head1.next;
            if(head2 != null) head2 = head2.next;
        }
        return ReverseList(res.next);// 答案需要最后翻转一下
    }
}

BM12 单链表的排序

单链表的排序_牛客题霸_牛客网
https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj
2025年7月30日23:01:29

  1. 归并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;
public class Solution {
    ListNode merge(ListNode ph1, ListNode ph2){
        if(ph1 == null) return ph2;// 1. 特判
        if(ph2 == null) return ph1;
        ListNode head = new ListNode(0);// 2， 添加表头
        ListNode cur = head;
        while(ph1 != null && ph2 != null){
            if(ph1.val <= ph2.val){// 3. 取较小的值连到新头后面
                cur.next = ph1;
                ph1 =ph1.next;
            }else{
                cur.next = ph2;
                ph2 = ph2.next;
            }
            cur = cur.next;
        }
        if(ph1 != null) cur.next = ph1;// 4. 有剩的链表直接接到后面
        else cur.next = ph2;
        return head.next;// 5. 去掉虚拟表头返回
    }
    public ListNode sortInList (ListNode head) {
        if(head == null || head.next == null) return head;// 1. 特判 
        ListNode left = head;
        ListNode mid = head.next;
        ListNode right = head.next.next;
        while(right != null && right.next != null){// 2. 快慢指针之找到中点
            left = left.next;
            mid = mid.next;
            right = right.next.next;
        }
        left.next = null;
        return merge(sortInList(head),sortInList(mid));// 3.分成两段排序，合并排好序的两段
    }
}

BM13 判断一个链表是否为回文结构

判断一个链表是否为回文结构_牛客题霸_牛客网
https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f?tpId=295&tqId=1008769&sourceUrl=%2Fexam%2Foj

  1. 双指针 + 中点翻转遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;
public class Solution {
    ListNode reverse(ListNode head){
        ListNode pre = null;
        while(head != null){
            ListNode curNext = head.next;
            head.next = pre;
            pre = head;
            head = curNext;
        }
        return pre;
    }
    public boolean isPail (ListNode head) {
        if(head == null) return true;// 1. 特判
        ListNode f = head;// 2. 快慢指针
        ListNode s = head;
        while(f != null && f.next != null){// 3. 快慢指针找到中点
            f = f.next.next;
            s = s.next;
        }
        s = reverse(s);// 4. 翻转中点之后的 可以少遍历一半
        f = head;// 5. 重头遍历
        while(s != null && f != null){
            if(s.val != f.val) return false;// 6. 如果不同则不是回文
            s = s.next;// 7. 移到下个节点
            f = f.next;
        }
        return true;// 8. 全部相同则是回文串
    }
}
  1. 借助额外空间 - 栈做法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;
public class Solution {
    public boolean isPail (ListNode head) {
        Stack<Integer> st = new Stack();// 1. 用一个栈来存储 因为栈是先进后出 直接全部进去再出来就是原来的倒序
        ListNode cur = head;// 2. cur 用于遍历
        while(cur != null){// 3. 链表元素全部压入栈中
            st.push(cur.val);
            cur = cur.next;
        }
        while(head != null){// 4. 遍历链表
            if(st.pop() != head.val) return false;// 5.对比倒序的是否一致
            head = head.next;
        }
        return true;// 6. 相同则返回是回文串
    }
}
  1. 借助额外空间 - 链表做法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;
public class Solution {
    public boolean isPail (ListNode head) {
        List<Integer> list = new ArrayList();// 1. 创建一个辅助数组
        while(head != null){// 2. 把链表的全部元素存入
            list.add(head.val);
            head = head.next;
        }
        int n = list.size();// 3. 计算长度
        for(int i = 0 ; i < n / 2; i ++){// 4. 第n个和倒数第n个比较
            if(list.get(i).equals(list.get(n - i - 1)) == false) return false;// 5. 坑点：记得用equals
        }
        return true;// 6. 都相同则是回文串
    }
}

BM14 链表的奇偶重排

链表的奇偶重排_牛客题霸_牛客网
https://www.nowcoder.com/practice/02bf49ea45cd486daa031614f9bd6fc3?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;
public class Solution {

    public ListNode oddEvenList (ListNode head) {
        if(head == null) return head;// 1. 特判
        ListNode even = head.next;// 2. even 是 偶数位的链表
        ListNode odd = head;// 3. 基数位链表
        ListNode evenHead = even;// 4. 记录偶数位的头,方便直接接到奇数的后面
        while(even != null && even.next != null){
            odd.next = even.next;// 5. 偶数的后面是奇数
            odd = odd.next;// 6. 移动下一个
            even.next = odd.next;// 7. 奇数后面是偶数
            even = even.next;// 8. 同上
        }
        odd.next = evenHead;// 9. 偶数的直接接到奇数后面
        return head;// 返回头结点
    }
}

BM15 删除有序链表中重复的元素-I

删除有序链表中重复的元素-I_牛客题霸_牛客网
https://www.nowcoder.com/practice/c087914fae584da886a0091e877f2c79?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
import java.util.*;
public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        if(head == null) return null;// 1. 特判 
        ListNode cur = head;// 2. cur用来遍历head
        while(cur != null && cur.next != null){// 3. 遍历直至末尾结点
            if(cur.next.val == cur.val) cur.next = cur.next.next;// 4. 当前和下一个结点的元素相同时 直接不要下一个结点 即当前的下一个指向下一个的下一个 
            else cur = cur.next;// 5. 不相等则遍历下一个
        }
        return head;
    }
}

BM16 删除有序链表中重复的元素-II

删除有序链表中重复的元素-II_牛客题霸_牛客网
https://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024?tpId=295&tqId=663&sourceUrl=%2Fexam%2Foj

  1. 虚拟头结点 + 遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;
public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        if(head == null) return null;// 1. 特判
        ListNode res = new ListNode(-1);// 2. 虚拟头节点 
        res.next = head;// 3. 新的头节点后面接原来的链表
        ListNode cur = res;// 4. cur用来遍历
        while(cur.next != null && cur.next.next != null){// 5. 可以遍历当前结点的后面两个
            if(cur.next.val == cur.next.next.val){ // 6. 如果下两个节点一样
                int temp = cur.next.val;// 7. 存储当前的值
                while(cur.next != null && cur.next.val == temp){// 8. 后面的第二个节点一致往后移 知道找到不等于temp的
                    cur.next = cur.next.next;
                }
            }else{
                cur = cur.next;// 9. 值不一样则遍历下一个节点
            }
        }
        return res.next;// 返回虚拟的头节点的下一个
    }
}
  1. 借助哈希表计数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;
public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        if(head == null) return null;// 1. 特判
        Map<Integer,Integer> mp = new HashMap<>();// 2. 新建哈希表用来计数
        ListNode cur = head;// 3. cur 用于遍历
        while(cur != null){// 4. 全部存到哈希表mp里面
            mp.merge(cur.val,1,Integer::sum);// 等价C++里面的mp[cur->val] ++;
            cur = cur.next;
        }
        ListNode res = new ListNode(-1);// 5. 虚拟一个空头节点
        res.next = head;// 6. 空的头节点接原来的链表
        cur = res;// 7. 遍历新的链表
        while(cur.next != null){
            if(mp.get(cur.next.val) != 1){// 8. 如果不止一个 则去掉
                cur.next = cur.next.next;
            }else{
                cur = cur.next;// 9. 遍历下一个
            }
        }
        return res.next;// 10. 去虚拟的头结点
    }
}

二分查找/排序

题号 题目名称 核心思路 时间复杂度 空间复杂度 代码亮点 牛客原题链接
BM17 二分查找-I 二分查找，不断缩小搜索范围 O(logn) O(1) 使用位运算优化中点计算，逻辑清晰 🔗 直达
BM18 二维数组中的查找 从左下角或右上角开始查找，利用二维数组的有序性 O(m+n) O(1) 选择合适的起点，避免重复比较，逻辑简洁 🔗 直达
BM19 寻找峰值 二分查找，利用峰值的性质 O(logn) O(1) 使用二分查找快速定位峰值，逻辑清晰 🔗 直达
BM20 数组中的逆序对 归并排序，在合并过程中统计逆序对 O(nlogn) O(n) 使用归并排序优化逆序对统计，逻辑简洁 🔗 直达
BM21 旋转数组的最小数字 二分查找，利用旋转数组的性质 O(logn) O(1) 使用二分查找快速定位最小值，逻辑清晰 🔗 直达
BM22 比较版本号 按点分隔版本号，逐段比较 O(n) O(1) 逐段比较版本号，逻辑简洁 🔗 直达

✅ 建议复习顺序（由易到难）：

BM17 → BM18 → BM19 → BM21 → BM20 → BM22

BM17 二分查找-I

二分查找-I_牛客题霸_牛客网
https://www.nowcoder.com/practice/d3df40bd23594118b57554129cadf47b?tpId=295&tqId=1499549&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;
public class Solution {
    public int search (int[] nums, int target) {
        int l = 0;// 1. 定义左端点
        int r = nums.length - 1;// 2. 定义右端点
        while(l <= r){
            int mid = (l + r) >> 1;// 3. 二分找中点
            if(nums[mid] == target) return mid;// 4. 判断中点值是否是target
            else if(nums[mid] > target) r = mid - 1;// 5. 中点值大于目标值 区间左移
            else l = mid + 1;// 6. 反之区间右移
        }
        return -1;// 7. 二分完毕没找到
    }
}

BM18 二维数组中的查找

二维数组中的查找_牛客题霸_牛客网
https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public boolean Find(int target, int [][] array) {
        if (array.length == 0) return false;          // 1. 数组为空，直接返回 false
        int n = array.length;                         // 2. 获取数组行数
        if (array[0].length == 0) return false;       // 3. 首行长度为 0，说明列数为 0，返回 false
        int m = array[0].length;                      // 4. 获取数组列数
        // 5. 从左下角 (n-1,0) 开始查找：往上值变小，往右值变大
        for (int i = n - 1, j = 0; i >= 0 && j < m; ) {
            if (array[i][j] > target) i--;            // 6. 当前值大于目标，上移一行
            else if (array[i][j] < target) j++;       // 7. 当前值小于目标，右移一列
            else return true;                         // 8. 找到目标，返回 true
        }
        return false;                                 // 9. 遍历结束仍未找到，返回 false
    }
}

BM19 寻找峰值

寻找峰值_牛客题霸_牛客网
https://www.nowcoder.com/practice/fcf87540c4f347bcb4cf720b5b350c76?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public boolean Find(int target, int [][] array) {
        if (array.length == 0) return false;          // 1. 数组为空，直接返回 false
        int n = array.length;                         // 2. 获取数组行数
        if (array[0].length == 0) return false;       // 3. 首行长度为 0，说明列数为 0，返回 false
        int m = array[0].length;                      // 4. 获取数组列数
        // 5. 从左下角 (n-1,0) 开始查找：往上值变小，往右值变大
        for (int i = n - 1, j = 0; i >= 0 && j < m; ) {
            if (array[i][j] > target) i--;            // 6. 当前值大于目标，上移一行
            else if (array[i][j] < target) j++;       // 7. 当前值小于目标，右移一列
            else return true;                         // 8. 找到目标，返回 true
        }
        return false;                                 // 9. 遍历结束仍未找到，返回 false
    }
}

BM20 数组中的逆序对

数组中的逆序对_牛客题霸_牛客网
https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int mod = 1000000007; // 1. 定义模数，用于防止结果溢出
    public int mergeSort(int left, int right, int[] data, int[] temp) {
        if (left >= right) return 0; // 2. 如果区间长度小于等于1，无需排序，返回0
        int mid = (left + right) / 2; // 3. 计算中间位置，将数组分为两部分
        // 4. 递归计算左半部分和右半部分的逆序对数量
        int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp);
        res %= mod; // 5. 对结果取模，防止溢出
        int i = left, j = mid + 1; // 6. 初始化左右两部分的指针
        // 7. 将原数组的值复制到临时数组，用于归并
        for (int k = left; k <= right; k++) temp[k] = data[k];
        // 8. 归并排序并统计逆序对
        for (int k = left; k <= right; k++) {
            if (i == mid + 1) data[k] = temp[j++]; // 9. 左半部分已处理完，直接取右半部分的值
            else if (j == right + 1 || temp[i] <= temp[j]) data[k] = temp[i++]; // 10. 右半部分已处理完或左半部分的值小于等于右半部分的值
            else { 
                data[k] = temp[j++]; // 11. 右半部分的值小于左半部分的值，发生逆序
                res += mid - i + 1; // 12. 计算逆序对数量：左半部分剩余的元素个数
            }
        }
        return res % mod; // 13. 返回当前区间内的逆序对总数
    }
    public int InversePairs(int[] array) {
        int n = array.length; // 14. 获取数组长度
        int[] res = new int[n]; // 15. 创建临时数组用于归并排序
        return mergeSort(0, n - 1, array, res); // 16. 调用归并排序函数计算逆序对
    }
}

BM21 旋转数组的最小数字

旋转数组的最小数字_牛客题霸_牛客网
https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=295&tqId=23269&sourceUrl=%2Fexam%2Foj

  1. 暴力 + Stream流
1
2
3
4
5
6
7
8
9
import java.util.*;

public class Solution {
    // 1. 找到旋转数组中的最小值
    public int minNumberInRotateArray(int[] nums) {
        // 2. 使用 Java 8 的 Stream API 找到数组中的最小值
        return Arrays.stream(nums).min().getAsInt();
    }
}
  1. 二分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;

public class Solution {
    public int minNumberInRotateArray (int[] nums) {
        if(nums.length == 0) return 0; // 1. 如果数组为空，返回 0
        int l = 0; // 2. 初始化左指针
        int r = nums.length - 1; // 3. 初始化右指针
        while(l < r){ // 4. 当左指针小于右指针时，继续查找
            int mid = (l + r) / 2; // 5. 计算中间位置
            if(nums[mid] < nums[r]) r = mid; // 6. 如果中间值小于右端值，最小值在左半部分或中间值就是最小值
            else if(nums[mid] > nums[r]) l = mid + 1; // 7. 如果中间值大于右端值，最小值在右半部分
            else r --; // 8. 如果中间值等于右端值，无法确定最小值位置，右指针左移
        }
        return nums[l]; // 9. 返回最小值
    }
}

BM22 比较版本号

比较版本号_牛客题霸_牛客网
https://www.nowcoder.com/practice/2b317e02f14247a49ffdbdba315459e7?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;

public class Solution {

    public int compare(String v1, String v2) {
        int n1 = v1.length(); // 1. 获取版本号 v1 的长度
        int n2 = v2.length(); // 2. 获取版本号 v2 的长度

        int i = 0, j = 0; // 3. 初始化两个指针，分别指向 v1 和 v2 的起始位置
        while (i < n1 || j < n2) { // 4. 当两个指针都未超出各自版本号的长度时，继续比较
            long num1 = 0; // 5. 初始化 v1 的当前部分数字
            long num2 = 0; // 6. 初始化 v2 的当前部分数字
            // 7. 解析 v1 的当前部分数字
            while (i < n1 && v1.charAt(i) != '.') {
                num1 = num1 * 10 + (v1.charAt(i) - '0'); // 8. 将字符转换为数字并累加
                i++;
            }
            i++; // 9. 跳过点（`.`）
            // 10. 解析 v2 的当前部分数字
            while (j < n2 && v2.charAt(j) != '.') {
                num2 = num2 * 10 + (v2.charAt(j) - '0'); // 11. 将字符转换为数字并累加
                j++;
            }
            j++; // 12. 跳过点（`.`）
            // 13. 比较当前部分数字
            if (num1 > num2) return 1; // 14. 如果 v1 的当前部分大于 v2 的当前部分，返回 1
            else if (num1 < num2) return -1; // 15. 如果 v1 的当前部分小于 v2 的当前部分，返回 -1
        }
        return 0; // 16. 如果所有部分都相等，返回 0
    }
}

二叉树

题号 题目名称 核心思路 时间复杂度 空间复杂度 代码亮点 牛客原题链接
BM23 二叉树的前序遍历 递归实现，先访问根节点，再递归遍历左子树，最后递归遍历右子树 O(n) O(n) 使用辅助函数 preorder，逻辑清晰，递归终止条件明确 🔗 直达
BM24 二叉树的中序遍历 递归实现，先递归遍历左子树，访问根节点，再递归遍历右子树 O(n) O(n) 递归逻辑简洁，通过辅助函数 inorder 实现 🔗 直达
BM25 二叉树的后序遍历 递归实现，先递归遍历左子树，再递归遍历右子树，最后访问根节点 O(n) O(n) 递归逻辑清晰，辅助函数 postorder 实现后序遍历 🔗 直达
BM26 求二叉树的层序遍历 使用队列实现广度优先搜索，逐层访问节点 O(n) O(n) 使用队列存储待访问的节点，逐层处理 🔗 直达
BM27 按之字形顺序打印二叉树 层序遍历结合反转操作，偶数层反转当前层的节点值 O(n) O(n) 使用队列实现层序遍历，通过 Collections.reverse 反转偶数层 🔗 直达
BM28 二叉树的最大深度 使用队列实现广度优先搜索，逐层访问节点，计算最大深度 O(n) O(n) 使用队列存储待访问的节点，逐层处理，每层深度加1 🔗 直达
BM29 二叉树中和为某一值的路径(一) 递归或广度优先搜索，记录从根节点到叶子节点的路径和 O(n) O(n) 递归方法简洁，广度优先搜索使用 Pair 类记录路径和 🔗 直达
BM30 二叉搜索树与双向链表 递归或非递归中序遍历，将二叉搜索树转换为双向链表 O(n) O(n) 递归方法中使用全局变量 head 和 pre，非递归方法使用栈 🔗 直达
BM31 对称的二叉树 递归或层序遍历，判断二叉树是否对称 O(n) O(n) 递归方法中使用辅助函数 chk，层序遍历使用队列 🔗 直达
BM32 合并二叉树 递归合并两棵二叉树，对应节点值相加 O(n) O(n) 递归方法简洁，新建节点 head 作为合并后的根节点 🔗 直达
BM33 二叉树的镜像 递归或栈实现，交换每个节点的左右子树 O(n) O(n) 递归方法简洁，栈方法使用迭代 🔗 直达
BM34 判断是不是二叉搜索树 递归或中序遍历，判断中序遍历结果是否递增 O(n) O(n) 递归方法中使用全局变量 pre，中序遍历方法使用栈 🔗 直达
BM35 判断是不是完全二叉树 使用队列实现层序遍历，检查是否为完全二叉树 O(n) O(n) 使用队列存储待访问的节点，逐层处理 🔗 直达
BM36 判断是不是平衡二叉树 递归计算子树高度，判断是否平衡 O(n) O(n) 使用辅助函数 depth，递归计算子树高度 🔗 直达
BM37 二叉搜索树的最近公共祖先 递归或路径比较，找到最近公共祖先 O(n) O(n) 使用辅助函数 getPath，记录路径 🔗 直达
BM38 在二叉树中找到两个节点的最近公共祖先 递归或路径比较，找到最近公共祖先 O(n) O(n) 使用辅助函数 lowestCommonAncestor，递归查找 🔗 直达
BM39 序列化二叉树 递归或层序遍历，序列化二叉树 O(n) O(n) 使用辅助函数 SerializeFuction 和 DeserializeFuction 🔗 直达
BM40 重建二叉树 递归或栈遍历，根据前序和中序遍历重建二叉树 O(n) O(n) 使用辅助函数 buildTree，递归重建 🔗 直达
BM41 输出二叉树的右视图 递归或层序遍历，输出二叉树的右视图 O(n) O(n) 使用辅助函数 rightSideView，层序遍历 🔗 直达

✅ 建议复习顺序（由易到难）：

BM23 → BM24 → BM25 → BM26 → BM27 → BM29 → BM30 → BM31 → BM32 → BM33 → BM34 → BM35 → BM36 → BM37 → BM38 → BM39 → BM40 → BM41

BM23 二叉树的前序遍历

二叉树的前序遍历_牛客题霸_牛客网
https://www.nowcoder.com/practice/5e2135f4d2b14eb8a5b06fab4c938635?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;

public class Solution {
    void preorder(List<Integer> list, TreeNode root){ // 1. 定义前序遍历辅助方法
        if(root == null) return ; // 2. 如果当前节点为空，直接返回
        list.add(root.val); // 3. 访问当前节点，将值加入列表
        preorder(list,root.left); // 4. 递归遍历左子树
        preorder(list,root.right); // 5. 递归遍历右子树
    }
    public int[] preorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList(); // 6. 创建一个列表用于存储遍历结果
        preorder(list,root); // 7. 调用前序遍历辅助方法
        int [] res = new int [list.size()]; // 8. 创建一个数组用于存储最终结果
        for(int i = 0 ; i < list.size(); i ++) res[i] = list.get(i); // 9. 将列表中的值复制到数组
        return res; // 10. 返回结果数组
    }
}

BM24 二叉树的中序遍历

二叉树的中序遍历_牛客题霸_牛客网
https://www.nowcoder.com/practice/0bf071c135e64ee2a027783b80bf781d?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import java.util.*;

public class Solution {
    void inorder(ArrayList<Integer> list, TreeNode root){ // 1. 定义中序遍历辅助方法
        if(root == null) return; // 2. 如果当前节点为空，直接返回
        inorder(list,root.left); // 3. 递归遍历左子树
        list.add(root.val); // 4. 访问当前节点，将值加入列表
        inorder(list,root.right); // 5. 递归遍历右子树
    }
    public int[] inorderTraversal (TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>(); // 6. 创建一个列表用于存储遍历结果
        inorder(list,root); // 7. 调用中序遍历辅助方法
        int [] res = new int [list.size()]; // 8. 创建一个数组用于存储最终结果
        for(int i = 0 ; i < list.size() ; i ++){ // 9. 将列表中的值复制到数组
            res[i] = list.get(i);
        }
        return res; // 10. 返回结果数组
    }
}

BM25 二叉树的后序遍历

二叉树的后序遍历_牛客题霸_牛客网
https://www.nowcoder.com/practice/1291064f4d5d4bdeaefbf0dd47d78541?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;

public class Solution {
    // 1. 递归辅助函数：后序遍历子树并把节点值追加到 list
    void postorder(ArrayList<Integer> list, TreeNode root){
        if(root == null) return;          // 2. 空节点直接返回
        postorder(list,root.left);        // 3. 递归遍历左子树
        postorder(list,root.right);       // 4. 递归遍历右子树
        list.add(root.val);               // 5. 访问当前节点：将值加入 list
    }
    
    // 6. 主函数：返回整棵树的后序遍历结果（int 数组形式）
    public int[] postorderTraversal (TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>(); // 7. 用于存放遍历结果的动态数组
        postorder(list,root);            // 8. 调用辅助函数完成后序遍历并填充 list
        int [] res = new int[list.size()]; // 9. 创建与 list 长度相同的 int 数组
        for(int i = 0 ; i < list.size() ; i ++) 
            res[i] = list.get(i);        // 10. 将 list 中的值逐个复制到数组 res
        return res;                      // 11. 返回后序遍历结果数组
    }
}

BM26 求二叉树的层序遍历

求二叉树的层序遍历_牛客题霸_牛客网
https://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;

public class Solution {
  
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList();// 1. 创建数据来存放答案
        if(root == null) return res;// 2. 如果是空树 则返回空
        Queue<TreeNode> q = new ArrayDeque<TreeNode> ();// 3. 创建一个双端队列来遍历
        q.add(root);// 4. 初始化根节点放到队列之中
        while(!q.isEmpty()){// 5. 如果队列不是空的
            ArrayList<Integer> row = new ArrayList();// 6. 存放当前层的节点的值
            int n = q.size();// 7. 计算当前层有多少个节点
            for(int i = 0 ; i < n ; i ++){// 8. 处理当前的所有节点
                TreeNode cur = q.poll();// 9. 结点出队
                row.add(cur.val);// 10. 当前节点的答案
                if(cur.left != null) q.add(cur.left);// 11. 当前层节点的左节点入队（若有）
                if(cur.right != null) q.add(cur.right);// 12. 当前层节点的右节点入队（若有）
            }
            res.add(row);// 13. 添加答案
        }
        return res;
    }
}

BM27 按之字形顺序打印二叉树

按之字形顺序打印二叉树_牛客题霸_牛客网
https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?tpId=295&tqId=644&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page

  1. 直接利用队列 广搜
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.*;

public class Solution {
 
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        TreeNode h = pRoot;                          // 1. 用临时变量 h 保存根节点引用，避免直接修改形参
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); // 2. 创建最终结果列表 res，用于存放按层划分的节点值
        if(h == null) return res;                    // 3. 如果根节点为空，直接返回空的结果列表
        Queue<TreeNode> q = new LinkedList<TreeNode>(); // 4. 创建队列 q，用于实现广度优先（层序）遍历
        q.offer(h);                                  // 5. 将根节点加入队列，作为遍历起点
        int f = 0;                                   // 6. 初始化层号计数器 f 为 0（根节点视为第 0 层）
        while(!q.isEmpty()){                         // 7. 只要队列中还有节点，就继续循环
            ArrayList<Integer> row = new ArrayList<>(); // 8. 创建当前层的节点值列表 row
            int n = q.size();                        // 9. 获取当前层的节点数量 n（队列长度）
            for(int i = 0 ; i < n ; i ++){          // 10. 循环 n 次，处理当前层的所有节点
                TreeNode cur = q.poll();             // 11. 从队列头部取出一个节点 cur
                row.add(cur.val);                    // 12. 将当前节点的值加入 row 列表
                if(cur.left != null) q.add(cur.left); // 13. 如果 cur 有左孩子，将左孩子加入队列
                if(cur.right != null) q.add(cur.right); // 14. 如果 cur 有右孩子，将右孩子加入队列
            }
            f++;                                     // 15. 层号计数器 f 加 1，准备处理下一层
            if(f % 2 == 0) Collections.reverse(row); // 16. 如果当前层号为偶数，反转 row 列表，实现之字形输出
            res.add(row);                            // 17. 将当前层的节点值列表加入最终结果 res
        }
        return res;                                  // 18. 返回层序遍历后的之字形结果列表
    }
}
  1. 使用两个栈，利用先进后出特性来反转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.*;

public class Solution {
 
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        TreeNode h = pRoot;                                  // 1. 用临时变量 h 保存根节点，避免直接修改形参
        ArrayList<ArrayList<Integer>> res = new ArrayList<>(); // 2. 创建最终结果容器 res
        if(h == null) return res;                            // 3. 空树直接返回空列表
        
        Stack<TreeNode> s1 = new Stack<TreeNode>();          // 4. 奇数层（从左到右）使用的栈
        Stack<TreeNode> s2 = new Stack<TreeNode>();          // 5. 偶数层（从右到左）使用的栈
        
        s1.push(h);                                          // 6. 根节点压入 s1，作为第 1 层（奇数层）
        
        while(!s1.isEmpty() || !s2.isEmpty()){               // 7. 只要任一栈非空就继续遍历
            ArrayList<Integer> row = new ArrayList<>();      // 8. 存放当前层节点值
            
            while(!s1.isEmpty()){                            // 9. 处理奇数层：s1 不为空
                TreeNode cur = s1.pop();                     // 10. 弹出栈顶节点
                row.add(cur.val);                            // 11. 记录节点值
                if(cur.left != null) s2.add(cur.left);       // 12. 左孩子先入 s2（下一层逆序用）
                if(cur.right != null) s2.add(cur.right);     // 13. 右孩子后入 s2
            }
            
            if(row.size() != 0)                              // 14. 若本层有节点
                res.add(new ArrayList<Integer>(row));        // 15. 深拷贝 row 加入到结果
            row.clear();                                     // 16. 清空 row，准备下一轮
            
            while(!s2.isEmpty()){                            // 17. 处理偶数层：s2 不为空
                TreeNode cur = s2.pop();                     // 18. 弹出栈顶节点
                row.add(cur.val);                            // 19. 记录节点值
                if(cur.right != null) s1.add(cur.right);     // 20. 右孩子先入 s1（下一层逆序用）
                if(cur.left != null) s1.add(cur.left);       // 21. 左孩子后入 s1
            }
            
            if(row.size() != 0)                              // 22. 若本层有节点
                res.add(new ArrayList<Integer>(row));        // 23. 深拷贝 row 加入到结果
            row.clear();                                     // 24. 清空 row，准备下一轮
        }
        return res;                                          // 25. 返回最终之字形层序遍历结果
    }
}

BM28 二叉树的最大深度

二叉树的最大深度_牛客题霸_牛客网
https://www.nowcoder.com/practice/8a2b2bf6c19b4f23a9bdb9b233eefa73?tpId=295&tqId=642&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;

public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0; // 1. 如果根节点为空，直接返回深度为 0
        Queue<TreeNode> q = new LinkedList<TreeNode>(); // 2. 创建一个队列用于层序遍历
        int res = 0; // 3. 初始化最大深度
        q.add(root); // 4. 将根节点加入队列
        while (!q.isEmpty()) { // 5. 当队列不为空时，继续遍历
            int size = q.size(); // 6. 获取当前层的节点数
            for (int i = 0; i < size; i++) { // 7. 遍历当前层的所有节点
                TreeNode node = q.poll(); // 8. 弹出队列中的节点
                if (node.left != null) q.add(node.left); // 9. 如果左子节点不为空，加入队列
                if (node.right != null) q.add(node.right); // 10. 如果右子节点不为空，加入队列
            }
            res++; // 11. 每遍历完一层，深度加 1
        }
        return res; // 12. 返回最大深度
    }
}

BM29 二叉树中和为某一值的路径(一)

二叉树中和为某一值的路径(一)_牛客题霸_牛客网
https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c?tpId=295&tqId=634&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AC%2594%25E9%259D%25A2%25E8%25AF%2595%25E7%25AF%2587%26topicId%3D295
2025年8月13日16:38:15 2025年8月13日16:48:21

  1. 递归
1
2
3
4
5
6
7
8
9
10
11
import java.util.*;

public class Solution {
    public boolean hasPathSum (TreeNode root, int sum) {
        if(root == null) return false;// 1. 空节点说明之前的路径已走完，且未满足目标和，返回 false
        if(root.left == null && root.right == null && root.val == sum) return true;// 2. 到达叶子节点：若剩余值等于当前节点值，则找到一条满足条件的路径，返回 true
        // 3. 递归检查左子树和右子树，目标和减去当前节点的值
        return hasPathSum(root.left, sum - root.val)   // 4. 向左子树继续寻找
            || hasPathSum(root.right, sum - root.val); // 5. 向右子树继续寻找
    }
}
  1. 使用广搜，Pair记录从头节点到叶子的总值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.*;

public class Solution {
    // 1. 辅助类 P：同时携带节点引用与该节点到根路径上的累加和
    class P {
        TreeNode node = null;  // 2. 当前节点
        int cursum = 0;        // 3. 从根到当前节点的路径和
        public P(TreeNode node, int cursum) {
            this.node = node;  // 4. 初始化节点
            this.cursum = cursum; // 5. 初始化累加和
        }
    }

    public boolean hasPathSum (TreeNode root, int sum) {
        // 6. 空树直接返回 false
        if (root == null) return false;
        // 7. 创建队列，用于广度优先遍历
        Queue<P> q = new LinkedList<>();
        // 8. 将根节点及其值封装成 P 并入队
        P p = new P(root, root.val);
        q.add(p);
        // 9. 队列非空则继续处理
        while (!q.isEmpty()) {
            // 10. 取出队首元素
            P cur = q.poll();
            // 11. 若存在左孩子，创建新的 P 并入队
            if (cur.node.left != null) {
                q.add(
                    new P(
                        cur.node.left,                  // 12. 左孩子节点
                        cur.cursum + cur.node.left.val  // 13. 新的累加和
                    )
                );
            }
            // 14. 若存在右孩子，创建新的 P 并入队
            if (cur.node.right != null) {
                q.add(
                    new P(
                        cur.node.right,                 // 15. 右孩子节点
                        cur.cursum + cur.node.right.val // 16. 新的累加和
                    )
                );
            }
            // 17. 当前节点是叶子节点
            if (cur.node.left == null && cur.node.right == null) {
                // 18. 若累加和等于目标和，立即返回 true
                if (sum == cur.cursum) return true;
            }
        }
        // 19. 遍历结束仍未找到符合条件的路径，返回 false
        return false;
    }
}

BM30 二叉搜索树与双向链表

二叉搜索树与双向链表_牛客题霸_牛客网
https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=295&tqId=23253&sourceUrl=%2Fexam%2Foj

  1. 递归中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;

public class Solution {
    TreeNode head = null;  // 1. 最终要返回的双向链表头结点
    TreeNode pre  = null;  // 2. 指向当前已处理部分的尾结点（上一次访问的结点）
    public TreeNode Convert(TreeNode p) {
        if (p == null) return null;// 3. 空树直接返回 null
        Convert(p.left);// 4. 递归处理左子树：把整棵左子树构造成双向链表
        if (pre == null) {// 5. 此时 pre == null 说明正在访问整棵树的最左叶子，即为链表头结点
            head = p;      // 6. 记录头结点
            pre  = p;      // 7. 当前结点成为已处理部分的尾结点
        } else {           // 8. 将当前结点 p 接到已处理链表的末尾
            pre.right = p; // 9. 尾结点的后继指向当前结点
            p.left  = pre; // 10. 当前结点的前驱指向尾结点
            pre = p;       // 11. 更新尾结点指针
        }
        Convert(p.right); // 12. 递归处理右子树：继续把右子树结点接到链表后面
        return head;// 13. 整棵树遍历完后，head 即为所求双向链表的头结点
    }
}
  1. 非递归中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;

public class Solution {
    public TreeNode Convert(TreeNode p) {
        if(p == null) return null;                  // 1. 空树直接返回 null
        Stack<TreeNode> s = new Stack<TreeNode>();  // 2. 创建栈，用于非递归中序遍历
        TreeNode head = null;                       // 3. 最终要返回的双向链表头结点
        TreeNode pre = null;                        // 4. 指向当前已处理链表的尾结点
        boolean isHead = true;                      // 5. 标记是否第一次访问到最左结点（即链表头结点）

        while(p != null || !s.isEmpty()){           // 6. 外层循环：当 p 非空或栈非空时继续
            while(p != null){                       // 7. 内层循环：沿左子树一路到底
                s.push(p);                          // 8. 当前结点入栈
                p = p.left;                         // 9. 继续深入左孩子
            }
            p = s.pop();                            // 10. 弹出栈顶结点（此时为最左未访问结点）
            if(isHead){                             // 11. 如果是第一次访问（最左结点）
                head = p;                           // 12. 记录头结点
                pre = p;                            // 13. 当前结点成为已处理链表的尾结点
                isHead = false;                     // 14. 标记已处理过头结点
            }else{                                  // 15. 否则，已有部分链表
                pre.right = p;                      // 16. 尾结点的后继指向当前结点
                p.left = pre;                       // 17. 当前结点的前驱指向尾结点
                pre = p;                            // 18. 更新尾结点指针
            }
            p = p.right;                            // 19. 转向当前结点的右子树（可能为空）
        }
        return head;                                // 20. 返回构造好的双向链表头结点
    }
}

BM31 对称的二叉树

对称的二叉树_牛客题霸_牛客网
https://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb?tpId=295&tqId=23253&sourceUrl=%2Fexam%2Foj
2025年8月14日14:05:33 2025年8月14日14:22:40

  1. 层序遍历 + 回文/对称
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;

public class Solution {
    int INF = 0x3f3f3f;                       // 1. 用一个极大值作为空节点的占位值
    TreeNode emptyNode = new TreeNode(INF);   // 2. 创建统一的空节点对象，用于缺失左右孩子时的占位
    // 3. 检查给定层序列表是否为回文（对称）
    boolean check(ArrayList<Integer> list){
        int n = list.size();                  // 4. 当前层节点个数
        for(int i = 0 ; i < n ; i ++){        // 5. 双指针对撞比较
            if(!list.get(i).equals(list.get(n - 1 - i))) return false; // 6. 发现不对称立即返回 false
        }
        return true;                          // 7. 全部对称则返回 true
    }
    public boolean isSymmetrical (TreeNode p) {
        if(p == null) return true;            // 8. 空树视为对称，直接返回 true
        Queue<TreeNode> q = new LinkedList<>(); // 9. 队列用于层序（广度优先）遍历
        q.offer(p);                           // 10. 根节点入队
        while(!q.isEmpty()){                  // 11. 逐层处理直到队列为空
            int n = q.size();                 // 12. 当前层的节点数量
            ArrayList<Integer> row = new ArrayList<>(); // 13. 存放当前层的值（含占位值）
            for(int i = 0; i < n ; i ++){     // 14. 处理当前层的所有节点
                TreeNode cur = q.poll();      // 15. 取出队首节点
                if(!cur.equals(emptyNode)){   // 16. 若非空节点
                    // 17. 左孩子存在则入队真实节点，否则入队空节点占位
                    q.add(cur.left != null ? cur.left : emptyNode);
                    // 18. 右孩子存在则入队真实节点，否则入队空节点占位
                    q.add(cur.right != null ? cur.right : emptyNode);
                }
                row.add(cur.val);             // 19. 记录当前节点值（含占位值）
            }
            // 20. 只要某层不对称，整棵树就不对称
            if(!check(row)) return false;
        }
        return true;                          // 21. 所有层都对称，返回 true
    }
}
  1. 递归写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;

public class Solution {
    // 1. 辅助函数：递归判断以 p1、p2 为根的两棵子树是否镜像对称
    boolean chk(TreeNode p1, TreeNode p2) {
        // 2. 两棵树同时为空 → 对称
        if (p1 == null && p2 == null) return true;
        // 3. 仅有一棵为空 → 不对称
        if (p1 == null || p2 == null) return false;
        // 4. 节点值不相等 → 不对称
        if (p1.val != p2.val) return false;
        // 5. 递归检查：p1 的左子树与 p2 的右子树、p1 的右子树与 p2 的左子树是否都镜像对称
        return chk(p1.left, p2.right) && chk(p1.right, p2.left);
    }

    public boolean isSymmetrical (TreeNode p) {
        // 6. 以整棵树的根节点同时作为左、右子树，调用 chk 判断整体是否对称
        return chk(p, p);
    }
}

BM32 合并二叉树

合并二叉树_牛客题霸_牛客网
https://www.nowcoder.com/practice/7298353c24cc42e3bd5f0e0bd3d1d759?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;

public class Solution {

    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // 1. 如果 t1 为空，直接返回 t2 作为合并结果
        if (t1 == null) return t2;
        // 2. 如果 t2 为空，直接返回 t1 作为合并结果
        if (t2 == null) return t1;

        // 3. 新建节点 head，其值为 t1 与 t2 节点值之和
        TreeNode head = new TreeNode(t1.val + t2.val);

        // 4. 递归合并 t1 与 t2 的左子树，结果挂到 head.left
        head.left = mergeTrees(t1.left, t2.left);

        // 5. 递归合并 t1 与 t2 的右子树，结果挂到 head.right
        head.right = mergeTrees(t1.right, t2.right);

        // 6. 返回合并后的根节点
        return head;
    }
}

BM33 二叉树的镜像

二叉树的镜像_牛客题霸_牛客网
https://www.nowcoder.com/practice/a9d0ecbacef9410ca97463e4a5c83be7?tpId=295&tqId=1374963&sourceUrl=%2Fexam%2Foj

  1. 直接递归
1
2
3
4
5
6
7
8
9
10
11
12
import java.util.*;

public class Solution {
    public TreeNode Mirror (TreeNode p) {
       if (p == null) return null; // 1. 若当前节点为空，直接返回 null
        TreeNode left = Mirror(p.left);// 2. 递归翻转左子树，得到翻转后的左子树（此时已变成右子树）
        TreeNode right = Mirror(p.right);// 3. 递归翻转右子树，得到翻转后的右子树（此时已变成左子树）
        p.left = right;// 4. 将当前节点的左指针指向翻转后的右子树
        p.right = left;// 5. 将当前节点的右指针指向翻转后的左子树
        return p;        // 6. 返回已完成翻转的当前节点
    }
}
  1. 借助辅助空间，栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;

public class Solution {
    public TreeNode Mirror (TreeNode p) {
        if (p == null) return null;         // 1. 空树直接返回
        Stack<TreeNode> s = new Stack<TreeNode>();  // 2. 创建栈用于迭代
        s.push(p);                          // 3. 根节点入栈
        while (!s.isEmpty()) {              // 4. 栈非空则继续处理
            TreeNode cur = s.pop();         // 5. 弹出当前待处理节点
            if (cur.left != null) s.push(cur.left); // 6. 左孩子入栈
            if (cur.right != null) s.push(cur.right); // 7. 右孩子入栈
            TreeNode temp = cur.left;       // 8. 暂存原左子树
            cur.left = cur.right;           // 9. 左指针指向原右子树
            cur.right = temp;               // 10. 右指针指向原左子树
        }
        return p;                           // 11. 返回翻转后的根节点
    }
}

BM34 判断是不是二叉搜索树

判断是不是二叉搜索树_牛客题霸_牛客网
https://www.nowcoder.com/practice/a69242b39baf45dea217815c7dedb52b?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. 栈模拟，然后中序遍历是否单调
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;

public class Solution {
    public boolean isValidBST (TreeNode root) {
        if (root == null) return true;                     // 1. 空树视为合法 BST
        Stack<TreeNode> s = new Stack<TreeNode>();         // 2. 创建栈，用于中序遍历
        ArrayList<Integer> list = new ArrayList<Integer>();// 3. 存放中序遍历得到的节点值
        TreeNode head = root;                              // 4. 当前遍历指针，初始指向根节点
        while (head != null || !s.isEmpty()) {             // 5. 只要指针非空或栈非空就继续
            while (head != null) {                         // 6. 一路向左走到头
                s.push(head);                              // 7. 沿途节点入栈
                head = head.left;                          // 8. 继续深入左子树
            }
            head = s.pop();                                // 9. 弹出栈顶（最左未访问节点）
            list.add(head.val);                            // 10. 记录节点值
            head = head.right;                             // 11. 转向右子树
        }
        for (int i = 1; i < list.size(); i++) { // 12. 检查中序序列是否严格递增
            if (list.get(i) <= list.get(i - 1)) return false; // 13. 出现非递增即非 BST
        }
        return true;                                       // 14. 全部递增，是合法 BST
    }
}
  1. 递归
1
2
3
4
5
6
7
8
9
10
11
12
import java.util.*;

public class Solution {
    int pre = Integer.MIN_VALUE;        // 1 保存前一个节点的值，初始化为整型最小值
    public boolean isValidBST (TreeNode root) {
       if(root == null) return true;    // 2 空树被认为是合法的 BST
       if(!isValidBST(root.left)) return false; // 3 先递归检查左子树是否合法
       if(root.val < pre) return false; // 4 若当前节点值不大于前一个节点值，则违反 BST 性质
       pre = root.val;                 // 5 更新 pre 为当前节点值，准备与下一个节点比较
       return isValidBST(root.right);  // 6 最后递归检查右子树是否合法
    }
}

BM35 判断是不是完全二叉树

判断是不是完全二叉树_牛客题霸_牛客网
https://www.nowcoder.com/practice/8daa4dff9e36409abba2adbe413d6fae?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;

public class Solution {
    public boolean isCompleteTree (TreeNode root) {
        if(root == null) return true;                // 1 空树视为完全二叉树
        Queue<TreeNode> q = new LinkedList<TreeNode>(); // 2 创建队列用于层序遍历
        q.offer(root);                               // 3 根节点入队
        boolean notOk = false;                       // 4 标记是否已遇到空节点
        while(!q.isEmpty()){                         // 5 队列非空时循环
            TreeNode cur = q.poll();                 // 6 取出队首节点
            if(cur == null) {                        // 7 遇到空节点
                notOk = true;                        // 8 置位标记
                continue;                            // 9 继续处理后续节点
            }
            if(notOk) return false;                  // 10 若之前已遇到空节点且当前节点非空，则不完整
            q.offer(cur.left);                       // 11 左孩子入队（可为 null）
            q.offer(cur.right);                      // 12 右孩子入队（可为 null）
        }
        return true;                                 // 13 全部遍历完未发现违规，返回 true
    }
}

BM36 判断是不是平衡二叉树

判断是不是平衡二叉树_牛客题霸_牛客网
https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;

public class Solution {
    boolean isOk = true;                         // 1 全局标志，记录整棵树是否平衡
    public int depth(TreeNode p){                // 2 后序遍历求当前子树高度
        if(p == null){                           // 3 空节点高度为 0
            return 0;
        }
        int l = depth(p.left);                   // 4 递归获取左子树高度
        int r = depth(p.right);                  // 5 递归获取右子树高度
        if(Math.abs(l - r) > 1){                 // 6 左右高度差超过 1，则不平衡
            isOk = false;
        }
        return Math.max(l, r) + 1;               // 7 返回当前子树高度
    }
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        int d = depth(pRoot);                    // 8 触发整棵树的遍历与标记
        return isOk;                             // 9 返回是否平衡的最终结果
    }
}
  1. 方法一 剪枝
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;

public class Solution {
    boolean isOk = true;                // 1 全局标志，标记整棵树是否平衡
    public int depth(TreeNode p){       // 2 后序遍历求子树高度，不平衡时直接返回-1剪枝
        if(p == null){                  // 3 空节点高度为0
            return 0;
        }
        int l = depth(p.left);          // 4 递归求左子树高度
        if(l == -1) return -1;          // 5 左子树不平衡，向上传递-1
        int r = depth(p.right);         // 6 递归求右子树高度
        if(r == -1) return -1;          // 7 右子树不平衡，向上传递-1
        if(Math.abs(l - r) > 1){        // 8 左右高度差大于1，当前子树不平衡
            isOk = false;               // 9 置位全局不平衡标志
            return -1;                  // 10 向上返回-1表示不平衡
        }
        return Math.max(l, r) + 1;      // 11 当前子树平衡，返回其高度
    }
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        int d = depth(pRoot);           // 12 触发整棵树的后序遍历与剪枝检查
        return isOk;                    // 13 返回最终是否平衡的结果
    }
}

BM37 二叉搜索树的最近公共祖先

二叉搜索树的最近公共祖先_牛客题霸_牛客网
https://www.nowcoder.com/practice/d9820119321945f588ed6a26f0a6991f?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. 遍历两个节点的路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;

public class Solution {
    ArrayList<Integer> getPath(TreeNode r, int n){
        ArrayList<Integer> res = new ArrayList<Integer>(); // 1. 创建结果列表，存储路径上的节点值
        TreeNode p = r; // 2. 从根节点开始
        while(p.val != n){ // 3. 遍历二叉搜索树，直到找到目标节点 n
            res.add(p.val); // 4. 将当前节点值加入路径
            if(n < p.val){ // 5. 如果目标值小于当前节点值，向左子树移动
                p = p.left;
            }else { // 6. 如果目标值大于当前节点值，向右子树移动
                p = p.right;
            }
        }  
        res.add(p.val); // 7. 将目标节点值加入路径
        return res; // 8. 返回完整的路径
    }
    public int lowestCommonAncestor (TreeNode r, int p, int q) {
        ArrayList<Integer> ppath = getPath(r,p); // 9. 获取从根节点到节点 p 的路径
        ArrayList<Integer> qpath = getPath(r,q); // 10. 获取从根节点到节点 q 的路径
        int ans = 0; // 11. 初始化最低公共祖先的值
        for(int i = 0 ; i  < ppath.size() && i < qpath.size(); i ++){ // 12. 遍历两条路径，找到最后一个相同的节点
            int x = ppath.get(i); // 13. 获取路径 p 中的当前节点值
            int y = qpath.get(i); // 14. 获取路径 q 中的当前节点值
            if(x == y) ans = ppath.get(i); // 15. 如果两个值相同，更新最低公共祖先
            else break; // 16. 如果不同，停止遍历
        }
        return ans; // 17. 返回最低公共祖先的值
    }
}
  1. 用一个set存 遍历到最后一个一样的节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;

public class Solution {
    public int lowestCommonAncestor (TreeNode r, int p, int q) {
        Set<Integer> s = new HashSet<Integer>(); // 1. 创建一个集合，用于存储从根节点到节点 p 的路径上的节点值
        TreeNode cur = r; // 2. 从根节点开始
        while(cur.val != p){ // 3. 遍历二叉搜索树，直到找到节点 p
            s.add(cur.val); // 4. 将当前节点值加入集合
            if(cur.val > p) cur = cur.left; // 5. 如果当前节点值大于 p，向左子树移动
            else cur = cur.right; // 6. 如果当前节点值小于 p，向右子树移动
        }
        s.add(cur.val); // 7. 将节点 p 的值加入集合
        cur = r; // 8. 重新从根节点开始
        int res = -1; // 9. 初始化最低公共祖先的值为 -1
        while(cur.val != q){ // 10. 遍历二叉搜索树，直到找到节点 q
            if(s.contains(cur.val)) res = cur.val; // 11. 如果当前节点值在集合中，更新最低公共祖先
            if(cur.val > q) cur = cur.left; // 12. 如果当前节点值大于 q，向左子树移动
            else cur = cur.right; // 13. 如果当前节点值小于 q，向右子树移动
        }
        return res == -1 ? q : res; // 14. 如果 res 仍为 -1，说明 q 本身就是最低公共祖先，否则返回 res
    }
}

BM38 在二叉树中找到两个节点的最近公共祖先

在二叉树中找到两个节点的最近公共祖先_牛客题霸_牛客网
https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. dfs + 路径比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.*;

public class Solution {
    boolean ok = false; // 剪枝标记
    void depth(TreeNode p,int t,ArrayList<Integer> cur){
        if(p == null || ok) return; // 1. 如果当前节点为空或已找到目标节点，直接返回
        cur.add(p.val); // 2. 将当前节点值加入路径
        if(p.val == t){ // 3. 如果当前节点值等于目标值 t
            ok = true; // 4. 标记找到目标节点
            return;
        }
        depth(p.left,t,cur); // 5. 递归遍历左子树
        depth(p.right,t,cur); // 6. 递归遍历右子树
        if(ok) return; // 7. 如果已找到目标节点，直接返回
        cur.remove(cur.size() - 1); // 8. 回溯，移除当前节点值
    }
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        ArrayList<Integer> l1 = new ArrayList<Integer>(); // 9. 存储从根节点到 o1 的路径
        ArrayList<Integer> l2 = new ArrayList<Integer>(); // 10. 存储从根节点到 o2 的路径
        ok = false; // 11. 重置标志变量
        depth(root,o1,l1); // 12. 获取从根节点到 o1 的路径
        ok = false; // 13. 重置标志变量
        depth(root,o2,l2); // 14. 获取从根节点到 o2 的路径

        int res = 0; // 15. 初始化最低公共祖先的值
        for(int i = 0 ; i < l1.size() && i < l2.size(); i ++){ // 16. 遍历两条路径，找到最后一个相同的节点
            if(l1.get(i).equals(l2.get(i))) res = l1.get(i); // 17. 如果两个路径上的节点值相同，更新最低公共祖先
            else break; // 18. 如果不同，停止遍历
        }
        return res; // 19. 返回最低公共祖先的值
    }
}
  1. 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.*;

public class Solution {
    public int lowestCommonAncestor(TreeNode r, int o1, int o2) {
        if (r == null) return -1; // 1. 如果当前节点为空，返回 -1 表示未找到
        if (r.val == o1 || r.val == o2) return r.val;// 2. 如果当前节点值等于 o1 或 o2，返回当前节点值
        int lf = lowestCommonAncestor(r.left, o1, o2); // 3. 递归在左子树中查找最低公共祖先
        int rh = lowestCommonAncestor(r.right, o1, o2); // 4. 递归在右子树中查找最低公共祖先
        if (lf == -1) return rh; // 5. 如果左子树未找到，返回右子树的结果
        if (rh == -1) return lf; // 6. 如果右子树未找到，返回左子树的结果
        return r.val; // 7. 如果左右子树都找到了，当前节点就是最低公共祖先
    }
}

BM39 序列化二叉树

序列化二叉树_牛客题霸_牛客网
https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84?tpId=295&tqId=23455&sourceUrl=%2Fexam%2Foj

  1. 广搜遍历 + StringBuilder
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.*;

public class Solution {
    int INF = Integer.MAX_VALUE; // 1. 定义一个无穷大值，用于标记空节点
    TreeNode emptyNode = new TreeNode(INF); // 2. 创建一个值为 INF 的空节点

    // 3. 序列化二叉树
    String Serialize(TreeNode r) {
        if (r == null) return ""; // 4. 如果根节点为空，返回空字符串
        StringBuilder sb = new StringBuilder(); // 5. 创建一个字符串构建器用于存储序列化结果
        Deque<TreeNode> dq = new ArrayDeque<>(); // 6. 创建一个双端队列用于层序遍历
        dq.addLast(r); // 7. 将根节点加入队列
        while (!dq.isEmpty()) { // 8. 遍历队列直到为空
            TreeNode cur = dq.pollFirst(); // 9. 取出队首节点
            sb.append(cur.val + "_"); // 10. 将当前节点值追加到字符串构建器
            if (!cur.equals(emptyNode)) { // 11. 如果当前节点不是空节点
                dq.addLast(cur.left != null ? cur.left : emptyNode); // 12. 将左子节点加入队列（若为空则加入空节点）
                dq.addLast(cur.right != null ? cur.right : emptyNode); // 13. 将右子节点加入队列（若为空则加入空节点）
            }
        }
        return sb.toString(); // 14. 返回序列化后的字符串
    }

    // 15. 反序列化二叉树
    TreeNode Deserialize(String str) {
        if (str.equals("")) return null; // 16. 如果字符串为空，返回空节点
        String[] s = str.split("_"); // 17. 将字符串按 "_" 分割成数组
        int n = s.length; // 18. 获取数组长度
        TreeNode p = new TreeNode(Integer.parseInt(s[0])); // 19. 创建根节点
        Deque<TreeNode> dq = new ArrayDeque<TreeNode>(); // 20. 创建一个双端队列用于层序遍历
        dq.addLast(p); // 21. 将根节点加入队列
        for (int i = 1; i < n - 1; i += 2) { // 22. 遍历数组，每次处理两个子节点
            TreeNode cur = dq.pollFirst(); // 23. 取出队首节点
            int l = Integer.parseInt(s[i]), r = Integer.parseInt(s[i + 1]); // 24. 获取左右子节点的值
            if (l != INF) { // 25. 如果左子节点值不是 INF
                cur.left = new TreeNode(l); // 26. 创建左子节点
                dq.addLast(cur.left); // 27. 将左子节点加入队列
            }
            if (r != INF) { // 28. 如果右子节点值不是 INF
                cur.right = new TreeNode(r); // 29. 创建右子节点
                dq.addLast(cur.right); // 30. 将右子节点加入队列
            }
        }
        return p; // 31. 返回重建的二叉树根节点
    }
}
  1. 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.*;

public class Solution {
    static int idx = 0; // 1. 静态变量，用于记录反序列化时的字符串索引位置

    // 2. 序列化辅助函数，递归地将二叉树序列化为字符串
    void SerializeFuction(TreeNode p, StringBuilder sb) {
        if (p == null) { // 3. 如果当前节点为空，追加 '#' 表示空节点
            sb.append('#');
            return;
        }
        sb.append(p.val).append("_"); // 4. 将当前节点值追加到字符串构建器，并添加分隔符 "_"
        SerializeFuction(p.left, sb); // 5. 递归序列化左子树
        SerializeFuction(p.right, sb); // 6. 递归序列化右子树
    }

    // 7. 序列化主函数，调用辅助函数完成序列化
    String Serialize(TreeNode r) {
        if (r == null) return "#"; // 8. 如果根节点为空，返回特殊字符 "#" 表示空树
        StringBuilder res = new StringBuilder(); // 9. 创建字符串构建器用于存储序列化结果
        SerializeFuction(r, res); // 10. 调用辅助函数进行序列化
        return res.toString(); // 11. 返回序列化后的字符串
    }

    // 12. 反序列化辅助函数，递归地从字符串中重建二叉树
    TreeNode DeserializeFuction(String str) {
        if (str.charAt(idx) == '#') { // 13. 如果当前字符是 '#'，表示空节点
            idx++; // 14. 索引后移
            return null;
        }
        int val = 0; // 15. 初始化节点值
        // 16. 解析当前节点的值，直到遇到分隔符 "_" 或字符串结束
        while (str.charAt(idx) != '_' && idx != str.length()) {
            val = val * 10 + (str.charAt(idx) - '0'); // 17. 将字符转换为数字并累加
            idx++; // 18. 索引后移
        }
        TreeNode p = new TreeNode(val); // 19. 创建当前节点
        if (idx == str.length()) return p; // 20. 如果已到达字符串末尾，返回当前节点
        else idx++; // 21. 跳过分隔符 "_"
        p.left = DeserializeFuction(str); // 22. 递归重建左子树
        p.right = DeserializeFuction(str); // 23. 递归重建右子树
        return p; // 24. 返回重建的当前节点
    }

    // 25. 反序列化主函数，调用辅助函数完成反序列化
    TreeNode Deserialize(String str) {
        if (str.equals("#")) return null; // 26. 如果字符串为 "#"，返回空节点
        idx = 0; // 27. 重置索引
        TreeNode res = DeserializeFuction(str); // 28. 调用辅助函数进行反序列化
        return res; // 29. 返回重建的二叉树根节点
    }
}

BM40 重建二叉树

重建二叉树_牛客题霸_牛客网
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;

public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
        int n = pre.length; // 1. 获取前序遍历数组的长度
        int m = vin.length; // 2. 获取中序遍历数组的长度
        if (n == 0 || m == 0) return null; // 3. 如果数组长度为 0，返回空节点

        TreeNode r = new TreeNode(pre[0]); // 4. 根据前序遍历的第一个元素创建根节点
        for (int i = 0; i < vin.length; i++) { // 5. 在中序遍历数组中找到根节点的位置
            if (pre[0] == vin[i]) {
                // 6. 递归重建左子树，使用前序遍历的 [1, i+1] 和中序遍历的 [0, i]
                r.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(vin, 0, i));
                // 7. 递归重建右子树，使用前序遍历的 [i+1, n] 和中序遍历的 [i+1, m]
                r.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, n), Arrays.copyOfRange(vin, i + 1, m));
                break; // 8. 找到根节点后退出循环
            }
        }
        return r; // 9. 返回重建的二叉树根节点
    }
}
  1. 栈遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.*;

public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
        int n = pre.length; // 1. 获取前序遍历数组的长度
        int m = pre.length; // 2. 获取中序遍历数组的长度
        if (n == 0 || m == 0) return null; // 3. 如果数组长度为 0，返回空节点

        Stack<TreeNode> s = new Stack<TreeNode>(); // 4. 创建一个栈，用于辅助重建二叉树
        TreeNode r = new TreeNode(pre[0]); // 5. 根据前序遍历的第一个元素创建根节点
        TreeNode cur = r; // 6. 当前节点指针初始化为根节点
        for (int i = 1, j = 0; i < n; i++) { // 7. 遍历前序遍历数组，从第二个元素开始
            if (cur.val != vin[j]) { // 8. 如果当前节点不是中序遍历中的当前节点
                cur.left = new TreeNode(pre[i]); // 9. 创建左子节点
                s.push(cur); // 10. 将当前节点压入栈
                cur = cur.left; // 11. 将当前节点指针移动到左子节点
            } else { // 12. 如果当前节点是中序遍历中的当前节点
                j++; // 13. 中序遍历指针后移
                while (!s.isEmpty() && s.peek().val == vin[j]) { // 14. 弹出栈中所有匹配的节点
                    cur = s.pop(); // 15. 更新当前节点指针
                    j++; // 16. 中序遍历指针后移
                }
                cur.right = new TreeNode(pre[i]); // 17. 创建右子节点
                cur = cur.right; // 18. 将当前节点指针移动到右子节点
            }
        }
        return r; // 19. 返回重建的二叉树根节点
    }
}

BM41 输出二叉树的右视图

输出二叉树的右视图_牛客题霸_牛客网
https://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0?tpId=295&tqId=1073834&sourceUrl=%2Fexam%2Foj

  1. 递归建树 ， 一个哈希表维护最深节点，两个栈分别维护节点和深度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.*;

public class Solution {
    // 1. 根据前序和中序遍历结果重建二叉树
    TreeNode buildTree(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) return null; // 2. 如果索引范围无效，返回空节点
        TreeNode p = new TreeNode(pre[preStart]); // 3. 根据前序遍历的第一个元素创建根节点
        int idx = inStart; // 4. 初始化中序遍历中根节点的索引
        while (idx <= inEnd && in[idx] != pre[preStart]) idx++; // 5. 在中序遍历中找到根节点的位置
        int leftSize = idx - inStart; // 6. 计算左子树的大小
        // 7. 递归构建左子树
        p.left = buildTree(pre, in, preStart + 1, preStart + leftSize, inStart, idx - 1);
        // 8. 递归构建右子树
        p.right = buildTree(pre, in, preStart + leftSize + 1, preEnd, idx + 1, inEnd);
        return p; // 9. 返回重建的子树根节点
    }

    // 10. 获取二叉树的右侧视图
    ArrayList<Integer> rightSideView(TreeNode r) {
        ArrayList<Integer> res = new ArrayList<>(); // 11. 存储结果
        if (r == null) return res; // 12. 如果根节点为空，返回空列表
        Queue<TreeNode> q = new LinkedList<>(); // 13. 使用队列实现广度优先搜索
        q.add(r); // 14. 将根节点入队
        while (!q.isEmpty()) { // 15. 遍历队列直到为空
            int size = q.size(); // 16. 获取当前层的节点数
            for (int i = 0; i < size; i++) { // 17. 遍历当前层的所有节点
                TreeNode cur = q.poll(); // 18. 弹出队首节点
                if (i == size - 1) { // 19. 如果是当前层的最后一个节点
                    res.add(cur.val); // 20. 添加到结果列表
                }
                if (cur.left != null) q.add(cur.left); // 21. 左子节点入队
                if (cur.right != null) q.add(cur.right); // 22. 右子节点入队
            }
        }
        return res; // 23. 返回结果
    }

    // 24. 主函数，根据前序和中序遍历结果，返回右侧视图
    public int[] solve(int[] pre, int[] in) {
        int n = pre.length; // 25. 前序遍历数组长度
        int m = in.length; // 26. 中序遍历数组长度
        if (m == 0 || n == 0) return new int[0]; // 27. 如果数组为空，返回空数组
        TreeNode r = buildTree(pre, in, 0, n - 1, 0, m - 1); // 28. 重建二叉树
        ArrayList<Integer> tmp = rightSideView(r); // 29. 获取右侧视图
        int[] res = new int[tmp.size()]; // 30. 转换为数组
        for (int i = 0; i < tmp.size(); i++) res[i] = tmp.get(i); // 31. 填充数组
        return res; // 32. 返回结果
    }
}
  1. 库函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.util.*;

public class Solution {
    // 1. 根据前序和中序遍历结果重建二叉树
    TreeNode buildTree(int[] pre, int l1, int r1, int[] in, int l2, int r2) {
        if (l1 > r1 || l2 > r2) return null; // 2. 如果索引范围无效，返回空节点
        TreeNode p = new TreeNode(pre[l1]); // 3. 根据前序遍历的第一个节点创建根节点
        int idx = 0; // 4. 初始化中序遍历中根节点的索引
        for (int i = l2; i <= r2; i++) { // 5. 在中序遍历中找到根节点的位置
            if (in[i] == pre[l1]) {
                idx = i; // 6. 记录根节点的索引
                break;
            }
        }
        int lsize = idx - l2; // 7. 计算左子树的大小
        int rsize = r2 - idx; // 8. 计算右子树的大小
        // 9. 递归构建左子树
        p.left = buildTree(pre, l1 + 1, l1 + lsize, in, l2, l2 + lsize - 1);
        // 10. 递归构建右子树
        p.right = buildTree(pre, r1 - rsize + 1, r1, in, idx + 1, r2);
        return p; // 11. 返回重建的子树根节点
    }

    // 12. 获取二叉树的右侧视图
    ArrayList<Integer> rightSideView(TreeNode r) {
        Map<Integer, Integer> mp = new HashMap<Integer, Integer>(); // 13. 用于存储每层最右侧的节点值
        int maxdepth = -1; // 14. 记录最大深度
        Stack<TreeNode> s1 = new Stack<TreeNode>(); // 15. 存储节点的栈
        Stack<Integer> s2 = new Stack<Integer>(); // 16. 存储节点深度的栈
        s1.push(r); // 17. 将根节点入栈
        s2.push(0); // 18. 根节点深度为 0
        while (!s1.isEmpty()) { // 19. 遍历栈直到为空
            TreeNode cur = s1.pop(); // 20. 弹出当前节点
            int curdepth = s2.pop(); // 21. 弹出当前节点深度
            if (cur != null) {
                maxdepth = Math.max(maxdepth, curdepth); // 22. 更新最大深度
                if (mp.get(curdepth) == null) { // 23. 如果当前深度没有记录节点值
                    mp.put(curdepth, cur.val); // 24. 记录当前节点值
                }
                s1.push(cur.left); // 25. 左子节点入栈
                s1.push(cur.right); // 26. 右子节点入栈
                s2.push(curdepth + 1); // 27. 左子节点深度 +1
                s2.push(curdepth + 1); // 28. 右子节点深度 +1
            }
        }
        ArrayList<Integer> res = new ArrayList<>(); // 29. 存储结果
        for (int i = 0; i <= maxdepth; i++) { // 30. 按深度顺序添加节点值
            res.add(mp.get(i));
        }
        return res; // 31. 返回结果
    }

    // 32. 主函数，根据前序和中序遍历结果，返回右侧视图
    public int[] solve(int[] pre, int[] in) {
        int n = pre.length; // 33. 前序遍历数组长度
        int m = in.length; // 34. 中序遍历数组长度
        if (m == 0 || n == 0) return new int[0]; // 35. 如果数组为空，返回空数组
        TreeNode r = buildTree(pre, 0, n - 1, in, 0, m - 1); // 36. 重建二叉树
        ArrayList<Integer> tmp = rightSideView(r); // 37. 获取右侧视图
        int[] res = new int[tmp.size()]; // 38. 转换为数组
        for (int i = 0; i < tmp.size(); i++) res[i] = tmp.get(i); // 39. 填充数组
        return res; // 40. 返回结果
    }
}

堆/栈/队列

题号 题目名称 核心思路 时间复杂度 空间复杂度 代码亮点 牛客原题链接
BM42 用两个栈实现队列 使用两个栈模拟队列的先进先出特性，一个栈用于存储元素，另一个栈用于反转元素顺序 O(1) O(n) 代码逻辑清晰，通过两个栈的交互实现队列功能 🔗直达
BM43 包含min函数的栈 使用两个栈，一个存储所有元素，另一个存储当前最小值，通过辅助栈实现O(1)时间复杂度的min函数 O(1) O(n) 使用辅助栈优化min函数的实现，代码简洁高效 🔗直达
BM44 有效括号序列 使用栈存储预期的闭合字符，遍历字符串时检查括号匹配情况 O(n) O(n) 利用栈的特性高效判断括号匹配，代码易于理解 🔗直达
BM45 滑动窗口的最大值 使用双端队列维护窗口内的最大值索引，通过队列的特性实现O(n)时间复杂度 O(n) O(n) 利用双端队列优化滑动窗口的最大值查找，代码逻辑清晰 🔗直达
BM46 最小的K个数 使用大根堆或小根堆筛选最小的K个数，通过堆的特性优化查找效率 O(nlogk) O(k) 提供了多种解法，包括排序、大根堆和小根堆，代码可读性强 🔗直达
BM47 寻找第K大 使用大根堆或排序找到第K大的元素，通过堆的特性优化查找效率 O(nlogn) O(1) 提供了多种解法，包括大根堆、排序和模拟快排，代码逻辑清晰 🔗直达
BM48 数据流中的中位数 使用两个堆（最大堆和最小堆）动态维护中位数，通过堆的特性实现高效查找 O(nlogn) O(n) 利用两个堆的特性优化中位数的查找，代码结构合理 🔗直达
BM49 表达式求值 使用递归和栈解析表达式，支持加减乘和括号 O(n) O(n) 使用递归和栈实现表达式求值，代码逻辑清晰，易于扩展 🔗直达

✅ 建议复习顺序（由易到难）：

BM42 → BM44 → BM43 → BM45 → BM46 → BM47 → BM48 → BM49

BM42 用两个栈实现队列

用两个栈实现队列_牛客题霸_牛客网
https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=295&tqId=23281&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>(); // 1. 主栈，用于存储所有元素
    Stack<Integer> stack2 = new Stack<Integer>(); // 2. 辅助栈，用于反转元素顺序

    public void push(int node) {
        stack1.push(node); // 3. 将新元素压入主栈
    }
    
    public int pop() {
        int ans = 0; // 4. 初始化返回值
        // 5. 将主栈中的所有元素依次弹出并压入辅助栈，实现反转
        while(!stack1.isEmpty()) {stack2.push(stack1.pop());}
        ans = stack2.pop(); // 6. 弹出辅助栈的栈顶元素，即原主栈的栈底元素
        // 7. 将辅助栈中的剩余元素依次弹出并重新压回主栈，恢复原顺序
        while(!stack2.isEmpty()) {stack1.push(stack2.pop());}
        return ans; // 8. 返回弹出的元素
    }
}

BM43 包含min函数的栈

包含min函数的栈_牛客题霸_牛客网
https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;
import java.util.Stack;

public class Solution {

    Stack<Integer> s1 = new Stack<Integer>(); // 1. 主栈，用于存储所有元素
    Stack<Integer> s2 = new Stack<Integer>(); // 2. 辅助栈，用于存储当前最小值

    public void push(int node) {
        s1.push(node); // 3. 将新元素压入主栈
        if (s2.isEmpty() || s2.peek() > node) { // 4. 如果辅助栈为空或当前元素小于辅助栈栈顶元素
            s2.push(node); // 5. 将当前元素压入辅助栈
        } else {
            s2.push(s2.peek()); // 6. 否则，将辅助栈栈顶元素再次压入辅助栈
        }
    }
    
    public void pop() {
        s1.pop(); // 7. 弹出主栈栈顶元素
        s2.pop(); // 8. 同时弹出辅助栈栈顶元素
    }
    
    public int top() {
        return s1.peek(); // 9. 返回主栈栈顶元素
    }
    
    public int min() {
        return s2.peek(); // 10. 返回辅助栈栈顶元素，即当前最小值
    }
}

BM44 有效括号序列

有效括号序列_牛客题霸_牛客网
https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<Character>(); // 1. 创建一个栈用于存储预期的闭合字符

        for (int i = 0; i < s.length(); i++) { // 2. 遍历字符串中的每个字符
            if (s.charAt(i) == '(') st.push(')'); // 3. 如果是左括号 '('，压入对应的右括号 ')'
            else if (s.charAt(i) == '[') st.push(']'); // 4. 如果是左括号 '[', 压入对应的右括号 ']'
            else if (s.charAt(i) == '{') st.push('}'); // 5. 如果是左括号 '{', 压入对应的右括号 '}'
            else if (st.isEmpty() || st.pop() != s.charAt(i)) return false; // 6. 如果是右括号，检查栈是否为空或栈顶元素是否匹配
        }
        return st.isEmpty(); // 7. 如果栈为空，说明所有括号都正确匹配
    }
}

BM45 滑动窗口的最大值

滑动窗口的最大值_牛客题霸_牛客网
https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
2025年8月18日20:05:05 2025年8月18日20:39:57 （- 8:20）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;

public class Solution {

    public ArrayList<Integer> maxInWindows(int[] num, int size) {
        Deque<Integer> dq = new ArrayDeque<>(); // 1. 创建一个双端队列，用于存储窗口中的索引
        ArrayList<Integer> ans = new ArrayList<>(); // 2. 创建一个列表，用于存储每个窗口的最大值
        int n = num.length; // 3. 获取数组的长度
        if (num.length == 0 || size < 1 || size > num.length) return ans; // 4. 如果数组为空或窗口大小无效，直接返回空列表
        for (int i = 0; i < n; i++) { // 5. 遍历数组
            while (!dq.isEmpty() && num[dq.peekLast()] < num[i]) { // 6. 如果队列不为空且队尾元素对应的值小于当前值
                dq.pollLast(); // 7. 移除队尾元素
            }
            dq.addLast(i); // 8. 将当前索引加入队列
            if (dq.peekFirst() + size <= i) { // 9. 如果队首元素对应的窗口已经滑过当前索引
                dq.pollFirst(); // 10. 移除队首元素
            }
            if (i + 1 >= size) { // 11. 如果已经形成窗口
                ans.add(num[dq.peekFirst()]); // 12. 将队首元素对应的值加入答案列表
            }
        }
        return ans; // 13. 返回结果列表
    }
}

BM46 最小的K个数

最小的K个数_牛客题霸_牛客网
https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
2025年8月18日20:50:45 2025年8月18日20:58:33

  1. 排序
1
2
3
4
5
6
7
8
9
10
11
12
import java.util.*;

public class Solution {

    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        int[] ans = Arrays.copyOfRange(input, 0, input.length); // 1. 复制输入数组
        Arrays.sort(ans); // 2. 对复制的数组进行排序
        ArrayList<Integer> ans2 = new ArrayList<Integer>(); // 3. 创建一个列表用于存储结果
        for (int i = 0; i < k; i++) ans2.add(ans[i]); // 4. 将前 k 个最小的数加入列表
        return ans2; // 5. 返回结果列表
    }
}
  1. 大根堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;

public class Solution {

    public ArrayList<Integer> GetLeastNumbers_Solution(int[] in, int k) {
        ArrayList<Integer> ans = new ArrayList<Integer>(); // 1. 创建一个列表用于存储结果
        int n = in.length; // 2. 获取输入数组的长度
        if (k == 0 || n == 0) return ans; // 3. 如果 k 为 0 或数组为空，直接返回空列表
        PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> o2 - o1); // 4. 创建一个最大堆
        for (int i = 0; i < k; i++) { // 5. 将前 k 个元素加入最大堆
            q.offer(in[i]);
        }
        for (int i = k; i < n; i++) { // 6. 遍历剩余的元素
            if (q.peek() > in[i]) { // 7. 如果当前元素小于堆顶元素
                q.poll(); // 8. 移除堆顶元素
                q.offer(in[i]); // 9. 将当前元素加入堆
            }
        }
        for (int i = 0; i < k; i++) { // 10. 将堆中的元素加入结果列表
            ans.add(q.poll());
        }
        return ans; // 11. 返回结果列表
    }
}
  1. 小根堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;

public class Solution {

    public ArrayList<Integer> GetLeastNumbers_Solution(int[] in, int k) {
        ArrayList<Integer> ans = new ArrayList<Integer>(); // 1. 创建一个列表用于存储结果
        int n = in.length; // 2. 获取输入数组的长度
        if (k == 0 || n == 0) return ans; // 3. 如果 k 为 0 或数组为空，直接返回空列表
        PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> o1 - o2); // 4. 创建一个最小堆
        for (int i = 0; i < n; i++) q.add(in[i]);// 5. 将所有元素加入最小堆
        for (int i = 0; i < k; i++) ans.add(q.poll()); // 6. 从最小堆中取出前 k 个最小的元素
        return ans; // 7. 返回结果列表
    }
}

BM47 寻找第K大

寻找第K大_牛客题霸_牛客网
https://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page

  • 2025年8月18日21:12:31
  1. 大根堆
1
2
3
4
5
6
7
8
9
10
import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> o2 - o1); // 1. 创建一个最大堆
        for (int i = 0; i < n; i++) q.add(a[i]); // 2. 将所有元素加入最大堆
        for (int i = 0; i < K - 1; i++) q.poll(); // 3. 移除堆顶元素 K-1 次
        return q.poll(); // 4. 第 K 次移除的元素即为第 K 大的元素
    }
}
  1. 排序
1
2
3
4
5
6
7
8
import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        Arrays.sort(a); // 1. 对数组进行升序排序
        return a[n - K]; // 2. 返回第 K 大的元素（从后往前数第 K 个元素）
    }
}
  1. 模拟快排 归并找到倒第K个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.util.*;

public class Solution {
    Random r = new Random(); // 1. 创建一个随机数生成器，用于随机选择基准元素

    // 2. 定义一个交换函数，用于交换数组中的两个元素
    void swap(int arr[], int a, int b) {
        int temp = arr[a]; // 3. 临时变量存储 arr[a] 的值
        arr[a] = arr[b]; // 4. 将 arr[b] 的值赋给 arr[a]
        arr[b] = temp; // 5. 将临时变量的值赋给 arr[b]
    }

    // 6. 辅助函数，用于递归查找第 K 小的元素
    int partition(int[] a, int low, int high, int k) {
        // 7. 随机选择一个基准元素的索引
        int x = Math.abs(r.nextInt()) % (high - low + 1) + low;
        // 8. 将基准元素交换到数组的起始位置
        swap(a, low, x);
        // 9. 保存基准元素的值
        int v = a[low];
        // 10. 初始化指针 i，从基准元素的下一个位置开始
        int i = low + 1;
        // 11. 初始化指针 j，从数组的末尾开始
        int j = high;

        // 12. 开始分区过程
        while (true) {
            // 13. 从右向左找到第一个大于基准元素的值
            while (j >= low + 1 && a[j] < v) j--;
            // 14. 从左向右找到第一个小于基准元素的值
            while (i <= high && a[i] > v) i++;
            // 15. 如果 i 和 j 交叉，结束循环
            if (i > j) break;
            // 16. 交换 i 和 j 位置的元素
            swap(a, i, j);
            // 17. 移动指针
            i++;
            j--;
        }

        // 18. 将基准元素交换到正确的位置
        swap(a, low, j);
        // 19. 如果基准元素的位置正好是第 K 小的元素，返回该值
        if (j + 1 == k) return a[j];
        // 20. 如果基准元素的位置小于 K，递归查找右半部分
        else if (j + 1 < k) return partition(a, j + 1, high, k);
        // 21. 如果基准元素的位置大于 K，递归查找左半部分
        else return partition(a, low, j - 1, k);
    }

    // 22. 主函数，调用辅助函数 partition，从数组的起始位置开始查找第 K 小的元素
    public int findKth(int[] a, int n, int K) {
        return partition(a, 0, n - 1, K);
    }
}

BM48 数据流中的中位数

数据流中的中位数_牛客题霸_牛客网
https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
2025年8月18日21:28:49 2025年8月18日22:09:09

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;

public class Solution {

    private PriorityQueue<Integer> midr = new PriorityQueue<>(); // 1. 创建一个最小堆，用于存储较大的一半数字
    private PriorityQueue<Integer> midl = new PriorityQueue<>(Collections.reverseOrder()); // 2. 创建一个最大堆，用于存储较小的一半数字
    public void Insert(Integer num) {// 3. 插入一个新数字
        midl.offer(num); // 4. 将新数字插入最大堆
        midr.offer(midl.poll()); // 5. 将最大堆的堆顶元素（当前最大堆中的最小值）移入最小堆
        if (midl.size() < midr.size()) midl.offer(midr.poll()); // 6. 如果最大堆的大小小于最小堆，将最小堆的堆顶元素移回最大堆，以保持平衡
    }
    public Double GetMedian() {    // 7. 获取当前数列的中位数
        if (midl.size() > midr.size()) return (double) midl.peek();// 8. 如果最大堆的大小大于最小堆，说明数列有奇数个元素，中位数是最大堆的堆顶元素
        else return (double) (midl.peek() + midr.peek()) / 2;// 9. 如果最大堆和最小堆的大小相等，说明数列有偶数个元素，中位数是两个堆顶元素的平均值
    }
}

BM49 表达式求值

表达式求值_牛客题霸_牛客网
https://www.nowcoder.com/practice/c215ba61c8b1443b996351df929dc4d4?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.util.*;

public class Solution {
    // 1. 定义一个递归函数，用于解析表达式
    ArrayList<Integer> func(String s, int idx) {
        Stack<Integer> st = new Stack<Integer>(); // 2. 创建一个栈，用于存储中间结果
        int num = 0; // 3. 初始化当前数字
        char op = '+'; // 4. 初始化当前操作符为加法
        int i;
        // 5. 遍历字符串
        for (i = idx; i < s.length(); i++) {
            // 6. 如果当前字符是数字
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                num = num * 10 + (s.charAt(i) - '0'); // 7. 构造多位数
                if (i != s.length() - 1) continue; // 8. 如果不是最后一个字符，继续
            }
            // 9. 如果当前字符是左括号
            if (s.charAt(i) == '(') {
                ArrayList<Integer> res = func(s, i + 1); // 10. 递归解析括号内的表达式
                num = res.get(0); // 11. 获取括号内的结果
                i = res.get(1); // 12. 更新索引
                if (i != s.length() - 1) continue; // 13. 如果不是最后一个字符，继续
            }
            // 14. 根据当前操作符处理数字
            switch (op) {
                case '+':
                    st.push(num); // 15. 加法：将数字压入栈
                    break;
                case '-':
                    st.push(-num); // 16. 减法：将负数压入栈
                    break;
                case '*':
                    int temp = st.pop(); // 17. 乘法：弹出栈顶元素并乘以当前数字
                    st.push(temp * num);
                    break;
            }
            num = 0; // 18. 重置当前数字
            // 19. 如果遇到右括号，结束当前表达式的解析
            if (s.charAt(i) == ')') {
                break;
            } else {
                op = s.charAt(i); // 20. 更新当前操作符
            }
        }
        // 21. 计算栈中所有数字的总和
        int sum = 0;
        while (!st.isEmpty()) {
            sum += st.pop();
        }
        // 22. 返回结果和当前索引
        ArrayList<Integer> temp = new ArrayList<Integer>();
        temp.add(sum);
        temp.add(i);
        return temp;
    }

    // 23. 主函数，调用递归函数解析整个表达式
    public int solve(String s) {
        ArrayList<Integer> ans = func(s, 0);
        return ans.get(0); // 24. 返回最终结果
    }
}

哈希

题号 题目名称 核心思路 时间复杂度 空间复杂度 代码亮点 牛客原题链接
BM50 两数之和 使用哈希表存储目标值与当前值的差值及其索引，快速查找 O(n) O(n) 使用哈希表优化查找过程，逻辑简洁 🔗 直达
BM51 数组中出现次数超过一半的数字 使用哈希表统计每个数字的出现次数 O(n) O(n) 使用哈希表快速统计次数，逻辑清晰 🔗 直达
BM52 数组中只出现一次的两个数字 使用哈希表统计每个数字的出现次数，找出只出现一次的数字 O(n) O(n) 使用哈希表优化查找过程，逻辑简洁 🔗 直达
BM53 缺失的第一个正整数 使用集合存储数组中的数字，查找最小未出现的正整数 O(n) O(n) 使用集合优化查找过程，逻辑简洁 🔗 直达
BM54 三数之和 排序后使用双指针查找满足条件的三元组 O(n^2) O(n) 使用排序和双指针优化查找过程，逻辑清晰 🔗 直达

✅ 建议复习顺序（由易到难）：

BM50 → BM51 → BM52 → BM53 → BM54

BM50 两数之和

两数之和_牛客题霸_牛客网
https://www.nowcoder.com/practice/20ef0972485e41019e39543e8e895b7f?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        HashMap<Integer, Integer> mp = new HashMap<>(); // 1. 创建一个哈希表，用于存储目标值与当前值的差值及其索引
        for (int i = 0; i < numbers.length; i++) { // 2. 遍历数组
            if (mp.containsKey(numbers[i])) { // 3. 如果哈希表中包含当前值
                int x = mp.get(numbers[i]); // 4. 获取哈希表中存储的索引
                return new int[]{x + 1, i + 1}; // 5. 返回两个索引（加1是因为题目要求从1开始计数）
            }
            mp.put(target - numbers[i], i); // 6. 将目标值与当前值的差值及其索引存入哈希表
        }
        return null; // 7. 如果没有找到符合条件的两个数，返回null
    }
}

BM51 数组中出现次数超过一半的数字

数组中出现次数超过一半的数字_牛客题霸_牛客网
https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj
2025年8月19日16:55:36 2025年8月19日16:57:20

1
2
3
4
5
6
7
8
9
10
11
12
import java.util.*;

public class Solution {
    public int MoreThanHalfNum_Solution(int[] numbers) {
        Map<Integer, Integer> mp = new HashMap<>(); // 1. 创建一个哈希表，用于存储每个数字及其出现次数
        for (int i : numbers) { // 2. 遍历数组
            mp.merge(i, 1, Integer::sum); // 3. 使用 merge 方法更新数字的出现次数
            if (mp.get(i) * 2 > numbers.length) return i; // 4. 如果当前数字的出现次数超过数组长度的一半，返回该数字
        }
        return 0; // 5. 如果没有找到符合条件的数字，返回 0
    }
}

BM52 数组中只出现一次的两个数字

数组中只出现一次的两个数字_牛客题霸_牛客网
https://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj
2025年8月19日16:57:47 2025年8月19日17:06:07

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;

public class Solution {
    public int[] FindNumsAppearOnce(int[] nums) {
        Map<Integer, Integer> mp = new HashMap<>(); // 1. 创建一个哈希表，用于存储每个数字及其出现次数
        for (int i : nums) { // 2. 遍历数组
            mp.merge(i, 1, Integer::sum); // 3. 使用 merge 方法更新数字的出现次数
        }
        ArrayList<Integer> ans = new ArrayList<Integer>(); // 4. 创建一个列表，用于存储只出现一次的数字
        for (Map.Entry<Integer, Integer> m : mp.entrySet()) { // 5. 遍历哈希表
            System.out.print(m.getKey() + " " + m.getValue()); // 6. 打印键值对（可选，用于调试）
            if (m.getValue() == 1) ans.add(m.getKey()); // 7. 如果某个数字的出现次数为 1，将其加入列表
        }
        int[] res = new int[2]; // 8. 创建一个数组，用于存储结果
        for (int i = 0; i < 2; i++) res[i] = ans.get(i); // 9. 将列表中的数字复制到数组
        return res; // 10. 返回结果数组
    }
}

BM53 缺失的第一个正整数

缺失的第一个正整数_牛客题霸_牛客网
https://www.nowcoder.com/practice/50ec6a5b0e4e45348544348278cdcee5?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj
2025年8月19日17:06:49 2025年8月19日17:08:24

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;

public class Solution {
    public int minNumberDisappeared(int[] nums) {
        Set<Integer> s = new HashSet<>(); // 1. 创建一个集合，用于存储数组中的数字
        for (int i : nums) { // 2. 遍历数组
            s.add(i); // 3. 将每个数字加入集合
        }
        int ans = 1; // 4. 初始化最小未出现的正整数为 1
        while (s.contains(ans)) { // 5. 如果当前数字在集合中，继续查找下一个数字
            ans++;
        }
        return ans; // 6. 返回最小未出现的正整数
    }
}

BM54 三数之和

三数之和_牛客题霸_牛客网
https://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj
2025年8月19日17:09:15 2025年8月19日17:44:12

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        int n = num.length; // 1. 获取数组长度
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>(); // 2. 创建一个列表，用于存储结果
        if (n < 3) return ans; // 3. 如果数组长度小于3，直接返回空结果
        Arrays.sort(num); // 4. 对数组进行排序，便于后续处理
        for (int i = 0; i < num.length - 2; i++) { // 5. 遍历数组，固定第一个数
            int j = i + 1; // 6. 初始化第二个数的指针
            int k = num.length - 1; // 7. 初始化第三个数的指针
            int t = -num[i]; // 8. 计算目标值，即 -num[i]
            while (j < k) { // 9. 当第二个数的指针小于第三个数的指针时，继续查找
                if (num[j] + num[k] > t) k--; // 10. 如果当前和大于目标值，移动第三个数的指针
                else if (num[j] + num[k] < t) j++; // 11. 如果当前和小于目标值，移动第二个数的指针
                else {
                    // 12. 找到一个满足条件的三元组
                    ArrayList<Integer> l = new ArrayList<>(Arrays.asList(num[i], num[j], num[k]));
                    ans.add(l); // 13. 将三元组加入结果列表
                    // 14. 跳过重复的第二个数
                    while (j + 1 < k && num[j + 1] == num[j]) j++;
                    // 15. 跳过重复的第三个数
                    while (k - 1 > j && num[k - 1] == num[k]) k--;
                    j++; // 16. 移动第二个数的指针
                    k--; // 17. 移动第三个数的指针
                }
            }
            // 18. 跳过重复的第一个数
            while (i + 1 < num.length - 2 && num[i + 1] == num[i]) i++;
        }
        return ans; // 19. 返回结果
    }
}

递归/回溯

题号 题目名称 核心思路 时间复杂度 空间复杂度 代码亮点 牛客原题链接
BM55 没有重复项数字的全排列 使用回溯法生成所有排列 O(n!) O(n) 使用回溯法生成所有排列，逻辑清晰 🔗 直达
BM56 有重复项数字的全排列 使用回溯法生成所有排列，并通过排序和剪枝去重 O(n!) O(n) 使用排序和剪枝去重，避免重复排列 🔗 直达
BM57 岛屿数量 使用深度优先搜索（DFS）或广度优先搜索（BFS）标记岛屿 O(n×m) O(n×m) 使用DFS或BFS标记岛屿，逻辑清晰 🔗 直达
BM58 字符串的排列 使用回溯法生成所有排列，并通过排序和剪枝去重 O(n!) O(n) 使用排序和剪枝去重，避免重复排列 🔗 直达
BM59 N皇后问题 使用回溯法放置皇后，并通过判断函数检查冲突 O(n!) O(n) 使用回溯法放置皇后，逻辑清晰 🔗 直达
BM60 括号生成 使用回溯法生成所有合法括号组合 O(2^n) O(n) 使用回溯法生成所有合法括号组合，逻辑清晰 🔗 直达
BM61 矩阵最长递增路径 使用深度优先搜索（DFS）和动态规划（DP）计算最长递增路径 O(n×m) O(n×m) 使用DFS和DP计算最长递增路径，逻辑清晰 🔗 直达

✅ 建议复习顺序（由易到难）：

BM55 → BM56 → BM57 → BM60 → BM58→ BM61→ BM59

BM55 没有重复项数字的全排列

没有重复项数字的全排列_牛客题霸_牛客网
https://www.nowcoder.com/practice/4bcf3081067a4d028f95acee3ddcd2b1?tpId=295&tqId=701&sourceUrl=%2Fexam%2Foj

  1. 搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.*;

public class Solution {
    // 1. 回溯函数，用于生成排列
    void backTrack(int[] num, LinkedList<Integer> cur, ArrayList<ArrayList<Integer>> res) {
        if (cur.size() == num.length) { // 2. 如果当前排列的大小等于数组长度，说明已经生成了一个完整的排列
            res.add(new ArrayList<>(cur)); // 3. 将当前排列添加到结果列表中
            return;
        }
        for (int i = 0; i < num.length; i++) { // 4. 遍历数组中的每个数字
            if (cur.contains(num[i])) { // 5. 如果当前数字已经在排列中，跳过
                continue;
            }
            cur.add(num[i]); // 6. 将当前数字添加到排列中
            backTrack(num, cur, res); // 7. 递归调用回溯函数
            cur.removeLast(); // 8. 回溯，移除最后一个添加的数字
        }
    }

    // 9. 主函数，生成给定数组的所有排列
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); // 10. 创建结果列表
        LinkedList<Integer> cur = new LinkedList<>(); // 11. 创建当前排列的列表
        backTrack(num, cur, res); // 12. 调用回溯函数
        return res; // 13. 返回结果列表
    }
}
  1. 使用记忆数组标记
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;

public class Solution {
    // 1. 回溯函数，用于生成排列
    void backTrack(int[] num, LinkedList<Integer> cur, ArrayList<ArrayList<Integer>> res, boolean[] vis) {
        if (cur.size() == num.length) { // 2. 如果当前排列的大小等于数组长度，说明已经生成了一个完整的排列
            res.add(new ArrayList<>(cur)); // 3. 将当前排列添加到结果列表中
            return;
        }
        for (int i = 0; i < num.length; i++) { // 4. 遍历数组中的每个数字
            if (vis[i]) { // 5. 如果当前数字已经被访问过，跳过
                continue;
            }
            cur.add(num[i]); // 6. 将当前数字添加到排列中
            vis[i] = true; // 7. 标记当前数字为已访问
            backTrack(num, cur, res, vis); // 8. 递归调用回溯函数
            cur.removeLast(); // 9. 回溯，移除最后一个添加的数字
            vis[i] = false; // 10. 回溯，标记当前数字为未访问
        }
    }

    // 11. 主函数，生成给定数组的所有排列
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); // 12. 创建结果列表
        LinkedList<Integer> cur = new LinkedList<>(); // 13. 创建当前排列的列表
        boolean[] vis = new boolean[num.length]; // 14. 创建布尔数组，用于记录每个数字是否已经被访问过
        backTrack(num, cur, res, vis); // 15. 调用回溯函数
        return res; // 16. 返回结果列表
    }
}

BM56 有重复项数字的全排列

有重复项数字的全排列_牛客题霸_牛客网
https://www.nowcoder.com/practice/a43a2b986ef34843ac4fdd9159b69863?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;

public class Solution {
    // 1. 递归函数，用于生成排列
    public void recursion(ArrayList<ArrayList<Integer>> res, int[] num, ArrayList<Integer> temp, Boolean[] vis) {
        if (temp.size() == num.length) { // 2. 如果当前排列的大小等于数组长度，说明已经生成了一个完整的排列
            res.add(new ArrayList<Integer>(temp)); // 3. 将当前排列添加到结果列表中
            return;
        }
        for (int i = 0; i < num.length; i++) { // 4. 遍历数组中的每个数字
            if (vis[i]) // 5. 如果当前数字已经被访问过，跳过
                continue;
            // 6. 剪枝：如果当前数字与前一个数字相同，且前一个数字未被访问过，则跳过
            if (i > 0 && num[i - 1] == num[i] && !vis[i - 1])
                continue;
            vis[i] = true; // 7. 标记当前数字为已访问
            temp.add(num[i]); // 8. 将当前数字添加到排列中
            recursion(res, num, temp, vis); // 9. 递归调用
            vis[i] = false; // 10. 回溯，标记当前数字为未访问
            temp.remove(temp.size() - 1); // 11. 回溯，移除最后一个添加的数字
        }
    }

    // 12. 主函数，生成给定数组的所有唯一排列
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        Arrays.sort(num); // 13. 对数组进行排序，便于剪枝
        Boolean[] vis = new Boolean[num.length]; // 14. 创建布尔数组，用于记录每个数字是否已经被访问过
        Arrays.fill(vis, false); // 15. 初始化布尔数组为 false
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); // 16. 创建结果列表
        ArrayList<Integer> temp = new ArrayList<Integer>(); // 17. 创建当前排列的列表
        recursion(res, num, temp, vis); // 18. 调用递归函数
        return res; // 19. 返回结果列表
    }
}

BM57 岛屿数量

岛屿数量_牛客题霸_牛客网
https://www.nowcoder.com/practice/0c9664d1554e466aa107d899418e814e?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.*;

public class Solution {
    int[] dx = {1, -1, 0, 0}; // 1. 定义四个方向的行偏移量
    int[] dy = {0, 0, 1, -1}; // 2. 定义四个方向的列偏移量
    // 3. 深度优先搜索函数，用于标记与当前岛屿相连的所有陆地
    void dfs(char[][] grid, int i, int j) {
        int n = grid.length; // 4. 获取网格的行数
        int m = grid[0].length; // 5. 获取网格的列数
        grid[i][j] = '0'; // 6. 将当前陆地标记为已访问（用 '0' 表示水）
        // 7. 遍历四个方向
        for (int k = 0; k < 4; k++) {
            int ti = i + dx[k]; // 8. 计算新行索引
            int tj = j + dy[k]; // 9. 计算新列索引
            // 10. 检查新索引是否在网格范围内且新位置是陆地
            if (ti >= 0 && ti < n && tj >= 0 && tj < m && grid[ti][tj] == '1') {
                dfs(grid, ti, tj); // 11. 递归调用 dfs，标记相连的陆地
            }
        }
    }
    // 12. 主函数，计算网格中的岛屿数量
    public int solve(char[][] grid) {
        int n = grid.length; // 13. 获取网格的行数
        if (n == 0) return 0; // 14. 如果网格为空，返回 0
        int m = grid[0].length; // 15. 获取网格的列数
        int cnt = 0; // 16. 初始化岛屿数量
        // 17. 遍历网格的每个位置
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') { // 18. 如果当前位置是陆地
                    cnt++; // 19. 岛屿数量加 1
                    dfs(grid, i, j); // 20. 调用 dfs，标记与当前岛屿相连的所有陆地
                }
            }
        }
        return cnt; // 21. 返回岛屿数量
    }
}
  1. BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.*;

public class Solution {
    int dx[] = {0, 0, 1, -1}; // 1. 定义四个方向的行偏移量
    int dy[] = {1, -1, 0, 0}; // 2. 定义四个方向的列偏移量
    int n = 0; // 3. 网格的行数
    int m = 0; // 4. 网格的列数
    int cnt = 0; // 5. 岛屿的数量

    // 6. 定义一个内部类 Node，用于存储网格中的位置
    class Node {
        int i;
        int j;
        public Node(int i, int j) { // 7. 构造函数，初始化位置
            this.i = i;
            this.j = j;
        }
    }

    // 8. 广度优先搜索函数，用于标记与当前岛屿相连的所有陆地
    void bfs(char[][] grid, int i, int j) {
        Queue<Node> q = new LinkedList<>(); // 9. 创建一个队列，用于 BFS
        q.add(new Node(i, j)); // 10. 将起始位置加入队列
        while (!q.isEmpty()) { // 11. 当队列不为空时，继续遍历
            Node t = q.poll(); // 12. 弹出队列中的第一个节点
            grid[t.i][t.j] = '0'; // 13. 将当前陆地标记为已访问（用 '0' 表示水）
            for (int k = 0; k < 4; k++) { // 14. 遍历四个方向
                int ti = dx[k] + t.i; // 15. 计算新行索引
                int tj = dy[k] + t.j; // 16. 计算新列索引
                // 17. 检查新索引是否在网格范围内且新位置是陆地
                if (ti >= 0 && tj >= 0 && ti < n && tj < m && grid[ti][tj] == '1') {
                    q.add(new Node(ti, tj)); // 18. 将新位置加入队列
                }
            }
        }
        cnt++; // 19. 岛屿数量加 1
    }

    // 20. 主函数，计算网格中的岛屿数量
    public int solve(char[][] grid) {
        this.n = grid.length; // 21. 获取网格的行数
        if (n == 0) return 0; // 22. 如果网格为空，返回 0
        this.m = grid[0].length; // 23. 获取网格的列数
        this.cnt = 0; // 24. 初始化岛屿数量
        for (int i = 0; i < n; i++) { // 25. 遍历网格的每一行
            for (int j = 0; j < m; j++) { // 26. 遍历网格的每一列
                if (grid[i][j] == '1') { // 27. 如果当前位置是陆地
                    bfs(grid, i, j); // 28. 调用 bfs，标记与当前岛屿相连的所有陆地
                }
            }
        }
        return cnt; // 29. 返回岛屿数量
    }
}

BM58 字符串的排列

字符串的排列_牛客题霸_牛客网
https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=295&tqId=23291&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;

public class Solution {
    public void recursion(ArrayList<String> res, char[] str, StringBuffer temp, boolean[] vis) {
        if (temp.length() == str.length) { // 1. 如果当前排列的长度等于字符串长度，说明已经生成了一个完整的排列
            res.add(new String(temp)); // 2. 将当前排列添加到结果列表中
            return;
        }
        for (int i = 0; i < str.length; i++) { // 3. 遍历字符串中的每个字符
            if (vis[i]) // 4. 如果当前字符已经被访问过，跳过
                continue;
            if (i > 0 && str[i - 1] == str[i] && !vis[i - 1]) // 5. 剪枝：如果当前字符与前一个字符相同，且前一个字符未被访问过，则跳过
                continue;
            vis[i] = true; // 6. 标记当前字符为已访问
            temp.append(str[i]); // 7. 将当前字符添加到排列中
            recursion(res, str, temp, vis); // 8. 递归调用
            vis[i] = false; // 9. 回溯，标记当前字符为未访问
            temp.deleteCharAt(temp.length() - 1); // 10. 回溯，移除最后一个添加的字符
        }
    }

    public ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<String>(); // 11. 创建结果列表
        if (str == null || str.length() == 0) // 12. 如果字符串为空，返回空列表
            return res;
        char[] charStr = str.toCharArray(); // 13. 将字符串转换为字符数组
        Arrays.sort(charStr); // 14. 对字符数组进行排序，便于剪枝
        boolean[] vis = new boolean[str.length()]; // 15. 创建布尔数组，用于记录每个字符是否已经被访问过
        Arrays.fill(vis, false); // 16. 初始化布尔数组为 false
        StringBuffer temp = new StringBuffer(); // 17. 创建当前排列的字符串缓冲区
        recursion(res, charStr, temp, vis); // 18. 调用递归函数
        return res; // 19. 返回结果列表
    }
}

BM59 N皇后问题

N皇后问题_牛客题霸_牛客网
https://www.nowcoder.com/practice/c76408782512486d91eea181107293b6?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. BF 递归 +判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;

public class Solution {
    private int res; // 1. 用于存储解决方案的数量

    public boolean isValid(int[] pos, int row, int col) {
        for (int i = 0; i < row; i++) { // 2. 遍历之前的行
            if (col == pos[i] || Math.abs(row - i) == Math.abs(col - pos[i])) { // 3. 检查列冲突和对角线冲突
                return false; // 4. 如果有冲突，返回 false
            }
        }
        return true; // 5. 如果没有冲突，返回 true
    }

    public void recursion(int n, int row, int[] pos) {
        if (row == n) { // 6. 如果已经放置了 n 个皇后
            res++; // 7. 解决方案数量加 1
            return;
        }
        for (int i = 0; i < n; i++) { // 8. 遍历当前行的所有列
            if (isValid(pos, row, i)) { // 9. 如果在第 i 列放置皇后有效
                pos[row] = i; // 10. 在第 row 行第 i 列放置皇后
                recursion(n, row + 1, pos); // 11. 递归调用，尝试放置下一个皇后
            }
        }
    }

    public int Nqueen(int n) {
        res = 0; // 12. 初始化解决方案数量为 0
        int[] pos = new int[n]; // 13. 创建一个数组，用于存储每行皇后的列位置
        Arrays.fill(pos, 0); // 14. 初始化数组
        recursion(n, 0, pos); // 15. 调用递归函数
        return res; // 16. 返回解决方案数量
    }
}
  1. 使用哈希表维护
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;
public class Solution {
    Set<Integer> col = new HashSet<Integer>(); // 1. 标记列不可用
    Set<Integer> posSlant = new HashSet<Integer>();// 2. 标记正斜线不可用
    Set<Integer> conSlant = new HashSet<Integer>();// 3. 标记反斜线不可用
    int result = 0; // 4. 用于存储解决方案的数量

    public int Nqueen(int n) {
        recursion(0, n); // 5. 调用递归函数，从第 0 行开始
        return result; // 6. 返回解决方案的数量
    }

    private void recursion(int i, int n) {
        if (i == n) { // 7. 如果已经放置了 n 个皇后
            result++; // 8. 解决方案数量加 1
            return;
        }
        for (int j = 0; j < n; j++) { // 9. 遍历当前行的所有列
            if (col.contains(j) || posSlant.contains(i - j) || conSlant.contains(i + j)) { // 10. 检查列、正斜线和反斜线是否冲突
                continue; // 11. 如果有冲突，跳过当前列
            }
            col.add(j); // 12. 标记当前列不可用
            posSlant.add(i - j); // 13. 标记当前正斜线不可用
            conSlant.add(i + j); // 14. 标记当前反斜线不可用
            recursion(i + 1, n); // 15. 递归调用，尝试放置下一个皇后
            col.remove(j); // 16. 回溯，清除当前列的标记
            posSlant.remove(i - j); // 17. 回溯，清除当前正斜线的标记
            conSlant.remove(i + j); // 18. 回溯，清除当前反斜线的标记
        }
    }
}
  1. 位运算优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;

public class Solution {
    int res; // 1. 用于存储解决方案的数量

    public void backtrack(int i, int col, int pos, int neg, int n) {
        if (i == n) { // 2. 如果已经放置了 n 个皇后
            res++; // 3. 解决方案数量加 1
            return;
        }
        int pre = ~(col | pos | neg) & ((1 << n) - 1); // 4. 计算当前行可以放置皇后的列
        while (pre > 0) { // 5. 遍历可以放置皇后的位置
            int cur = pre & (-pre); // 6. 找到最低位的 1，表示当前可以放置皇后的位置
            backtrack(i + 1, col | cur, (pos | cur) >> 1, (neg | cur) << 1, n); // 7. 递归调用，尝试放置下一个皇后
            pre &= pre - 1; // 8. 移除最低位的 1，继续检查下一个位置
        }
    }

    public int Nqueen(int n) {
        res = 0; // 9. 初始化解决方案数量为 0
        backtrack(0, 0, 0, 0, n); // 10. 调用回溯函数，从第 0 行开始
        return res; // 11. 返回解决方案的数量
    }
}

BM60 括号生成

括号生成_牛客题霸_牛客网
https://www.nowcoder.com/practice/c9addb265cdf4cdd92c092c655d164ca?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;

public class Solution {
    public void recursion(int left, int right, String temp, ArrayList<String> res, int n) {
        if (left == n && right == n) { // 1. 如果左括号和右括号的数量都达到 n
            res.add(temp); // 2. 将当前组合添加到结果列表中
            return;
        }
        if (left < n) { // 3. 如果左括号的数量小于 n
            recursion(left + 1, right, temp + "(", res, n); // 4. 递归调用，添加一个左括号
        }
        if (right < n && left > right) { // 5. 如果右括号的数量小于 n 且左括号的数量大于右括号的数量
            recursion(left, right + 1, temp + ")", res, n); // 6. 递归调用，添加一个右括号
        }
    }

    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> res = new ArrayList<String>(); // 7. 创建结果列表
        recursion(0, 0, "", res, n); // 8. 调用递归函数，从 0 个左括号和 0 个右括号开始
        return res; // 9. 返回结果列表
    }
}

BM61 矩阵最长递增路径

矩阵最长递增路径_牛客题霸_牛客网
https://www.nowcoder.com/practice/7a71a88cdf294ce6bdf54c899be967a2?tpId=295&tqId=1076860&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.*;

public class Solution {
    int[] dx = {0, 0, 1, -1}; // 1. 定义四个方向的行偏移量
    int[] dy = {1, -1, 0, 0}; // 2. 定义四个方向的列偏移量
    int n, m; // 3. 定义矩阵的行数和列数

    // 4. 深度优先搜索函数，用于计算从 (i, j) 开始的最长递增路径长度
    int dfs(int[][] matrix, int[][] dp, int i, int j) {
        if (dp[i][j] != 0) return dp[i][j]; // 5. 如果已经计算过 (i, j) 的最长递增路径，直接返回结果
        dp[i][j]++; // 6. 初始化当前路径长度为 1
        for (int k = 0; k < 4; k++) { // 7. 遍历四个方向
            int ti = i + dx[k]; // 8. 计算新行索引
            int tj = j + dy[k]; // 9. 计算新列索引
            // 10. 检查新索引是否在矩阵范围内且新位置的值大于当前位置的值
            if (ti >= 0 && ti < n && tj >= 0 && tj < m && matrix[ti][tj] > matrix[i][j]) {
                dp[i][j] = Math.max(dp[i][j], dfs(matrix, dp, ti, tj) + 1); // 11. 更新最长递增路径长度
            }
        }
        return dp[i][j]; // 12. 返回从 (i, j) 开始的最长递增路径长度
    }

    // 13. 主函数，计算矩阵中最长递增路径的长度
    public int solve(int[][] matrix) {
        int ans = 0; // 14. 初始化结果
        this.n = matrix.length; // 15. 获取矩阵的行数
        this.m = matrix[0].length; // 16. 获取矩阵的列数
        if (n == 0 || m == 0) return ans; // 17. 如果矩阵为空，直接返回 0
        int[][] dp = new int[n][m]; // 18. 创建一个二维数组用于存储每个位置的最长递增路径长度
        for (int i = 0; i < n; i++) { // 19. 遍历矩阵的每一行
            for (int j = 0; j < m; j++) { // 20. 遍历矩阵的每一列
                ans = Math.max(ans, dfs(matrix, dp, i, j)); // 21. 更新最长递增路径长度
            }
        }
        return ans; // 22. 返回最终结果
    }
}

动态规划

题号 题目名称 核心思路 时间复杂度 空间复杂度 代码亮点 牛客原题链接
BM62 斐波那契数列 动态规划（迭代） / 递归 O(n) / O(2ⁿ) O(1) / O(n) 迭代版空间 O(1) 优化 🔗 直达
BM63 跳台阶 DP：前两项和 O(n) O(1) 与斐波那契同模型 🔗 直达
BM64 最小花费爬楼梯 DP：min(前两项花费+成本) O(n) O(1) 边界 dp[0]=dp[1]=0 技巧 🔗 直达
BM65 最长公共子序列 二维 DP + 回溯构造子序列 O(n·m) O(n·m) 方向矩阵 b[][] 回溯输出 LCS 🔗 直达
BM66 最长公共子串 二维 DP + 记录 max 长度位置 O(n·m) O(n·m) 子串必须连续 🔗 直达
BM67 不同路径的数目(一) DP 累加 / 组合数 C(m+n-2,n-1) O(n·m) O(min(n,m)) 组合数写法更简洁 🔗 直达
BM68 矩阵的最小路径和 二维 DP：min(上,左)+当前值 O(n·m) O(n·m) 从左至右、从上至下 🔗 直达
BM69 数字翻译字符串 线性 DP：单双数字解码 O(n) O(1) 用于存储每个位置的解码方法数 🔗 直达
BM70 兑换零钱(一) 完全背包求最小硬币数 O(n·aim) O(aim) INF=0x3f3f3f3f 初始化技巧 🔗 直达
BM71 最长上升子序列 线性 DP + 贪心优化 O(n²) O(n) 初始化动态规划数组，每个位置的初始值为 1，因为每个元素自身可以看作长度为 1 的递增子序列 🔗 直达
BM72 连续子数组最大和 Kadane：max(前和+当前, 当前) O(n) O(1) 经典最大子段和 🔗 直达
BM73 最长回文子串 中心扩展 / Manacher O(n²) O(1) 奇偶中心双指针 🔗 直达
BM74 复原 IP 地址 三重循环枚举三段分割 O(1) O(1) 剪枝提前结束 🔗 直达
BM75 编辑距离(一) 二维 DP 经典 Levenshtein O(n·m) O(n·m) 可滚动数组优化 🔗 直达
BM76 正则表达式匹配 二维 DP：处理 * 和 . O(n·m) O(n·m) 状态转移分三种情况 🔗 直达
BM77 最长括号子串 栈 / 线性 DP O(n) O(n) / O(1) 栈存索引或 DP 分段累加 🔗 直达
BM78 打家劫舍(一) 线性 DP：不相邻取数 O(n) O(1) dp[i]=max(dp[i-1],dp[i-2]+nums[i-1]) 🔗 直达
BM79 打家劫舍(二) 环形 DP：拆成两段线性 DP O(n) O(1) 两次 DP 取 max 🔗 直达
BM80 买卖股票(一) 一次交易 DP / 贪心 O(n) O(1) minPrice 贪心写法更简洁 🔗 直达
BM81 买卖股票(二) 无限交易贪心 / DP O(n) O(1) 贪心：累加所有上升段 🔗 直达
BM82 买卖股票(三) 最多两次交易状态机 DP O(n) O(1) 5 个状态滚动更新 🔗 直达

✅ 复习顺序建议（由易到难）

BM62 → BM63 → BM64 → BM69 → BM67 → BM68 → BM70 → BM71 → BM72 → BM77 → BM78 → BM79 → BM80 → BM81 → BM82 → BM65 → BM66 → BM75 → BM76

BM62 斐波那契数列

斐波那契数列_牛客题霸_牛客网
https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;

public class Solution {
    // 1. 计算斐波那契数列的第 n 项
    public int Fibonacci(int n) {
        List<Integer> fib = new ArrayList<Integer>(); // 2. 创建一个列表，用于存储斐波那契数列
        fib.add(0); // 3. 添加第 0 项，值为 0
        fib.add(1); // 4. 添加第 1 项，值为 1
        for (int i = 2; i <= n; i++) { // 5. 从第 2 项开始计算，直到第 n 项
            fib.add(fib.get(i - 1) + fib.get(i - 2)); // 6. 计算当前项，值为前两项之和
        }
        return fib.get(n); // 7. 返回第 n 项的值
    }
}
  1. 空间优化 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;

public class Solution {
    public int Fibonacci(int n) {
        if (n <= 1) return n;            // 1. 基准情况：F(0)=0, F(1)=1
        int a = 0, b = 1, c = 0;         // 2. 初始化 F(0), F(1), 临时变量
        for (int i = 2; i <= n; i++) {   // 3. 从 F(2) 递推到 F(n)
            c = a + b;                   // 4. 计算当前项
            a = b;                       // 5. 更新前两项
            b = c;
        }
        return c;                        // 6. 返回 F(n)
    }
}
  1. 递归
1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // 1. 计算斐波那契数列的第 n 项
    public int Fibonacci(int n) {
        // 2. 如果 n 小于等于 1，直接返回 n（第 0 项是 0，第 1 项是 1）
        if (n <= 1) return n;
        else {
            // 3. 根据斐波那契数列的定义，递归计算第 n 项
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }
    }
}

BM63 跳台阶

跳台阶_牛客题霸_牛客网
https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;

public class Solution {
    // 1. 计算青蛙跳到第 number 级台阶的方法数
    public int jumpFloor(int number) {
        List<Integer> dp = new ArrayList<>(); // 2. 创建一个列表，用于存储每级台阶的方法数
        dp.add(1); // 3. 第 0 级台阶有 1 种方法（即站在地上）
        dp.add(1); // 4. 第 1 级台阶有 1 种方法（跳1级）
        for (int i = 2; i <= 40; i++) { // 5. 从第 2 级台阶开始计算，直到第 40 级
            dp.add(dp.get(i - 1) + dp.get(i - 2)); // 6. 当前级的方法数等于前两级方法数之和
        }
        return dp.get(number); // 7. 返回第 number 级台阶的方法数
    }
}

BM64 最小花费爬楼梯

最小花费爬楼梯_牛客题霸_牛客网
https://www.nowcoder.com/practice/6fe0302a058a4e4a834ee44af88435c7?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj
2025年8月23日20:51:18 2025年8月23日20:57:18

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;

public class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length; // 1. 获取楼梯的阶数
        int[] dp = new int[n + 1]; // 2. 创建一个数组，用于存储到达每一阶的最小成本
        // 3. 初始化前两阶的成本，因为可以从地面或第一阶开始，所以初始成本为0
        dp[0] = 0;
        dp[1] = 0;
        // 4. 从第2阶开始计算，直到第n阶
        for (int i = 2; i <= n; i++) {
            // 5. 到达第i阶的最小成本等于到达前两阶的最小成本加上对应的楼梯成本
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n]; // 6. 返回到达最后一阶的最小成本
    }
}

BM65 最长公共子序列(二)

最长公共子序列(二)_牛客题霸_牛客网
https://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11?tpId=295&tqId=991075&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.*;

public class Solution {
    String x = ""; // 1. 存储第一个字符串
    String y = ""; // 2. 存储第二个字符串

    // 3. 递归函数，用于根据方向矩阵 b 构造 LCS
    String ans(int l1, int l2, int[][] b) {
        String res = ""; // 4. 初始化结果字符串
        if (l1 == 0 || l2 == 0) { // 5. 如果某个字符串的长度为 0，直接返回空字符串
            return res;
        }
        if (b[l1][l2] == 1) { // 6. 如果方向矩阵 b[l1][l2] 为 1，表示当前字符是 LCS 的一部分
            res += ans(l1 - 1, l2 - 1, b); // 7. 递归构造 LCS，并添加当前字符
            res += x.charAt(l1 - 1); // 8. 添加当前字符
        } else if (b[l1][l2] == 2) { // 9. 如果方向矩阵 b[l1][l2] 为 2，表示从上一个状态转移过来
            res += ans(l1 - 1, l2, b); // 10. 递归构造 LCS
        } else { // 11. 如果方向矩阵 b[l1][l2] 为 3，表示从左边的状态转移过来
            res += ans(l1, l2 - 1, b); // 12. 递归构造 LCS
        }
        return res; // 13. 返回构造的 LCS
    }

    // 14. 主函数，计算两个字符串的 LCS
    public String LCS(String s1, String s2) {
        int l1 = s1.length(); // 15. 获取第一个字符串的长度
        int l2 = s2.length(); // 16. 获取第二个字符串的长度
        if (l1 == 0 || l2 == 0) { // 17. 如果某个字符串为空，直接返回 "-1"
            return "-1";
        }
        x = s1; // 18. 存储第一个字符串
        y = s2; // 19. 存储第二个字符串

        int[][] dp = new int[l1 + 1][l2 + 1]; // 20. 创建动态规划表，用于存储 LCS 的长度
        int[][] b = new int[l1 + 1][l2 + 1]; // 21. 创建方向矩阵，用于记录构造 LCS 的路径

        // 22. 动态规划计算 LCS 的长度，并填充方向矩阵
        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) { // 23. 如果当前字符匹配
                    dp[i][j] = dp[i - 1][j - 1] + 1; // 24. LCS 长度加 1
                    b[i][j] = 1; // 25. 标记当前字符是 LCS 的一部分
                } else {
                    if (dp[i - 1][j] > dp[i][j - 1]) { // 26. 如果从上一个状态转移过来的 LCS 更长
                        dp[i][j] = dp[i - 1][j]; // 27. 更新 LCS 长度
                        b[i][j] = 2; // 28. 标记从上一个状态转移过来
                    } else { // 29. 如果从左边的状态转移过来的 LCS 更长
                        dp[i][j] = dp[i][j - 1]; // 30. 更新 LCS 长度
                        b[i][j] = 3; // 31. 标记从左边的状态转移过来
                    }
                }
            }
        }

        String res = ans(l1, l2, b); // 32. 调用递归函数构造 LCS
        if (res.isEmpty()) { // 33. 如果结果为空，返回 "-1"
            return "-1";
        }
        return res; // 34. 返回构造的 LCS
    }
}

BM66 最长公共子串

最长公共子串_牛客题霸_牛客网
https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;

public class Solution {
    public String LCS(String str1, String str2) {
        int[][] dp = new int[str1.length() + 1][str2.length() + 1]; // 1. 创建动态规划表，用于存储最长公共子串的长度
        int max = 0; // 2. 初始化最长公共子串的长度
        int pos = 0; // 3. 初始化最长公共子串的结束位置
        // 4. 动态规划计算最长公共子串的长度
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) { // 5. 如果当前字符匹配
                    dp[i][j] = dp[i - 1][j - 1] + 1; // 6. 当前位置的最长公共子串长度等于前一个位置的长度加1
                    if (dp[i][j] > max) { // 7. 更新最长公共子串的长度和结束位置
                        max = dp[i][j];
                        pos = i - 1;
                    }
                } else {
                    dp[i][j] = 0; // 8. 如果当前字符不匹配，当前位置的最长公共子串长度为0
                }
            }
        }
        // 9. 返回最长公共子串
        return str1.substring(pos - max + 1, pos + 1);
    }
}

BM67 不同路径的数目(一)

不同路径的数目(一)_牛客题霸_牛客网
https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358?tpId=295&tqId=685&sourceUrl=%2Fexam%2Foj

  1. 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;

public class Solution {

    // 1. 计算从网格的左上角到右下角的唯一路径数
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1]; // 2. 创建一个动态规划表，用于存储到达每个位置的路径数
        dp[0][0] = 1; // 3. 初始化起点的路径数为1
        // 4. 初始化第一列的路径数，只能从上方来
        for (int i = 1; i < m; i++) {
            dp[i][0] = 1;
        }
        // 5. 初始化第一行的路径数，只能从左方来
        for (int i = 1; i < n; i++) {
            dp[0][i] = 1;
        }
        // 6. 动态规划计算每个位置的路径数
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // 7. 到达当前位置的路径数等于上方和左方路径数之和
            }
        }
        return dp[m - 1][n - 1]; // 8. 返回到达右下角的路径数
    }
}
  1. 组合数学
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;

public class Solution {
    // 1. 计算从网格的左上角到右下角的唯一路径数
    public int uniquePaths(int m, int n) {
        long res = 1; // 2. 初始化结果为 1
        int x = n, y = 1; // 3. 初始化变量 x 和 y，x 表示分子的起始值，y 表示分母的起始值
        while (y < m) { // 4. 当 y 小于 m 时，继续计算
            res = res * x / y; // 5. 更新结果，每次乘以 x 并除以 y
            x++; // 6. 分子 x 增加 1
            y++; // 7. 分母 y 增加 1
        }
        return (int) res; // 8. 返回结果，强制转换为 int 类型
    }
}

BM68 矩阵的最小路径和

矩阵的最小路径和_牛客题霸_牛客网
https://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;

public class Solution {

    public int minPathSum(int[][] matrix) {
        int m = matrix.length; // 1. 获取矩阵的行数
        int n = matrix[0].length; // 2. 获取矩阵的列数
        int[][] dp = new int[m][n]; // 3. 创建一个动态规划表，用于存储到达每个位置的最小路径和

        for (int i = 0; i < m; i++) { // 4. 遍历矩阵的每一行
            for (int j = 0; j < n; j++) { // 5. 遍历矩阵的每一列
                if (i == 0 && j == 0) { // 6. 如果是左上角的起点
                    dp[0][0] = matrix[0][0]; // 7. 起点的最小路径和就是它本身的值
                } else if (i == 0) { // 8. 如果在第一行，只能从左边来
                    dp[i][j] = matrix[i][j] + dp[i][j - 1]; // 9. 当前位置的最小路径和等于左边的最小路径和加上当前值
                } else if (j == 0) { // 10. 如果在第一列，只能从上边来
                    dp[i][j] = matrix[i][j] + dp[i - 1][j]; // 11. 当前位置的最小路径和等于上边的最小路径和加上当前值
                } else { // 12. 其他位置可以从左边或上边来
                    dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + matrix[i][j]; // 13. 当前位置的最小路径和等于左边和上边的最小路径和中较小的一个加上当前值
                }
            }
        }
        return dp[m - 1][n - 1]; // 14. 返回到达右下角的最小路径和
    }
}
  1. 直接在原数组上修改
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;

public class Solution {

    public int minPathSum(int[][] matrix) {
        int m = matrix.length; // 1. 获取矩阵的行数
        int n = matrix[0].length; // 2. 获取矩阵的列数
        for (int i = 0; i < m; i++) { // 3. 遍历矩阵的每一行
            for (int j = 0; j < n; j++) { // 4. 遍历矩阵的每一列
                if (i == 0 && j == 0) { // 5. 如果是左上角的起点
                    continue; // 6. 跳过，因为起点的值不需要更新
                } else if (i == 0) { // 7. 如果在第一行
                    matrix[i][j] += matrix[i][j - 1]; // 8. 当前位置的值加上左边的值
                } else if (j == 0) { // 9. 如果在第一列
                    matrix[i][j] += matrix[i - 1][j]; // 10. 当前位置的值加上上边的值
                } else { // 11. 其他位置
                    matrix[i][j] += Math.min(matrix[i][j - 1], matrix[i - 1][j]); // 12. 当前位置的值加上左边和上边的较小值
                }
            }
        }
        return matrix[m - 1][n - 1]; // 13. 返回右下角的值，即最小路径和
    }
}

BM69 把数字翻译成字符串

把数字翻译成字符串_牛客题霸_牛客网
https://www.nowcoder.com/practice/046a55e6cd274cffb88fc32dba695668?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;

public class Solution {
    public int solve(String nums) {
        int n = nums.length(); // 1. 获取字符串的长度
        if (nums.charAt(0) == '0' || n == 0) return 0; // 2. 如果字符串以 '0' 开头或为空，返回 0
        int[] dp = new int[n + 1]; // 3. 创建一个动态规划数组，用于存储每个位置的解码方法数
        dp[0] = 1; // 4. 初始化 dp[0] 为 1，表示空字符串有一种解码方法
        for (int i = 1; i < n; i++) { // 5. 遍历字符串
            if (nums.charAt(i) != '0') dp[i] = dp[i - 1]; // 6. 如果当前字符不是 '0'，继承前一个位置的解码方法数
            int t = (nums.charAt(i - 1) - '0') * 10 + (nums.charAt(i) - '0'); // 7. 计算当前字符和前一个字符组成的两位数
            if (t >= 10 && t <= 26) { // 8. 如果这个两位数在 10 到 26 之间
                if (i == 1) { // 9. 如果是第二个字符
                    dp[i] += 1; // 10. 增加一种解码方法
                } else {
                    dp[i] += dp[i - 2]; // 11. 增加前两个位置的解码方法数
                }
            }
        }
        return dp[n - 1]; // 12. 返回最后一个位置的解码方法数
    }
}

BM70 兑换零钱(一)

兑换零钱(一)_牛客题霸_牛客网
https://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45?tpId=295&tqId=988994&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;

public class Solution {
    public int minMoney(int[] arr, int aim) {
        if (aim < 1) return 0; // 1. 如果目标金额小于1，返回0
        int[] dp = new int[aim + 1]; // 2. 创建一个动态规划数组，用于存储每个金额的最少硬币数量
        Arrays.fill(dp, 0x3f3f3f); // 3. 初始化数组为一个很大的数（表示无穷大）
        dp[0] = 0; // 4. 初始化dp[0]为0，表示金额为0时不需要任何硬币
        for (int i = 1; i <= aim; i++) { // 5. 遍历所有金额，从1到目标金额
            for (int j = 0; j < arr.length; j++) { // 6. 遍历所有硬币面值
                if (i - arr[j] >= 0) // 7. 如果当前金额减去硬币面值不小于0
                    dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1); // 8. 更新当前金额的最少硬币数量
            }
        }
        return dp[aim] == 0x3f3f3f ? -1 : dp[aim]; // 9. 如果dp[aim]仍为无穷大，返回-1，否则返回dp[aim]
    }
}

BM71 最长上升子序列(一)

最长上升子序列(一)_牛客题霸_牛客网
https://www.nowcoder.com/practice/5164f38b67f846fb8699e9352695cd2f?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;

public class Solution {
    public int LIS(int[] arr) {
        int n = arr.length; // 1. 获取数组的长度
        if (n == 0) return 0; // 2. 如果数组为空，返回 0
        int[] dp = new int[n]; // 3. 创建一个动态规划数组，用于存储每个位置的最长递增子序列长度
        Arrays.fill(dp, 1); // 4. 初始化动态规划数组，每个位置的初始值为 1，因为每个元素自身可以看作长度为 1 的递增子序列
        int maxl = 1; // 5. 初始化最长递增子序列的长度为 1
        for (int i = 1; i < n; i++) { // 6. 遍历数组，从第二个元素开始
            for (int j = 0; j < i; j++) { // 7. 遍历当前元素之前的所有元素
                if (arr[i] > arr[j] && dp[i] < dp[j] + 1) { // 8. 如果当前元素大于之前的某个元素，并且可以形成更长的递增子序列
                    dp[i] = dp[j] + 1; // 9. 更新当前元素的最长递增子序列长度
                    maxl = Math.max(maxl, dp[i]); // 10. 更新最长递增子序列的长度
                }
            }
        }
        return maxl; // 11. 返回最长递增子序列的长度
    }
}

BM72 连续子数组的最大和

连续子数组的最大和_牛客题霸_牛客网
https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int n = array.length; // 1. 获取数组的长度
        int[] dp = new int[n]; // 2. 创建一个动态规划数组，用于存储每个位置的最大子数组和
        dp[0] = array[0]; // 3. 初始化第一个位置的最大子数组和为数组的第一个元素
        int maxsum = array[0]; // 4. 初始化最大子数组和为数组的第一个元素
        for (int i = 1; i < n; i++) { // 5. 遍历数组，从第二个元素开始
            dp[i] = Math.max(dp[i - 1] + array[i], array[i]); // 6. 更新当前位置的最大子数组和
            maxsum = Math.max(maxsum, dp[i]); // 7. 更新全局最大子数组和
        }
        return maxsum; // 8. 返回全局最大子数组和
    }
}
  1. 优化空间动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int n = array.length; // 1. 获取数组的长度
        int sum = 0; // 2. 初始化当前子数组的和为 0
        int maxsum = array[0]; // 3. 初始化最大子数组和为数组的第一个元素
        for (int i = 0; i < n; i++) { // 4. 遍历数组
            sum = Math.max(sum, 0) + array[i]; // 5. 更新当前子数组的和，如果当前和小于 0，则重置为 0
            maxsum = Math.max(maxsum, sum); // 6. 更新全局最大子数组和
        }
        return maxsum; // 7. 返回全局最大子数组和
    }
}

BM73 最长回文子串

最长回文子串_牛客题霸_牛客网
https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. 中心拓展
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;

public class Solution {
    // 1. 辅助函数，用于从中心向两边扩展，计算以某个字符或两个字符为中心的回文子串长度
    public int fun(String s, int b, int e) {
        while (b >= 0 && e < s.length() && s.charAt(b) == s.charAt(e)) { // 2. 当左右指针在范围内且字符相等时，扩展
            b--; // 3. 左指针左移
            e++; // 4. 右指针右移
        }
        return e - b - 1; // 5. 返回回文子串的长度
    }

    // 6. 主函数，计算最长回文子串的长度
    public int getLongestPalindrome(String A) {
        int maxl = 1; // 7. 初始化最长回文子串的长度为 1
        for (int i = 0; i < A.length() - 1; i++) { // 8. 遍历字符串，尝试每个字符作为中心
            maxl = Math.max(maxl, Math.max(fun(A, i, i), fun(A, i, i + 1))); // 9. 更新最长回文子串的长度
        }
        return maxl; // 10. 返回最长回文子串的长度
    }
}
  1. 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;

public class Solution {

    public int getLongestPalindrome(String a) {
        int n = a.length(); // 1. 获取字符串的长度
        boolean[][] f = new boolean[n][n]; // 2. 创建一个二维布尔数组，用于存储子串是否为回文
        int max = 0; // 3. 初始化最长回文子串的长度为 0
        for (int c = 0; c < n; c++) { // 4. 遍历所有可能的子串长度
            for (int i = 0; i < n - c; i++) { // 5. 遍历所有可能的子串起始位置
                int j = c + i; // 6. 计算子串的结束位置
                if (a.charAt(i) == a.charAt(j)) { // 7. 如果子串的首尾字符相同
                    if (c <= 1) f[i][j] = true; // 8. 如果子串长度为 1 或 2，直接标记为回文
                    else f[i][j] = f[i + 1][j - 1]; // 9. 否则，检查去掉首尾字符后的子串是否为回文
                    if (f[i][j]) max = c + 1; // 10. 如果当前子串是回文，更新最长回文子串的长度
                }
            }
        }
        return max; // 11. 返回最长回文子串的长度
    }
}
  1. 马拉车
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.*;

public class Solution {

    public int getLongestPalindrome(String s) {
        int n = s.length(); // 1. 获取字符串的长度
        char[] t = new char[n * 2 + 3]; // 2. 创建一个新数组，用于存储处理后的字符串
        Arrays.fill(t, '#'); // 3. 初始化数组，填充为 '#'
        t[0] = '^'; // 4. 在数组的开头添加一个特殊字符 '^'
        for (int i = 0; i < n; i++) { // 5. 将原字符串的每个字符插入到新数组中
            t[i * 2 + 2] = s.charAt(i);
        }
        t[n * 2 + 2] = '$'; // 6. 在数组的末尾添加一个特殊字符 '$'

        int[] hl = new int[t.length - 2]; // 7. 创建一个数组，用于存储每个位置的回文半径
        hl[1] = 1; // 8. 初始化第一个位置的回文半径为 1
        int maxi = 0; // 9. 初始化最长回文子串的中心位置
        int boxm = 0; // 10. 初始化当前回文子串的中心位置
        int boxr = 0; // 11. 初始化当前回文子串的右边界
        for (int i = 2; i < hl.length; i++) { // 12. 遍历处理后的字符串
            int tmpl = 1; // 13. 初始化当前回文半径为 1
            if (i < boxr) { // 14. 如果当前索引在当前回文子串的右边界内
                tmpl = Math.min(hl[boxm * 2 - i], boxr - i); // 15. 利用对称性，计算当前回文半径
            }

            while (t[i - tmpl] == t[i + tmpl]) { // 16. 尝试扩展当前回文子串
                tmpl++; // 17. 扩展回文半径
                boxm = i; // 18. 更新当前回文子串的中心位置
                boxr = i + tmpl; // 19. 更新当前回文子串的右边界
            }

            hl[i] = tmpl; // 20. 更新当前索引的回文半径
            if (tmpl > hl[maxi]) { // 21. 如果当前回文半径大于之前的最大值
                maxi = i; // 22. 更新最长回文子串的中心位置
            }
        }
        int ansl = hl[maxi]; // 23. 获取最长回文子串的长度
        return (maxi + ansl) / 2 - 1 - (maxi - ansl) / 2; // 24. 计算并返回最长回文子串的实际长度
    }
}

BM74 数字字符串转化成IP地址

数字字符串转化成IP地址_牛客题霸_牛客网
https://www.nowcoder.com/practice/ce73540d47374dbe85b3125f57727e1e?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.*;

public class Solution {
    // 1. 检查字符串是否表示的数字大于255
    boolean chk(String s) {
        return Integer.parseInt(s) > 255; // 2. 如果字符串表示的数字大于255，返回true
    }

    // 3. 检查字符串是否以0开头且长度大于1
    boolean chk2(String s) {
        return s.length() != 1 && s.charAt(0) == '0'; // 4. 如果字符串长度大于1且以0开头，返回true
    }

    // 5. 主函数，恢复IP地址
    public ArrayList<String> restoreIpAddresses(String s) {
        LinkedList<String> res = new LinkedList<String>(); // 6. 创建结果列表
        int n = s.length(); // 7. 获取字符串的长度
        // 8. 遍历所有可能的分割点
        for (int i = 1; i < 4 && i < n - 2; i++) {
            for (int j = i + 1; j < i + 4 && j < n - 1; j++) {
                for (int k = j + 1; k < j + 4 && k < n; k++) {
                    if (n - k >= 4) continue; // 9. 如果剩余部分长度大于4，跳过
                    String a = s.substring(0, i); // 10. 获取第一部分
                    String b = s.substring(i, j); // 11. 获取第二部分
                    String c = s.substring(j, k); // 12. 获取第三部分
                    String d = s.substring(k); // 13. 获取第四部分
                    // 14. 检查每个部分是否有效
                    if (chk(a) || chk(b) || chk(c) || chk(d)) continue;
                    if (chk2(a) || chk2(b) || chk2(c) || chk2(d)) continue;
                    // 15. 构造当前IP地址
                    String cur = a + '.' + b + '.' + c + '.' + d;
                    res.addLast(cur); // 16. 将当前IP地址添加到结果列表
                }
            }
        }
        return new ArrayList<>(res); // 17. 返回结果列表
    }
}

BM75 编辑距离(一)

编辑距离(一)_牛客题霸_牛客网
https://www.nowcoder.com/practice/6a1483b5be1547b1acd7940f867be0da?tpId=295&tqId=2294660&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;

public class Solution {
    public int editDistance(String str1, String str2) {
        int n1 = str1.length(); // 1. 获取第一个字符串的长度
        int n2 = str2.length(); // 2. 获取第二个字符串的长度
        int[][] d = new int[n1 + 1][n2 + 1]; // 3. 创建一个动态规划表，用于存储编辑距离
        d[0][0] = 0; // 4. 初始化两个空字符串的编辑距离为 0
        // 5. 初始化第一行，表示将第一个字符串的前 i 个字符转换为空字符串的编辑距离
        for (int i = 1; i <= n1; i++) {
            d[i][0] = d[i - 1][0] + 1; // 6. 删除操作
        }
        // 7. 初始化第一列，表示将第二个字符串的前 j 个字符转换为空字符串的编辑距离
        for (int i = 1; i <= n2; i++) {
            d[0][i] = d[0][i - 1] + 1; // 8. 插入操作
        }
        // 9. 动态规划计算编辑距离
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) { // 10. 如果当前字符相同
                    d[i][j] = d[i - 1][j - 1]; // 11. 编辑距离不变
                } else {
                    // 12. 如果当前字符不同，选择三种操作中最小的编辑距离
                    d[i][j] = Math.min(d[i - 1][j], Math.min(d[i][j - 1], d[i - 1][j - 1])) + 1;
                }
            }
        }
        return d[n1][n2]; // 13. 返回最终的编辑距离
    }
}
  1. 压缩空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;

public class Solution {

    public int editDistance(String str1, String str2) {
        int n1 = str1.length(); // 1. 获取第一个字符串的长度
        int n2 = str2.length(); // 2. 获取第二个字符串的长度
        int[][] f = new int[2][n2 + 1]; // 3. 创建一个二维数组，用于存储动态规划的结果，只使用两行来节省空间
        for (int i = 1; i <= n2; i++) { // 4. 初始化第一行，表示将空字符串转换为 str2 的前 i 个字符所需的编辑距离
            f[0][i] = i;
        }
        for (int i = 1; i <= n1; i++) { // 5. 遍历第一个字符串的每个字符
            for (int j = 1; j <= n2; j++) { // 6. 遍历第二个字符串的每个字符
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) { // 7. 如果当前字符相同
                    if (j - 1 == 0) f[i % 2][j] = i - 1; // 8. 特殊情况处理
                    else f[i % 2][j] = f[(i + 1) % 2][j - 1]; // 9. 当前字符相同，编辑距离等于前一个状态的编辑距离
                } else {
                    if (j - 1 == 0) f[i % 2][j] = Math.min(f[(i + 1) % 2][j] + 1, i); // 10. 特殊情况处理
                    else f[i % 2][j] = Math.min(f[(i + 1) % 2][j], Math.min(f[(i + 1) % 2][j - 1], f[i % 2][j - 1])) + 1; // 11. 当前字符不同，选择三种操作中最小的编辑距离
                }
            }
        }
        return f[n1 % 2][n2]; // 12. 返回最终的编辑距离
    }
}

BM76 正则表达式匹配

正则表达式匹配_牛客题霸_牛客网
https://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;

public class Solution {
    public boolean match(String str, String pattern) {
        int n1 = str.length(); // 1. 获取字符串的长度
        int n2 = pattern.length(); // 2. 获取模式串的长度
        str = " " + str; // 3. 在字符串前添加一个空格，方便处理边界情况
        pattern = " " + pattern; // 4. 在模式串前添加一个空格，方便处理边界情况
        char[] s = str.toCharArray(); // 5. 将字符串转换为字符数组
        char[] p = pattern.toCharArray(); // 6. 将模式串转换为字符数组
        boolean[][] f = new boolean[n1 + 1][n2 + 1]; // 7. 创建一个二维布尔数组，用于存储动态规划的结果
        f[0][0] = true; // 8. 初始化：空字符串和空模式串匹配
        for (int i = 0; i <= n1; i++) { // 9. 遍历字符串的所有前缀
            for (int j = 1; j <= n2; j++) { // 10. 遍历模式串的所有前缀
                if (j + 1 <= n2 && p[j + 1] == '*') continue; // 11. 如果当前字符的下一个字符是 '*'，跳过当前字符
                if (i - 1 >= 0 && p[j] != '*') { // 12. 如果当前模式字符不是 '*'，且字符串前缀长度足够
                    f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.'); // 13. 当前字符匹配，且前一个状态匹配
                } else if (p[j] == '*') { // 14. 如果当前模式字符是 '*'
                    f[i][j] = (j - 2 >= 0 && f[i][j - 2]) || // 15. '*' 表示前面的字符出现 0 次
                            (i - 1 >= 0 && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.')); // 16. '*' 表示前面的字符出现至少 1 次
                }
            }
        }
        return f[n1][n2]; // 17. 返回最终的匹配结果
    }
}

BM77 最长的括号子串

最长的括号子串_牛客题霸_牛客网
https://www.nowcoder.com/practice/45fd68024a4c4e97a8d6c45fc61dc6ad?tpId=295&tqId=715&sourceUrl=%2Fexam%2Foj

  1. 栈匹配
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;

public class Solution {
    public int longestValidParentheses(String s) {
        int res = 0; // 1. 初始化最长有效括号的长度为 0
        int st = -1; // 2. 初始化栈底索引为 -1，表示栈底
        Stack<Integer> stk = new Stack<Integer>(); // 3. 创建一个栈，用于存储未匹配的左括号的索引
        for (int i = 0; i < s.length(); i++) { // 4. 遍历字符串
            if (s.charAt(i) == '(') stk.push(i); // 5. 如果当前字符是左括号，将其索引压入栈
            else {
                if (stk.isEmpty()) st = i; // 6. 如果栈为空，更新栈底索引为当前索引
                else {
                    stk.pop(); // 7. 弹出栈顶元素，表示匹配了一个左括号
                    if (!stk.isEmpty()) { // 8. 如果栈不为空
                        res = Math.max(res, i - stk.peek()); // 9. 更新最长有效括号的长度
                    } else res = Math.max(res, i - st); // 10. 如果栈为空，更新最长有效括号的长度
                }
            }
        }
        return res; // 11. 返回最长有效括号的长度
    }
}
  1. 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;

public class Solution {
    public int longestValidParentheses(String s) {
        int ans = 0; // 1. 初始化最长有效括号的长度为 0
        int n = s.length(); // 2. 获取字符串的长度
        if (n == 0 || s == null) return ans; // 3. 如果字符串为空或长度为 0，直接返回 0
        int[] f = new int[n + 1]; // 4. 创建一个动态规划数组，用于存储每个位置的最长有效括号长度
        for (int i = 1; i < n; i++) { // 5. 遍历字符串，从第二个字符开始
            if (s.charAt(i) == ')') { // 6. 如果当前字符是右括号
                if (s.charAt(i - 1) == '(') { // 7. 如果前一个字符是左括号
                    f[i] = (i >= 2 ? f[i - 2] : 0) + 2; // 8. 当前位置的最长有效括号长度等于前两个位置的长度加 2
                } else if (i - f[i - 1] > 0 && s.charAt(i - f[i - 1] - 1) == '(') { // 9. 如果前一个有效括号的前一个字符是左括号
                    f[i] = (i - f[i - 1] > 1 ? f[i - f[i - 1] - 2] : 0) + f[i - 1] + 2; // 10. 当前位置的最长有效括号长度等于前一个有效括号的长度加上当前匹配的长度
                }
            }
            ans = Math.max(ans, f[i]); // 11. 更新最长有效括号的长度
        }
        return ans; // 12. 返回最长有效括号的长度
    }
}

BM78 打家劫舍(一)

打家劫舍(一)_牛客题霸_牛客网
https://www.nowcoder.com/practice/c5fbf7325fbd4c0ea3d0c3ea6bc6cc79?tpId=295&tqId=2285793&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;

public class Solution {
    public int rob(int[] nums) {
        int n = nums.length; // 1. 获取数组的长度
        if (n == 0) return 0; // 2. 如果数组为空，返回 0
        if (n == 1) return nums[0]; // 3. 如果只有一个房子，返回该房子的金额

        int[] f = new int[n + 1]; // 4. 创建一个动态规划数组，用于存储每个位置的最大金额
        f[1] = nums[0]; // 5. 初始化第一个位置的最大金额为数组的第一个元素
        for (int i = 2; i <= n; i++) { // 6. 遍历数组，从第二个位置开始
            f[i] = Math.max(f[i - 2] + nums[i - 1], f[i - 1]); // 7. 更新当前位置的最大金额
        }
        return f[n]; // 8. 返回最后一个位置的最大金额
    }
}

BM79 打家劫舍(二)

https://www.nowcoder.com/practice/a5c127769dd74a63ada7bff37d9c5815?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;

public class Solution {

    public int rob(int[] nums) {
        if (nums.length == 0) return 0; // 1. 如果数组为空，返回 0
        if (nums.length == 1) return nums[0]; // 2. 如果只有一个房子，返回该房子的金额

        int[] f = new int[nums.length + 1]; // 3. 创建一个动态规划数组，用于存储每个位置的最大金额
        f[1] = nums[0]; // 4. 初始化第一个位置的最大金额为数组的第一个元素
        for (int i = 2; i < nums.length; i++) { // 5. 遍历数组，从第二个位置开始
            f[i] = Math.max(f[i - 1], nums[i - 1] + f[i - 2]); // 6. 更新当前位置的最大金额
        }
        int res = f[nums.length - 1]; // 7. 保存偷第一个房子的结果

        Arrays.fill(f, 0); // 8. 重置动态规划数组
        f[1] = 0; // 9. 不偷第一个房子，初始化第一个位置的最大金额为 0
        for (int i = 2; i <= nums.length; i++) { // 10. 遍历数组，从第二个位置开始
            f[i] = Math.max(f[i - 1], nums[i - 1] + f[i - 2]); // 11. 更新当前位置的最大金额
        }
        return Math.max(res, f[nums.length]); // 12. 返回两种情况中的最大值
    }
}

BM80 买卖股票的最好时机(一)

买卖股票的最好时机(一)_牛客题霸_牛客网
https://www.nowcoder.com/practice/64b4262d4e6d4f6181cd45446a5821ec?tpId=295&tqId=625&sourceUrl=%2Fexam%2Foj

  1. 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;

public class Solution {

    public int maxProfit(int[] prices) {
        int n = prices.length; // 1. 获取股票价格数组的长度
        if (n == 0) return 0; // 2. 如果数组为空，返回 0

        int[][] dp = new int[n][2]; // 3. 创建一个动态规划数组，用于存储每个状态的最大利润
        dp[0][0] = 0; // 4. 初始化第 0 天不持有股票的最大利润为 0
        dp[0][1] = -prices[0]; // 5. 初始化第 0 天持有股票的最大利润为 -prices[0]（买入股票）

        for (int i = 1; i < n; i++) { // 6. 遍历股票价格数组，从第 1 天开始
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); // 7. 更新第 i 天不持有股票的最大利润
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]); // 8. 更新第 i 天持有股票的最大利润
        }

        return dp[n - 1][0]; // 9. 返回最后一天不持有股票的最大利润
    }
}
  1. 贪心 + 找当前最小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;

public class Solution {

    public int maxProfit(int[] prices) {
        int minp = Integer.MAX_VALUE; // 1. 初始化最小价格为最大整数值
        int ans = 0; // 2. 初始化最大利润为 0
        for (int p : prices) { // 3. 遍历股票价格数组
            ans = Math.max(ans, p - minp); // 4. 更新最大利润，选择当前利润和已知最大利润中的较大值
            minp = Math.min(minp, p); // 5. 更新最小价格，选择当前价格和已知最小价格中的较小值
        }
        return ans; // 6. 返回最大利润
    }
}

BM81 买卖股票的最好时机(二)

买卖股票的最好时机(二)_牛客题霸_牛客网
https://www.nowcoder.com/practice/9e5e3c2603064829b0a0bbfca10594e9?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;

public class Solution {

    public int maxProfit(int[] prices) {
        int n = prices.length; // 1. 获取股票价格数组的长度
        if (n == 0) return 0; // 2. 如果数组为空，返回 0

        int[][] f = new int[n][2]; // 3. 创建一个动态规划数组，用于存储每个状态的最大利润
        f[0][0] = 0; // 4. 初始化第 0 天不持有股票的最大利润为 0
        f[0][1] = -prices[0]; // 5. 初始化第 0 天持有股票的最大利润为 -prices[0]（买入股票）

        for (int i = 1; i < n; i++) { // 6. 遍历股票价格数组，从第 1 天开始
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] + prices[i]); // 7. 更新第 i 天不持有股票的最大利润
            f[i][1] = Math.max(f[i - 1][1], f[i - 1][0] - prices[i]); // 8. 更新第 i 天持有股票的最大利润
        }

        return f[n - 1][0]; // 9. 返回最后一天不持有股票的最大利润
    }
}
  1. 贪心 + 只要是单增 就是赚的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;

public class Solution {

    public int maxProfit(int[] prices) {
        int ans = 0; // 1. 初始化最大利润为 0
        for (int i = 1; i < prices.length; i++) { // 2. 遍历股票价格数组，从第 1 天开始
            if (prices[i] > prices[i - 1]) { // 3. 如果当前价格大于前一天的价格
                ans += prices[i] - prices[i - 1]; // 4. 累加当前利润
            }
        }
        return ans; // 5. 返回最大利润
    }
}

BM82 买卖股票的最好时机(三)

买卖股票的最好时机(三)_牛客题霸_牛客网
https://www.nowcoder.com/practice/4892d3ff304a4880b7a89ba01f48daf9?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;

public class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length; // 1. 获取股票价格数组的长度
        if (n == 0) return 0; // 2. 如果数组为空，返回 0
        int[][] f = new int[n][5]; // 3. 创建一个动态规划数组，用于存储每个状态的最大利润
        Arrays.fill(f[0], -200000 * 100); // 4. 初始化第 0 天的状态，除了 f[0][0] 为 0，其他状态初始化为一个很小的值
        f[0][0] = 0; // 5. 初始化第 0 天不进行任何操作的最大利润为 0
        f[0][1] = -prices[0]; // 6. 初始化第 0 天进行第一次买入的最大利润为 -prices[0]
        for (int i = 1; i < n; i++) { // 7. 遍历股票价格数组，从第 1 天开始
            f[i][0] = f[i - 1][0]; // 8. 第 i 天不进行任何操作的最大利润等于前一天不进行任何操作的最大利润
            f[i][1] = Math.max(f[i - 1][1], f[i - 1][0] - prices[i]); // 9. 第 i 天进行第一次买入的最大利润
            f[i][2] = Math.max(f[i - 1][2], f[i - 1][1] + prices[i]); // 10. 第 i 天进行第一次卖出的最大利润
            f[i][3] = Math.max(f[i - 1][3], f[i - 1][2] - prices[i]); // 11. 第 i 天进行第二次买入的最大利润
            f[i][4] = Math.max(f[i - 1][4], f[i - 1][3] + prices[i]); // 12. 第 i 天进行第二次卖出的最大利润
        }

        return Math.max(0, Math.max(f[n - 1][4], f[n - 1][2])); // 13. 返回最后一天的最大利润，考虑不进行任何操作、进行一次交易和进行两次交易的情况
    }
}

字符串

题号 题目名称 核心思路 时间复杂度 空间复杂度 代码亮点 牛客原题链接
BM83 字符串变形 两次反转：先整体反转，再按空格反转单词 O(n) O(n) 使用 StringBuffer 便于反转和替换；先整体后局部反转思路清晰 🔗 直达
BM84 最长公共前缀 1. 纵向扫描（逐位比较）
2. 二分优化（前缀长度二分）		 O(S) / O(S·log L) O(1) / O(1) 纵向扫描思路直观；二分优化适合前缀较短场景；空间均为 O(1) 🔗 直达
BM85 验证IP地址 1. 条件枚举逐段检查
2. 正则表达式一次性匹配		 O(1) O(1) 枚举法逻辑清晰易调试；正则法代码简洁但可读性稍差 🔗 直达
BM86 大数加法 1. 两次翻转+进位
2. 倒序遍历+进位
3. 栈+进位		 O(max(len1,len2)) O(max(len1,len2)) 倒序遍历无需显式翻转字符串；栈写法天然逆序处理；均支持超大整数 🔗 直达

✅ 复习顺序建议（由易到难）

BM84 → BM85 → BM86 → BM83

BM83 字符串变形

字符串变形_牛客题霸_牛客网
https://www.nowcoder.com/practice/c3120c1c1bc44ad986259c0cf0f0b80e?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;

public class Solution {
    public String trans(String s, int n) {
        if (n == 0) return s; // 1. 如果字符串长度为 0，直接返回原字符串
        StringBuffer sb = new StringBuffer(); // 2. 创建一个字符串缓冲区，用于存储转换后的字符串
        for (int i = 0; i < n; i++) { // 3. 遍历字符串的每个字符
            if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') // 4. 如果当前字符是小写字母
                sb.append((char) (s.charAt(i) - 'a' + 'A')); // 5. 转换为大写字母并追加到缓冲区
            else if (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') // 6. 如果当前字符是大写字母
                sb.append((char) (s.charAt(i) - 'A' + 'a')); // 7. 转换为小写字母并追加到缓冲区
            else sb.append(s.charAt(i)); // 8. 如果当前字符不是字母，直接追加到缓冲区
        }
        sb = sb.reverse(); // 9. 反转整个字符串
        for (int i = 0; i < n; i++) { // 10. 遍历字符串的每个字符
            int j = i; // 11. 初始化单词的起始位置
            while (j < n && sb.charAt(j) != ' ') j++; // 12. 找到单词的结束位置
            String tmp = sb.substring(i, j); // 13. 提取当前单词
            StringBuffer stringBuffer = new StringBuffer(tmp); // 14. 创建一个临时字符串缓冲区
            tmp = stringBuffer.reverse().toString(); // 15. 反转当前单词
            sb.replace(i, j, tmp); // 16. 将反转后的单词替换回原位置
            i = j; // 17. 更新索引到下一个单词的起始位置
        }
        return sb.toString(); // 18. 返回最终的字符串
    }
}

BM84 最长公共前缀

最长公共前缀_牛客题霸_牛客网
https://www.nowcoder.com/practice/28eb3175488f4434a4a6207f6f484f47?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. 遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        int n = strs.length; // 1. 获取字符串数组的长度
        if (n == 0) return ""; // 2. 如果数组为空，返回空字符串
        for (int i = 0; i < strs[0].length(); i++) { // 3. 遍历第一个字符串的每个字符
            char tmp = strs[0].charAt(i); // 4. 获取当前字符
            for (int j = 1; j < n; j++) { // 5. 遍历数组中的其他字符串
                if (i == strs[j].length() || strs[j].charAt(i) != tmp) { // 6. 如果当前字符串长度不足或字符不匹配
                    return strs[0].substring(0, i); // 7. 返回当前已匹配的最长公共前缀
                }
            }
        }
        return strs[0]; // 8. 如果第一个字符串的所有字符都匹配，返回第一个字符串
    }
}
  1. 二分优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;

public class Solution {
    // 1. 辅助函数，用于判断长度为 len 的前缀是否是所有字符串的公共前缀
    boolean isPre(String[] s, int len) {
        String s0 = s[0].substring(0, len); // 2. 获取第一个字符串的前 len 个字符
        int cnt = s.length; // 3. 获取字符串数组的长度
        for (int i = 1; i < cnt; i++) { // 4. 遍历数组中的其他字符串
            String str = s[i]; // 5. 获取当前字符串
            for (int j = 0; j < len; j++) { // 6. 遍历当前字符串的前 len 个字符
                if (s0.charAt(j) != str.charAt(j)) { // 7. 如果字符不匹配
                    return false; // 8. 返回 false
                }
            }
        }
        return true; // 9. 如果所有字符串的前 len 个字符都匹配，返回 true
    }

    // 10. 主函数，寻找最长公共前缀
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return ""; // 11. 如果数组为空，返回空字符串
        int minlen = Integer.MAX_VALUE; // 12. 初始化最小字符串长度为最大整数值
        for (String s : strs) minlen = Math.min(minlen, s.length()); // 13. 遍历数组，找到最短字符串的长度
        int l = 0, r = minlen; // 14. 初始化二分查找的左右边界
        while (l < r) { // 15. 二分查找
            int mid = (r - l + 1) / 2 + l; // 16. 计算中间位置
            if (isPre(strs, mid)) { // 17. 如果长度为 mid 的前缀是公共前缀
                l = mid; // 18. 更新左边界
            } else {
                r = mid - 1; // 19. 更新右边界
            }
        }
        return strs[0].substring(0, l); // 20. 返回最长公共前缀
    }
}

BM85 验证IP地址

验证IP地址_牛客题霸_牛客网
https://www.nowcoder.com/practice/55fb3c68d08d46119f76ae2df7566880?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. 按照条件枚举
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;

public class Solution {
    public String solve(String IP) {
        boolean mayIPv4 = false; // 1. 标记是否可能是 IPv4 地址
        boolean mayIPv6 = false; // 2. 标记是否可能是 IPv6 地址
        if (IP.contains(".")) mayIPv4 = true; // 3. 如果包含 '.', 可能是 IPv4 地址
        if (IP.contains(":")) mayIPv6 = true; // 4. 如果包含 ':', 可能是 IPv6 地址
        if (mayIPv4) { // 5. 如果可能是 IPv4 地址
            String[] a = IP.split("\\."); // 6. 使用 '.' 分割字符串
            if (IP.charAt(0) == '.' || IP.charAt(IP.length() - 1) == '.') return "Neither"; // 7. 如果首尾有 '.', 不是有效的 IPv4 地址
            if (a.length != 4) return "Neither"; // 8. 如果分割后的部分不是 4 个，不是有效的 IPv4 地址
            for (int i = 0; i < 4; i++) { // 9. 遍历每个部分
                if (a[i].charAt(0) == '0' && a[i].length() > 1) return "Neither"; // 10. 如果部分以 '0' 开头且长度大于 1，不是有效的 IPv4 地址
                int sum = 0; // 11. 初始化当前部分的数值
                for (int j = 0; j < a[i].length(); j++) { // 12. 遍历部分的每个字符
                    sum = sum * 10 + (a[i].charAt(j) - '0'); // 13. 转换为数值
                }
                if (sum > 255) { // 14. 如果数值大于 255，不是有效的 IPv4 地址
                    return "Neither";
                }
            }
            return "IPv4"; // 15. 如果所有部分都有效，是 IPv4 地址
        }
        if (mayIPv6) { // 16. 如果可能是 IPv6 地址
            String[] b = IP.split(":"); // 17. 使用 ':' 分割字符串
            if (IP.charAt(0) == ':' || IP.charAt(IP.length() - 1) == ':') return "Neither"; // 18. 如果首尾有 ':', 不是有效的 IPv6 地址
            if (b.length != 8) return "Neither"; // 19. 如果分割后的部分不是 8 个，不是有效的 IPv6 地址
            for (int i = 0; i < 8; i++) { // 20. 遍历每个部分
                if (b[i].length() == 0 || b[i].length() > 4) return "Neither"; // 21. 如果部分长度为 0 或超过 4，不是有效的 IPv6 地址
                for (int j = 0; j < b[i].length(); j++) { // 22. 遍历部分的每个字符
                    if (!((b[i].charAt(j) >= '0' && b[i].charAt(j) <= '9') || 
                         (b[i].charAt(j) >= 'A' && b[i].charAt(j) <= 'F') || 
                         (b[i].charAt(j) >= 'a' && b[i].charAt(j) <= 'f'))) { // 23. 如果字符不是有效的十六进制字符
                        return "Neither";
                    }
                }
            }
            return "IPv6"; // 24. 如果所有部分都有效，是 IPv6 地址
        }
        return "Neither"; // 25. 如果既不是 IPv4 也不是 IPv6，返回 "Neither"
    }
}
  1. 正则表达式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;

import java.util.regex.*;

public class Solution {
    public String solve(String IP) {
        // 1. 定义 IPv4 的正则表达式
        String ipv4 = "(([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])\\.){3}([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])";
        Pattern ipv4p = Pattern.compile(ipv4); // 2. 编译 IPv4 的正则表达式
        // 3. 定义 IPv6 的正则表达式
        String ipv6 = "([0-9a-fA-F]{1,4}\\:){7}([0-9a-fA-F]{1,4})";
        Pattern ipv6p = Pattern.compile(ipv6); // 4. 编译 IPv6 的正则表达式
        // 5. 使用 IPv4 的正则表达式匹配输入的字符串
        if (ipv4p.matcher(IP).matches()) {
            return "IPv4"; // 6. 如果匹配成功，返回 "IPv4"
        } else if (ipv6p.matcher(IP).matches()) { // 7. 使用 IPv6 的正则表达式匹配输入的字符串
            return "IPv6"; // 8. 如果匹配成功，返回 "IPv6"
        }
        return "Neither"; // 9. 如果都不匹配，返回 "Neither"
    }
}

BM86 大数加法

大数加法_牛客题霸_牛客网
https://www.nowcoder.com/practice/11ae12e8c6fe48f883cad618c2e81475?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. 两次翻转 + 枚举 + 进位标记
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;

public class Solution {
    // 1. 辅助函数，用于反转字符串
    String rev(String s) {
        StringBuffer sb = new StringBuffer(); // 2. 创建一个字符串缓冲区
        for (int i = s.length() - 1; i >= 0; i--) { // 3. 从字符串的末尾开始遍历
            sb.append(s.charAt(i)); // 4. 将每个字符追加到缓冲区
        }
        return sb.toString(); // 5. 返回反转后的字符串
    }

    // 6. 主函数，用于计算两个字符串表示的非负整数相加的结果
    public String solve(String s, String t) {
        int l1 = s.length(); // 7. 获取第一个字符串的长度
        int l2 = t.length(); // 8. 获取第二个字符串的长度
        if (l1 == 0) return t; // 9. 如果第一个字符串为空，返回第二个字符串
        if (l2 == 0) return s; // 10. 如果第二个字符串为空，返回第一个字符串
        s = rev(s); // 11. 反转第一个字符串
        t = rev(t); // 12. 反转第二个字符串
        StringBuffer sb = new StringBuffer(); // 13. 创建一个字符串缓冲区，用于存储结果
        int curry = 0; // 14. 初始化进位
        for (int i = 0; i < Math.max(l1, l2); i++) { // 15. 遍历两个字符串的最大长度
            int s1 = (i < l1) ? s.charAt(i) - '0' : 0; // 16. 获取第一个字符串的当前数字，如果超出长度则为 0
            int s2 = (i < l2) ? t.charAt(i) - '0' : 0; // 17. 获取第二个字符串的当前数字，如果超出长度则为 0
            int sum = s1 + s2 + curry; // 18. 计算当前位的和
            curry = 0; // 19. 重置进位
            sb.append(sum % 10); // 20. 将当前位的结果追加到缓冲区
            if (sum >= 10) curry = 1; // 21. 如果和大于等于 10，设置进位
        }
        if (curry == 1) sb.append(curry); // 22. 如果最后还有进位，追加到结果
        String res = sb.toString(); // 23. 将结果转换为字符串
        return rev(res); // 24. 反转结果并返回
    }
}
  1. 倒序遍历 + 进位标记 + 翻转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;

public class Solution {
    public String solve(String s, String t) {
        int l1 = s.length(); // 1. 获取第一个字符串的长度
        int l2 = t.length(); // 2. 获取第二个字符串的长度
        if (l1 == 0) return t; // 3. 如果第一个字符串为空，返回第二个字符串
        if (l2 == 0) return s; // 4. 如果第二个字符串为空，返回第一个字符串
        StringBuffer sb = new StringBuffer(); // 5. 创建一个字符串缓冲区，用于存储结果
        int curry = 0; // 6. 初始化进位
        for (int i = 0; i < Math.max(l1, l2); i++) { // 7. 遍历两个字符串的最大长度
            int s1 = (i < l1) ? s.charAt(l1 - 1 - i) - '0' : 0; // 8. 获取第一个字符串的当前数字，从末尾开始
            int s2 = (i < l2) ? t.charAt(l2 - 1 - i) - '0' : 0; // 9. 获取第二个字符串的当前数字，从末尾开始
            int sum = s1 + s2 + curry; // 10. 计算当前位的和
            sb.append(sum % 10); // 11. 将当前位的结果追加到缓冲区
            curry = (sum >= 10) ? 1 : 0; // 12. 更新进位
        }
        if (curry == 1) sb.append(curry); // 13. 如果最后还有进位，追加到结果
        String res = sb.reverse().toString(); // 14. 反转结果字符串
        return res; // 15. 返回最终结果
    }
}
  1. 栈 + 进位标记 + 倒序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;


public class Solution {
    public String solve (String s, String t) {
        int l1 = s.length();
        int l2 = t.length();
        Stack<Integer> st = new Stack<>();
        StringBuffer sb = new StringBuffer();
        int curry = 0;
        for(int i = 0; i < Math.max(l1,l2) ; i ++){
            int s1 = (i < l1) ? s.charAt(l1 - 1 - i) - '0' : 0;
            int s2 = (i < l2) ? t.charAt(l2 - 1 - i) - '0' : 0;
            int sum = s1 + s2 + curry ;
            st.add(sum % 10);
            curry = (sum >= 10) ?  1 :0; 
        }
        if(curry == 1)st.add(curry);
        while(!st.isEmpty()) sb.append(st.pop());
        return sb.toString();
    }
}

双指针

题号 题目名称 核心思路 时间复杂度 空间复杂度 代码亮点 牛客原题链接
BM87 合并两个有序的数组 逆向双指针，原地归并 O(m+n) O(1) 从尾部填充，避免覆盖未处理元素 🔗 直达
BM88 判断是否为回文字符串 左右双指针相向扫描 O(n) O(1) 字符数组随机访问，发现不匹配立即返回 🔗 直达
BM89 合并区间 排序 + 贪心扫描 O(n log n) O(n) 按 start 升序排序，重叠即合并，一次遍历完成 🔗 直达
BM90 最小覆盖子串 滑动窗口 + 哈希/数组计数 O( S + T
BM91 反转字符串 双指针交换 / StringBuffer.reverse O(n) O(1) / O(n) 原地交换无需额外空间；StringBuffer 一行代码版 🔗 直达
BM92 最长无重复子数组 滑动窗口 + HashMap 计数 O(n) O(n) 右指针扩展，出现重复时左指针收缩，一次遍历求最大长度 🔗 直达
BM93 盛水最多的容器 双指针夹逼法 O(n) O(1) 短板向内移动才可能得到更大面积，数学证明保证最优 🔗 直达
BM94 接雨水问题 双指针 + 左右最大高度 O(n) O(1) 维护左右最大值，低侧先结算，避免使用栈或额外数组 🔗 直达

✅ 复习顺序建议（由易到难）

BM91 → BM88 → BM87 → BM92 → BM93 → BM94 → BM89 → BM90

BM87 合并两个有序的数组

合并两个有序的数组_牛客题霸_牛客网
https://www.nowcoder.com/practice/89865d4375634fc484f3a24b7fe65665?tpId=295&tqId=658&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int a = m - 1;               // 1. A 数组有效元素末尾索引
        int b = n - 1;               // 2. B 数组末尾索引
        for (int i = m + n - 1; i >= 0; i--) {   // 3. 从合并后数组末尾开始填充
            if (b < 0 || (a >= 0 && A[a] >= B[b])) {   // 4. B 已取完 或 A 的当前元素更大
                A[i] = A[a];         // 5. 将 A[a] 放到位置 i
                a--;                 // 6. A 指针前移
            } else {                 // 7. A 已取完 或 B 的当前元素更大
                A[i] = B[b];         // 8. 将 B[b] 放到位置 i
                b--;                 // 9. B 指针前移
            }
        }
    }
}

BM88 判断是否为回文字符串

判断是否为回文字符串_牛客题霸_牛客网
https://www.nowcoder.com/practice/e297fdd8e9f543059b0b5f05f3a7f3b2?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;

public class Solution {
    public boolean judge(String str) {
        int l = 0;                               // 1. 左指针初始化到字符串开头
        int r = str.length() - 1;                // 2. 右指针初始化到字符串末尾
        char[] a = str.toCharArray();            // 3. 将字符串转为字符数组便于随机访问
        while (l <= r) {                         // 4. 双指针相向扫描
            if (a[l] != a[r]) return false;      // 5. 发现不一致字符，立即返回 false
            l++;                                 // 6. 左指针右移
            r--;                                 // 7. 右指针左移
        }
        return true;                             // 8. 全部字符匹配，是回文
    }
}

BM89 合并区间

合并区间_牛客题霸_牛客网
https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. 排序 + 贪心
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;

public class Solution {

    public ArrayList<Interval> merge(ArrayList<Interval> is) {
        ArrayList<Interval> ans = new ArrayList<>(); // 1. 结果列表
        if (is.size() == 0) return ans;              // 2. 空列表直接返回

        // 3. 按 start 升序排序，start 相同时按 end 升序排序
        Collections.sort(is, new Comparator<Interval>() {
            public int compare(Interval o1, Interval o2) {
                if (o1.start != o2.start) return o1.start - o2.start;
                return o1.end - o2.end;
            }
        });

        ans.add(is.get(0));           // 4. 将第一个区间加入结果
        int cnt = 0;                  // 5. 当前结果末尾区间的索引
        for (int i = 1; i < is.size(); i++) { // 6. 从第二个区间开始遍历
            Interval curr = is.get(i);        // 7. 当前区间
            Interval last = ans.get(cnt);     // 8. 结果末尾区间
            if (curr.start > last.end) {      // 9. 无重叠，直接加入
                ans.add(curr);
                cnt++;
            } else {                          // 10. 有重叠，合并区间
                int newStart = last.start;
                int newEnd   = Math.max(curr.end, last.end);
                ans.remove(cnt);              // 11. 移除原区间
                ans.add(new Interval(newStart, newEnd));
                // 12. cnt 不变，因为末尾仍是合并后的区间
            }
        }
        return ans;                           // 13. 返回合并后的区间列表
    }
}

BM90 最小覆盖子串

最小覆盖子串_牛客题霸_牛客网
https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. 哈希表记录 + 双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;
public class Solution {
    // 1. 检查当前哈希表中所有字符的计数是否都 ≥ 0（即窗口已覆盖 T）
    boolean chk(Map<Character, Integer> map) {
        for (Map.Entry<Character, Integer> e : map.entrySet()) {
            if (e.getValue() < 0) return false;
        }
        return true;
    }
    public String minWindow(String S, String T) {
        Map<Character, Integer> map = new HashMap<>(); // 2. 记录各字符在窗口中的“剩余需求”
        int n1 = T.length(); // 3. T 的长度
        int n2 = S.length(); // 4. S 的长度
        // 5. 初始化需求：T 中每个字符的需求为 -1，便于后续累加
        for (int i = 0; i < n1; i++) {
            map.merge(T.charAt(i), -1, Integer::sum);
        }
        int i = 0;            // 6. 滑动窗口左指针
        int l = -1, r = -1;   // 7. 记录最短窗口的左右边界
        int cnt = 0x3f3f3f;   // 8. 当前最短窗口长度，初始设为极大值
        // 9. 滑动窗口右指针 j 遍历 S
        for (int j = 0; j < n2; j++) {
            map.merge(S.charAt(j), 1, Integer::sum); // 10. 右移窗口：把 S[j] 加入窗口
            // 11. 当前窗口已覆盖 T 时，尝试收缩左边界
            while (chk(map)) {
                if (cnt > j - i + 1) { // 12. 找到更短窗口
                    cnt = j - i + 1;
                    l = i;
                    r = j;
                }
                // 13. 收缩窗口左侧：把 S[i] 移出窗口
                map.merge(S.charAt(i), -1, Integer::sum);
                i++;
            }
        }
        // 14. 如果没有找到有效窗口，返回空串；否则返回子串
        return (l == -1) ? "" : S.substring(l, r + 1);
    }
}
  1. 数组记录 + 双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;

public class Solution {
    static int[] cnt = new int[128];      // 1. 全局计数器，下标映射字符 ASCII
    boolean chk() {                       // 2. 检查当前窗口是否已覆盖 T 的所有字符
        for (int i = 0; i < 128; i++)
            if (cnt[i] < 0) return false; // 3. 任一字符需求未满足（负值）即失败
        return true;                      // 4. 全部需求满足（非负）返回 true
    }

    public String minWindow(String S, String T) {
        Arrays.fill(cnt, 0);              // 5. 初始化计数器
        for (int i = 0; i < T.length(); i++)
            cnt[T.charAt(i)]--;           // 6. 统计 T 的字符需求（负值表示缺失量）
        int s = 0, f = 0;                 // 7. s 左指针，f 右指针
        int l = -1, r = -1;               // 8. 记录最短窗口左右边界
        int count = 0x3f3f3f;             // 9. 最短窗口长度初设为极大值
        while (f < S.length()) {          // 10. 右指针遍历 S
            cnt[S.charAt(f)]++;           // 11. 右指针字符进入窗口
            while (chk()) {               // 12. 当前窗口已满足要求
                if (count > f + 1 - s) {  // 13. 发现更短窗口
                    count = f + 1 - s;
                    l = s;
                    r = f;
                }
                cnt[S.charAt(s)]--;       // 14. 左指针字符移出窗口
                s++;                      // 15. 收缩左边界
            }
            f++;                          // 16. 右指针继续扩张
        }
        if (l == -1) return "";           // 17. 无满足条件的窗口
        return S.substring(l, r + 1);     // 18. 返回最短窗口子串
    }
}

BM91 反转字符串

反转字符串_牛客题霸_牛客网
https://www.nowcoder.com/practice/c3a6afee325e472386a1c4eb1ef987f3?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. 双指针翻转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.*;

public class Solution {
    public String solve(String str) {
        char[] ans = str.toCharArray(); // 1. 将字符串转为字符数组
        int l = 0, r = ans.length - 1;  // 2. 双指针：左指针 l 和右指针 r
        while (l < r) {                 // 3. 当两指针未相遇时循环
            char tmp = ans[l];          // 4. 交换 ans[l] 和 ans[r]
            ans[l] = ans[r];
            ans[r] = tmp;
            l++;                        // 5. 左指针右移
            r--;                        // 6. 右指针左移
        }
        return new String(ans);         // 7. 返回反转后的新字符串
    }
}```

2. StringBuffer 翻转
```java
import java.util.*;

public class Solution {
    public String solve(String str) {
        StringBuffer sb = new StringBuffer();           // 1. 创建可变的字符缓冲区
        for (char ch : str.toCharArray()) sb.append(ch); // 2. 将原字符串每个字符追加到缓冲区
        return sb.reverse().toString();                 // 3. 反转缓冲区内容并返回结果字符串
    }
}

BM92 最长无重复子数组

最长无重复子数组_牛客题霸_牛客网
https://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;

public class Solution {
    public int maxLength(int[] arr) {
        Map<Integer,Integer> cnt = new HashMap<>(); // 1. 哈希表：记录窗口内每个数的出现次数
        int ans = 0, l = 0, r = 0;                  // 2. ans：最长长度；l：左指针；r：右指针
        while (r < arr.length) {                    // 3. 右指针遍历整个数组
            cnt.merge(arr[r], 1, Integer::sum);     // 4. 把 arr[r] 加入窗口，计数 +1
            while (cnt.get(arr[r]) > 1)             // 5. 出现重复：收缩左边界直到无重复
                cnt.merge(arr[l++], -1, Integer::sum);
            ans = Math.max(ans, r - l + 1);         // 6. 更新最长无重复子数组长度
            r++;                                    // 7. 右指针前进，继续扩展窗口
        }
        return ans;                                 // 8. 返回结果
    }
}

BM93 盛水最多的容器

盛水最多的容器_牛客题霸_牛客网
https://www.nowcoder.com/practice/3d8d6a8e516e4633a2244d2934e5aa47?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;

public class Solution {
    public int maxArea(int[] height) {
        if (height.length < 2) return 0;        // 1. 不足两根柱子无法盛水
        int l = 0, r = height.length - 1;       // 2. 双指针初始化为数组两端
        int ans = 0;                            // 3. 保存最大面积
        while (l < r) {                         // 4. 相向扫描直至相遇
            int lh = height[l], rh = height[r]; // 5. 获取当前左右高度
            ans = Math.max(ans, Math.min(lh, rh) * (r - l)); // 6. 计算当前面积并更新最大值
            if (lh < rh) l++;                   // 7. 左侧矮，移动左指针（可能得到更大的高）
            else r--;                           // 8. 右侧矮或等高，移动右指针
        }
        return ans;                             // 9. 返回最大盛水量
    }
}

BM94 接雨水问题

接雨水问题_牛客题霸_牛客网
https://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.*;

public class Solution {
    public long maxWater(int[] arr) {
        long ans = 0;                       // 1. 总接水量
        int l = 0, r = arr.length - 1;      // 2. 双指针
        int lh = 0, rh = 0;                 // 3. 左右两侧当前最大墙高
        while (l < r) {                     // 4. 相向扫描
            lh = Math.max(lh, arr[l]);      // 5. 更新左侧最大高度
            rh = Math.max(rh, arr[r]);      // 6. 更新右侧最大高度
            if (lh < rh) {                  // 7. 左侧瓶颈低
                ans += lh - arr[l++];       // 8. 累加当前柱子的存水量
            } else {                        // 9. 右侧瓶颈低或等高
                ans += rh - arr[r--];       // 10. 累加当前柱子的存水量
            }
        }
        return ans;                         // 11. 返回总接水量
    }
}

贪心算法

题号 题目名称 核心思路 时间复杂度 空间复杂度 代码亮点 牛客原题链接
BM95 分糖果问题 两次贪心扫描：先左→右，再右→左 O(n) O(n) 无需回溯，两次线性遍历即可满足相邻与高分的双重约束 🔗 直达
BM96 主持人调度（二） 贪心 + 双指针（或最小堆） O(n log n) O(n) 将起止时间拆开排序，扫描线思想；堆写法更直观 🔗 直达

✅ 复习顺序建议（由易到难）

BM95 → BM96

BM95 分糖果问题

分糖果问题_牛客题霸_牛客网
https://www.nowcoder.com/practice/76039109dd0b47e994c08d8319faa352?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;

public class Solution {
    public int candy(int[] arr) {
        int n = arr.length;                 // 1. 获取孩子数量
        if (n <= 1) return n;               // 2. 只有一个孩子直接返回 1
        int[] ans = new int[n];             // 3. 每个孩子糖果数
        Arrays.fill(ans, 1);                // 4. 初始每人 1 颗

        // 5. 从左到右：右邻居高则多给 1
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) ans[i] = ans[i - 1] + 1;
        }

        // 6. 从右到左：左邻居高且糖果不足则补
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1] && ans[i] <= ans[i + 1])
                ans[i] = ans[i + 1] + 1;
        }

        return Arrays.stream(ans).sum();    // 7. 返回糖果总数
    }
}

BM96 主持人调度（二）

主持人调度（二）_牛客题霸_牛客网
https://www.nowcoder.com/practice/4edf6e6d01554870a12f218c94e8a299?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. 分开排序 + 计算区间的个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;

public class Solution {
    public int minmumNumberOfHost(int n, int[][] startEnd) {
        int[] st = new int[n];           // 1. 存储所有会议开始时间
        int[] ed = new int[n];           // 2. 存储所有会议结束时间
        for (int i = 0; i < n; i++) {    // 3. 拆分输入数组到 st[] 和 ed[]
            st[i] = startEnd[i][0];
            ed[i] = startEnd[i][1];
        }
        Arrays.sort(st);                 // 4. 升序排序开始时间
        Arrays.sort(ed);                 // 5. 升序排序结束时间
        int res = 0;                     // 6. 所需最少主持人数量
        int j = 0;                       // 7. 指向最早结束的会议
        for (int i = 0; i < n; i++) {    // 8. 遍历所有开始时间
            if (st[i] >= ed[j]) {        // 9. 当前会议开始前已有会议结束，主持人可复用
                j++;                     // 10. 释放该主持人
            } else {                     // 11. 无空闲主持人，需新增
                res++;
            }
        }
        return res;                      // 12. 返回结果
    }
}
  1. 重载排序+大顶堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;

public class Solution {
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        Arrays.sort(startEnd, new Comparator<int[]>() { // 1. 按会议开始时间升序排序
            public int compare(int[] o1, int[] o2) {     // 2. 自定义比较器
                return Integer.compare(o1[0], o2[0]);    // 3. 比较会议的开始时间
            }
        });
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 4. 创建小顶堆，记录各会议室的最早释放时间
        pq.offer(Integer.MIN_VALUE);                       // 5. 先放入哨兵值，避免首次 poll 时空指针
        for (int i = 0; i < n; i++) {                      // 6. 遍历每场会议
            if (pq.peek() <= startEnd[i][0]) {             // 7. 最早结束的会议室已空闲，复用该主持人
                pq.poll();                                 // 8. 弹出该释放时间
            }
            pq.offer(startEnd[i][1]);                      // 9. 把当前会议的结束时间压入堆
        }
        return pq.size();                                  // 10. 堆大小即为所需最少主持人数量
    }
}

模拟

题号 题目名称 核心思路 时间复杂度 空间复杂度 代码亮点 牛客原题链接
BM97 旋转数组 三次反转法 O(n) O(1) 先整体反转，再局部反转两次，无需额外数组 🔗 直达
BM98 螺旋矩阵 模拟层遍历 O(n·m) O(1) 用四个边界控制方向，注意单行/单列去重 🔗 直达
BM99 顺时针旋转矩阵 转置+水平翻转 或 直接映射 O(n²) O(1) / O(n²) 两次翻转原地完成；一次映射写法更直观 🔗 直达
BM100 设计LRU缓存 哈希+双向链表 O(1) O(capacity) 手写双向链表实现最近/最久节点移动；LinkedHashMap版简洁 🔗 直达
BM101 设计LFU缓存 哈希+频次双向链表+最小频次指针 O(1) O(capacity) 维护freq→LinkedList映射，O(1)提频与淘汰 🔗 直达

✅ 复习顺序建议（由易到难）

BM97 → BM98 → BM99 → BM100 → BM101

BM97 旋转数组

旋转数组_牛客题霸_牛客网
https://www.nowcoder.com/practice/e19927a8fd5d477794dac67096862042?tpId=295&tqId=1024689&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.*;

public class Solution {
    void rev(int [] a,int s,int e){  //1. 反转数组a中从索引s到e的元素
        while(s < e){               //2. 双指针，当s < e时循环
            int tmp = a[s];         //3. 交换a[s]和a[e]
            a[s] = a[e];            //4. 将a[e]的值赋给a[s]
            a[e] = tmp;             //5. 将tmp的值赋给a[e]，完成交换
            s ++;e--;               //6. 指针移动，继续下一轮交换
        }
    }
    public int[] solve (int n, int m, int[] a) {  //7. 主函数，实现数组循环右移m位
        m %= n;                     //8. 处理m大于n的情况，取模防止无效旋转
        rev(a,0,n - 1);             //9. 整体反转数组
        rev(a,0,m - 1);             //10. 反转前m个元素
        rev(a,m ,n - 1);            //11. 反转剩余元素
        return a;                   //12. 返回旋转后的数组
    }
}

BM98 螺旋矩阵

螺旋矩阵_牛客题霸_牛客网
https://www.nowcoder.com/practice/7edf70f2d29c4b599693dc3aaeea1d31?tpId=295&tqId=1024689&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;

public class Solution {
    public ArrayList<Integer> spiralOrder (int[][] matrix) {
        ArrayList<Integer> ans = new ArrayList<Integer>();  //1. 存放结果的列表
        if(matrix.length == 0) return ans;                  //2. 矩阵为空直接返回
        int m = matrix.length, n = matrix[0].length;        //3. 矩阵行数m、列数n
        int t = 0, b = m - 1, l = 0, r = n - 1;             //4. 定义上、下、左、右四个边界
        while(t < (m + 1) / 2 && l < (n + 1) / 2) {         //5. 循环条件：未越界
            for(int i = l; i <= r; i++) {                   //6. 从左到右遍历上边
                ans.add(matrix[t][i]);
            }
            for(int i = t + 1; i <= b; i++) {               //7. 从上到下遍历右边
                ans.add(matrix[i][r]);
            }
            for(int i = r - 1; t != b && i >= l; i--) {     //8. 从右到左遍历下边（t != b防重）
                ans.add(matrix[b][i]);
            }
            for(int i = b - 1; l != r && i >= t + 1; i--) { //9. 从下到上遍历左边（l != r防重）
                ans.add(matrix[i][l]);
            }
            t++; l++; b--; r--;                             //10. 缩小边界
        }
        return ans;                                         //11. 返回螺旋遍历结果
    }
}

BM99 顺时针旋转矩阵

顺时针旋转矩阵_牛客题霸_牛客网
https://www.nowcoder.com/practice/2e95333fbdd4451395066957e24909cc?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

  1. 两次翻转 （主对角线 + 水平）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;

public class Solution {

    public int[][] rotateMatrix (int[][] a, int n) {
        int l = a.length;                                   // 1. 获取矩阵的边长
        for(int i = 0 ; i < l ; i ++){                      // 2. 主对角线对称交换，完成矩阵转置
            for(int j = 0 ; j < i ; j ++){                  // 3. 只需遍历下三角，避免重复交换
                int t = a[i][j];                            // 4. 暂存当前位置的值
                a[i][j] = a[j][i];                          // 5. 将上三角对应位置的值赋给下三角
                a[j][i] = t;                                // 6. 将暂存的值赋给上三角对应位置
            }
        }
        for(int i = 0 ; i < l; i ++){                       // 7. 按列中心对称交换，完成水平翻转
            for(int j = 0 ; j < l / 2; j ++){               // 8. 只需遍历左半边，避免重复交换
                int t = a[i][j];                            // 9. 暂存当前位置的值
                a[i][j] = a[i][l - 1 - j];                  // 10. 将右半边对应位置的值赋给左半边
                a[i][l - 1 - j] = t;                        // 11. 将暂存的值赋给右半边对应位置
            }
        }
        return a;                                           // 12. 返回顺时针旋转90度后的矩阵
    }
}
  1. 一次翻转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;

public class Solution {

    public int[][] rotateMatrix (int[][] a, int n) {
        int l = a.length;                          // 1. 获取矩阵边长
        int[][] ans = new int[n][n];               // 2. 创建新矩阵存储旋转结果
        for (int i = 0; i < l; i++) {              // 3. 遍历原矩阵行
            for (int j = 0; j < l; j++) {          // 4. 遍历原矩阵列
                ans[j][n - 1 - i] = a[i][j];       // 5. 将原位置(i,j)元素放到旋转后的位置(j, n-1-i)
            }
        }
        return ans;                                // 6. 返回旋转90°后的矩阵
    }
}

BM100 设计LRU缓存结构

设计LRU缓存结构_牛客题霸_牛客网
https://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.util.*;

public class Solution {
    int capacity = 0;              // 1. 缓存最大容量
    Node head = null;              // 2. 双链表头指针（最近使用）
    Node tail = null;              // 3. 双链表尾指针（最久未使用）
    int used = 0;                  // 4. 当前已用节点数
    HashMap<Integer, Node> map = new HashMap<>(); // 5. key -> 节点映射

    class Node {                   // 6. 双链表节点定义
        int key;
        int val;
        Node pre;
        Node next;
        public Node(int k, int v) {
            key = k;
            val = v;
            pre = null;
            next = null;
        }
    }

    void update(int key) {         // 7. 将指定 key 对应节点移到头部（最近使用）
        Node t = map.get(key);
        if (t != head) {           // 8. 已在头部则无需移动
            if (t == tail) {       // 9. 若节点在尾部，需更新尾指针
                tail = tail.pre;
                tail.next = null;
            } else {               // 10. 中间节点：前后节点直接相连
                t.pre.next = t.next;
                t.next.pre = t.pre;
            }
            t.pre = null;          // 11. 插入头部
            t.next = head;
            head.pre = t;
            head = t;
        }
    }

    void removelast() {            // 12. 淘汰最久未使用节点（尾部）
        map.remove(tail.key);
        tail = tail.pre;
        tail.next = null;
        used--;
    }

    void insert(int key, int val) { // 13. 在头部新增节点
        if (head == null) {         // 14. 首个节点
            head = new Node(key, val);
            tail = head;
        } else {
            Node t = new Node(key, val);
            t.pre = null;
            t.next = head;
            head.pre = t;
            head = t;
        }
    }

    public Solution(int capacity) { // 15. 构造方法，初始化容量
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.used = 0;
    }

    public int get(int key) {       // 16. 查询接口
        if (!map.containsKey(key)) {
            return -1;
        }
        update(key);                // 17. 访问后更新为最近使用
        return map.get(key).val;
    }

    public void set(int key, int val) { // 18. 写入接口
        if (map.containsKey(key)) {     // 19. key 已存在，更新值并置为最近使用
            map.get(key).val = val;
            update(key);
            return;
        }
        if (used == capacity) {         // 20. 容量已满，先淘汰尾部
            removelast();
        }
        insert(key, val);               // 21. 头部插入新节点
        map.put(key, head);
        used++;
    }
}
  1. 内聚一个线程安全的 LRUCache 实例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.LinkedHashMap;
import java.util.Map;

public class Solution {
    // 1. 内聚一个线程安全的 LRUCache 实例
    private final LRUCache<Integer, Integer> cache;

    // 2. 构造方法：由调用方指定最大容量
    public Solution(int capacity) {
        this.cache = new LRUCache<>(capacity);
    }

    // 3. 查询接口：未命中返回 -1，否则返回对应值
    public int get(int key) {
        Integer val = cache.get(key);
        return val == null ? -1 : val;
    }

    // 4. 写入接口：key 存在则刷新值并置为最近使用；不存在则插入（可能触发淘汰）
    public void set(int key, int value) {
        cache.put(key, value);
    }

    // 5. 静态内部类：利用 LinkedHashMap 的 accessOrder 实现 LRU
    private static class LRUCache<K, V> extends LinkedHashMap<K, V> {
        private final int capacity; // 6. 缓存上限

        // 7. 构造器：initialCapacity=capacity，loadFactor=0.75，accessOrder=true 保证访问有序
        LRUCache(int capacity) {
            super(capacity, 0.75f, true);
            this.capacity = capacity;
        }

        // 8. 每插入新节点时回调，返回 true 即触发最老节点移除
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > capacity; // 9. 超过容量时淘汰最久未使用条目
        }
    }
}

BM101 设计LFU缓存结构

设计LFU缓存结构_牛客题霸_牛客网
https://www.nowcoder.com/practice/93aacb4a887b46d897b00823f30bfea1?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import java.util.*;

public class Solution {
    static class N {                       // 1. 链表节点封装 key/value/freq
        int freq;                            // 2. 该节点被访问的频次
        int key;                             // 3. 键，用于全局哈希表反向查找
        int val;                             // 4. 实际存储的值
        public N(int f, int k, int v) {      // 5. 构造器一次性赋值
            this.freq = f;
            this.key = k;
            this.val = v;
        }
    }

    // 6. freq -> 双向链表（头插=最新，尾=最老）
    Map<Integer, LinkedList<N>> freqmp = new HashMap<>();
    // 7. key -> 节点，O(1) 定位
    Map<Integer, N> mp = new HashMap<>();
    int size = 0;       // 8. 缓存允许的最大容量
    int minFreq = 0;    // 9. 全局最小频次，淘汰时直接定位

    // 10. 访问/修改后把节点提到更高 freq 链表头部
    void update(N n, int k, int v) {
        int freq = n.freq;                   // 11. 原频次
        freqmp.get(freq).remove(n);          // 12. 从旧链表删除
        if (freqmp.get(freq).isEmpty()) {    // 13. 旧链表空了则清理
            freqmp.remove(freq);
            if (minFreq == freq) minFreq++;  // 14. 最小频次上移
        }
        // 15. 新频次链表不存在就新建
        if (!freqmp.containsKey(freq + 1))
            freqmp.put(freq + 1, new LinkedList<N>());
        // 16. 头插：保证最新
        freqmp.get(freq + 1).addFirst(new N(freq + 1, k, v));
        // 17. 更新全局 key 索引
        mp.put(k, freqmp.get(freq + 1).getFirst());
    }

    // 18. 插入或更新缓存
    void set(int k, int v) {
        if (mp.containsKey(k)) {               // 19. key 已存在，仅更新值并提频
            update(mp.get(k), k, v);
            return;
        }
        // 20. 容量已满，淘汰最久未使用（minFreq 尾部）
        if (size == 0) {
            int oldKey = freqmp.get(minFreq).getLast().key;
            freqmp.get(minFreq).removeLast();
            if (freqmp.get(minFreq).isEmpty()) freqmp.remove(minFreq);
            mp.remove(oldKey);
        } else size--;                         // 21. 还有空位，容量计数减 1

        // 22. 新节点频次必为 1
        minFreq = 1;
        if (!freqmp.containsKey(1)) freqmp.put(1, new LinkedList<N>());
        freqmp.get(1).addFirst(new N(1, k, v)); // 23. 头插
        mp.put(k, freqmp.get(1).getFirst());    // 24. 建立索引
    }

    // 25. 查询接口，返回 -1 表示未命中
    int get(int k) {
        int res = -1;
        if (mp.containsKey(k)) {
            N n = mp.get(k);
            res = n.val;
            update(n, k, res);       // 26. 访问后提频
        }
        return res;
    }

    // 27. 主入口：operators 按顺序执行 set/get，k 为容量
    public int[] LFU(int[][] operators, int k) {
        this.size = k;               // 28. 记录容量
        // 29. 先统计 get 操作次数，用于结果数组长度
        int len = (int) Arrays.stream(operators)
                              .filter(x -> x[0] == 2)
                              .count();
        int[] res = new int[len];
        // 30. 遍历所有操作
        for (int i = 0, j = 0; i < operators.length; i++) {
            if (operators[i][0] == 1) {              // 31. set 操作
                set(operators[i][1], operators[i][2]);
            } else {                                 // 32. get 操作
                res[j++] = get(operators[i][1]);
            }
        }
        return res;                                  // 33. 返回所有 get 结果
    }
}