开始动态规划了，动规五部曲如下：1、确定dp[i]的含义2、确定递归公式3、dp数组的初始化4、遍历顺序5、打印dp数组（用于debug）

968监控二叉树class Solution {private:int result = 0;int traversal(TreeNode* cur){//递归出口if(cur == NULL) return 2;//左int left = traversal(cur->left);//右int right = traversal(cur->right);//中//情况1if(left == 2 && right == 2) return 0;//情况2if(left == 0 || right == 0){result++;return 1;}//情况3if(left == 1 || right == 1) return 2;return -1;//其实上面三种情况包括了所有情况，并不会走到这步，但必须这里加个return，否则编译不通过}public:int minCameraCover(TreeNode* root) {//贪心和二叉树的结合，尽量让叶子节点的根节点安装摄像头，可以覆盖上中下三层，减少覆盖范围的浪费//后序遍历这个二叉树，根据叶子结点的状态（0无覆盖、1有摄像头、2有覆盖），来判断根节点的状态//注意，遇到空结点的时候，将其状态定为2有覆盖，才能让叶子节点是个0无覆盖状态，而其父节点为1有摄像头//根据叶子结点的情况主要可以分为以下三类//1、左右叶子节点都为2有覆盖，则父节点为0无覆盖(等着它的上层加摄像头来覆盖)//2、左右结点至少有一个为0无覆盖，则父节点必须为1有摄像头//3、左右结点至少有一个为1有摄像头，则父节点必须为2有覆盖（注意，情况2的判断必须要放在3之前）//此外，还有一种特殊情况//4、根节点最后为0无覆盖，因为根节点没有父节点，所以被办法对其进行上层加摄像头覆盖了，所以此时根节点要放一个摄像头if(traversal(root) == 0) result++;//特殊情况4出现，摄像头再加一个return result;}};

重叠区间问题要对数组进行排序，再去判断右边界（更新为最小值）与下一个区间的重叠情况。划分字母区间要首先统计每个字母出现的最远位置的索引，然后再去遍历这个字符串，当下标值与最远位置索引相等时即到达了分割点。明天开始面向对象设计。以及下周二终面，要好好准备一下。

贪心真难啊！好难想到，自己能想到的又老是不周全要调整，不管了先刷题再说。今天还写了个LRU算法，学了下成员函数适配器mem_fn，还是被面试影响到了学习的状态，老去想面试的事情，何必呢，等着就好了，到面的前两天再准备一下宝洁八大问和过往经历梳理，现在还是先专心学习吧，不要因为这个又浪费了时间。

今天继续做了贪心，要考虑的细节特别多！122.买卖股票的最佳时机 II 和 1005.K次取反后最大化的数组和这两道题自己慢慢调就可以写出来，跳跃的两道题自己就做不出来了，关键是跳跃后能覆盖到的下标位置，求最少步数时只有i ==curcover时才步数+1，并更新curcover的值。下午进行了整整两个小时的面试，面试体验感超级好就是时间太久了累了，hr人很好，一共7个人，全是女孩子嘻嘻，氛围超级好！因为没啥群面经验，压根没打算去争角色，结果因为讲到点上了，被大家cue了两次，最后进行了汇报。小姐姐们都好好啊哈哈哈。官网上看到进终面了，太棒了运气真好哈哈，希望每次面试运气都这么好！尽管很激动，但不要激动，现在还是要静下心来继续学，等收到后续的面试通知再想这个事。希望能成功拿到这个外企当保底！冲！

今天开始贪心算法了，贪心算法没有套路，只有找到局部最优解！还有点难，考虑不周全。然后差不多把bind、以及bind和function结合使用用于实现多态搞明白了。

今天算法只刷了N皇后一道题，是一道经典的回溯算法用于棋盘问题的题。然后还把迭代器、算法库、lambda表达式学了下，对bind还不是很理解，明天接着学。最近降温了，不知道自己抽什么风开学搬校区的时候懒得带那么多东西，就把羽绒服和珊瑚绒睡衣、甚至秋衣都全寄回家了，只留了最薄的羽绒服。。现在又重新买了秋衣和睡衣，反正也不咋出门，先这样吧，实在太冷了，再让家里寄回来。那时候对自己太自信了，觉得能日复一日学很多，然后找到实习就不用待在学校了，没想到后面从9月下旬开始因为准备国奖材料、老板催文章、本专业秋招这些乱七八糟的事严重耽误了学习进度，国庆还回了趟家，还跟爸妈错峰去福建旅游了好几天，一下子十月的半个月就没了。。所以现在拖到这么晚了，不过没关系，离过年还有两月呢，这两个月坚持坚持，把C++基础学完，看是继续学Qt、做项目啥的，还是就开始边把Linux、C++相关的八股文复习背一下，边准备找实习试试。后面再看吧，情况不好的话，寒假就继续深入学，冲明年的春招。上半年不应该把那么多时间都花在写文章上的，又不读博，那么多文章除了评奖学金啥用也没有，而且今年只要一两篇一区就能评上的，真是失算了。当初就应该全身心投入转码学习的，两万块其实也没啥，也就是以后一两个月的工资罢了。继续加油吧，现在就是努力的最好时刻！冲！

1、491非递减子序列：由于题目给出的是个无序可重复数组，要求它的自增子序列，所以并不能采用之前的去重逻辑（先对数组排序）。本题的去重逻辑也是针对树层的，可以用一个unordered_set（无序唯一）来记录本层使用过的元素,在给出的数组元素范围比较小的时候，还可以用数组来做哈希提高效率，在处理前先检查一下该元素是否有被使用过。注意，unordered_set必须声明在回溯函数中，且此次的去重可以不需要回溯。用外部used并不能达到去重的目的！因为不能对原数组进行排序也就没有办法对树层去重复！2、46全排列：排列问题由于顺序不同，即便元素完全相同也算是不同的结果，因此不再使用startIndex去排除掉前面取过的元素，直接使用used数组对其进行标记，避免在取一个子集时取到同一元素。3、47全排列 II：与上一题不同的是，原始数组里存在值相同的元素，所以要对树层进行去重。要对原始数组进行排序，并检查在本层for循环中该值是否已经使用。今天把无序关联式容器学了下，还把堆排复习了一下，写了堆排模板的代码。

今天完成了力扣93.复原IP地址、78.子集、90.子集II三道题，完全能自己写出来，就是过程中有点小错误，稍微调了一下。嘿嘿感觉回溯比二叉树简单。还把序列式容器、关联式容器的基本用法学了下，晚上写了个双向分区的快排模板，有点成就感。加油！我可以！

1.39组合总和。2.40组合总和II：题目给出的数组中可能含有重复元素值，不可以重复使用同一元素，但由于值重复，所以得到的组合里仍然有可能出现重复值（这是允许的）。同时，为了避免出现重复的组合，就必须对树层去重（树层就是组合的第一个元素取下一个元素，来收集下一个组合的过程），而不需要对树枝去重（树枝就是还在收集当下这个组合，不同元素可能值重复）。有点类似于三数之和的去重逻辑（收集下一个组合时，如果第一个元素与上个组合的第一个元素值相同，则说明本次收集结果一定被上次收集结果包含了）。要对数组提前进行排序，才方便后续去重。去重操作：if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false) continue;3.131.分割回文串：切割问题类似组合问题，将判断回文串的逻辑放在单层递归处理结点处，当前切割出来的子串如果是回文串，就加入到收集当前组合的数组中，如果不符合，就直接跳过本次循环。此外，注意startIndex到i的距离就是切割出来的子串。昨天晚上接了个导师电话，整个人都不好了，本来现在不焦虑，心态很平缓了，被他一说又焦虑了。。不行不能被他影响，就当他是在放屁，继续做我的事情。后面毕业论文就抽空写一下，应该也不难，我的实验的英文文章都已经发了，只要翻译一下，然后稍微扩充一下说的罗嗦一点就能凑出毕业论文了。满打满算最多一个礼拜就能搞完。现在还是要把精力放在刷题刷课上！

今天开始回溯算法部分的刷题了，由于回溯算法的思路比较固定，主要要注意的是不同的题处理部分的逻辑不一样。完成了77、206、17三道题void backtracking(参数) {if (终止条件) {存放结果;return;}for (遍历本层集合中的元素，有时可进行剪枝操作) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果；//注意回溯的不仅是暂存结果，一些变量可能也需要回撤。}}昨天终于把那个小项目磕过去了，关关难过关关过，然后今天新的一天就迎来好运了嘻嘻，一大早起来就在去年的口腔项目群收到最后一个最大的红包五十多哈哈哈哈，中午和朋友立马去吃了顿好的（黄豆鸡脚、藜蒿腊肉、糖醋里脊、番茄虾滑）犒劳一下最近这么辛苦的自己。做了个药企的笔试，还收到了下礼拜的健合无领导面，这几天在吃饭的时候可以拿b站上无领导面试的视频来下饭，多点了解。要把其他面试者当成朋友，就当跟他们在讨论一个有趣的事情，要一起出个主意，不要再像上回那样当场尬住了。要勇敢表达自己的想法，做出一点贡献，也希望不要再遇见那种很爱抢话太强势的人，要peace一点氛围好一点。这些都是可以练出来的，熟悉流程之后就不怕了。加油！同时开始学STL。

1.669. 修剪二叉搜索树（难）：递归法，当当前节点的值小于区间最小值，就遍历其右子树（左子树肯定都不符合条件，可以完全放弃了），直到返回符合条件的结点作为当前根节点（大于区间最大值时同理）。然后再继续处理下一层，即对它的左右结点分别作为根节点进行递归，最后将处理后得到的结果作为左右子节点返回给当前根节点。2.108.将有序数组转换为二叉搜索树：要求是平衡二叉搜索树，所以取数组中间值作为根节点，然后进行分割。再递归获取左右子树的根节点（根据分割点生成相对应的左右子树的区间）。3.538.把二叉搜索树转换为累加树：题目要求把当前结点与比它大的值都做一个相加操作。采用递归右中左遍历（结点值是倒序的），双指针执行相加操作。文本查询项目终于搞清楚了各个类之间的关系，以及函数调用的过程。但还是有点懵懵的，等后面学了面向对象的设计应该会有更深的理解。

1.235.二叉搜索树的最近公共祖先：递归法：利用二叉搜索树的特性，如果遇到的结点是第一次出现在[p,q]区间中的，那么这个结点一定是最近公共祖先，pq分别出现在这个结点的左右子树中，由这个结点分化出来的任何结点尽管值在[p,q]区间，但是它们都不是公共祖先。2.701.二叉搜索树中的插入操作：不考虑改变树结构的方法，只将其加入到树最后的空结点处。利用搜索树的特性，找到要插入结点的空结点处，并让此时的root->left/root->right等于新new出来的结点。3.450.删除二叉搜索树中的节点：//递归，多种情况分析//1.没找到待删除结点，遍历到空结点,直接返回if(root == NULL) return root;//找到待删除结点if(root->val == key){//2.待删除结点为叶子结点，直接删除该节点，并返回空结点if(root->left == NULL && root->right == NULL){delete root;return NULL;}//3.待删除结点左孩子为空，右孩子不为空，右孩子补位，并返回else if(root->left == NULL){TreeNode* node = root->right;delete root;return node;}//4.待删除结点右孩子为空，左孩子不为空，左孩子补位，并返回else if(root->right == NULL){TreeNode* node = root->left;delete root;return node;}//5.待删除结点左右孩子都不为空，//则将待删除节点的左子树放到待删除节点的右子树的最左面节点的左孩子的位置//并返回删除节点右孩子为新的根节点。else{TreeNode* cur = root->right;while(cur->left){cur = cur->left;}//找到右子树最左边结点的孩子位置cur->left = root->left;TreeNode* tmp = root;root = root->right;delete tmp;return root;}}if(root->val > key) root->left = deleteNode(root->left, key);if(root->val < key) root->right = deleteNode(root->right, key);return root;

1.530.二叉搜索树的最小绝对差：依然是利用二叉搜索树中序遍历得到的结点是有序的特性，对其进行递归中序遍历，并采用双指针法得到两个结点间的绝对差（中序遍历得到的有序数组中相邻两个结点间的绝对差一定是最小的，不需要再去与更远的结点进行比较，只需要比较两两相邻间的差值就够了），最后通过对绝对差进行不断更新就能获得最小绝对差。2.501.二叉搜索树中的众数： 递归中序遍历，双指针比较前后两个结点是否相等，同时更新maxValue，当count==maxValue时，将该元素加入到结果集中。如果count>maxValue，要注意更新maxValue的值，并清空结果集（失效）。注意递归过程中这些值都要是全局变量。3.236.二叉树的最近公共祖先：递归后序遍历，//左右子树都不为空，说明找到了pq，此时root就是最近公共祖先if(left != NULL && right != NULL) return root;//当一边找了了p/q，就直接返回这边的结点，//当层层递归结束，要么会只返回这个结点（这个结点本身就是最近公共祖先）//要么会与另外一支汇合，分别作为左右结点返回值，最后返回他们此时的根节点if(left != NULL && right == NULL) return left;else if(left == NULL && right != NULL) return right;else return NULL;这两天被文本查询卡住了，有点烦躁，把权游八季的解说看完了，现在心静下来了，后面继续刷算法，搞完这个文本查询就开始学STL了。不要放弃！