每日一题（一）

目录

1. 189. 轮转数组

2. 55. 跳跃游戏

3. 238. 除自身以外数组的乘积

4. 142. 环形链表 II

5. 28. 找出字符串中第一个匹配项的下标

最近刷了几道 LeetCode 经典中等题，都是面试高频考点，整理了解法 + 核心思路，分享给大家～

1. 189. 轮转数组

题目：将数组元素向右轮转 k 个位置（k 非负）。示例：输入[1,2,3,4,5,6,7]，k=3 → 输出[5,6,7,1,2,3,4]

解法（三次反转法）：

class Solution { public: void rotate(vector<int>& nums, int k) { k %= nums.size(); // 避免k超过数组长度 reverse(nums.begin(), nums.end()); // 反转整个数组 reverse(nums.begin(), nums.begin()+k); // 反转前k个元素 reverse(nums.begin()+k, nums.end()); // 反转剩余元素 } };

核心思路：通过三次反转实现 “轮转”，时间复杂度 O (n)，空间复杂度 O (1)（原地操作）。比如[1,2,3,4,5,6,7]→ 全反转[7,6,5,4,3,2,1]→ 反转前 3 个[5,6,7,4,3,2,1]→ 反转后 4 个[5,6,7,1,2,3,4]。

2. 55. 跳跃游戏

题目：初始在数组第一个下标，每个元素是最大跳跃长度，判断能否到达最后一个下标。示例：输入[2,3,1,1,4]→ 输出true

解法（贪心算法）：

class Solution { public: bool canJump(vector<int>& nums) { int max_reach = 0; // 记录当前能到达的最远位置 for (int i = 0; i < nums.size(); i++) { if (i > max_reach) return false; // 无法到达当前位置 max_reach = max(max_reach, i + nums[i]); } return true; } };

核心思路：不用纠结每一步跳多远，只维护 “当前能到达的最远位置”。如果遍历到某位置时，该位置超过了最远位置 → 无法到达终点；否则更新最远位置，最终判断是否能覆盖终点。

3. 238. 除自身以外数组的乘积

题目：返回数组answer，其中answer[i]是数组中除nums[i]外所有元素的乘积（不能用除法，时间 O (n)）。示例：输入[1,2,3,4]→ 输出[24,12,8,6]

解法（左右前缀积）：

class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> left(n, 1); // left[i]：nums[0..i-1]的乘积 vector<int> right(n, 1); // right[i]：nums[i+1..n-1]的乘积 for (int i = 1; i < n; i++) left[i] = left[i-1] * nums[i-1]; for (int i = n-2; i >= 0; i--) right[i] = right[i+1] * nums[i+1]; vector<int> res(n); for (int i = 0; i < n; i++) res[i] = left[i] * right[i]; return res; } };

核心思路：用两个数组分别存 “前缀积” 和 “后缀积”，最终answer[i] = 前缀积[i] * 后缀积[i]。空间复杂度 O (n)，也可以优化到 O (1)（用结果数组存前缀积，再逆序乘后缀积）。

4. 142. 环形链表 II

题目：找到链表入环的第一个节点，无环则返回 null。示例：链表3→2→0→-4→2→ 入环点是 2。

解法（快慢指针）：

class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode *slow = head, *fast = head; // 第一步：快慢指针找相遇点 while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { // 第二步：相遇点和头节点同时出发，相遇点即入环点 ListNode *p1 = head, *p2 = slow; while (p1 != p2) { p1 = p1->next; p2 = p2->next; } return p1; } } return nullptr; } };

核心思路：

1. 快慢指针（快 2 步、慢 1 步），若有环则必相遇；
2. 相遇后，一个指针从表头出发，另一个从相遇点出发，同速前进，相遇点就是入环点（数学推导：设表头到入环点距离 a，入环点到相遇点距离 b，环长 c，则2(a+b) = a + b + kc→a = (k-1)c + (c-b)）。

5. 28. 找出字符串中第一个匹配项的下标

题目：在 haystack 中找 needle 的第一个匹配下标，无则返回 - 1。示例：输入haystack="sadbutsad", needle="sad"→ 输出 0

解法（直接调用库函数，面试需手写 KMP）：

class Solution { public: int strStr(string haystack, string needle) { return haystack.find(needle); // 库函数实现，面试建议手写KMP } };

补充：KMP 算法（避免暴力匹配的重复比较）：核心是预处理 needle 得到前缀函数数组（记录每个位置的最长相等前后缀长度），然后用前缀函数快速匹配，时间复杂度 O (n+m)。

以上就是 5 道题的解法和思路啦～这些题都是面试常考的 “中等难度”，掌握思路后能举一反三～