刷题疑问

1.K个链表合并，新建的节点怎么样能不使得内存泄漏；以及在 使用priority_queue的时候，compare 二元谓词、仿函数怎么使用来？

template <class T, class Container = vector<T>,class Compare = less<typename Container::value_type> > class priority_queue;

2.括号问题总结--dfs\\最长有效括号字符串长度

3.下一个排列 库函数 next_permutation

4.dfs路径问题，总结  四道类似题目一口气解决 - 机器人的运动范围 - 力扣（LeetCode）

5.c++中，vector的emplace_back 和 push_back的区别，后者是先创建一个对象，然后复制拷贝到容器中，后者是直接在容器尾部创建一个对象，省去了复制拷贝的步骤，性能有所提升

6. 给定target，给出组合39. 组合总和 - 力扣（LeetCode）

7.找两个有序数组中的第 k 小的数

8.接雨量、最大面积、双指针提升效率 \\柱状图中最大矩形------单调栈使用、

9.矩阵旋转，原地操作，48. 旋转图像 - 力扣（LeetCode）  tie 和 make_tuple 

10.线段树   解决 最大子数组和、区间最长连续上升序列问题、区间最大子段和问题

11.两个有序数组的中位数求解：二分查找 和 划分数组方法还没看，自己的方法空间复杂度高

12.中序遍历的结果是递增序列，dfs，

13.二叉遍历搜索树找第k大值，就是找中序遍历的倒序， 右-左-根 ；dfs

 14 动规步骤：

1. 确定dp数组（dp table）以及下标的含义 2.确定递推公式，3.dp数组初始化 , 4. 确定遍历顺序，5.举例推导

15.不同路径问题：深搜（超时）、动规、数论、

16. 子集问题。全排列，方法一 ：等价于二进制位；方法二：回溯

17. 编辑距离、动规  、动规的思想，代表的dp的意思

18 把数组排成最小的数    快排 + 比较大小的规则、此处的 排序算法自由选择，重点是比较大小时的规则、、排序的算法都写一下；；；

19 扑克牌中的顺子问题中，方法二中 用的set的 *st. rbegin() - *st.begin() 不能用 end() 去减，end定义是越过最后一个元素的 。An iterator to the past-the-end element in the container.

20. 最小覆盖字串---滑动窗口方法、

21、快排中的 分界点 pivot 的选取注意是随机选取还是第一个；

22、数据流中的中位数--大顶堆比小顶堆多1 的原因就是 让 插入的数是按从小到大递增，堆顶即为中位数

23、柱状图中的最大矩形、最大矩形、---单调栈的方法，确定每一个柱状条的左右边界，类似于 接雨量（问题8）

24、不同的二叉搜索树、-动态规划做、卡特兰数  

25.  中序遍历 可以判断一个 二叉搜索树 、迭代判断

26、对称的二叉搜索树 -----入口可以写两个根节点进行递归遍历判断；或者 使用队列进行迭代，入队时 左右、右左节点 两两入队，每次出队两个节点进行比较，

27、中序遍历方法：递归、迭代、Morris 中序遍历

28、层序遍历：迭代用队列、递归（都要熟练写）；

29、平衡二叉树判断方法：自顶向下、自底而上--- 熟练写

30、二叉树展开为单链表方法：先序遍历迭代、 后续遍历递归、迭代      收藏的一篇讲解很通透   、、  

　　　https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--26/  特殊的先序遍历，先将右子节点压入栈中，再左子节点

31、前序和中序遍历 得到一个二叉搜索树  递归 + 迭代、、

32、两两相同的异或为0；剩下一个即为解；

33、单词拆分经典题   方法：dfs、动规、bfs、

34、最长连续序列 、unordered_set集合；

35、1-n求和 不用判断、利用&&操作符、bool型变量、

36、二叉树的最近公共祖先、二叉搜索树的最近公共祖先， -- 递归求解，可以记录路径的写法注意一下

37、环形链表问题  找出入环点  方法： 快慢指针、哈希表

38、排序链表方法： 自顶向下的递归 归并、自下而上的迭代归并排序    多写写；迭代归并的时间复杂度：O(N logN)  空间复杂度：O(1)

39、LRU缓存题（高频题多写写） -- 手写实现链表、哈希+双向链表    

40、自己实现幂函数 快速幂+递归 、、、快速幂+迭代；

41、验证数组元素顺序为后序遍历方法：递归、另一种方法是利用 其倒序为 根 - 右 - 左的顺序，借助辅助栈+迭代实现

42、找链表的相交点：哈希set、双指针遍历一遍两个链表，相等时返回

43、最小栈的实现：利用两个栈实现 （一个辅助栈存储此刻的最小值）、 一个栈实现（存储差值）

44、找出数组中的多数元素方法：摩尔投票法，相等次数+1，否则-1，为0时重新赋值；

45、单向链表反转--迭代 、 递归（easy题）

