排序链表package hot100; import com.sun.source.tree.WhileLoopTree; //guibing public class lc148 { /*排序链表 给你链表的头结点 head 请将其按 升序 排列并返回 排序后的链表 。 输入head [4,2,1,3] 输出[1,2,3,4] */ public ListNode sortList(ListNode head) { //递归先传递到低再归并 //要看看也没有两个节点了还 if(head null || head.next null){ return head; } ListNode list1 head; ListNode list2 middle(head); //处理的是递归上来的 ListNode l1 sortList(list1); ListNode l2 sortList(list2); return merge(l1,l2); } private ListNode middle(ListNode head) { ListNode pre head; ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null){ pre slow; slow slow.next; fast fast.next.next; } pre.next null; return slow; } private ListNode merge(ListNode list1, ListNode list2) { ListNode dummy new ListNode(0); ListNode cur dummy; while(list1 ! null list2 ! null){ if(list1.val list2.val){ cur.next list1; list1 list1.next; }else { cur.next list2; list2 list2.next; } cur cur.next; } cur.next (list1 ! null) ? list1 : list2; return dummy.next; } public ListNode buildNode(int[] nums){ ListNode dummy new ListNode(); ListNode cur dummy; for(int num : nums){ cur.next new ListNode(num); cur cur.next; } return dummy.next; } public void printList(ListNode node){ while (node ! null){ System.out.print(node.val ); node node.next; } System.out.println(); } public static void main(String[] args) { lc148 solution new lc148(); int[] nums new int[]{4,2,1,3}; ListNode head solution.buildNode(nums); solution.printList(head); ListNode ans solution.sortList(head); solution.printList(ans); } }LRU 缓存package hot100; import java.util.HashMap; public class LRUCache { /* LRU 缓存 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类 LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在则变更其数据值 value 如果不存在则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity 则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行*/ //hashmap 链表 //ListNode的里面有两个keyval static class ListNode{ int val; int key; ListNode pre; ListNode next; ListNode(){}; ListNode(int key, int val){ this.key key; this.val val; } } int capacity; HashMapInteger,ListNode map; ListNode dummy; public LRUCache(int capacity) { map new HashMap(); this.capacity capacity; dummy new ListNode(); dummy.next dummy; dummy.pre dummy; } public int get(int key) { ListNode temp map.get(key); if(temp ! null){ //传入的也是key getNode(temp.key); return temp.val; }else{ return -1; } } public void put(int key, int value) { ListNode temp map.get(key); if(temp null){ ListNode newnode new ListNode(key,value); toFirst(newnode); map.put(key,newnode); }else{ temp.val value; getNode(temp.key); } while(map.size() capacity){ ListNode dele dummy.pre; remove(dele); //删除的饿是key map.remove(dele.key); } } //getNode(Node) public void getNode(int key){ ListNode temp map.get(key); remove(temp); toFirst(temp); } //tofirst public void toFirst(ListNode node){ //ListNode temp getNode(node); ListNode next dummy.next; dummy.next node; next.pre node; node.next next; node.pre dummy; } //remove public void remove(ListNode node){ ListNode pre node.pre; ListNode next node.next; pre.next next; next.pre pre; } public static void main(String[] args) { LRUCache cache new LRUCache(2); cache.put(1, 1); cache.put(2, 2); System.out.println(cache.get(1)); // 1 cache.put(3, 3); System.out.println(cache.get(2)); // -1 cache.put(4, 4); System.out.println(cache.get(1)); // -1 System.out.println(cache.get(3)); // 3 System.out.println(cache.get(4)); // 4 } }二叉树的中序遍历package hot100; import java.util.*; public class lc94 { /*94. 二叉树的中序遍历 给定一个二叉树的根节点 root 返回 它的 中序 遍历 。 输入root [1,null,2,3] 输出[1,3,2] */ /*递归 ListInteger ans new ArrayList(); public ListInteger inorderTraversal(TreeNode root) { dfs(root); return ans; } public void dfs(TreeNode root){ if(root null){ return; } dfs(root.left); ans.add(root.val); dfs(root.right); } * */ public ListInteger inorderTraversal(TreeNode root) { //栈 if(root null){ return new ArrayList(); } ListInteger ans new ArrayList(); DequeTreeNode stack new ArrayDeque(); //push,poll,pop,offer //stack.push(root); while(!stack.isEmpty() || root ! null){ while(root ! null){ stack.push(root); root root.left; } root stack.pop(); ans.add(root.val); root root.right; } return ans; } public static TreeNode buildTreeFromArray(Integer[] arr) { if (arr null || arr.length 0 || arr[0] null) { return null; } TreeNode root new TreeNode(arr[0]); QueueTreeNode queue new LinkedList(); queue.offer(root); int i 1; int n arr.length; while (!queue.isEmpty() i n) { TreeNode cur queue.poll(); // 左子节点 if (i n arr[i] ! null) { cur.left new TreeNode(arr[i]); queue.offer(cur.left); } i; // 右子节点 if (i n arr[i] ! null) { cur.right new TreeNode(arr[i]); queue.offer(cur.right); } i; } return root; } // ---------- 测试 main ---------- public static void main(String[] args) { // 示例输入[1,null,2,3] Integer[] input {1, null, 2, 3}; TreeNode root buildTreeFromArray(input); lc94 solution new lc94(); ListInteger result solution.inorderTraversal(root); System.out.println(result); // 输出 [1, 3, 2] // 也可以测试其他情况例如 [1,2,3,null,null,4,5] Integer[] input2 {1, 2, 3, null, null, 4, 5}; TreeNode root2 buildTreeFromArray(input2); System.out.println(solution.inorderTraversal(root2)); // 预期 [2, 1, 4, 3, 5] } }二叉树的最大深度package hot100; import java.util.*; public class lc104 { /* *二叉树的最大深度 给定一个二叉树 root 返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 输入root [3,9,20,null,null,15,7] 输出3 */ public int maxDepth(TreeNode root) { int ans dfs(root); return ans; } public int dfs(TreeNode node){ if(node null){ return 0; } int left dfs(node.left); int right dfs(node.right); return Math.max(left, right) 1; } public static TreeNode buildTreeFromArray(Integer[] arr) { if (arr null || arr.length 0 || arr[0] null) { return null; } TreeNode root new TreeNode(arr[0]); QueueTreeNode queue new LinkedList(); queue.offer(root); int i 1; int n arr.length; while (!queue.isEmpty() i n) { TreeNode cur queue.poll(); // 左子节点 if (i n arr[i] ! null) { cur.left new TreeNode(arr[i]); queue.offer(cur.left); } i; // 右子节点 if (i n arr[i] ! null) { cur.right new TreeNode(arr[i]); queue.offer(cur.right); } i; } return root; } // ---------- 测试 main ---------- public static void main(String[] args) { // 测试用例1: [3,9,20,null,null,15,7] 期望深度 3 Integer[] input1 {3, 9, 20, null, null, 15, 7}; TreeNode root1 buildTreeFromArray(input1); lc104 solution new lc104(); int depth1 solution.maxDepth(root1); System.out.println(深度1: depth1); // 输出 3 // 测试用例2: [1,null,2] 期望深度 2 Integer[] input2 {1, null, 2}; TreeNode root2 buildTreeFromArray(input2); int depth2 solution.maxDepth(root2); System.out.println(深度2: depth2); // 输出 2 // 测试用例3: 空树 [] 期望深度 0 Integer[] input3 {}; TreeNode root3 buildTreeFromArray(input3); int depth3 solution.maxDepth(root3); System.out.println(深度3: depth3); // 输出 0 } }翻转二叉树package hot100; import java.util.*; public class lc226 { /*. 翻转二叉树 给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。 输入root [4,2,7,1,3,6,9] 输出[4,7,2,9,6,3,1]*/ public TreeNode invertTree(TreeNode root) { TreeNode ans dfs(root); return ans; } public TreeNode dfs(TreeNode root){ if(root null){ return null; } TreeNode left dfs(root.left); TreeNode right dfs(root.right); root.left right; root.right left; return root; } public TreeNode invertTree1(TreeNode root) { if (root null) return null; QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { TreeNode cur queue.poll(); // 交换左右孩子 TreeNode temp cur.left; cur.left cur.right; cur.right temp; // 将非空孩子入队 if (cur.left ! null) queue.offer(cur.left); if (cur.right ! null) queue.offer(cur.right); } return root; } public static TreeNode buildTreeFromArray(Integer[] arr) { if (arr null || arr.length 0 || arr[0] null) return null; TreeNode root new TreeNode(arr[0]); QueueTreeNode queue new LinkedList(); queue.offer(root); int i 1, n arr.length; while (!queue.isEmpty() i n) { TreeNode cur queue.poll(); if (i n arr[i] ! null) { cur.left new TreeNode(arr[i]); queue.offer(cur.left); } i; if (i n arr[i] ! null) { cur.right new TreeNode(arr[i]); queue.offer(cur.right); } i; } return root; } // ---------- 辅助函数层序遍历打印树用于验证 ---------- public static ListInteger levelOrder(TreeNode root) { ListInteger result new ArrayList(); if (root null) return result; QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { TreeNode cur queue.poll(); result.add(cur.val); if (cur.left ! null) queue.offer(cur.left); if (cur.right ! null) queue.offer(cur.right); } return result; } // ---------- 测试 ---------- public static void main(String[] args) { // 原树 [4,2,7,1,3,6,9] Integer[] input {4, 2, 7, 1, 3, 6, 9}; TreeNode root buildTreeFromArray(input); System.out.println(原始层序: levelOrder(root)); // [4, 2, 7, 1, 3, 6, 9] lc226 solution new lc226(); TreeNode inverted solution.invertTree(root); System.out.println(翻转后层序: levelOrder(inverted)); // [4, 7, 2, 9, 6, 3, 1] } }对称二叉树package hot100; import java.util.*; public class lc101 { //第一次没做出来 /* 对称二叉树 给你一个二叉树的根节点 root 检查它是否轴对称*/ public boolean isSymmetric(TreeNode root) { if(root null){ return true; } boolean ans dfs(root.left, root.right); return ans; } public boolean dfs(TreeNode root1, TreeNode root2){ if(root1null || root2 null){ return root1 root2; } boolean left dfs(root1.left,root2.right); boolean right dfs(root1.right, root2.left); if(left true right true root1.val root2.val){ return true; }else{ return false; } } // ---------- 辅助函数从数组构造二叉树 ---------- public static TreeNode buildTreeFromArray(Integer[] arr) { if (arr null || arr.length 0 || arr[0] null) { return null; } TreeNode root new TreeNode(arr[0]); QueueTreeNode queue new LinkedList(); queue.offer(root); int i 1, n arr.length; while (!queue.isEmpty() i n) { TreeNode cur queue.poll(); if (i n arr[i] ! null) { cur.left new TreeNode(arr[i]); queue.offer(cur.left); } i; if (i n arr[i] ! null) { cur.right new TreeNode(arr[i]); queue.offer(cur.right); } i; } return root; } // ---------- 测试 main ---------- public static void main(String[] args) { lc101 solution new lc101(); // 测试用例1对称树 [1,2,2,3,4,4,3] 应返回 true Integer[] arr1 {1, 2, 2, 3, 4, 4, 3}; TreeNode root1 buildTreeFromArray(arr1); System.out.println(树1是否对称 solution.isSymmetric(root1)); // true // 测试用例2不对称树 [1,2,2,null,3,null,3] 应返回 false Integer[] arr2 {1, 2, 2, null, 3, null, 3}; TreeNode root2 buildTreeFromArray(arr2); System.out.println(树2是否对称 solution.isSymmetric(root2)); // false // 测试用例3空树 应返回 true TreeNode root3 null; System.out.println(空树是否对称 solution.isSymmetric(root3)); // true } }二叉树的直径package hot100; import java.util.*; public class lc543 { /*二叉树的直径 给你一棵二叉树的根节点返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。 输入root [1,2,3,4,5] 输出3 解释3 取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。 */ int max 0; public int diameterOfBinaryTree(TreeNode root) { int ans depth(root); //节点和路径3个节点里面的路径是2 return max-1; } public int depth(TreeNode root){ if(root null){ return 0; } int left depth(root.left); int right depth(root.right); max Math.max(max, left right 1); return Math.max(left, right)1; } // ---------- 辅助函数从数组构造二叉树 ---------- public static TreeNode buildTreeFromArray(Integer[] arr) { if (arr null || arr.length 0 || arr[0] null) { return null; } TreeNode root new TreeNode(arr[0]); QueueTreeNode queue new LinkedList(); queue.offer(root); int i 1, n arr.length; while (!queue.isEmpty() i n) { TreeNode cur queue.poll(); if (i n arr[i] ! null) { cur.left new TreeNode(arr[i]); queue.offer(cur.left); } i; if (i n arr[i] ! null) { cur.right new TreeNode(arr[i]); queue.offer(cur.right); } i; } return root; } // ---------- 测试 main ---------- public static void main(String[] args) { // 示例root [1,2,3,4,5] Integer[] input {1, 2, 3, 4, 5}; TreeNode root buildTreeFromArray(input); lc543 solution new lc543(); int diameter solution.diameterOfBinaryTree(root); System.out.println(二叉树的直径为: diameter); // 预期输出 3 } }二叉树的层序遍历package hot100; import java.util.*; public class lc102 { /*二叉树的层序遍历 给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点*/ public ListListInteger levelOrder(TreeNode root) { //队列 DequeTreeNode queue new ArrayDeque(); ListListInteger anss new ArrayList(); if(root null){ return anss; } queue.offer(root); while(!queue.isEmpty()){ int size queue.size(); ListInteger ans new ArrayList(); for(int i 0; i size; i){ TreeNode temp queue.poll(); ans.add(temp.val); if(temp.left ! null){ queue.offer(temp.left); } if(temp.right ! null){ queue.offer(temp.right); } } anss.add(ans); } return anss; } // ---------- 辅助函数从数组构造二叉树 ---------- public static TreeNode buildTreeFromArray(Integer[] arr) { if (arr null || arr.length 0 || arr[0] null) { return null; } TreeNode root new TreeNode(arr[0]); QueueTreeNode queue new LinkedList(); queue.offer(root); int i 1, n arr.length; while (!queue.isEmpty() i n) { TreeNode cur queue.poll(); if (i n arr[i] ! null) { cur.left new TreeNode(arr[i]); queue.offer(cur.left); } i; if (i n arr[i] ! null) { cur.right new TreeNode(arr[i]); queue.offer(cur.right); } i; } return root; } // ---------- 测试 main ---------- public static void main(String[] args) { // 示例树[3,9,20,null,null,15,7] Integer[] input {3, 9, 20, null, null, 15, 7}; TreeNode root buildTreeFromArray(input); lc102 solution new lc102(); ListListInteger result solution.levelOrder(root); // 输出结果[[3], [9, 20], [15, 7]] System.out.println(result); } }碎碎念后续会更新每天学习的八股和算法 题开始准备秋招的第69天。努力连续更新100天以后每天就按秋招项目【java agent】科研必做项目算法八股锻炼身体来总结。总结第一次周六学了点冲冲冲1.hot100 【acm】 41/100 2到3h快速把hot100过一遍【6/20】2.秋招项目【java 项目】【agent 项目 】继续3.科研。确定方向就搞就可以了4.实习6.背八股无7.锻炼身体无要点:继续加油