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

public class Solution {
    /**
     * 将给定标题字符串中的单词首字母大写，并将其余字母转换为小写。
     * @param title 给定的标题字符串
     * @return 首字母大写的标题字符串
     */
    public String capitalizeTitle(String title) {
        StringBuilder ans = new StringBuilder(); // 用于构建结果的字符串
        for (String s : title.split(" ")) { // 按空格分割标题字符串，并遍历每个单词
            if (!ans.isEmpty()) { // 如果结果字符串非空，则在单词间添加空格
                ans.append(' ');
            }
            if (s.length() > 2) { // 如果单词长度大于 2
                ans.append(s.substring(0, 1).toUpperCase()); // 将单词首字母大写
                s = s.substring(1); // 去掉首字母
            }
            ans.append(s.toLowerCase()); // 将单词中剩余字母转换为小写，并添加到结果字符串中
        }
        return ans.toString(); // 返回首字母大写的标题字符串
    }
}

import java.util.HashSet;
import java.util.Set;
/**
 * FindElements 类用于在恢复的二叉树中搜索特定的元素。
 * 它采用了哈希表方法来实现高效的搜索。
 */
class FindElements {
    private final Set<Integer> s = new HashSet<>(); // 使用 HashSet 存储所有恢复的元素
    /**
     * 初始化 FindElements 对象，并根据给定的根节点恢复二叉树中的所有元素。
     * @param root 二叉树的根节点。
     */
    public FindElements(TreeNode root) {
        dfs(root, 0); // 从根节点开始深度优先遍历恢复元素
    }
    /**
     * 检查恢复的二叉树中是否存在指定的目标值。
     * @param target 目标值。
     * @return 如果目标值存在于恢复的二叉树中，则返回 true，否则返回 false。
     */
    public boolean find(int target) {
        return s.contains(target); // 检查 HashSet 中是否包含目标值
    }
    /**
     * 深度优先遍历二叉树，并恢复所有元素。
     * @param node 当前正在处理的节点。
     * @param val 当前节点的值。
     */
    private void dfs(TreeNode node, int val) {
        if (node == null) { // 如果当前节点为空，直接返回
            return;
        }
        s.add(val); // 将当前节点的值添加到 HashSet 中
        dfs(node.left, val * 2 + 1); // 递归遍历左子树
        dfs(node.right, val * 2 + 2); // 递归遍历右子树
    }
}

/**
 * FindElements 类用于在恢复的二叉树中搜索特定的元素。
 * 它采用了二进制路径方法来实现高效的搜索。
 */
class FindElements {
    private TreeNode root; // 二叉树的根节点
    /**
     * 初始化 FindElements 对象，并设置根节点。
     * @param root 二叉树的根节点。
     */
    public FindElements(TreeNode root) {
        this.root = root; // 设置根节点
    }
    /**
     * 搜索是否存在目标值。
     * @param target 目标值。
     * @return 如果目标值存在于恢复的二叉树中，则返回 true，否则返回 false。
     */
    public boolean find(int target) {
        target++; // 对目标值进行处理
        TreeNode cur = root; // 从根节点开始搜索
        // 从目标值的次高位开始向下搜索二进制路径
        for (int i = 30 - Integer.numberOfLeadingZeros(target); i >= 0; i--) {
            int bit = (target >> i) & 1; // 获取目标值在当前位的比特值
            cur = bit == 0 ? cur.left : cur.right; // 根据比特值选择左子节点或右子节点
            if (cur == null) { // 如果当前节点为空，表示目标值不在二叉树中
                return false;
            }
        }
        return true; // 没有遇到空节点，目标值存在于二叉树中
    }
}

public class Solution {
    /**
     * 将给定的二进制字符串转换为最大奇数的二进制字符串。
     * @param s 给定的二进制字符串
     * @return 最大奇数的二进制字符串
     */
    public String maximumOddBinaryNumber(String s) {
        // 统计字符串中 '1' 的个数
        int cnt1 = (int) s.chars().filter(c -> c == '1').count();
        
        // 构造最大奇数的二进制字符串
        // '1' 的个数减一后重复 '1'，然后加上剩余长度的 '0'，最后再加一个 '1'
        return "1".repeat(cnt1 - 1) + "0".repeat(s.length() - cnt1) + "1";
    }
}

class Solution {
    /**
     * 寻找数组中最大的子数组和。
     * @param nums 给定的整数数组
     * @return 最大的子数组和
     */
    public long maxArrayValue(int[] nums) {
        int n = nums.length; // 获取数组长度
        long sum = nums[n - 1]; // 将最后一个元素作为初始的子数组和
        // 从倒数第二个元素开始向前遍历数组
        for (int i = n - 2; i >= 0; i--) {
            // 如果当前元素与之前的子数组和相加后的结果比当前元素大，则更新子数组和为相加后的结果，
            // 否则更新子数组和为当前元素，表示从当前元素开始重新计算子数组和
            sum = nums[i] <= sum ? sum + nums[i] : nums[i];
        }
        return sum; // 返回最大的子数组和
    }
}

