【题解】—— LeetCode一周小结9

/**
 * 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 {
    int low, high;
    int ans;
    public int rangeSumBST(TreeNode root, int _low, int _high) {
        low = _low; high = _high;
        dfs(root);
        return ans;
    }
    void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        if (low <= root.val && root.val <= high) ans += root.val;
        dfs(root.right);
    }
}

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        int ans = 0;
        Deque<TreeNode> d = new ArrayDeque<>();
        while (root != null || !d.isEmpty()) {
            while (root != null) {
                d.addLast(root);
                root = root.left;
            }
            root = d.pollLast();
            if (low <= root.val && root.val <= high) {
                ans += root.val;
            }
            root = root.right;
        }
        return ans;
    }
}

class Solution {
    private final static int MX = (int) 1e5;
    private final static boolean[] np = new boolean[MX + 1]; // 质数=false 非质数=true
    // 预处理出所有质数
    static {
        np[1] = true;
        for (int i = 2; i * i <= MX; i++) {
            if (!np[i]) {
                for (int j = i * i; j <= MX; j += i) {
                    np[j] = true;
                }
            }
        }
    }
    /**
     * 计算从每个质数出发，经过不同路径到达非质数的路径总数。
     * @param n 树的节点数
     * @param edges 树的边集合
     * @return 路径总数
     */
    public long countPaths(int n, int[][] edges) {
        // 构建树的邻接表
        List<Integer>[] g = new ArrayList[n + 1];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (var e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x);
        }
        long ans = 0; // 结果路径总数
        int[] size = new int[n + 1]; // 保存每个连通块的节点数量
        var nodes = new ArrayList<Integer>(); // 保存当前连通块的节点集合
        // 遍历每个质数
        for (int x = 1; x <= n; x++) {
            if (np[x]) { // 跳过非质数
                continue;
            }
            int sum = 0; // 记录所有非质数的节点数量
            // 遍历与当前质数相连的节点
            for (int y : g[x]) {
                if (!np[y]) { // 只考虑非质数节点
                    if (size[y] == 0) { // 若当前连通块尚未计算过
                        nodes.clear(); // 清空节点集合
                        dfs(y, -1, g, nodes); // 从当前非质数节点出发，深度优先遍历连通块，并将节点添加到集合中
                        // 更新当前连通块中每个节点的连通块大小
                        for (int z : nodes) {
                            size[z] = nodes.size();
                        }
                    }
                    // 计算从当前质数节点出发，经过不同路径到达非质数节点的路径总数
                    ans += (long) size[y] * sum;
                    sum += size[y]; // 更新所有非质数的节点数量
                }
            }
            ans += sum; // 将从当前质数节点出发的路径总数加入结果中
        }
        return ans; // 返回路径总数
    }
    /**
     * 深度优先搜索函数，用于遍历树的连通块并保存节点。
     * @param x 当前处理的节点
     * @param fa 当前节点的父节点
     * @param g 树的邻接表表示
     * @param nodes 保存当前连通块的节点集合
     */
    private void dfs(int x, int fa, List<Integer>[] g, List<Integer> nodes) {
        nodes.add(x); // 将当前节点加入节点集合
        // 遍历当前节点的邻居节点
        for (int y : g[x]) {
            if (y != fa && np[y]) { // 跳过父节点和质数节点
                dfs(y, x, g, nodes); // 递归遍历当前节点的邻居节点
            }
        }
    }
}

class Solution {
    /**
     * 计算将二叉树中的每个非叶节点的两个子节点变为相同值所需的最小增量之和。
     * @param n 二叉树的节点数
     * @param cost 二叉树中每个节点的值
     * @return 最小增量之和
     */
    public int minIncrements(int n, int[] cost) {
        int ans = 0; // 初始化最小增量之和为0
        for (int i = n / 2; i > 0; i--) { // 从最后一个非叶节点开始向上计算
            // 计算将两个子节点变为相同值所需的增量，累加到结果中
            ans += Math.abs(cost[i * 2 - 1] - cost[i * 2]);
            // 将当前节点更新为其子节点中值较大的那个，以满足父节点的要求
            cost[i - 1] += Math.max(cost[i * 2 - 1], cost[i * 2]);
        }
        return ans; // 返回最小增量之和
    }
}

