算法刷题模型整理（三）

LC454 四数相加II

解题模型：

​ 分组

核心思路：

​ 将两个数组各取一个元素相加的结果存入哈希表，key为值，value为出现次数，另两个数组各取一个元素相加的值的相反数在表中查找，找到答案就加上对应出现次数，即简化为类似于两数之和的问题

易错点

• 哈希表直接用[]运算符访问，若key不存在，会创建一个新key，若value为int类型，会被初始化为0，所以当value为int，直接用ht[key]+=1;时，若key不存在，会插入(key, 0)，再将ht[key]+=1;
• 这题不需要下标，需要答案数，所以哈希表value存出现次数

字符串

LC344 反转字符串

解题模型：

​ 双指针

核心思路：

​ 头尾指针，swap字符

易错点：

• right指针的--不要写成++了

LC541 反转字符串II

解题模型：

​ 模拟法

核心思路：

​ i从0开始，步长2*k，大于等于n时退出，可使用std::reverse，注意要传入迭代器，参数为s.begin()+i, s.begin()+i+min(k,n-i);

易错点：

• 迭代器可以直接+运算符
• 注意不足k时的操作，直接使用min函数

LC151 反转字符串中的单词

解题模型：

​ 双指针

核心思路：

​ 思路1：快慢指针，同时从尾部开始扫描

​ 思路2：去除多余空格，反转整个字符串，再对每个单词进行反转

易错点：

• 注意string操作的性能问题，如ans= “ ” + ans;性能低，substr和earse都对性能影响很大
• 去除多余空格的方法，快慢指针扫描，可参考数组的移除目标元素，直接前移，去除头部和中间多余空格，然后resize顺便去除尾部空格

​

二叉树

LC144/094/145/102 二叉树的前/中/后/层序遍历

解题模型：

​ 递归/迭代

核心思路：

​ 前/中/后序：

​ 思路1：递归，编写递归函数

​ 思路2：迭代，手动维护栈模拟遍历过程

​ 层序：

​ BFS，不需要分层用队列即可，需要分层就从开始的时候记录队列长度n，此时后面的n个即为所有的该层元素，遍历完n个以后 再更新一遍n

易错点：

• 前/中/后序的退出时间，后序遍历因为最后遍历根节点，所以遍历完需要将指针设为空，否则不能退出循环，另外两个最后遍历右节点，所以不用
• 层序遍历要套两层循环

LC226 翻转二叉树

解题模型：

​ 递归/迭代

核心思路：

​ 后序遍历二叉树，翻转左右节点

易错点：

• 注意根节点为空的情况