算法 二叉树的最近公共祖先 给定一个二叉树，找到该树中两个指定节点的最近公共祖先。 最近公共祖先的定义为： 对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大。 一个节点也可以是它自己的祖先。 示例 1： 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3。 示例 2： 输入：
算法 前 K 个高频元素 给你一个整数数组 nums 和一个整数 k。 请返回其中出现频率前 k 高的元素。 答案可以按任意顺序返回。 示例 1： 输入：nums = [1,1,1,2,2,3], k = 2 输出：[1,2] 示例 2： 输入：nums = [1], k = 1 输出：[1] 示例 3： 输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2 输出：[1,
哈希表 LRU 缓存 请你设计并实现一个满足 LRU 最近最少使用约束的数据结构。 实现 LRUCache 类： * LRUCache(int capacity)：以正整数作为容量 capacity 初始化 LRU 缓存 * int get(int key)：如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 * void put(int key, int value)：如果关键字 key 已经存在，则更新它的值；如果不存在，则插入这组 key-value 如果插入操作导致关键字数量超过 capacity，则应该逐出最久未使用的关键字。 get 和 put 必须以 O(1) 的平均时间复杂度运行。 示例： 输入：
算法 随机链表的复制 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random。 该指针可以指向链表中的任何节点，也可以指向空节点。 请构造这个链表的深拷贝。 深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应原节点的值。 新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。 复制链表中的指针都不应该指向原链表中的节点。 例如，如果原链表中有 X 和 Y 两个节点，其中： X.random -> Y 那么在复制链表中对应的两个节点 x 和 y，也应该满足： x.random -> y 返回复制链表的头节点。 输入和输出中的链表用 n 个节点表示，每个节点用一个 [val, random_index] 表示： * val：表示
算法 划分字母区间 给你一个字符串 s。 我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。 例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s。 返回一个表示每个字符串片段长度的列表。 示例 1： 输入：s = "ababcbacadefegdehijhklij" 输出：[9,7,
哈希表 环形链表 II 给定一个链表的头节点 head，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置，索引从 0 开始。 如果 pos 是 -1，则在该链表中没有环。 注意： * pos 不作为参数进行传递。 * pos 仅仅是为了标识链表的实际情况。 * 不允许修改链表。 示例 1： 输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。 示例 2： 输入：head
链表 环形链表 给你一个链表的头节点 head，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置，索引从 0 开始。 注意： * pos 不作为参数进行传递。 * pos 仅仅是为了标识链表的实际情况。 如果链表中存在环，则返回 true。 否则，返回 false。 示例 1： 输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。 示例 2： 输入：head = [1,2], pos = 0 输出：
算法 相交链表 给你两个单链表的头节点 headA 和 headB。 请你找出并返回两个单链表相交的起始节点。 如果两个链表不存在相交节点，返回 null。 题目数据保证整个链式结构中不存在环。 注意： * 函数返回结果后，链表必须保持其原始结构。 * 链表相交指的是两个链表从某个节点开始，后续节点在内存中是同一批节点。 * 不能只比较节点值是否相等，必须比较节点本身是否相同。 自定义评测中会使用： * intersectVal：相交的起始节点的值。如果不存在相交节点，这一值为 0 * listA：第一个链表 * listB：第二个链表 * skipA：在 listA 中从头节点开始跳到交叉节点的节点数 * skipB：在 listB 中从头节点开始跳到交叉节点的节点数 评测系统会根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给程序。 示例 1： 输入：intersectVal = 8, listA = [4,1,8,4,
算法 缺失的第一个正数 给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n)，并且只使用常数级别额外空间的解决方案。 示例 1： 输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。 示例 2： 输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。 示例 3： 输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数
算法 和为 K 的子数组 给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的子数组的个数。 子数组是数组中元素的连续非空序列。 示例 1： 输入：nums = [1,1,1], k = 2 输出：2 示例 2： 输入：nums = [1,2,3], k = 3 输出：2 提示： * 1 <= nums.length <= 2 * 10^4 * -1000 <= nums[i] <= 1000 * -10^7 <= k <
算法 最长连续序列 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1： 输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。 示例 2： 输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9 示例 3： 输入：nums = [1,
算法 字母异位词分组 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 示例 1: 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]] 解释： * 在 strs 中没有字符串可以通过重新排列来形成
算法 两数之和 Two Sum（两数之和）哈希表解法原理 核心思想 使用 unordered_map 建立一个哈希表，保存已经遍历过的数字以及它对应的下标。 遍历数组时，对于当前数字 nums[i]： * 计算它需要的另一个数字： [ need = target - nums[i] ] * 如果 need 已经存在于哈希表中，说明找到了两个数： [ nums[i] + need = target ] 返回它们的下标。 * 如果不存在，则将当前数字和下标存入哈希表，供后续查找。 代码 class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map&