力扣第 454 场周赛

给你一个字符串 caption，表示一个视频的标题。

需要按照以下步骤 按顺序 生成一个视频的 有效标签 ：

1. 将 所有单词 组合为单个 驼峰命名字符串 ，并在前面加上 '#'。驼峰命名字符串 指的是除第一个单词外，其余单词的首字母大写，且每个单词的首字母之后的字符必须是小写。

2. 移除 所有不是英文字母的字符，但 保留 第一个字符 '#'。

3. 将结果 截断 为最多 100 个字符。

对 caption 执行上述操作后，返回生成的 标签 。

示例 1：

示例 2：

示例 3：

提示：

• 1 <= caption.length <= 150
• caption 仅由英文字母和 ' ' 组成。

思路：

把 caption 按照空格，分割成若干个单词。
把每个单词的字母全部小写。
把除了第一个单词以外的单词，首字母大写。
在单词列表前面加个井号。
把单词列表 连接起来，得到答案。
如果答案长度超过 100，截断，只保留前 100 个字符

答：

class Solution {
    public String generateTag(String caption) {
        StringBuilder ans = new StringBuilder();
        ans.append('#');
        for (String s : caption.trim().split("\\s+")) { // 用一个或多个空格分隔 caption
            if (ans.length() == 1) { // s 是第一个单词
                s = s.toLowerCase();
            } else {
                s = s.substring(0, 1).toUpperCase() + s.substring(1).toLowerCase();
            }
            ans.append(s);
            if (ans.length() >= 100) {
                ans.setLength(100);
                break;
            }
        }
        return ans.toString();
    }
}

3583. 统计特殊三元组

给你一个整数数组 nums。

特殊三元组 定义为满足以下条件的下标三元组 (i, j, k)：

• 0 <= i < j < k < n，其中 n = nums.length
• nums[i] == nums[j] * 2
• nums[k] == nums[j] * 2

返回数组中 特殊三元组 的总数。

由于答案可能非常大，请返回结果对 10^9 + 7 取余数后的值。

示例 1：

输入： nums = [6,3,6]

输出： 1

解释：

唯一的特殊三元组是 (i, j, k) = (0, 1, 2)，其中：

• nums[0] = 6, nums[1] = 3, nums[2] = 6
• nums[0] = nums[1] * 2 = 3 * 2 = 6
• nums[2] = nums[1] * 2 = 3 * 2 = 6

示例 2：

输入： nums = [0,1,0,0]

输出： 1

解释：

唯一的特殊三元组是 (i, j, k) = (0, 2, 3)，其中：

• nums[0] = 0, nums[2] = 0, nums[3] = 0
• nums[0] = nums[2] * 2 = 0 * 2 = 0
• nums[3] = nums[2] * 2 = 0 * 2 = 0

示例 3：

输入： nums = [8,4,2,8,4]

输出： 2

解释：

共有两个特殊三元组：

• (i, j, k) = (0, 1, 3)
  • nums[0] = 8, nums[1] = 4, nums[3] = 8
  • nums[0] = nums[1] * 2 = 4 * 2 = 8
  • nums[3] = nums[1] * 2 = 4 * 2 = 8
• (i, j, k) = (1, 2, 4)
  • nums[1] = 4, nums[2] = 2, nums[4] = 4
  • nums[1] = nums[2] * 2 = 2 * 2 = 4
  • nums[4] = nums[2] * 2 = 2 * 2 = 4

提示：

• 3 <= n == nums.length <= 10^5
• 0 <= nums[i] <= 10^5

思路：

• 枚举中间下标 j；

• 使用两个哈希表：

  • leftCount：存储 j 左边某个数出现了多少次；

  • rightCount：存储 j 右边某个数出现了多少次；

• 对于每个中间值 nums[j]，我们找：

  • 有多少个 i < j 满足 nums[i] == nums[j] * 2

  • 有多少个 k > j 满足 nums[k] == nums[j] * 2

• 两者相乘就是以当前 j 为中间值的合法三元组数量。

答：

public class SpecialTriplets {
    public static int countSpecialTriplets(int[] nums) {
        int n = nums.length;
        int MOD = 1_000_000_007;
        long result = 0;

        // 用来记录从右边开始遍历时，某个值的出现次数
        Map<Integer, Integer> rightCount = new HashMap<>();

        // 初始化：统计所有数出现的次数
        for (int i = 0; i < n; i++) {
            rightCount.put(nums[i], rightCount.getOrDefault(nums[i], 0) + 1);
        }

        // 左侧计数器
        Map<Integer, Integer> leftCount = new HashMap<>();

        for (int j = 0; j < n; j++) {
            int mid = nums[j];
            rightCount.put(mid, rightCount.get(mid) - 1); // j 不能作为右侧计数

            int doubleVal = mid * 2;

            long left = leftCount.getOrDefault(doubleVal, 0);   // i 的个数（左边）
            long right = rightCount.getOrDefault(doubleVal, 0); // k 的个数（右边）

            result = (result + (left * right) % MOD) % MOD;

            // 把当前值加入左侧计数
            leftCount.put(mid, leftCount.getOrDefault(mid, 0) + 1);
        }

        return (int) result;
    }
}

