𝒞𝒶𝓃𝒶𝓇𝓎

问题描述给你单链表的头节点 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...

题目描述给定两个字符串 s 和 goal，如果在若干次旋转操作之后，s 能变成 goal，那么返回 true。 s 的旋转操作就是将 s 最左边的字符移动到最右边。 例如： s = "abcde", goal = "cdeab" → 输出 true s = "abcde", goal = "abced" → 输出 false 解题思路本题有一个非常巧妙的技巧。 核心观察如果我们把 s 和自己拼接起来得到 s + s，那么 s 的所有旋转结果都一定是 s + s 的一个子串。 例如 s = "abcde"： s + s = "abcdeabcde" 旋转 1 次："bcdea" → 是 s + s 从下标 1 开始的子串 旋转 2 次："cdeab" → 是 s + s 从下标 2 开始的子串 旋转 3 次："deabc" → 是 s + s 从下标 3 开始的子串 旋转 4 次："eab...

题目描述给定一个已排序的链表的头 head，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。 解题思路本题要求删除排序链表中的重复元素。由于链表已经排序，重复元素必然相邻，因此只需要遍历链表，比较当前节点和下一个节点的值是否相同。 核心思路： 首先处理特殊情况：如果链表为空（head == null），直接返回 null。 保存头节点指针 res，用于最终返回结果。 遍历链表，当 head.next 不为空时： 如果当前节点值等于下一个节点值（head.val == head.next.val），说明找到了重复元素，将当前节点的 next 指针跳过下一个节点，直接指向下下个节点（head.next = head.next.next）。注意这里使用 continue 而不是移动 head，因为可能需要连续删除多个重复元素（例如 1 → 1 → 1 → 2）。 如果值不相同，正常移动指针到下一个节点（head = head.next）。 这种做法的关键是：当删除一个重复节点后不立即移动指针，这是因为被跳过的那个节点后面的新节点可能仍然与当前节点值相同，需要继续判断...

题目描述给定两个以升序排列的整数数组 nums1 和 nums2，以及一个整数 k。定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。请找到和最小的 k 个数对 (u1,v1), (u2,v2) ... (uk,vk)。 例如：nums1 = [1,7,11]，nums2 = [2,4,6]，k = 3，输出 [[1,2],[1,4],[1,6]]。 解释：和最小的三对依次是 (1,2) 和=3，(1,4) 和=5，(1,6) 和=7。 解题思路暴力法枚举所有 m * n 个数对，排序后取前 k 个。时间复杂度 O(mn log(mn))。当数组较大时效率很低。 最小堆优化（O(k log k)）核心思想：利用两个数组升序排列的性质，使用最小堆来”多路归并”。 关键观察对于固定 nums1[i]，它与 nums2 中元素配对的和是递增的： 1234(i,0): nums1[i] + nums2[0] （最小）(i,1): nums1[i] + nums2[1](i,2): nums1[i] + nums2[2].....

题目描述有一堆石头，每块石头的重量都是正整数。 每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设两块石头的重量分别为 x 和 y，且 x <= y： 如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y - x。 最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。 例如：stones = [2,7,4,1,8,1] 第一轮：选出 8 和 7，剩下 8-7=1，数组变为 [2,4,1,1,1] 第二轮：选出 4 和 2，剩下 4-2=2，数组变为 [2,1,1,1] 第三轮：选出 2 和 1，剩下 2-1=1，数组变为 [1,1,1] 第四轮：选出 1 和 1，完全粉碎，数组变为 [1] 返回 1 解题思路这道题完美适合使用最大堆（优先队列）来求解。因为每一轮都需要快速获取最大的两个元素，并在可能的情况下将差值插回。 大顶堆解法 将所有石头重量插入最大堆中。 当堆中元素数量 > 1 时，循环执行： 取出最大的元素...

题目描述给你一个整数数组 target。一开始，你有一个数组 A，它的所有元素均为 1，你可以执行以下操作： 令 x 为你数组里所有元素的和。 选择满足 0 <= i < target.length 的任意下标 i，并让 A 数组中对应下标处的值为 x。 你可以重复该过程任意次。如果能从 A 开始构造出目标数组 target，返回 true，否则返回 false。 例如：target = [9,3,5] → true 初始 A = [1,1,1]，sum = 3，选择下标 0 → A = [3,1,1]，sum = 5 选择下标 2 → A = [3,1,5]，sum = 9 选择下标 0 → A = [9,1,5]，sum = 15 选择下标 1 → A = [9,3,5]，等于 target 例如：target = [1,1,1,2] → false 解题思路该题的关键是逆向思维：与其从全 1 数组构造 target，不如从 target 反向推导回全 1 数组。 正...

题目描述学校的自助午餐提供圆形和方形的三明治，分别用 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个栈里，每一轮： 如果队列最前面的学生喜欢栈顶的三明治，会拿走它并离开队列； 否则学生会放弃这个三明治并回到队列的尾部。这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。返回无法吃上午餐的学生数量。 例如：students = [1,1,0,0]，sandwiches = [0,1,0,1]，输出 0。 解释：所有学生最终都能拿到喜欢的三明治。 解题思路核心思想这是一个模拟问题，使用队列来模拟学生的排队行为。 步骤 将所有学生放入队列 queue 中。 遍历三明治栈（sandwiches），对于每个三明治： 记录已检查的学生数 r = 0。 不断检查队首学生是否喜欢当前三明治： 如果喜欢（queue.peek() == sandwich），该学生拿走三明治并出队，跳出内层循环。 如果不喜欢，该学生回到队尾（queue.offer(queue.poll())），r++。 关键：如果 ...