class Solution {
    /**
     * 计算卖出木材的最大收益。
     * @param m 木材的长度
     * @param n 木材的宽度
     * @param prices 二维数组，表示每个切割方案的价格
     * @return 最大收益
     */
    public long sellingWood(int m, int n, int[][] prices) {
        int[][] pr = new int[m + 1][n + 1]; // 创建一个二维数组存储每个切割方案的价格
        for (int[] p : prices) {
            pr[p[0]][p[1]] = p[2]; // 将给定的切割方案价格赋值到对应的位置
        }
        long[][] f = new long[m + 1][n + 1]; // 创建一个二维数组存储每个位置的最大收益
        for (int i = 1; i <= m; i++) { // 遍历木材的长度
            for (int j = 1; j <= n; j++) { // 遍历木材的宽度
                f[i][j] = pr[i][j]; // 初始情况下，收益就是切割方案的价格
                // 垂直切割：将木材垂直切割成两部分，找到使收益最大的切割方案
                for (int k = 1; k < j; k++) {
                    f[i][j] = Math.max(f[i][j], f[i][k] + f[i][j - k]);
                }
                // 水平切割：将木材水平切割成两部分，找到使收益最大的切割方案
                for (int k = 1; k < i; k++) {
                    f[i][j] = Math.max(f[i][j], f[k][j] + f[i - k][j]);
                }
            }
        }
        return f[m][n]; // 返回最大收益
    }
}

class Solution {
    /**
     * 计算卖出木材的最大收益（优化版）。
     * @param m 木材的长度
     * @param n 木材的宽度
     * @param prices 二维数组，表示每个切割方案的价格
     * @return 最大收益
     */
    public long sellingWood(int m, int n, int[][] prices) {
        long[][] f = new long[m + 1][n + 1]; // 创建一个二维数组存储每个位置的最大收益
        for (int[] p : prices) {
            f[p[0]][p[1]] = p[2]; // 将给定的切割方案价格赋值到对应的位置
        }
        for (int i = 1; i <= m; i++) { // 遍历木材的长度
            for (int j = 1; j <= n; j++) { // 遍历木材的宽度
                // 垂直切割：将木材垂直切割成两部分，找到使收益最大的切割方案
                for (int k = 1; k <= j / 2; k++) {
                    f[i][j] = Math.max(f[i][j], f[i][k] + f[i][j - k]);
                }
                // 水平切割：将木材水平切割成两部分，找到使收益最大的切割方案
                for (int k = 1; k <= i / 2; k++) {
                    f[i][j] = Math.max(f[i][j], f[k][j] + f[i - k][j]);
                }
            }
        }
        return f[m][n]; // 返回最大收益
    }
}

class Solution {
    private int ans; // 存储最大移动步数
    /**
     * 计算在给定网格中，从第一列的任一单元格出发，能够移动的最大步数。
     * @param grid 给定的二维网格
     * @return 最大移动步数
     */
    public int maxMoves(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            dfs(i, 0, grid); // 从第一列的任一单元格出发，进行深度优先搜索
        }
        return ans; // 返回最大移动步数
    }
    /**
     * 深度优先搜索函数，用于递归地搜索可以到达的最大步数。
     * @param i 当前单元格的行索引
     * @param j 当前单元格的列索引
     * @param grid 给定的二维网格
     */
    private void dfs(int i, int j, int[][] grid) {
        ans = Math.max(ans, j); // 更新最大移动步数
        if (ans == grid[0].length - 1) { // 如果已达到最大值，则无需继续搜索
            return;
        }
        // 向右上/右/右下走一步，探索下一步可行的移动方向
        for (int k = Math.max(i - 1, 0); k < Math.min(i + 2, grid.length); k++) {
            if (grid[k][j + 1] > grid[i][j]) { // 仅当下一步高度高于当前单元格时，才可以移动
                dfs(k, j + 1, grid); // 递归搜索下一步
            }
        }
        grid[i][j] = 0; // 标记当前单元格已经访问过
    }
}