3584. 子序列首尾元素的最大乘积

给你一个整数数组 nums 和一个整数 m。

返回任意大小为 m 的 子序列 中首尾元素乘积的最大值。

子序列 是可以通过删除原数组中的一些元素（或不删除任何元素），且不改变剩余元素顺序而得到的数组。

示例 1：

输入： nums = [-1,-9,2,3,-2,-3,1], m = 1

输出： 81

解释：

子序列 [-9] 的首尾元素乘积最大：-9 * -9 = 81。因此，答案是 81。

示例 2：

输入： nums = [1,3,-5,5,6,-4], m = 3

输出： 20

解释：

子序列 [-5, 6, -4] 的首尾元素乘积最大。

示例 3：

输入： nums = [2,-1,2,-6,5,2,-5,7], m = 2

输出： 35

解释：

子序列 [5, 7] 的首尾元素乘积最大。

提示:

• 1 <= nums.length <= 10^5
• -10^5 <= nums[i] <= 10^5
• 1 <= m <= nums.length

思路：

题目意思是首尾元素下标相差至少是 m−1，这样子序列长度才能是 m（否则长度就小于 m 了）。

我们只需关注首尾两个数，于是问题转化成：

nums 的任意下标相差至少为 m−1 的两数之积的最大值。
枚举 nums[i]，为了让乘积最大，贪心地，维护 [0,i−m+1] 中的最小值和最大值。维护最小值是因为负负得正，答案可以来自两个负数相乘。

注意最终答案可能是负数，要把答案初始化成 −∞。

答：

class Solution {
    public long maximumProduct(int[] nums, int m) {
        long ans = Long.MIN_VALUE;
        int mn = Integer.MAX_VALUE;
        int mx = Integer.MIN_VALUE;
        for (int i = m - 1; i < nums.length; i++) {
            // 维护左边 [0,i-m+1] 中的最小值和最大值
            int y = nums[i - m + 1];
            mn = Math.min(mn, y);
            mx = Math.max(mx, y);
            // 枚举右
            long x = nums[i];
            ans = Math.max(ans, Math.max(x * mn, x * mx));
        }
        return ans;
    }
}

3585. 树中找到带权中位节点

给你一个整数 n，以及一棵 无向带权 树，根节点为节点 0，树中共有 n 个节点，编号从 0 到 n - 1。该树由一个长度为 n - 1 的二维数组 edges 表示，其中 edges[i] = [ui, vi, wi] 表示存在一条从节点 ui 到 vi 的边，权重为 wi。

带权中位节点 定义为从 ui 到 vi 路径上的 第一个 节点 x，使得从 ui 到 x 的边权之和 大于等于 该路径总权值和的一半。

给你一个二维整数数组 queries。对于每个 queries[j] = [uj, vj]，求出从 uj 到 vj 路径上的带权中位节点。

返回一个数组 ans，其中 ans[j] 表示查询 queries[j] 的带权中位节点编号。

示例 1：

输入： n = 2, edges = [[0,1,7]], queries = [[1,0],[0,1]]

输出： [0,1]

解释：

查询	路径	边权	总路径权值和	一半	解释	答案
[1, 0]	1 → 0	[7]	7	3.5	从 1 → 0 的权重和为 7 >= 3.5，中位节点是 0。	0
[0, 1]	0 → 1	[7]	7	3.5	从 0 → 1 的权重和为 7 >= 3.5，中位节点是 1。	1

示例 2：

输入： n = 3, edges = [[0,1,2],[2,0,4]], queries = [[0,1],[2,0],[1,2]]

输出： [1,0,2]

解释：

查询	路径	边权	总路径权值和	一半	解释	答案
[0, 1]	0 → 1	[2]	2	1	从 0 → 1 的权值和为 2 >= 1，中位节点是 1。	1
[2, 0]	2 → 0	[4]	4	2	从 2 → 0 的权值和为 4 >= 2，中位节点是 0。	0
[1, 2]	1 → 0 → 2	[2, 4]	6	3	从 1 → 0 = 2 < 3， 从 1 → 2 = 6 >= 3，中位节点是 2。	2

示例 3：

输入： n = 5, edges = [[0,1,2],[0,2,5],[1,3,1],[2,4,3]], queries = [[3,4],[1,2]]

输出： [2,2]

解释：

查询	路径	边权	总路径权值和	一半	解释	答案
[3, 4]	3 → 1 → 0 → 2 → 4	[1, 2, 5, 3]	11	5.5	从 3 → 1 = 1 < 5.5， 从 3 → 0 = 3 < 5.5， 从 3 → 2 = 8 >= 5.5，中位节点是 2。	2
[1, 2]	1 → 0 → 2	[2, 5]	7	3.5	从 1 → 0 = 2 < 3.5， 从 1 → 2 = 7 >= 3.5，中位节点是 2。	2

提示:

