力扣刷题总结c++ 解题报告（持续更新中）（csdn）————程序.pdf

在力扣（LeetCode）平台上，刷题是提升编程技能和算法理解的重要方式。这篇解题报告主要聚焦于C++语言的解决方案，涵盖了多种不同类型的题目，包括但不限于数组操作、字符串处理、链表操作以及数学问题。以下是这些题目及其解法的详细分析： 1. **两数之和** 这是一个基础的哈希表应用问题。给定一个整数数组和一个目标值，任务是找到数组中两个数的索引，使它们相加等于目标值。解法一是简单的双层循环，时间复杂度O(n^2)，效率较低。解法二和三利用了`unordered_map`来存储已遍历过的数值及其索引，当遇到目标值减去当前数值时可以直接查找到对应的索引，时间复杂度降为O(n)。 2. **两数相加** 此题要求将两个链表表示的非负整数相加，每个节点存储一个数字位。可以采用同时遍历两个链表，逐位相加并处理进位的方法。最后的结果链表将包含相加后的每一位数字。 3. **无重复字符的最长子串** 这是一道滑动窗口的问题，可以使用哈希表记录字符的出现状态，每次移动窗口时检查是否有重复字符，记录最长无重复字符子串的长度。 4. **最长回文子串** 可以采用动态规划或中心扩散法求解，动态规划的解决方案会使用二维数组记录子串是否为回文，中心扩散法则从每个可能的中心位置开始向两边扩展，找到最长的回文子串。 5. **Z 字形变换** 这个题目涉及到字符串的排列，可以使用两个指针，按照Z字形的顺序分别对上下两半进行遍历。 6. **整数反转** 可以使用取模和除法操作，每次将数字的末位移到最前面，直到所有位都处理完。 7. **字符串转换整数 (atoi)** 需要处理字符串中的前导空格，有效数字和无效字符，可以采用模拟计算的方式实现。 8. **回文数** 通过比较整数的正序和反序是否相同来判断是否为回文数，可以利用位运算或者字符串操作。 9. **盛最多水的容器** 这是经典的两个指针问题，从两端向中间移动，找到最大的宽度乘以高度。 10. **有效的括号** 可以使用栈来验证括号的有效性，遇到左括号入栈，遇到右括号检查栈顶元素是否为匹配的左括号。 11. **删除链表的倒数第 N 个结点** 可以使用两个指针，一个快指针先走N步，然后两个指针一起走，当快指针走到链表尾部时，慢指针所在位置即为倒数第N个节点的前一个节点。 12. **整数转罗马数字** 建立罗马数字与阿拉伯数字的映射关系，根据整数的每一位转换成对应的罗马数字。 13. **罗马数字转整数** 罗马数字转整数需要理解罗马数字的规则，从左到右读取，遇到小数字在大数字右边时需要减去小数字的值。 14. **最长公共前缀** 可以逐字符比较字符串的公共部分，直到找到第一个不相同的字符。 15. **三数之和** 这是经典的双指针问题，先对数组排序，然后对于每个元素，使用两个指针在剩余元素中寻找满足条件的另外两个数。 16. **最接近的三数之和** 类似三数之和，但需要找到绝对差最小的组合。 19. **删除链表的倒数第 N 个结点** 同11题，只是删除操作更复杂，需要记录前一个节点。 20. **有效的括号** 同10题，只是这里需要判断整个字符串是否构成有效括号序列。 21. **合并两个有序链表** 通过比较两个链表的首节点，将较小的节点放入结果链表，然后更新指向下一个节点的指针。 23. **合并 K 个升序链表** 可以使用优先队列（最小堆）来合并多个链表，每次取出当前最小的节点连接到结果链表。 这些题目展示了C++在解决算法问题时的灵活性和效率，涉及了数据结构（如数组、链表、哈希表、栈和队列）、基本操作（如字符串处理、整数转换、位运算）以及多种算法思想（如暴力求解、动态规划、双指针、滑动窗口、回溯、贪心、分治等）。通过不断刷题和总结，可以加深对C++语言和算法的理解，提升编程能力。