刷题日记 - 10

class LRUCache {

    // 定义一个HashMap来存储键值对，键是Integer类型，值是双向链表节点BiNode
    HashMap<Integer, BiNode> map;
    // 定义头节点head和尾节点tail，指向链表的头和尾
    BiNode head, tail;
    // 当前缓存的节点数量
    int count;
    // 缓存的容量
    int capacity;

    // 构造函数，初始化缓存的容量和内部数据结构
    public LRUCache(int capacity) {
        map = new HashMap<>();
        count = 0;
        this.capacity = capacity;
        // 初始化头节点和尾节点，头节点和尾节点不存储实际数据
        head = new BiNode(-1, -1);
        tail = new BiNode(-1, -1);
        // 头尾相连，形成一个空的双向链表
        head.right = tail;
        tail.left = head;
    }
    
    // get方法，获取指定key对应的值
    public int get(int key) {
        int res = -1;
        // 如果map中包含key
        if (map.containsKey(key)) {
            BiNode node = map.get(key); // 获取该节点
            res = node.val; // 获取节点的值
            moveToFront(node); // 将该节点移动到链表的头部，表示最近使用
        }
        return res;
    }
    
    // put方法，插入或更新一个key-value对
    public void put(int key, int value) {
        BiNode node = null;
        // 如果map中已经包含该key
        if (map.containsKey(key)) {
            node = map.get(key); // 获取节点
            node.val = value; // 更新节点的值
            moveToFront(node); // 将节点移动到链表的头部
        } else {
            count++;
            // 如果当前缓存容量超过了设定容量
            if (count > capacity) {
                removeLastNode(); // 移除链表尾部节点，即最久未使用的节点
                count--;
            }
            // 新建一个节点
            node = new BiNode(key, value);
            map.put(key, node); // 将节点添加到map中
            // 将节点插入到头部
            node.left = head;
            node.right = head.right;
            head.right.left = node;
            head.right = node;
        }
    }

    // 将已有的节点移动到链表的头部
    private void moveToFront(BiNode node) {
        if (node.left != head) {
            // 从链表中取出节点
            node.left.right = node.right;
            node.right.left = node.left;
            // 将节点插入到链表头部
            node.right = head.right;
            head.right.left = node;
            head.right = node;
            node.left = head;
        }
    }

    // 移除链表尾部节点，即最久未使用的节点
    private void removeLastNode() {
        int key = tail.left.key;
        tail.left.left.right = tail;
        tail.left = tail.left.left;
        map.remove(key); // 从map中删除该节点
    }
}

// 定义双向链表节点类
class BiNode {
    int key;
    int val;
    BiNode left;
    BiNode right;

    // 构造函数，初始化节点的key和val
    public BiNode(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

class Solution {

    // 主函数：排序链表
    public ListNode sortList(ListNode head) {
        // 如果链表为空，直接返回null
        if (head == null) return null;
        // 调用归并排序函数，传入头节点和尾节点
        return merge(head, null);
    }

    // 归并排序函数
    private ListNode merge(ListNode head, ListNode tail) {
        // 当头节点的下一个节点就是tail时，直接返回头节点，并将头节点的next置为null（这样不会丢失节点，因为递归的时候mid在左边做了一回tail节点，但是在右边不会作为tail节点）
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        // 快慢指针找到链表中点
        ListNode slow = head, fast = head;
        while (fast != tail) {
            fast = fast.next;
            slow = slow.next;
            if (fast == tail) break;
            fast = fast.next;
        }
        ListNode mid = slow; // slow指针即为链表中点
        // 递归地对左右两部分进行排序
        ListNode node1 = merge(head, mid);
        ListNode node2 = merge(mid, tail);
        // 合并已排序的两个子链表
        return mergeSortedList(node1, node2);
    }

    // 合并两个有序链表
    private ListNode mergeSortedList(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(-1); 
        ListNode t = dummy, p = head1, q = head2;
        while (p != null && q != null) {
            if (p.val <= q.val) {
                t.next = p;
                p = p.next;
                t = t.next;
            } else {
                t.next = q;
                q = q.next;
                t = t.next;
            }
        }
        t.next = (p == null) ? q : p;
        return dummy.next;
    }
}

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return dfs(p,q);
    }

    private boolean dfs(TreeNode p,TreeNode q){
        if(p==null&&q==null){
            return true;
        }else if((q!=null&&p!=null)&&q.val==p.val){
            return true && dfs(p.left,q.left) && dfs(p.right,q.right);
        }
        return false;
    }
}

