𝒞𝒶𝓃𝒶𝓇𝓎

题目描述有一个自行车手打算进行一场公路骑行，这条路线总共由 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 且 ...

问题描述给你单链表的头节点 head，请你反转链表，并返回反转后的链表。 解题思路本题使用递归方式反转链表，核心思想是利用函数调用栈天然的后进先出特性。 递归三部曲 终止条件：当链表为空 (head == null) 或只有一个节点 (head.next == null) 时，直接返回 head，因为空链表或单节点链表反转后仍是自身。 递推过程：递归调用 reverseList(head.next)，一直深入到链表的最后一个节点。当递归触底时，返回的 newHead 就是原链表的尾节点，也就是反转后链表的头节点。 回溯处理：当递归逐层返回时，假设当前节点为 head，其下一个节点 head.next 已经完成了它之后所有节点的反转。此时 head.next 指向的是反转后链表中的最后一个节点（即原链表中 head 之后的子链表反转后的尾节点）。我们需要做两件事： 将 head.next.next = head，让原本指向 head 的节点反过来指向 head 将 head.next = null，断开 head 对后续节点的引用，防止形成环 举例说明以链表 1 -&g...

问题描述给定单链表的头节点 head，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。第一个节点索引为奇数，第二个节点为偶数，以此类推。 解题思路本题要求就地重新排列链表，将奇数位置（1, 3, 5, …）的节点放在前面，偶数位置（2, 4, 6, …）的节点放在后面，且保持各自的相对顺序。 双指针分离法使用两个指针 odd 和 even 分别追踪奇数和偶数链表的尾节点： 初始化： odd 指向头节点（第 1 个节点，奇数位） even 指向第二个节点（第 2 个节点，偶数位） evenHead 保存偶数链表的头节点，用于最后拼接 交替跳转：在循环中，每次操作两个节点： odd.next = even.next：将当前奇数节点的 next 跳过偶数节点，连接到下一个奇数节点 odd = odd.next：odd 指针移动到下一个奇数节点 even.next = odd.next：将当前偶数节点的 next 跳过新奇数节点，连接到下一个偶数节点 even = even.next：even 指针移动到下一个偶数节点 终止条件：当 even...

问题描述给定一个非空的字符串 s，检查是否可以通过由它的一个子串重复多次构成。 解题思路如果字符串 s 可以由子串 p 重复 k 次构成，那么 s 的长度 n 必定是子串长度 len(p) 的整数倍，即 len(p) 是 n 的因数。 因数枚举法 找出所有可能的子串长度： 一个子串如果可以重复构成整个字符串，其长度必然是字符串总长度 n 的一个因数 遍历 1 到 n/2，收集所有 n 的因数（子串长度不可能超过 n/2，因为至少要重复两次） 逐个验证： 对于每个因数 factor（可能的子串长度）： 计算重复次数 count = n / factor 截取前 factor 个字符作为候选子串 sub 使用 sub.repeat(count) 生成重复字符串，与原始字符串 s 比较 如果相等，返回 true 返回结果：如果所有因数都无法匹配，返回 false。 举例说明以输入 s = "abab"（n=4）为例： 因数有：[1, 2] 检查 factor=1：sub = "a"，重复 4 次得 &qu...

题目描述给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。 例如： a = "abcd", b = "cdabcdab" → 输出 3，因为 "abcdabcdabcd" 包含 "cdabcdab"。 a = "a", b = "aa" → 输出 2。 解题思路题目要求找到最小的整数 k，使得 b 是 a 重复 k 次得到的字符串的子串。 核心分析我们需要确定重复次数的上界。假设 a 的长度为 lenA，b 的长度为 lenB。 要让 b 成为子串，叠加后的字符串长度至少要为 lenB。最朴素的想法是：重复 ceil(lenB / lenA) 次。但考虑到 b 可能跨越 a 的边界（即 b 从前一个 a 的尾部开始，延伸到下一个 a 的前部），我们需要在首尾各多加上一个完整的 a。 因此，最多需要重复 (lenB / lenA) + 2 次（或者更精确地说，ceil(len...