46、二进制中1的个数：循环进位、巧用n&(n-1)  快速判断   

47、不用加减乘除做加法， 利用 循环进位，异或为无进位相加，逻辑与 为进位加   easy题但是不好想出来

48、由前序和后序遍历重构二叉树， 递归(容易理解)、迭代(难理解)；

49、课程表题目---有向图是否存在环； dfs、bfs、、、

50、字典树知识、实现字典树数据结构    多看看  官方题解是vector 、还有  哈希做的；

✳✳51、Top K 值问题，实现时间复杂度为O(N)的算法：   思路一是自建堆，面试高频问题、思路二是选用快速选择+快速排序算法、其中的分区思想利用两个指针实现，很实用；

52、回文链表 方法：快慢指针提取中点、接着翻转之后的节点进行比较、、、方法二：利用递归 保存上一次的节点的值，与全局变量指针往后遍历进行比较、、

53、数组中出现一次的数字， 使用异或 得到，若是两个数字，则再找到首位为1的 地方，即可分成两个数组 分别异或得到最终的值、、注意 == 优先级高于 &  ；

54、最近公共祖先问题(LCA)---思路一是递归记录每一个子树是否包含所属节点，返回bool型，或者当前节点正好等于所求节点的值、、

55、构建乘积最大数组 、除自身以外数组的乘积问题：主对角线分割的两半三角线 ，两次遍历，逐层相乘，利用上一次的乘积缩小空间复杂度。

56、搜索二维矩阵目标值：  lower_bound(begin,end,val),返回不小于val的iterator；z字形求解，右上角为比价的基值 ；

57、滑动窗口最大值 ： 方法一 使用双端队列deque，存储下标值，队首存最大值的索引、、方法二 使用priority_queue结构，大顶堆\\此处使用emplace可以存入二元组，底层是构建一个二元组尾加。

58、完全背包问题 、『 套用完全背包模板 』详解完全背包（含数学推导） - 完全平方数 - 力扣（LeetCode） （未看问题）

59、剪绳子问题---用动规做、、

60、移动零问题：双指针 左指针指向非零数组末尾，右指针指向零 的末尾，左指针到右指针区间都为零；碰到非零元素叫交换 左右下标的值，碰到零右指针加一；

61、寻找重复数问题：思路 -用下标到值看成是映射，转化为链表，有重复数的地方会形成一个环，，进而转化为利用快慢指针找到环的入口问题、、

62、二叉树的序列化和反序列化问题： DFS、BFS遍历(还没写)、熟练写    

63、和为s的连续数列：暴利解法、双指针（right边界不会重新枚举，利用上次的值继续)、

64、圆圈中最后剩下的数字：利用下标索引 倒推结果、、

65、最长递增子序列的问题：贪心算法+二分查找、、、lower_bound函数 自己实现；

66、零钱兑换、打家劫舍3、比特位计数问题：动规

67、最佳买股票时间含冷冻期问题：动规+状态机

68、前K个高频元素：hash+堆 、、快速选择排序没做、

69、字符串解码问题（华为一面）：利用可变长数组 vector 模拟栈的功能，方便最后输出字符串；两个库函数：isdigit(char )函数，isalpha(char )函数、、递归方法没有看、

　　　　char型转变为string型，可以利用string的特性，直接push_back，或者使用string的构造函数string(size_t  n , char  c);

70、实现stoi函数，看答案吧，并查集答案没做；

71、戳气球问题：动规问题、看答案；从左到右，从下到上，并增加两边的边界点，值设置为1，那么就有n + 2个节点，三层循环，j为右边界，i为左边界， k 为最后一个戳破的气球，动态的求 （i，k，j）开区间内最大值。

72、手写堆排序问题，没学会

73、动态规划问题、0-1背包问题、完全背包问题：分割等和子集问题、

74、根据身高重建队列问题：理解官解方法一，按键值身高从小到大排列，对于相同的身高的键值对，针对第二个值采取降序排列；先摆好size大小的空队列，再进行入队占位操作：从左往右数，第i个人前面有ki个空格；方法二：第一键值采取降序排序，相同身高的按第二键值升序排列，排序完后采用insert方法进行插入，（好理解）

排序第三参数自定义：    
　　　struct mycom{
        bool operator()(vector<int>&left, vector<int>& right){
            return left[0] < right[0] || (left[0] == right[0] && left[1] > right[1]);
        }
    }mycom;
或者：
    bool mycompare(vector<int>&left, vector<int>& right) {
        return left[0] < right[0] || (left[0] == right[0] && left[1] > right[1]);
    }

75、找到字符串中的所有的字母异位词：双指针滑动窗口+哈希遍历，优化版本没看、、

76、路径总和Ⅲ问题、递归方法：递归求出每一个节点可能的值；；；；前缀和方法没有看、、、

77、队列的最大值问题、、O(1）时间复杂度，使用queue和deque实现，queue存放元素，deque存放当前队列有过的最大值；；

78、