class Solution {
    private List<Integer>[] g; // 邻接表表示的图
    private Set<Long> s = new HashSet<>(); // 哈希表存储猜测的结果
    private int k, ans, cnt0; // k: 猜对的最小次数；ans: 可能的根节点个数；cnt0: 以根节点为0时的猜对次数
    /**
     * 计算以哪些节点为根时，满足猜对的最小次数的根节点个数。
     * @param edges 二维数组表示边的关系
     * @param guesses 二维数组表示猜测的结果
     * @param k 猜对的最小次数
     * @return 满足猜对的最小次数的根节点个数
     */
    public int rootCount(int[][] edges, int[][] guesses, int k) {
        this.k = k; // 初始化猜对的最小次数
        g = new ArrayList[edges.length + 1]; // 初始化邻接表
        Arrays.setAll(g, i -> new ArrayList<>()); // 初始化每个顶点的邻接表
        for (int[] e : edges) { // 建图
            int x = e[0];
            int y = e[1];
            g[x].add(y);
            g[y].add(x);
        }
        for (int[] e : guesses) { // 将猜测的结果转换成哈希表存储
            s.add((long) e[0] << 32 | e[1]); // 将两个 4 字节 int 压缩成一个 8 字节 long
        }
        dfs(0, -1); // 以0为根进行dfs
        reroot(0, -1, cnt0); // 以每个节点为根进行dfs
        return ans; // 返回结果
    }
    /**
     * 以根节点为0进行深度优先搜索，计算每个节点为根时猜对的次数。
     * @param x 当前处理的节点
     * @param fa 当前节点的父节点
     */
    private void dfs(int x, int fa) {
        for (int y : g[x]) { // 遍历当前节点的相邻节点
            if (y != fa) { // 如果相邻节点不是父节点
                if (s.contains((long) x << 32 | y)) { // 如果当前边是猜对的
                    cnt0++; // 增加以0为根时猜对的次数
                }
                dfs(y, x); // 递归处理相邻节点
            }
        }
    }
    /**
     * 以每个节点为根进行深度优先搜索，计算满足猜对次数的根节点个数。
     * @param x 当前处理的节点
     * @param fa 当前节点的父节点
     * @param cnt 以当前节点为根时猜对的次数
     */
    private void reroot(int x, int fa, int cnt) {
        if (cnt >= k) { // 如果以当前节点为根时猜对的次数大于等于要求的最小次数k
            ans++; // 增加满足条件的根节点个数
        }
        for (int y : g[x]) { // 遍历当前节点的相邻节点
            if (y != fa) { // 如果相邻节点不是父节点
                int c = cnt; // 记录以当前节点为根时猜对的次数
                if (s.contains((long) x << 32 | y)) c--; // 如果原来是对的，现在是错的
                if (s.contains((long) y << 32 | x)) c++; // 如果原来是错的，现在是对的
                reroot(y, x, c); // 递归处理相邻节点
            }
        }
    }
}

