做地坪网站,wordpress php那个版本号,做网站是用源码还是模版,深圳品牌做网站公司哪家好3582. 为视频标题生成标签 给你一个字符串 caption#xff0c;表示一个视频的标题。 需要按照以下步骤 按顺序 生成一个视频的 有效标签 #xff1a; 将 所有单词 组合为单个 驼峰命名字符串 #xff0c;并在前面加上 #。驼峰命名字符串 指的是除第一个单词外#xff0c;其… 3582. 为视频标题生成标签 给你一个字符串 caption表示一个视频的标题。 需要按照以下步骤 按顺序 生成一个视频的 有效标签 将 所有单词 组合为单个 驼峰命名字符串 并在前面加上 #。驼峰命名字符串 指的是除第一个单词外其余单词的首字母大写且每个单词的首字母之后的字符必须是小写。 移除 所有不是英文字母的字符但 保留 第一个字符 #。 将结果 截断 为最多 100 个字符。 对 caption 执行上述操作后返回生成的 标签 。 示例 1 输入 caption Leetcode daily streak achieved 输出 #leetcodeDailyStreakAchieved 解释 除了 leetcode 以外的所有单词的首字母需要大写。 示例 2 输入 caption can I Go There 输出 #canIGoThere 解释 除了 can 以外的所有单词的首字母需要大写。 示例 3 输入 caption hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh 输出 #hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh 解释 由于第一个单词长度为 101因此需要从单词末尾截去最后两个字符。 提示 1 caption.length 150caption 仅由英文字母和 组成。 思路 把 caption 按照空格分割成若干个单词。 把每个单词的字母全部小写。 把除了第一个单词以外的单词首字母大写。 在单词列表前面加个井号。 把单词列表 连接起来得到答案。 如果答案长度超过 100截断只保留前 100 个字符 答 class Solution {public String generateTag(String caption) {StringBuilder ans new StringBuilder();ans.append(#);for (String s : caption.trim().split(\\s)) { // 用一个或多个空格分隔 captionif (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.lengthnums[i] nums[j] * 2nums[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] 6nums[0] nums[1] * 2 3 * 2 6nums[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] 0nums[0] nums[2] * 2 0 * 2 0nums[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] 8nums[0] nums[1] * 2 4 * 2 8nums[3] nums[1] * 2 4 * 2 8 (i, j, k) (1, 2, 4) nums[1] 4, nums[2] 2, nums[4] 4nums[1] nums[2] * 2 2 * 2 4nums[4] nums[2] * 2 2 * 2 4 提示 3 n nums.length 10^50 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;// 用来记录从右边开始遍历时某个值的出现次数MapInteger, Integer rightCount new HashMap();// 初始化统计所有数出现的次数for (int i 0; i n; i) {rightCount.put(nums[i], rightCount.getOrDefault(nums[i], 0) 1);}// 左侧计数器MapInteger, 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^51 m nums.length 思路 题目意思是首尾元素下标相差至少是 m−1这样子序列长度才能是 m否则长度就小于 m 了。 我们只需关注首尾两个数于是问题转化成 nums 的任意下标相差至少为 m−1 的两数之积的最大值。 枚举 nums[i]为了让乘积最大贪心地维护 [0,i−m1] 中的最小值和最大值。维护最小值是因为负负得正答案可以来自两个负数相乘。 注意最终答案可能是负数要把答案初始化成 −∞。 答 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-m1] 中的最小值和最大值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]73.5从 1 → 0 的权重和为 7 3.5中位节点是 0。0[0, 1]0 → 1[7]73.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]21从 0 → 1 的权值和为 2 1中位节点是 1。1[2, 0]2 → 0[4]42从 2 → 0 的权值和为 4 2中位节点是 0。0[1, 2]1 → 0 → 2[2, 4]63从 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]115.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]73.5从 1 → 0 2 3.5 从 1 → 2 7 3.5中位节点是 2。2 提示: 2 n 10^5edges.length n - 1edges[i] [ui, vi, wi]0 ui, vi n1 wi 10^91 queries.length 10^5queries[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.枚举 imx−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; // 如果是无权树边权为 1dis 可以去掉用 depth 代替public final int[][] pa;public LcaBinaryLifting(int[][] edges) {int n edges.length 1;int m 32 - Integer.numberOfLeadingZeros(n); // n 的二进制长度Listint[][] 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(Listint[][] 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) { // 可以跳至多 dx 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然后再跳一步就是至少 halfint to g.uptoDis(x, half - 1);ans[i] g.pa[to][0];} else { // 答案在 y-lca 路径中// 从 y 出发至多 dis_xy-half就是从 x 出发至少 halfans[i] g.uptoDis(y, disXY - half);}}return ans;}
}
