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

二叉树的右视图要点层次遍历的套路/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public ListInteger rightSideView(TreeNode root) { if(root null){ return new ArrayList(); } //层次遍历 ListInteger ans new ArrayList(); DequeTreeNode queue new ArrayDeque(); queue.offer(root); while(!queue.isEmpty()){ int size queue.size(); for(int i 0; i size; i){ TreeNode temp queue.poll(); if(temp.left ! null){ queue.offer(temp.left); } if(temp.right ! null){ queue.offer(temp.right); } if(i size -1){ ans.add(temp.val); } } } return ans; } }二叉树的层平均值同上/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public ListDouble averageOfLevels(TreeNode root) { ListDouble ans new ArrayList(); DequeTreeNode queue new ArrayDeque(); queue.offer(root); while(!queue.isEmpty()){ int size queue.size(); double sum 0; for(int i 0; i size; i){ TreeNode temp queue.poll(); sum temp.val; if(temp.left ! null){ queue.offer(temp.left); } if(temp.right ! null){ queue.offer(temp.right); } } ans.add(sum/size); } return ans; } }二叉树的层序遍历/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public ListListInteger levelOrder(TreeNode root) { //队列 if(root null){ return new ArrayList(); } DequeTreeNode deque new ArrayDeque(); ListListInteger anss new ArrayList(); deque.offer(root); while(!deque.isEmpty()){ int size deque.size(); ListInteger ans new ArrayList(); for(int i 0; i size; i){ TreeNode temp deque.poll(); ans.add(temp.val); if(temp.left ! null){ deque.offer(temp.left); } if(temp.right ! null){ deque.offer(temp.right); } } anss.add(ans); } return anss; } }二叉树的锯齿形层序遍历/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public ListListInteger zigzagLevelOrder(TreeNode root) { if(root null){ return new ArrayList(); } //偶数反转 DequeTreeNode deque new ArrayDeque(); ListListInteger anss new ArrayList(); //boolean isOuShu false; deque.offer(root); while(!deque.isEmpty()){ int size deque.size(); ListInteger ans new ArrayList(); for(int i 0; i size; i){ TreeNode temp deque.poll(); ans.add(temp.val); if(temp.left ! null){ deque.offer(temp.left); } if(temp.right ! null){ deque.offer(temp.right); } } if(anss.size() % 2 0){ Collections.reverse(ans); } anss.add(ans); } return anss; } }二叉搜索树的最小绝对差要点中序遍历/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public int getMinimumDifference(TreeNode root) { //中序遍历 ListInteger ans new ArrayList(); DequeTreeNode stack new ArrayDeque(); //stack.push(root); while(!stack.isEmpty() || root ! null){ while(root ! null){ stack.push(root); root root.left; } TreeNode temp stack.pop(); ans.add(temp.val); root temp.right ; } int minDiff Integer.MAX_VALUE; for (int i 1; i ans.size(); i) { minDiff Math.min(minDiff, ans.get(i) - ans.get(i - 1)); } return minDiff; } }class Solution { public int getMinimumDifference(TreeNode root) { DequeTreeNode stack new ArrayDeque(); TreeNode cur root; Integer prev null; // 用 null 表示还没有前驱 int minDiff Integer.MAX_VALUE; while (!stack.isEmpty() || cur ! null) { // 一路向左 while (cur ! null) { stack.push(cur); cur cur.left; } // 访问当前节点 cur stack.pop(); if (prev ! null) { minDiff Math.min(minDiff, cur.val - prev); } prev cur.val; // 转向右子树 cur cur.right; } return minDiff; } }二叉搜索树中第 K 小的元素要点中序遍历/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public int kthSmallest(TreeNode root, int k) { //中层遍历 DequeTreeNode stack new ArrayDeque(); while(!stack.isEmpty() || root ! null){ while(root ! null){ stack.push(root); root root.left; } TreeNode temp stack.pop(); k--; if(k 0){ return temp.val; } root temp.right; } return 0; } }验证二叉搜索树要点中序遍历/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public boolean isValidBST(TreeNode root) { DequeTreeNode stack new ArrayDeque(); Double pre -Double.MAX_VALUE; while(!stack.isEmpty() || root ! null){ while(root ! null){ stack.push(root); root root.left; } TreeNode temp stack.pop(); if(temp.val pre){ return false; } pre (double)temp.val; root temp.right; } return true; } }岛屿数量要点bfsclass Solution { public int numIslands(char[][] grid) { //bfs int ans 0; int m grid.length; int n grid[0].length; for(int i 0; i m; i){ for(int j 0; j n; j){ if(grid[i][j] 1){ dfs(i, j, grid); ans; } } } return ans; } public void dfs(int i, int j, char[][] grid){ if(i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0){ return; } grid[i][j] 0; dfs(i1,j,grid); dfs(i-1,j,grid); dfs(i,j1,grid); dfs(i,j-1,grid); } }随机知识HashMap 1.7 vs 1.8 源码对比 画图文字描述 口述自测答案一、底层结构核心差异表格维度JDK1.7 HashMapJDK1.8 HashMap数组节点EntryK,V单向链表NodeK,V单向链表 TreeNode红黑树节点链表插入头插法新节点放链表头部尾插法新节点追加到链表尾部长链表优化无优化链表无限变长查询 O (n)链表长度≥8 树化为红黑树查询 O (logn)≤6 退化为链表扩容 rehash全部节点重新计算 hash头插倒置链表利用 hash 高位拆分高低链表尾插保留原有顺序二、为什么从 1.7 改成 1.8两大核心原因1. 头插法扩容并发死链最关键改动动机1.7 头插法扩容逻辑扩容时新建 2 倍长度数组遍历原链表每次把当前节点插到新链表头部链表顺序完全反转。 并发场景下两个线程同时触发扩容线程 A 遍历链表A→B→null刚处理完 A时间片切走线程 B 完整完成扩容新链表变成B→A→null线程 A 恢复执行继续拿 B 节点头插后形成A→BB 的 next 又指向 A环形链表后续get()、containsKey()遍历链表无限循环CPU 100%。1.8 尾插法解决死链扩容时节点追加到高低链表尾部原有节点相对顺序不变不会倒置链表并发扩容不会产生循环引用彻底根除环形链表问题。2. 长链表查询性能太差引入红黑树优化1.7 哈希冲突严重时一条链表挂载几十上百节点查询需要从头到尾遍历时间复杂度 O (n) 1.8 当链表过长转为红黑树查找、插入、删除 O (logn)大幅降低高冲突下查询耗时。三、图文还原1.7 环形链表形成过程文字绘图可直接手绘初始状态原数组桶内链表A - B - null扩容 newTab 长度翻倍线程 A 执行 transfer指针e Anext B还未迁移 A被挂起线程 B 完整执行扩容迁移迁移 BnewTab 链表B迁移 A头插到 B 前面newTab 链表A - B - null线程 A 恢复执行当前 eAnextB将 A 头插入新链表Ae 更新为 nextBB 不为 null继续迁移 BB 的 next 原本是 null但线程 B 已经把 B.next 指向 A头插 B 到链表头部得到B - AA.next B最终形成环A ↔ B无限循环手绘简记plaintext原始链表A → B → null 线程B扩容后A → B → null 线程A继续处理B.nextAA.nextB 环形闭环四、1.8 红黑树插入流程图文字版手绘新 Node 计算 hash定位数组下标桶判断桶首节点桶为空直接放数组结束桶不为空key 相等覆盖旧值结束桶是链表节点循环遍历链表尾部同步统计链表长度找到同 key 则覆盖没找到则追加到链表尾部尾插追加完成后判断链表长度len 8执行treeifyBin()树化treeifyBin 流程判断数组长度是否小于 64不树化直接扩容扩容打散冲突更高效链表节点转为 TreeNode 双向链表双向链表构建红黑树平衡染色、左旋右旋调整树结构桶已经是红黑树根节点树中查找 key匹配则覆盖无匹配则插入新 TreeNode自动平衡红黑树流程图简化结构plaintext计算hash定位桶 ↓ 桶空→ 直接存入 ↓否 首节点key相等→ 覆盖 ↓否 首节点是TreeNode→ 红黑树插入平衡 ↓否普通链表 遍历链表尾部尾插计数长度 ↓ 长度≥8 tab容量≥64 → 链表转红黑树 ↓ 长度≥8 tab容量64 → 扩容打散五、自测口述标准答案为什么阈值是 8 转树、6 退链不是 6 转树从概率、性能、红黑树开销三个层面解释哈希分布概率依据HashMap 默认 hash 扰动算法下单个链表节点数量符合泊松分布。链表长度达到 8 的概率极低仅千万分之一正常业务几乎不会出现长链表如果阈值设为 6轻微哈希冲突就频繁树化完全没必要。树化 / 退树的开销平衡红黑树节点 TreeNode 比普通 Node 内存占用大很多存储父、左右、颜色、前驱后继指针维护平衡树还要左旋、右旋、染色插入删除开销远高于普通链表。 如果阈值设 6少量冲突就频繁转树内存与计算开销陡增等到链表长度到 8线性遍历性能衰减已经非常明显此时树化收益远大于开销。6 作为退链阈值防止频繁切换震荡树化阈值 8、退化阈值 6中间留出差值缓冲。如果进树和退树阈值相同比如都是 8当链表节点在 8 个左右浮动时会反复执行树化、退链频繁转换结构造成性能抖动。设置 6 作为退化阈值预留缓冲区间避免频繁切换数据结构。链表与红黑树查询性能拐点链表长度小于 8 时顺序遍历的 CPU 缓存连续访问效率很高O (n) 遍历速度并不慢超过 8 个节点后线性遍历耗时显著上升红黑树 O (logn) 的优势才能体现出来因此选择 8 作为树化临界点。总结8 是兼顾哈希概率、查询性能、结构转换开销的最优临界点6 作为退化阈值缓冲防止结构频繁震荡。碎碎念后续会更新每天学习的八股和算法 题开始准备秋招的第46/7/8/9/50/【身体原因休息五天】51天。努力连续更新100天以后每天就按秋招项目【java agent】科研必做项目算法八股锻炼身体来总结。总结坚持不管干什么都得坚持1.算法面试150 97/150 2h2.秋招项目【java 项目】【agent 项目 】3.科研要跑一下4.检测项目4h6.背八股7.锻炼身体坚持不完美也开始坚定目标学习心平气和。