链接: leetcode

题目要求：实现一个满足LRU(最近最少使用)缓存约束的数据结构类。

解题思路：
数据结构的选择：时间复杂度O(1)的插入与查询，优先考虑哈希表的查询，队列和栈的插入，而插入要按时间顺序，因为超出范围后要删除时间最久的，故而选用双端队列,即容器内元素以哈希表结构存储的双端队列,这里用list<pair<int,int>>的结构实现哈希匹配。

链接:leetcode

题目要求：判断链表是否有环，有环返回入环的第一个节点，否则返回null

解题思路：双指针，若快慢指针能相遇在，则说明有环，且当前位置即为所求。
快指针和慢指针同时开始，每次快指针走两步，慢指针走一步，设共a+b个节点，且第a+1个节点即为环的入口，那么快慢指针第一次相遇时二者必然差n个环，即快指针走的步数f-慢指针走的步数s=n*b，,且此时,再设入口节点为k，那么,如果此时快指针从0开始，与慢指针同步走，每次都只走一步，那么当快指针走到入口处时，慢指针也刚好走到，二者第二次相遇，返回慢指针此时指向的节点即得所求。

链接: leetcode

题目描述：给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

解题思路：类似于元素交换，新建一个链表存储当前链表下一节点，更改当前链表的下一节点为上一节点（初始为空指针），给上一节点赋值为当前节点，当前节点接着赋值为暂存的下一节点

链接: leetcode

题目描述：合并两个有序链表并按升序返回

解题思路：引入第三个链表实现即可，同时为了方便处理新链表的头节点，引入了一个cur指针初始化指向一个新的链表节点，节点值为0，避免头节点处理。

链接: leetcode-中
leetcode-前
leetcode-后

链接: leetcode

题目描述：合并两个非递减顺序排列的整数数组，结果按非递减顺序排列并原地保存在其中一个数组中，

解题思路：逆向双指针，从后向前填充可避免覆盖

基本思想是采用分治法（Divide and Conquer）策略来把一个序列分为较小和较大的两个子序列，然后递归地对这两个子序列进行排序。快速排序通常比其他基于比较的排序算法更快，在实际应用中非常广泛。

快速排序的基本步骤：
选择基准（Pivot）: 从数组中选择一个元素作为基准。
分区操作（Partitioning）: 重新排列数组，所有小于基准的元素都排在基准前面，所有大于基准的元素都排在基准后面。这个操作完成后，基准元素就位于其最终位置。
递归排序子数组:
对基准左侧的子数组递归执行上述步骤。
对基准右侧的子数组递归执行上述步骤。
快速排序算法有两个核心点，分别为 哨兵划分 和 递归 。
哨兵划分：
以数组某个元素（一般选取首元素）为 基准数 ，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。
递归：
对 左子数组 和 右子数组 分别递归执行 哨兵划分，直至子数组长度为 1 时终止递归，即可完成对整个数组的排序。

链接: leetcode

题目描述：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

解题思路：unordered_map存储

链接: leetcode

题目描述：给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串的长度。

解题思路：回文串倒序后与自身完全相同，当回文串长度为偶数所有字符出现偶数次，当回文串长度为奇数除了中间字符出现奇数次，其余都出现偶数次，因此可以用哈希表计数，遍历统计构造回文串的最大长度

链接: leetcode

题目描述：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

解题思路：迭代，分析pq是否在root的同一子树，进一步深度遍历