import java.util.*;
class Solution {
    /**
     * 计算在给定网格中，从第一列的任一单元格出发，能够移动的最大步数。
     * @param grid 给定的二维网格
     * @return 最大移动步数
     */
    public int maxMoves(int[][] grid) {
        int m = grid.length; // 网格的行数
        int n = grid[0].length; // 网格的列数
        int[] vis = new int[m]; // 用于记录每一行最右边已访问到的列索引
        Arrays.fill(vis, -1); // 初始化为 -1，表示未访问
        List<Integer> q = new ArrayList<>(m); // 存储当前可移动的行索引
        for (int i = 0; i < m; i++) {
            q.add(i); // 初始化为所有行
        }
        for (int j = 0; j < n - 1; j++) { // 从第一列开始逐列进行搜索
            List<Integer> nxt = new ArrayList<>(); // 存储下一步可移动的行索引
            for (int i : q) { // 遍历当前可移动的行索引
                for (int k = Math.max(i - 1, 0); k < Math.min(i + 2, m); k++) { // 在当前行的上下范围内进行搜索
                    if (vis[k] != j && grid[k][j + 1] > grid[i][j]) { // 检查是否满足条件可以移动
                        vis[k] = j; // 更新第 k 行最右边访问到的列索引
                        nxt.add(k); // 将可移动的行索引添加到下一步可移动的列表中
                    }
                }
            }
            if (nxt.isEmpty()) { // 如果下一步没有可移动的行索引，说明无法再往右移动了，返回当前列索引
                return j;
            }
            q = nxt; // 更新当前可移动的行索引列表
        }
        return n - 1; // 如果遍历完所有列都有可移动的行索引，则返回最后一列的索引
    }
}

class Solution {
    /**
     * 计算在给定网格中，从第一列的任一单元格出发，能够移动的最大步数。
     * @param grid 给定的二维网格
     * @return 最大移动步数
     */
    public int maxMoves(int[][] grid) {
        int m = grid.length; // 网格行数
        int n = grid[0].length; // 网格列数
        
        // 使用负值作为入队标记，将第一列网格元素的值全部取相反数
        for (int[] row : grid) {
            row[0] *= -1; // 入队标记
        }
        
        // 从第一列开始进行遍历，判断是否可以继续向右移动
        for (int j = 0; j < n - 1; j++) {
            boolean ok = false; // 记录是否可以继续向右移动的标志
            for (int i = 0; i < m; i++) {
                if (grid[i][j] > 0) { // 如果当前单元格值大于 0，说明不在队列中，无需考虑
                    continue;
                }
                // 遍历当前单元格周围的相邻单元格
                for (int k = Math.max(i - 1, 0); k < Math.min(i + 2, m); k++) {
                    // 如果相邻单元格的值大于当前单元格的绝对值，说明可以移动到该相邻单元格
                    if (grid[k][j + 1] > -grid[i][j]) {
                        grid[k][j + 1] *= -1; // 入队标记，将相邻单元格的值取相反数
                        ok = true; // 设置标志为 true，表示可以继续向右移动
                    }
                }
            }
            // 如果无法继续向右移动，则返回当前已经遍历到的列索引
            if (!ok) {
                return j;
            }
        }
        // 如果遍历完所有列仍能继续向右移动，则返回最后一列的索引
        return n - 1;
    }
}

class Solution {
    int N = 20010, M = N * 2, idx = 0;
    int[] he = new int[N], e = new int[M], ne = new int[M];
    int[] f1 = new int[N], f2 = new int[N], g = new int[N], p = new int[N];
    // 添加边关系到邻接表
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
    }
    // 找出最小高度的树的根节点
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        Arrays.fill(he, -1);
        for (int[] e : edges) {
            int a = e[0], b = e[1];
            add(a, b);
            add(b, a);
        }
        dfs1(0, -1);
        dfs2(0, -1);
        List<Integer> ans = new ArrayList<>();
        int min = n;
        for (int i = 0; i < n; i++) {
            int cur = Math.max(f1[i], g[i]);
            if (cur < min) {
                min = cur;
                ans.clear();
                ans.add(i);
            } else if (cur == min) {
                ans.add(i);
            }
        }
        return ans;
    }
    // DFS计算每个节点到其它节点的最大距离
    int dfs1(int u, int fa) {
        for (int i = he[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == fa) continue;
            int sub = dfs1(j, u) + 1;
            if (sub > f1[u]) {
                f2[u] = f1[u];
                f1[u] = sub;
                p[u] = j;
            } else if (sub > f2[u]) {
                f2[u] = sub;
            }
        }
        return f1[u];
    }
    // DFS根据dfs1的结果计算每个节点的次大距离
    void dfs2(int u, int fa) {
        for (int i = he[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == fa) continue;
            if (p[u] != j) g[j] = Math.max(g[j], f1[u] + 1);
            else g[j] = Math.max(g[j], f2[u] + 1);
            g[j] = Math.max(g[j], g[u] + 1);
            dfs2(j, u);
        }
    }
}