class Solution {
    public Node connect(Node root) {
        // 如果树为空，直接返回null ⭐ 一定要处理这个特殊情况，不然会死循环。
        if (root == null) return null;

        // 使用队列进行层次遍历
        LinkedList<Node> queue = new LinkedList<>();
        queue.offerLast(root); // 将根节点加入队列
        queue.offerLast(null); // 使用null作为每一层的结束标志

        Node last = null; // 上一个处理的节点，用于连接next指针

        while (true) {
            Node cur = queue.pollFirst(); // 取出队首节点
            if (last != null) {
                last.next = cur; // 将上一个节点的next指向当前节点
            }
            last = cur; // 更新last为当前节点

            if (cur != null) {
                // 如果当前节点有左子节点，将其加入队列
                if (cur.left != null) queue.addLast(cur.left);
                // 如果当前节点有右子节点，将其加入队列
                if (cur.right != null) queue.addLast(cur.right);
            } else {
                // 如果当前节点为null，表示当前层结束
                if (queue.isEmpty()) break; // 如果队列空了，说明遍历完成
                queue.addLast(null); // 继续标记下一层的结束
            }
        }
        return root; // 返回根节点
    }
}

class Solution {
    public void flatten(TreeNode root) {
        // 如果根节点为空，直接返回
        if (root == null) return;

        // 定义指针p，指向当前节点
        TreeNode p = root;
        TreeNode q = null;  // q用来找到左子树的最右节点

        // 遍历树(右孩子)，直到所有节点都处理完
        while (p != null) {
            // 如果当前节点有左子树
            if (p.left != null) {
                // 找到左子树的最右节点
                q = p.left;
                while (q.right != null) {
                    q = q.right;
                }
                // 将当前节点的右子树接到左子树的最右节点的右孩子上
                q.right = p.right;

                // 将当前节点的左子树移到右子树位置
                p.right = p.left;

                // 将当前节点的左子树置空
                p.left = null;
            }
            // 继续处理右子树
            p = p.right;
        }
    }
}

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // 如果根节点为空，直接返回false，因为没有路径
        if (root == null) return false;
        
        // 使用深度优先搜索（DFS）来查找是否存在满足条件的路径
        return dfs(root, targetSum, 0);
    }

    // 深度优先搜索方法
    private boolean dfs(TreeNode node, int targetSum, int sum) {
        // 当前节点的值累加到sum中
        sum += node.val;
        
        // 如果当前节点是叶子节点，并且累加和等于目标和，则返回true
        if (node.left == null && node.right == null && sum == targetSum) return true;
        
        // 如果有左子节点但没有右子节点，递归搜索左子树
        if (node.left != null && node.right == null) return dfs(node.left, targetSum, sum);
        
        // 如果有右子节点但没有左子节点，递归搜索右子树
        if (node.left == null && node.right != null) return dfs(node.right, targetSum, sum);
        
        // 如果同时有左子节点和右子节点，递归搜索左子树和右子树，只要有一个满足条件即返回true
        if (node.left != null && node.right != null) return dfs(node.left, targetSum, sum) || dfs(node.right, targetSum, sum);
        
        // 如果以上条件都不满足，返回false（通常不会执行到这里）
        return false;
    }
}

class Solution {
    // 用于存储从根到叶子节点路径所代表的所有数字
    List<Integer> array = new ArrayList<>();

    public int sumNumbers(TreeNode root) {
        // 使用深度优先搜索遍历树，并计算路径代表的数字
        dfs(root, 0);
        
        int res = 0;
        // 将所有路径表示的数字相加，得到最终结果
        for (int i = 0; i < array.size(); i++) {
            res += array.get(i);
        }
        
        return res;
    }

    // 深度优先搜索方法，用于计算路径代表的数字
    private void dfs(TreeNode node, int sum) {
        // 当前节点的值加入到路径数字中
        sum = sum * 10 + node.val;

        // 如果当前节点是叶子节点，将路径数字加入数组
        if (node.left == null && node.right == null) array.add(sum);

        // 如果有左子节点但没有右子节点，递归搜索左子树
        if (node.left != null && node.right == null) dfs(node.left, sum);

        // 如果有右子节点但没有左子节点，递归搜索右子树
        if (node.left == null && node.right != null) dfs(node.right, sum);

        // 如果同时有左子节点和右子节点，递归搜索左右子树
        if (node.left != null && node.right != null) {
            dfs(node.left, sum);
            dfs(node.right, sum);
        }
    }
}

class Solution {

    // 用于记录路径和的最大值，初始值为最小的整数
    int res = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        // 调用深度优先搜索计算路径和
        dfs(root);
        // 返回路径和的最大值
        return res;
    }

    // 该dfs方法返回能给父节点提供的最长路径（一条线不拐弯，从底向上）
    private int dfs(TreeNode node){
        // 如果当前节点为空，返回0
        if (node == null) return 0;

        int l = 0, r = 0;

        // 递归计算左子树所能提供的最长路径值
        if (node.left != null) l = dfs(node.left);

        // 递归计算右子树所能提供的最长路径值
        if (node.right != null) r = dfs(node.right);

        // 以当前节点拐弯的最长路径值
        int takeCurNodeRootLPS = l + r + node.val;

        // 更新最终答案
        res = Math.max(takeCurNodeRootLPS, res);

        // 计算单条路径最大值，这是要提供给当前节点的父节点的
        int oneLargestPath = Math.max(l, r) + node.val;

        // 如果能提供给父节点的最大路径是负数，那么直接返回0让父节点舍弃自己即可
        return oneLargestPath > 0 ? oneLargestPath : 0;
    }
}