被围绕的区域要点bfsclass 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(i1, j, board); bfs(i-1, j, board); bfs(i,j1,board); bfs(i, j-1,board); } }课程表要点建图入度bfsclass Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { //建图计算入度然后找入度为0 的bfs计算课程 //第一步建图 ListInteger[] 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的课程 DequeInteger 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. 建图邻接表 ListInteger[] 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 的课程入队可以直接学 DequeInteger 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 AA.next nullT1 恢复继续执行持有旧节点 AT1 把 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 会转为红黑树进一步降低长链表遍历开销弥补了尾插 “新元素在尾部查询略慢” 的微小缺陷。六、一句话总结JDK1.7 头插设计初衷是热点数据快速查询但并发扩容链表反转极易形成环形链表死循环 CPU100%JDK1.8 尾插扩容迁移保留链表原有顺序节点指针单向无反向闭环彻底解决并发扩容死循环漏洞。碎碎念后续会更新每天学习的八股和算法 题开始准备秋招的第53天。努力连续更新100天以后每天就按秋招项目【java agent】科研必做项目算法八股锻炼身体来总结。总结慢慢恢复状态吧1.算法面试150 100/150 2h2.秋招项目【java 项目】【agent 项目 】3.科研要跑一下4.实习6h6.背八股1h7.锻炼身体明天试试番茄钟学习法吧