class Solution {
    /**
     * 判断数组是否可以分成若干连续子序列，每个子序列长度至少为3，且相邻元素之间的差值为1。
     * @param nums 给定的整数数组
     * @return 若数组可以分成若干连续子序列，返回true；否则，返回false
     */
    public boolean validPartition(int[] nums) {
        int n = nums.length; // 数组的长度
        boolean[] f = new boolean[n + 1]; // 动态规划数组，f[i]表示前i个元素是否可以构成连续子序列
        f[0] = true; // 初始条件，前0个元素肯定可以构成连续子序列
        for (int i = 1; i < n; i++) {
            if (f[i - 1] && nums[i] == nums[i - 1] || // 如果前i-1个元素可以构成连续子序列，并且当前元素与前一个元素相同
                i > 1 && f[i - 2] && (nums[i] == nums[i - 1] && nums[i] == nums[i - 2] || // 或者前i-2个元素可以构成连续子序列，并且当前元素与前一个元素相同，并且当前元素与前两个元素相同
                                      nums[i] == nums[i - 1] + 1 && nums[i] == nums[i - 2] + 2)) { // 或者当前元素与前一个元素相差1，与前两个元素相差2
                f[i + 1] = true; // 则前i个元素可以构成连续子序列
            }
        }
        return f[n]; // 返回前n个元素是否可以构成连续子序列
    }
}

class Solution {
    /**
     * 计算在移除若干受限制的边之后，从节点 0 开始可以到达的节点数。
     * @param n 图中节点的数量
     * @param edges 图中的边
     * @param restricted 受限制的节点数组
     * @return 从节点 0 开始可以到达的节点数
     */
    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        // 将受限制的节点转换成一个布尔数组，方便进行判断
        boolean[] isRestricted = new boolean[n];
        for (int x : restricted) {
            isRestricted[x] = true;
        }
        // 构建图的邻接表表示
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        // 遍历所有边，如果两个节点都不受限制，则在邻接表中添加边
        for (int[] e : edges) {
            int x = e[0], y = e[1];
            if (!isRestricted[x] && !isRestricted[y]) {
                g[x].add(y);
                g[y].add(x);
            }
        }
        // 进行深度优先搜索，计算可以到达的节点数
        return dfs(0, -1, g);
    }
    /**
     * 深度优先搜索函数，计算以节点 x 为起点可以到达的节点数。
     * @param x 当前处理的节点
     * @param fa x 的父节点
     * @param g 图的邻接表表示
     * @return 以节点 x 为起点可以到达的节点数
     */
    private int dfs(int x, int fa, List<Integer>[] g) {
        int cnt = 1; // 从节点 x 出发，可以到达它自己
        for (int y : g[x]) { // 遍历节点 x 的所有邻居节点
            if (y != fa) { // 避免回到父节点，防止形成环
                cnt += dfs(y, x, g); // 递归计算从邻居节点 y 出发可以到达的节点数
            }
        }
        return cnt; // 返回以节点 x 为起点可以到达的节点数
    }
}

import java.util.LinkedList;
import java.util.Queue;
class MyStack {
    Queue<Integer> queue1; // 主队列，用于存储栈中的元素
    Queue<Integer> queue2; // 辅助队列，用于辅助元素入栈操作
    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<Integer>(); // 初始化主队列
        queue2 = new LinkedList<Integer>(); // 初始化辅助队列
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue2.offer(x); // 将新元素入辅助队列
        // 将主队列中的所有元素依次出队并入辅助队列，确保新元素位于队列头部
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        // 交换主队列和辅助队列，确保主队列始终为非空队列
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue1.poll(); // 从主队列中出队即可
    }
    
    /** Get the top element. */
    public int top() {
        return queue1.peek(); // 返回主队列的队首元素，即栈顶元素
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty(); // 判断主队列是否为空即可
    }
}

import java.util.LinkedList;
import java.util.Queue;
class MyStack {
    Queue<Integer> queue; // 使用队列实现栈
    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<Integer>(); // 初始化队列
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        int n = queue.size(); // 获取当前队列的大小
        queue.offer(x); // 将元素入队
        // 将之前的元素逐个出队再入队，使得新入队的元素位于队首，实现栈的特性
        for (int i = 0; i < n; i++) {
            queue.offer(queue.poll());
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll(); // 直接出队即可
    }
    
    /** Get the top element. */
    public int top() {
        return queue.peek(); // 获取队首元素，即栈顶元素
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty(); // 判断队列是否为空
    }
}