𝒞𝒶𝓃𝒶𝓇𝓎

题目描述给定一个长度为 n 的链表，对于列表中的每个节点，查找下一个更大节点的值。返回一个整数数组 answer，其中 answer[i] 是第 i 个节点下一个更大节点的值。如果第 i 个节点没有下一个更大节点的值，设置 answer[i] = 0。 例如：链表 [2,1,5] → 输出 [5,5,0] 节点 2：下一个更大的是 5 节点 1：下一个更大的是 5 节点 5：后面没有更大的，为 0 再如：链表 [2,7,4,3,5] → 输出 [7,0,5,5,0] 解题思路本题是”下一个更大元素”问题的变种，只不过数据结构从数组变成了链表。核心思路依然是单调栈。 整体流程 链表转数组：首先遍历链表，将所有节点的值存入一个 ArrayList 中，这样可以方便地通过下标随机访问。同时记录元素总数 n。 单调递减栈求解：使用一个单调递减栈（存储下标），从左到右遍历数组： 当栈不为空，且当前元素 nums.get(i) 大于栈顶下标对应元素时： 弹出栈顶下标 index，意味着节点 index 找到了下一个更大的值。 设置 answer[index] = nums.get(i...

题目描述给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random，该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向新链表中的对应节点，从而使原链表和新链表中的这些指针能够表示相同的链表状态。 解题思路本题的难点在于处理 random 指针。由于 random 指针可以指向链表中的任意节点，在普通遍历中，我们可能还没有创建该目标节点，导致无法直接设置 random 指针。 使用哈希表可以优雅地解决这个问题，具体分为两趟遍历： 第一趟遍历：创建所有新节点，并建立原节点到新节点的映射关系（map<原节点, 新节点>）。此时新节点的 next 和 random 指针暂时为 null。这一步确保了所有节点都已经被创建，后续可以放心地引用它们。 第二趟遍历：再次遍历原链表，通过哈希表查找： 当前新节点的 next 应该指向 map.get(原节点.next)（即原节点 next 对应的新节点） 当前新节点的 ...

题目描述给你一个正整数数组 nums，请你移除最短子数组（可以为空），使得剩余元素的和能被 p 整除。不允许将整个数组都移除。返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1。 例如：nums = [3,1,4,2]，p = 6，输出 1。 解释：数组总和为 3+1+4+2=10，10 % 6 = 4。我们需要移除一个和为 4 的子数组。移除子数组 [4]（索引 2），剩余元素和 3+1+2=6，能被 6 整除。子数组长度为 1，是最短的。 解题思路核心数学原理设数组总和模 p 的值为 totalSum % p = target： 如果 target == 0，说明整个数组的和已经能被 p 整除，直接返回 0。 否则，我们需要移除一个子数组，使得该子数组的和模 p 等于 target，这样剩余元素的和模 p 就等于 0。 为什么？ 因为剩余和 = 总和 - 子数组和。若剩余和能被 p 整除，即 (totalSum - subSum) % p == 0，则 subSum % p == totalSum % p == target。 前缀和 + 哈希表...

题目描述给你一个整数数组 nums。你需要恰好移除一个元素后，使得剩余元素中，奇数下标元素之和等于偶数下标元素之和。返回满足条件的移除方案数。 例如：nums = [2,1,6,4]，输出 1。 解释： 移除下标 0：[1,6,4]，偶数下标和 = 1+4=5，奇数下标和 = 6，5 ≠ 6 移除下标 1：[2,6,4]，偶数下标和 = 2+4=6，奇数下标和 = 6，6 = 6 ✓ 移除下标 2：[2,1,4]，偶数下标和 = 2+4=6，奇数下标和 = 1，6 ≠ 1 移除下标 3：[2,1,6]，偶数下标和 = 2+6=8，奇数下标和 = 1，8 ≠ 1只有移除下标 1 满足条件。 解题思路核心思想直接枚举每个元素被移除的情况需要 O(n²)。我们可以用前缀和的思想在 O(n) 时间内解决。 当移除下标 i 的元素后，剩余元素的下标会发生变化： i 之前的元素，其下标奇偶性不变。 i 之后的元素，其下标奇偶性反转（原来的偶数变奇数，奇数变偶...

题目描述有一个自行车手打算进行一场公路骑行，这条路线总共由 n + 1 个不同海拔的点组成。自行车手从海拔为 0 的点 0 开始骑行。给你一个长度为 n 的整数数组 gain，其中 gain[i] 是点 i 和点 i + 1 的净海拔高度差（0 <= i < n）。请你返回最高点的海拔。 例如：gain = [-5,1,5,0,-7]，输出 1。 解释：海拔变化：0 → -5 → -4 → 1 → 1 → -6，最高海拔为 1。 解题思路核心思想这是一个典型的前缀和问题。给定相邻两点之间的高度差数组 gain，我们需要求出所有点的海拔值中的最大值。 设点 0 的海拔 altitude[0] = 0，则： altitude[1] = altitude[0] + gain[0] altitude[2] = altitude[1] + gain[1] … altitude[i+1] = altitude[i] + gain[i] 每个点的海拔都是前一个点的海拔加上对应的高度差，这正是前缀和。 步骤 创建一个长度为 n+1 的数组 prefixAndGain，其中 pre...

题目描述给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。要求时间复杂度 O(n) 且只使用常数级别额外空间。 解题思路这是一道经典的原地哈希题目。由于要求 O(n) 时间复杂度和 O(1) 额外空间，我们需要在原数组上进行操作。 核心思路是将数组视为一个”哈希表”，让每个正整数尽可能地放在它对应的索引位置上（即值 x 应该放在下标 x - 1 的位置）。如果数组中存在 1，那么 1 应该在下标 0 的位置；存在 2，那么 2 应该在下标 1 的位置，以此类推。 具体步骤分为三趟遍历： 第一趟：将数组中所有非正整数（≤ 0）替换为 len + 1（一个超出有效范围的值）。这是为了后续处理时，只关注正整数的范围，负数和其他非正整数不会干扰标记过程。 第二趟：使用数组的索引作为标记位。遍历数组，对于每个元素的绝对值 cur，如果它在有效范围 [1, len] 内，我们就将该值对应下标 cur - 1 处的元素标记为负数（取反）。这表示数字 cur 在数组中出现过。注意需要使用绝对值处理可能已被标记为负数的元素。 第三趟：遍历数组，找到第一个值大于 0 的下标 i...

问题描述给你一个整数数组 nums 和一个整数 k，如果 nums 有一个好的子数组（长度至少为 2，且子数组元素总和为 k 的倍数），返回 true；否则返回 false。 解题思路本题是前缀和 + 同余定理的经典应用。 核心数学原理：同余定理若子数组 nums[i...j] 的和是 k 的倍数，则有： 1(sum[j] - sum[i-1]) % k == 0 等价于： 1sum[j] % k == sum[i-1] % k 这意味着：如果两个前缀和对 k 取余的余数相同，且它们对应的索引距离 ≥ 2，则它们之间的子数组和就是 k 的倍数。 算法步骤 初始化哈希表：将 (0, -1) 放入哈希表，表示前缀和为 0 时的索引为 -1。这是为了处理”从数组开头开始的子数组”的情况（如 [6, 6] 且 k=6）。 遍历数组，维护前缀和： 累加当前元素到 runningSum 计算 remainder = runningSum % k 注意处理 k == 0 的特例：直接取 runningSum 作为余数（即两个相同的前缀和才满足条件） 处理负数余数：如果 remainder...

题目描述给你一个字符串 date，它的格式为 Day Month Year，其中 Day 是集合 {"1st", "2nd", "3rd", "4th", ..., "30th", "31st"} 中的一个元素，Month 是集合 {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"} 中的一个元素，Year 的范围在 [1900, 2100] 之间。请你将字符串转变为 YYYY-MM-DD 的格式。 例如：date = "20th Oct 2052"，输出 "2052-10-20&q...

题目描述给你一个字符串 sequence，如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串，那么单词 word 的重复值为 k。单词 word 的最大重复值是单词 word 在 sequence 中最大的重复值。返回单词 word 的最大重复值。 例如：sequence = "ababc"，word = "ab"，输出 2。 解释："abab"（word 重复 2 次）是 "ababc" 的子串；但 "ababab"（重复 3 次）不是 "ababc" 的子串。所以最大重复值为 2。 解题思路核心思想要找到 word 重复 k 次后成为 sequence 子串的最大 k 值，我们可以从小到大尝试： 不断将 word 拼接自身，检查拼接后的字符串是否是 sequence 的子串。 只要匹配，就增加计数，继续尝试。 直到匹配失败则停止。 步骤 初始化计数器 res = 0，保存原始字符串 wordBK = word。 进入循...

题目描述有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后腐烂，变得无法食用。你打算每天最多吃一个苹果，以保持营养均衡。返回你可以吃掉的苹果的最大数目。 例如：apples = [1,2,3,5,2]，days = [3,2,1,4,2]，输出 7。 解题思路核心贪心策略这是一个经典的贪心 + 最小堆问题。为了最大化吃掉的苹果数量，每天应该优先吃掉最早腐烂的苹果（即过期时间最早的苹果）。这样可以避免苹果在腐烂前没有被吃掉。 数据结构定义一个 Apple 类，包含两个属性： count：该批次苹果的剩余数量。 days：该批次苹果的过期时间（即 i + days[i]），在 days 天之前（不含当天）可以食用。 使用最小堆按过期时间 days 排序，堆顶始终是即将最早腐烂的苹果。 算法步骤 初始化最小堆 heap，计数器 res = 0，天数 i = 0。 当 i < n（还有苹果在生长）或堆非空（还有苹果可以吃）时进行循环： 添加当天的苹果：如果 i < n 且 ...