小象学院刷题班：字符串、数组与链表专题

"小象学院2020 刷题班 3.2-4.171" 在小象学院2020年的刷题班中，涉及了一系列关于字符串、数组、链表和二叉树的编程问题。这些题目旨在帮助学员提升算法能力和对数据结构的理解。下面将对各个主题及其相关题目进行详细解析。 3.1 题目：验证回文串 链接：https://leetcode-cn.com/problems/valid-palindrome/ 这道题要求判断一个字符串是否为回文串，即正读反读都一样的字符串。解决这个问题通常可以使用双指针法，一个指针从字符串的开头向后移动，另一个指针从末尾向前移动，比较它们指向的字符是否相等，如果在移动过程中发现不相等则返回false，否则全部比较完成后返回true。 3.2 题目：亲密字符串 链接：https://leetcode-cn.com/problems/buddy-strings/ 亲密字符串是指两个字符串可以通过交换任意数量的字符而变得相同。解题思路是首先检查两个字符串长度是否相同，然后遍历两个字符串，统计字符出现的次数，如果存在相同字符个数超过2的，或者存在不相同的字符，则不是亲密字符串。 3.3 题目：反转字符串中的单词 链接：https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/ 该题要求反转字符串中的每个单词，但保持单词间的顺序不变。可以先将字符串中的所有空格替换为特殊字符，然后反转整个字符串，再反转每个单词，最后恢复空格。 3.4 题目：3sum 链接：https://leetcode-cn.com/problems/3sum/ 这是一个经典的双指针问题，目标是在一个整数数组中找到三个元素的和等于给定的值。可以先对数组进行排序，然后使用两层循环，每次固定一个元素，用双指针法寻找其他两个元素的和。 3.5 题目：数组中第k大的数 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/ 这题可以通过优先队列（堆）或快速选择算法解决。使用堆可以保持数组中的k个最大元素，并在插入新元素时自动维护这个顺序。快速选择算法则是通过分治策略在平均情况下达到线性时间复杂度。 附加题：数组中的逆序对 链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/ 逆序对是指在数组中，对于下标较小的元素a，如果它位于下标较大的元素b的右侧，且a > b，则称(a, b)为逆序对。可以使用归并排序的思路，对排序过程中产生的逆序对进行计数。 3.6 题目：环形链表 链接：https://leetcode-cn.com/problems/linked-list-cycle-ii/ 本题要求检测链表中是否存在环，如果有，找到环的入口节点。Floyd判圈法（快慢指针）是解决此类问题的常见方法，快指针每次移动两步，慢指针每次移动一步，若二者相遇则说明存在环。 附加题：翻转链表 链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/ 翻转链表可以使用迭代或递归的方法实现。迭代法使用两个指针，一个记录当前节点，另一个记录前一个节点，逐个翻转；递归法则从头节点开始，每次递归调用翻转子链表的后半部分。 3.7 题目：二叉树的镜像 链接：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/ 这道题要求实现二叉树的镜像操作，即交换每个节点的左右子树。可以使用递归的方法，交换每个节点的左右子节点。 附加题：二叉树的子结构 链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/ 这题要求判断一个二叉树是否包含另一个二叉树作为其子结构。可以使用深度优先搜索（DFS）算法，递归地比较每个节点及其子树。 最后，了解DFS算法是解决问题的关键，它是一种在图或树中搜索所有可能路径的方法，具有广泛的应用。在学习这些题目时，不仅要掌握解题技巧，还要深入理解数据结构和算法背后的逻辑，这将有助于提升编程能力。