Leetcode 236. 二叉树的最近公共祖先

142. 环形链表 II

问题描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

**进阶：**你是否可以使用 O(1) 空间解决此题？

解题思路与代码实现

解题思路I:

使用辅助集合存储访问过的节点：

如果有环，第一个遇到的访问过的节点即为入环的第一个节点；

如果无环，返回null；

 class Solution {public ListNode detectCycle(ListNode head) {ListNode pos = head;Set<ListNode> visited = new HashSet<ListNode>();	// 记录访问过的节点while (pos != null) {if (visited.contains(pos)) {return pos;} else {visited.add(pos);}pos = pos.next;}return null;}
}

解题思路II：

1. 先判断是否有环，使用快慢指针，初始时fast和slow都指向head，fast指针每次走两步，slow指针每次走一步；
2. 如果有环，fast移到head头结点，然后fast和slow每次都走一步，相遇时返回相遇节点；
3. 如果无环，则返回null。

public class Solution {public ListNode detectCycle(ListNode head) {if(head == null || head.next == null){  // 节点数量小于等于1，不可能有环return null;}// 快慢指针判断是否有环ListNode slow = head ,fast = head; while(fast!=null && slow!=null){slow = slow.next;   // slow走一步fast = fast.next;    // fast走两步if(fast!=null && fast.next != null){fast = fast.next;}else{  // fast 指针走过链表末端，说明链表无环，return null; }if(fast == slow){   // 二者指向同一节点fast = head;break;}}//有环while (fast != null){if (fast == slow ){return fast;}fast = fast.next;slow = slow.next;}return null;}
}

踩坑点

无

92. 反转链表 II

问题描述

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

• 链表中节点数目为 n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

解题思路与代码实现

解题思路:

将链表划分为三部分：[1, left)、[left, right]、[right+1, n]

扫描链表，将[left, right]区间的中间链表反转后重新拼接

需要注意特殊的情况导致的NPE，如左链表不存在，右链表不存在

class Solution {/*** 反转从位置 left 到位置 right 的链表节点*/public ListNode reverseBetween(ListNode head, int left, int right) {if (head == null || head.next == null) {    // 节点数不超过1的链表直接返回return head;}int count = 1;  // 计数器ListNode cur = head;    // 辅助指针ListNode leftHead = head, leftTail = null; // 左链表头尾结点while (cur != null && count < left) {leftTail = cur;cur = cur.next;count++;}if (leftTail != null) { // 左链表不为空leftTail.next = null;}ListNode midHead = cur, midTail = null; // 需要翻转的中间链表头尾结点while (cur != null && count <= right) {midTail = cur;cur = cur.next;count++;}if (midTail != null){midTail.next = null;}ListNode rightHead = cur;   // 右链表的头结点ListNode[] nodes = reverseList(midHead); // 中间链表反转if ( leftTail == null) {leftHead = nodes[0];} else {leftTail.next = nodes[0];}nodes[1].next = rightHead;return leftHead;}/*** 反转链表，返回值包含反转后新链表的头尾节点*/private ListNode[] reverseList(ListNode head) {ListNode newTail = head, newHead = null;    // 新链表的头尾节点ListNode current = head, post = null;   // 辅助指针while (current != null) {post = current.next;current.next = newHead;newHead = current;current = post;}return new ListNode[]{newHead, newTail};}}

踩坑点

NPE

146. 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) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多调用 2 * 105 次 get 和 put

解题思路与代码实现

解题思路:

使用哈希表缓存键值对，使用双端队列实现LRU（最近最少使用）算法，最近最少访问的key放在队头，最新访问的key放在队尾。

调用get方法：若key存在，将key从双端队列中移除并重新添加到队尾；

调用put方法：

若key存在，更新value，同时将key从双端队列中移除并重新添加到队尾；

若key不存在：

​ 如果缓存未满，直接插入到缓存中并将key保存到双端队列的队尾；

​ 如果缓存已满，先从队头移除一个旧key，同时移除缓存；然后将新的key-value添加到缓存，并将key保存到双端队列的队尾。

class LRUCache {private HashMap<Integer, Integer> map = null; // 存储键值对private int capacity = 0; // 缓存容量private Deque<Integer> deque = null; // 辅助双端队列，实现lru算法，淘汰先入队的public LRUCache(int capacity) {this.capacity = capacity;map = new HashMap<>(capacity);deque = new LinkedList<>();}/*** 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1** @param key 关键字key*/public int get(int key) {if (map.containsKey(key)) {// key被访问，调整其在队列中的位置deque.remove(key);deque.addLast(key);return map.get(key);}return -1;}/*** 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。* 如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。** @param key   关键字* @param value 关键字对应的值*/public void put(int key, int value) {// 如果关键字 key 已经存在，则变更其数据值 valueif (map.containsKey(key)) {// 更新原有key在队列中的位置deque.remove(key);} else if (map.size() == capacity) { // key不存在且容量不充足// 找到最久未使用的关键字key移除Integer oldKey = deque.removeFirst();map.remove(oldKey);}// 入队deque.addLast(key);// 存在则更新，不存在则加入map.put(key, value);}
}
/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/

踩坑点

236. 二叉树的最近公共祖先

问题描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

• 树中节点数目在范围 [2, 105] 内。
• -109 <= Node.val <= 109
• 所有 Node.val 互不相同 。
• p != q
• p 和 q 均存在于给定的二叉树中。

解题思路与代码实现

解题思路:

解题思路是通过递归后序遍历二叉树，查找节点 p 和 q 的最近公共祖先。如果当前节点为 null 或者是 p 或 q 中的一个，直接返回当前节点。递归地在左右子树中查找 p 和 q，并根据返回结果判断：

• 如果左子树返回 null，右子树返回 null，则 p 和 q 不在当前树中，返回 null。
• 如果左子树返回非 null，右子树返回 null，则 p 和 q 都在左子树中，返回左子树的结果。
• 如果左子树返回 null，右子树返回非 null，则 p 和 q 都在右子树中，返回右子树的结果。
• 如果左右子树分别返回非 null，则当前节点即为 p 和 q 的最近公共祖先，返回当前节点。

class Solution {/*** 返回p、q在root树中的最近公共祖先*/public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 当root为null或者p、q之一为root时，返回rootif (root == null || root == p || root == q) {return root;}// 后序遍历TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if (left == null && right == null) { // p或q不在root树中return null;} else if (left == null) { // 在右子树中找到了p、qreturn right;} else if (right == null) { // 左子树中找到了p、qreturn left;} else { // p、q分别在左右子树中return root;}}
}

踩坑点

124. 二叉树中的最大路径和

问题描述

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

• 树中节点数目范围是 [1, 3 * 104]
• -1000 <= Node.val <= 1000

解题思路与代码实现

解题思路:

通过递归后序遍历二叉树来求解节点及其子树的最大路径和。

在递归过程中，空节点视为0，对于每个节点，计算其左右子树的最大路径和（如果为负数则视作0），然后更新全局变量 res，记录可能的最大路径和，最后返回以当前节点为根的子树中包含当前节点的最大路径和。

class Solution {private int res = Integer.MIN_VALUE; // 记录全局最大路径和/*** 返回以root为根节点的子树中的最大路径和* @param root 当前节点* @return 当前节点及其子树的最大路径和*/public int maxPathSum(TreeNode root) {postOrder(root); // 调用后序遍历函数return res; // 返回最大路径和}/*** 后序遍历递归函数，计算以当前节点为根的子树的最大路径和* @param root 当前节点* @return 当前节点及其子树的最大贡献值（即单侧最大路径和）*/private int postOrder(TreeNode root) {if (root == null) { // 如果当前节点为空，返回0return 0;}// 计算左右子树的最大贡献值，小于0的贡献值视为0int leftVal = Math.max(0, postOrder(root.left));int rightVal = Math.max(0, postOrder(root.right));// 更新全局最大路径和res = Math.max(res, leftVal + rightVal + root.val);// 返回当前节点及其子树的最大贡献值（单侧最大路径和）return root.val + Math.max(leftVal, rightVal);}
}

踩坑点

373. 查找和最小的 K 对数字

问题描述

给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。

示例 1:

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

示例 2:

输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

提示:

• 1 <= nums1.length, nums2.length <= 105
• -109 <= nums1[i], nums2[i] <= 109
• nums1 和 nums2 均为 升序排列
• 1 <= k <= 104
• k <= nums1.length * nums2.length

解题思路与代码实现

解题思路:

初始时将所有的 (i,0) 对入堆，这是因为 (i,0) 对应的数对是数组 nums1 的前 k 个元素与 nums2 的第一个元素的和，这些是最小的数对之一。

在每次从堆中取出数对 (i,j) 后，将 (i,j+1) 入堆。这是因为 (i,j+1) 对应的数对是数组 nums1[i] 和 nums2[j+1] 的和，可能成为下一个可能的最小数对。这样做可以保证堆中始终是当前可能的最小数对集合，确保了答案的正确性和最小性。

class Solution {/*** 返回两个数组 nums1 和 nums2 中前 k 个最小的数对* @param nums1 第一个数组* @param nums2 第二个数组* @param k 最小数对的个数* @return 前 k 个最小数对的列表*/public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {List<List<Integer>> ans = new ArrayList<>(k); // 预分配空间PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); // 小顶堆// 初始将所有 (i,0) 入堆，其中 i 为 0 到 nums1.length - 1for (int i = 0; i < Math.min(nums1.length, k); i++) {pq.add(new int[] { nums1[i] + nums2[0], i, 0 });}// 依次取出堆中最小的数对，加入结果列表，同时将其下一个数对 (i, j+1) 入堆while (ans.size() < k && !pq.isEmpty()) {int[] p = pq.poll(); // 取出当前最小的数对int i = p[1];int j = p[2];ans.add(List.of(nums1[i], nums2[j])); // 加入结果列表// 如果 nums2 中仍有下一个元素，将其与 nums1[i] 的和入堆if (j + 1 < nums2.length) {pq.add(new int[] { nums1[i] + nums2[j + 1], i, j + 1 });}}return ans; // 返回前 k 个最小数对的列表}
}

踩坑点

暴力枚举所有组合导致超时

530. 二叉搜索树的最小绝对差

问题描述

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

提示：

• 树中节点的数目范围是 [2, 104]
• 0 <= Node.val <= 105

解题思路与代码实现

解题思路:

二叉搜索树的性质，中序遍历的数组是升序排列的。

所以最小绝对值差必然在|根节点值-左子树最大值| 和|根节点值-右子树最小值|，在中序遍历数组中它们三者是相邻的。

public int getMinimumDifference(TreeNode root) {int res = Integer.MAX_VALUE; // 初始化最小绝对差为最大整数Integer pre = null; // 用于记录中序遍历时前一个节点的值// 非递归中序遍历二叉搜索树Stack<TreeNode> stack = new Stack<>(); // 辅助栈TreeNode cur = root;	// 辅助指针while (cur != null || !stack.isEmpty()) {if (cur != null) {stack.push(cur);cur = cur.left; // 往左子树遍历} else {TreeNode node = stack.pop(); // 弹出栈顶节点if (pre != null) {res = Math.min(res, Math.abs(pre - node.val)); // 更新最小绝对差}pre = node.val; // 更新前一个节点的值为当前节点的值cur = node.right; // 遍历右子树}}return res;}

踩坑点