• 2 <= n <= 10^5
• edges.length == n - 1
• edges[i] == [ui, vi, wi]
• 0 <= ui, vi < n
• 1 <= wi <= 10^9
• 1 <= queries.length <= 10^5
• queries[j] == [uj, vj]
• 0 <= uj, vj < n
• 输入保证 edges 表示一棵合法的树。

思路：参考灵神的题解-

定义：

1.询问中的两个节点分别为 x 和 y。
2.lca 为 x 和 y 的最近公共祖先。
3.disXY 为 x 到 y 的距离。
4.half 为 disXY 的至少一半，即 ⌈ disXY/2 ⌉。
分类讨论：

如果 x 到 lca 的距离 ≥half，那么答案在 x 到 lca 的路径中，我们需要计算从 x 往上跳至少 half 的节点。
否则，那么答案在 y 到 lca 的路径中，我们需要计算从 y 往上跳至多 disXY−half 的节点，就是从 x 出发，距离 x 至少 half 的节点。
至少 half 可以转化成往上跳至多 half−1 到达的最远节点，从这个节点再往上跳一步，就是至少 half 的最近节点。

现在，两种情况统一为：

从 x 出发，往上跳至多 d，所能到达的最远节点。这和 LCA 模板中的 uptoDep 函数类似：

1.枚举 i=mx−1,mx−2,…,0。
2.设 p 为 x 的 2^i级祖先。
3.如果 x 到 p 的距离 ≤d，那么可以跳到 p，更新 x 为 p。
4.继续枚举下一个 i。
5.最终返回跳到的节点。

答：

class LcaBinaryLifting {
    private final int[] depth;
    public final long[] dis; // 如果是无权树（边权为 1），dis 可以去掉，用 depth 代替
    public final int[][] pa;

    public LcaBinaryLifting(int[][] edges) {
        int n = edges.length + 1;
        int m = 32 - Integer.numberOfLeadingZeros(n); // n 的二进制长度
        List<int[]>[] g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0], y = e[1], w = e[2];
            g[x].add(new int[]{y, w});
            g[y].add(new int[]{x, w});
        }

        depth = new int[n];
        dis = new long[n];
        pa = new int[n][m];

        dfs(g, 0, -1);

        for (int i = 0; i < m - 1; i++) {
            for (int x = 0; x < n; x++) {
                int p = pa[x][i];
                pa[x][i + 1] = p < 0 ? -1 : pa[p][i];
            }
        }
    }

    private void dfs(List<int[]>[] g, int x, int fa) {
        pa[x][0] = fa;
        for (int[] e : g[x]) {
            int y = e[0];
            if (y != fa) {
                depth[y] = depth[x] + 1;
                dis[y] = dis[x] + e[1];
                dfs(g, y, x);
            }
        }
    }

    public int getKthAncestor(int node, int k) {
        for (; k > 0; k &= k - 1) {
            node = pa[node][Integer.numberOfTrailingZeros(k)];
        }
        return node;
    }

    // 返回 x 和 y 的最近公共祖先（节点编号从 0 开始）
    public int getLCA(int x, int y) {
        if (depth[x] > depth[y]) {
            int tmp = y;
            y = x;
            x = tmp;
        }
        // 使 y 和 x 在同一深度
        y = getKthAncestor(y, depth[y] - depth[x]);
        if (y == x) {
            return x;
        }
        for (int i = pa[x].length - 1; i >= 0; i--) {
            int px = pa[x][i], py = pa[y][i];
            if (px != py) {
                x = px;
                y = py; // 同时往上跳 2^i 步
            }
        }
        return pa[x][0];
    }

    // 返回 x 到 y 的距离（最短路长度）
    public long getDis(int x, int y) {
        return dis[x] + dis[y] - dis[getLCA(x, y)] * 2;
    }

    // 从 x 往上跳【至多】d 距离，返回最远能到达的节点
    public int uptoDis(int x, long d) {
        long dx = dis[x];
        for (int i = pa[x].length - 1; i >= 0; i--) {
            int p = pa[x][i];
            if (p != -1 && dx - dis[p] <= d) { // 可以跳至多 d
                x = p;
            }
        }
        return x;
    }
}

class Solution {
    public int[] findMedian(int n, int[][] edges, int[][] queries) {
        LcaBinaryLifting g = new LcaBinaryLifting(edges);

        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int x = queries[i][0];
            int y = queries[i][1];
            if (x == y) {
                ans[i] = x;
                continue;
            }
            int lca = g.getLCA(x, y);
            long disXY = g.dis[x] + g.dis[y] - g.dis[lca] * 2;
            long half = (disXY + 1) / 2;
            if (g.dis[x] - g.dis[lca] >= half) { // 答案在 x-lca 路径中
                // 先往上跳至多 half-1，然后再跳一步，就是至少 half
                int to = g.uptoDis(x, half - 1);
                ans[i] = g.pa[to][0];
            } else { // 答案在 y-lca 路径中
                // 从 y 出发至多 dis_xy-half，就是从 x 出发至少 half
                ans[i] = g.uptoDis(y, disXY - half);
            }
        }
        return ans;
    }
}