Solution of leetcode in Interview
数据结构 - Data Structures
- 数组与链表：单 / 双向链表、跳舞链
- 栈与队列
- 树与图：最近公共祖先、并查集
- 哈希表
- 堆：大 / 小根堆、可并堆
- 字符串：字典树、后缀树
算法 - Algorithms
- 排序算法：快速排序、归并排序、计数排序
- 搜索算法：回溯、递归、剪枝技巧
- 图论：最短路、最小生成树、网络流建模
- 动态规划：背包问题、最长子序列、计数问题
- 基础技巧：分治、倍增、二分、贪心
题目
开始之前
- 思路：使用「异或」运算
- 思路：使用「打擂台」的方式更新候选元素
- 思路：从右上角元素开始与
target比较，判断向下移动或向右移动或返回结果。
- 思路：双指针，倒序比较两数组中有效元素，并将较大者放入数组一的末尾。
- 思路：hard
字符串
- 思路：对撞指针，判断双指针当前指向的字母或数字字符是否相等。
- 思路：回溯，判断
s中以idx开始的每个子串是否是回文串，如是则添加到comb中。
- 思路：动态规划，
dp[i]表示s中的前i个字符组成的字符串是否可以拆分为字典中的单词，dp[i] = dp[j] && check(s[j...i-1])。
- 思路：回溯，使用哈希表存储
s中以索引i开始的子串组成的句子，判断每个子串是否出现在字典中，如出现则递归判断下一个子串。
- 思路：每个节点包括一个
vector<Trie*> children和一个bool isEnd。
- 思路：回溯，在四个方向上判断当前字符是否与
word中对象的字符相同，并更新visited。
- 思路：字母表或哈希表。
- 思路：哈希表，返回出现次数为1的字符。
- 思路：对撞指针。
数组
- 思路：动态规划，
maxPrefix[i]表示以索引i结尾的子数组最大乘积，minPrefix[i]表示以索引i结尾的子数组最小乘积。
- 思路：打擂台。
- 思路：三次翻转。
- 思路：哈希表。
- 思路：双指针，将非零元素移动至开头并后移双指针。
- 思路：交换
nums[i]和nums[i + rand() % (n-i)]实现打乱数组。
- 思路：哈希表，存储元素及其出现次数。
- 思路：贪心，使得
first及second较小使得更容易找到三元组。
- 思路：双指针或者二分查找（将数组展平）。
- 思路：一次遍历，每次计算索引
i处的前缀积和n-i-1处的后缀积。
堆、栈与队列
- 思路：维护两个栈，一个保存当前元素，一个保存当前最小元素。
- 思路：最大堆排序或快速选择。
- 思路：使用两个优先级队列（小根堆和大根堆）模拟整个有序列表。
- 思路：使用优先级队列（小根堆）存储矩阵中的点，根据行索引搜索得到第k小的值。
- 思路：使用优先级队列（大根堆）存储
pair<int, int>元素，记录每个元素出现的次数。
- 思路：使用优先级队列（大根堆）保存当前窗口内的最大值及其在原数组内的索引。
- 思路：使用一个
stack保存每个左括号前的符号，如遇正号则不变号，如符号则变号，如遇数字则乘以符号标志后加到结果中。
- 思路：使用一个
vector保存所有整数，使用preSign记录上一次出现的符号。根据符号的不同对当前整数进行不同处理。
- 思路：使用一个
stack逆序保存扁平化列表中的元素，对于hasNext()：栈顶元素为整数时直接返回true，为列表时则将其展平为元素并逆序放入栈中。
- 思路：使用
stack保存列表中的每个数，遇到符号时则依次弹出两个数进行计算并将结果再次压入栈中。
链表
- 思路：使用哈希表存储旧表节点及其对应的新表节点，并依据旧表结点中的
next和random构造新表节点中的对应next和random。
- 思路：快慢指针结合
do...while()。
- 思路：归并排序，首先将原链表根据中点一分为二，并递归进行拆分操作，而后将子链表回溯合并即可。
- 思路：双指针，各自遍历
list1 + list2，相遇后即为首个相交节点。
- 思路：更改
prev、curr、next。
- 思路：翻转后半部分链表后，比较前后两部分子链表节点值是否一致。
- 思路：将后一节点前移覆盖当前节点，随后删除该后一节点。
- 思路：双指针，
odd->next = even->next，even->next = odd->next。
哈希与映射
- 思路：26进制转换
- 思路：使用哈希map存储前两个数组之间元素和及其出现的次数，然后针对后两个数组之间元素和，判断其相反数是否出现在哈希map中。
- 思路：使用线性表存储每个元素，使用哈希map存储元素及其在线性表中的下标。
树
- 思路：使用迭代版中序遍历，当遍历到第k个元素时返回即可。
- 思路：使用哈希map存储每个节点及其父节点，然后节点
p开始向上递归，并记录访问过的节点，在q向上递归的过程中如遇到p访问过的节点即为最近公共祖先。
- 思路：使用
dfs将节点序列化为字符串，使用istringstream存储序列化的结果，并递归进行二叉树的构造。