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 已经存在，则变更其数据值 value
        if (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时，返回root
        if (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、q
            return right;
        } else if (right == null) { // 左子树中找到了p、q
            return 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) { // 如果当前节点为空，返回0
            return 0;
        }
        // 计算左右子树的最大贡献值，小于0的贡献值视为0
        int 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 - 1
        for (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;
    }

踩坑点