企业官网建设流程全解析

东坑东莞微信网站建设,湖南省造价管理站官网,中国建设银行集团,苏州网站建设网络推广目录 1. 189. 轮转数组 2. 55. 跳跃游戏 3. 238. 除自身以外数组的乘积 4. 142. 环形链表 II 5. 28. 找出字符串中第一个匹配项的下标 最近刷了几道 LeetCode 经典中等题#xff0c;都是面试高频考点#xff0c;整理了解法 核心思路#xff0c;分享给大家#xff5e;…目录1. 189. 轮转数组2. 55. 跳跃游戏3. 238. 除自身以外数组的乘积4. 142. 环形链表 II5. 28. 找出字符串中第一个匹配项的下标最近刷了几道 LeetCode 经典中等题都是面试高频考点整理了解法 核心思路分享给大家1. 189. 轮转数组题目将数组元素向右轮转 k 个位置k 非负。示例输入[1,2,3,4,5,6,7]k3 → 输出[5,6,7,1,2,3,4]解法三次反转法class Solution { public: void rotate(vectorint 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(vectorint 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: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint left(n, 1); // left[i]nums[0..i-1]的乘积 vectorint right(n, 1); // right[i]nums[i1..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[i1] * nums[i1]; vectorint 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; } };核心思路快慢指针快 2 步、慢 1 步若有环则必相遇相遇后一个指针从表头出发另一个从相遇点出发同速前进相遇点就是入环点数学推导设表头到入环点距离 a入环点到相遇点距离 b环长 c则2(ab) a b kc→a (k-1)c (c-b)。5. 28. 找出字符串中第一个匹配项的下标题目在 haystack 中找 needle 的第一个匹配下标无则返回 - 1。示例输入haystacksadbutsad, needlesad→ 输出 0解法直接调用库函数面试需手写 KMPclass Solution { public: int strStr(string haystack, string needle) { return haystack.find(needle); // 库函数实现面试建议手写KMP } };补充KMP 算法避免暴力匹配的重复比较核心是预处理 needle 得到前缀函数数组记录每个位置的最长相等前后缀长度然后用前缀函数快速匹配时间复杂度 O (nm)。以上就是 5 道题的解法和思路啦这些题都是面试常考的 “中等难度”掌握思路后能举一反三题目编号及名称核心解法核心思路注意事项 思路亮点189. 轮转数组三次反转法1. 先对k取模k≥数组长度时简化操作2. 反转整个数组3. 反转前k个元素4. 反转剩余元素。通过反转操作的组合实现元素的轮转效果。• 亮点原地操作时间复杂度O(n)空间复杂度O(1)避免额外数组开销• 注意k可能大于数组长度必须先执行k % nums.size()否则会出现越界或无效操作。55. 跳跃游戏贪心算法1. 维护“当前能到达的最远位置”max_reach2. 遍历数组若当前索引超过max_reach说明无法到达该位置直接返回false3. 否则更新max_reach为当前索引当前元素值的最大值4. 遍历结束后若max_reach≥数组末尾索引返回true。• 亮点无需模拟跳跃过程仅通过贪心策略维护最远可达位置时间复杂度O(n)高效简洁• 注意初始max_reach为0遍历从索引0开始覆盖所有可能的跳跃起点。238. 除自身以外数组的乘积左右前缀积法1. 定义left数组left[i]表示nums[0..i-1]的乘积2. 定义right数组right[i]表示nums[i1..n-1]的乘积3. 遍历计算left和right数组4. 结果数组res[i] left[i] * right[i]。• 亮点规避除法避免除数为0问题时间复杂度O(n)• 优化点可将空间复杂度降至O(1)用res数组先存left值再逆序遍历乘right值无需额外right数组。142. 环形链表 II快慢指针法1. 快慢指针初始化指向表头快指针每次走2步慢指针每次走1步2. 若有环两指针必相遇3. 相遇后一个指针从表头出发另一个从相遇点出发两指针同速前进相遇点即为入环点4. 若无环快指针会先到达null。• 亮点通过数学推导确定入环点无需额外空间空间复杂度O(1)避免哈希表存储节点的开销• 数学依据设表头到入环点距离为a入环点到相遇点距离为b环长为c则2(ab) abkc → a(k-1)c(c-b)。28. 找出字符串中第一个匹配项的下标KMP算法面试推荐/ 库函数KMP核心1. 预处理模式串needle生成前缀函数数组记录每个位置的最长相等前后缀长度2. 用双指针分别遍历主串haystack和模式串needle利用前缀函数快速跳过重复比较匹配成功则返回起始索引。• 亮点KMP算法时间复杂度O(nm)n为主串长度m为模式串长度避免暴力匹配的O(nm)复杂度• 注意库函数haystack.find(needle)可快速解题但面试中需手写KMP算法核心是前缀函数的理解与实现。