当前位置：首页 > news >正文

leecodecode【面试150】【2026.7.2打卡-java版本】

news 2026/7/5 14:03:53

被围绕的区域

要点：bfs

class Solution { public void solve(char[][] board) { //bfs int m = board.length; int n = board[0].length; for(int j = 0; j < n; j++){ if(board[0][j] == 'O'){ bfs(0, j, board); } if(board[m-1][j] == 'O'){ bfs(m-1, j, board); } } for(int i = 0; i < m; i++){ if(board[i][0] == 'O'){ bfs(i,0,board); } if(board[i][n-1] == 'O'){ bfs(i, n-1, board); } } for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ //注意顺序 if(board[i][j] == 'O'){ board[i][j] = 'X'; } if(board[i][j] == '#'){ board[i][j] = 'O'; } } } } public void bfs(int i, int j, char[][] board){ //退出的条件 if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#'){ return; } board[i][j] = '#'; bfs(i+1, j, board); bfs(i-1, j, board); bfs(i,j+1,board); bfs(i, j-1,board); } }

课程表

要点：建图，入度，bfs

class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { //建图，计算入度，然后找入度为0 的bfs，计算课程 //第一步：建图 List<Integer>[] graph = new ArrayList[numCourses]; for(int i = 0; i < numCourses; i++){ graph[i] = new ArrayList<>(); } //第二步：统计入度 + 完善图的关系 int[] inDegree = new int[numCourses]; for(int[] p : prerequisites){ //这个要修改 int pre = p[1]; int next = p[0]; graph[pre].add(next); inDegree[next]++; } //第三步：找出入读为0的课程 Deque<Integer> queue = new ArrayDeque<>(); for(int i = 0; i < numCourses; i++){ if(inDegree[i] == 0){ queue.offer(i); } } //第四步： 开启上课 bfs int count = 0; while(!queue.isEmpty()){ int current = queue.poll(); count++; for(int nextcourse : graph[current]){ inDegree[nextcourse]--; if(inDegree[nextcourse] == 0){ queue.offer(nextcourse); } } } return count == numCourses; } }

课程表 II

要点：同上，价格返回的数组

class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { // 1. 建图（邻接表） List<Integer>[] graph = new ArrayList[numCourses]; for (int i = 0; i < numCourses; i++) { graph[i] = new ArrayList<>(); } // 2. 统计入度 + 填充图 int[] inDegree = new int[numCourses]; for (int[] p : prerequisites) { int pre = p[1]; // 先修课 int next = p[0]; // 后修课 graph[pre].add(next); inDegree[next]++; // 后修课的入度 +1 } // 3. 将所有入度为 0 的课程入队（可以直接学） Deque<Integer> queue = new ArrayDeque<>(); for (int i = 0; i < numCourses; i++) { if (inDegree[i] == 0) { queue.offer(i); } } // 4. BFS 拓扑排序，同时记录学习顺序 int[] result = new int[numCourses]; // 存储最终顺序 int index = 0; // 当前填到 result 的第几个位置 while (!queue.isEmpty()) { int current = queue.poll(); result[index++] = current; // 学完这门课，记录顺序 for (int nextCourse : graph[current]) { inDegree[nextCourse]--; // 依赖当前课的课程，前置需求减1 if (inDegree[nextCourse] == 0) { queue.offer(nextCourse); } } } // 5. 如果所有课程都能被安排，返回顺序；否则返回空数组 if (index == numCourses) { return result; } else { return new int[0]; // 有环，无法完成 } } }

随机知识

HashMap JDK1.7 头插法 vs JDK1.8 尾插法完整解析

一、先搞懂：什么是头插、尾插

HashMap 底层数组 + 链表，当哈希冲突时，新元素挂载到链表上：

JDK1.7 头插法新节点直接放在链表头部，原来的链表整体挂在新节点后面。插入顺序：A→B→C，链表存储顺序：C→B→A（逆序）
JDK1.8 尾插法遍历到链表尾部，把新节点接在最后。插入顺序：A→B→C，链表存储顺序：A→B→C（原顺序保留）

二、JDK1.7 为什么设计头插？初衷

设计者理论假设：刚插入的元素，后续被查询的概率更高。头插后新元素在链表头部，查询时不用遍历整条链表，能更快命中，提升查询效率。单线程环境下这个逻辑没问题，但完全没考虑多线程并发扩容场景。

三、头插法致命缺陷：并发扩容死循环（CPU100%）

1. 扩容核心逻辑

HashMap 容量满了会触发扩容：新建 2 倍长度数组，把旧数组所有链表节点重新哈希迁移到新数组。头插迁移规则：每条链表节点从头取出，依次插到新链表头部，迁移后链表反转。

2. 并发下环形链表产生过程（两个线程同时扩容）

假设原链表：A → B，两线程 T1、T2 同时执行resize()扩容

T1 先执行到迁移节点A，刚取出 A，时间片被剥夺暂停；
T2 完整完成扩容：
- 取出 A 头插 → 新链表 [A]
- 取出 B 头插 → 新链表 [B→A] 此时内存中B.next = A，A.next = null
T1 恢复继续执行，持有旧节点 A：
- T1 把 A 头插到新数组，A.next = null
- 再取旧链表下一个节点 B，把 B 头插，B.next = A
- 循环读取 B 的下一个节点 A，再次头插，A.next = B
最终形成环：A ↔ B，环形链表。

3. 死循环现象

后续任何操作（get/put）遍历这条链表时，永远在 A、B 之间无限循环，线程卡死，CPU 占用直接拉满 100%。除此之外，并发头插还会出现数据丢失、数据重复问题。

四、JDK1.8 尾插法如何彻底规避环形链表

1. 迁移规则改变：保留原有链表顺序

扩容迁移时，整条链表按原顺序复制，节点相对顺序不变，不会反转链表。原链表A→B，迁移后依然A→B。

2. 为什么不会出现环？

尾插是顺序遍历追加，不会颠倒节点指向：

迁移时先完整记录当前链表头、尾节点；
依次把节点接到新链表尾部，节点的 next 指针只单向向后；
不存在 “后插入节点指向前面节点” 的反向指针，永远不可能形成闭环。

多线程同时扩容时，最多出现数据覆盖、丢失（HashMap 本身线程不安全这点没变），不会生成环形链表，彻底杜绝死循环 CPU 打满问题。

五、补充两个关键细节

HashMap 本身自始至终都不是线程安全尾插只是修复了并发扩容死循环 bug，多线程场景依然会丢数据、覆盖数据，并发环境必须用ConcurrentHashMap。
JDK1.8 不止改了插入方式冲突链表长度超过 8 会转为红黑树，进一步降低长链表遍历开销，弥补了尾插 “新元素在尾部，查询略慢” 的微小缺陷。