2022-03-07
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：4小时
学习题目：如图
遇到的问题：快慢指针的设置，数学推导有点理不清；指针的设置有点迷糊；
总结：多画图举例便于理解，了解STL模板；
2022-03-08
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：3小时
学习题目：如图
遇到的问题：做反转列表想不到几个指针进行指向且想到但写不出部分递归链表切割的方法；没学习STL:map的用法，花费时间去看STL：map；有效括号的问题没有讨论好情况，漏了一些情况；
总结：多画图举例便于理解，了解STL模板；再接再厉，加油。
2022-03-09
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：4小时
学习题目：如图
遇到的问题：解题思路能看懂，不能自己想到；
总结：分情况讨论，耐心；先进后出，辅助栈的应用；涉及到比较存取考虑栈；获取第一个最大最小，凹凸槽都设计到了比较遍历存取，考虑递增栈和递减栈的使用；栈不不止可以存取索引值，也要考虑存取索引的情况，然后去通过a[i]获取索引值；
栈的主要特性：先进后出，辅助栈，递增栈
2022-03-10
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：4小时
学习题目：如图
遇到的问题：不能散发思维，待提高脑回路；
总结：还是要注重情况的讨论，分情况->情况内条件->情况内操作；双端数组deque可以利用递减队列的特性，最大值存在表头；链表中反转部分链表要处理好断链和重新连接的部分，指针可以适当多设置；
2022-03-11
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：5小时
学习题目：如图
遇到的问题：逻辑顺序有待提高，不要急；
总结：快慢指针的应用，辅助栈的应用，pre指针的应用（断开链表需要用到）
2022-03-12
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：2小时
学习题目：排序算法和堆结构；
遇到的问题：堆的结构
总结：各种排序算法的应用、原理；堆的STL结构
2022-03-13
今天是否学习了训练营的内容：
答案：无
原因：适当放松
学习时长：×××
2022-03-14
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：4小时
学习题目：如图
遇到的问题：归并排序搞不明白，堆的概念不太懂；
总结：归并排序先分后治，不断递归分完整个列表，然后比较每个列表的大小进行更新；堆可以采用STL中的priority_queue，特性是最大/小值在队头，插入时就进行排序（priority_queue);
2022-03-15
今天是否学习了训练营的内容：
答案：是
原因：开题，核酸
学习时长：1H
学习题目：有序数组的平方
遇到的问题：想不到双指针的解题思路；
总结：优先队列的时间复杂度为O(n)，可以通过优先队列进行排序
2022-03-16
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：6小时
学习题目：如图
遇到的问题：归并排序的写法和运用；双指针的应用不够熟练；贪婪思想（优先最小满足最小）；哈希表的使用；
总结：
归并排序：先分后并;分：mergesort(arr,左1，右1)；mergesort(arr,左2，右2);并：merge(arr,左，中，右)。并又分为4个部分，首先左序列和右序列比较，然后左序列剩余的话添加（有的话），然后右序列剩余的话添加（有的话），更新排完序的数据和索引；
哈希表：插入相同的键值会覆盖前面输入的键值；判断map是否存在value，由语句if(map.find(value)map.end()),因为end()指向不存在的地址，如果等于end()代表不存在当前值。
2022-03-17
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：4小时
学习题目：如图
遇到的问题：栈的运用，贪心思维
总结：数字间不断比较，弹出舍弃考虑用栈；贪心解体思路，考虑记录每次能够最远或者最大的值然后比较
2022-03-18
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：4小时
学习题目：
#376 摆动序列
#15 三数之和
#16 最接近的三数之和
遇到的问题：双指针的使用，贪心思维
总结：三种状态分三种情况讨论，每种情况再细分；先排序，然后使用i，left和right指针的使用，不断遍历，知道找到所需条件，注意去重的操作；
2022-03-19
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：4小时
学习题目：
#134 加油站
#剑指offer40 最小的k个数
#23 合并K个升序链表
遇到的问题：快排，贪心，递归
总结：topK问题可以使用快排获取到前k个最小元素，如果k小于当前的mid则左递归，反之右递归，vector赋值nums.assgin(nums.begin(),nums.begin()+k);
合并K个升序链表，先不断分解链表，然后两辆合并，若是自己和自己则返回当前链表；
2022-03-21
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：4小时
学习题目：
遇到的问题：w无
总结：背好三种遍历的非递归模板，层序遍历使用队列+数组实现，锯齿形遍历使用队列+双端队列实现（可以分为插入前判断和遍历时判断两种思路）
2022-03-22
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：6.5小时
学习题目：
遇到的问题：二叉树的递归解题思路
总结：递归的重要思想不去管函数内部的细节是如何处理的，只看函数的作用以及输入与输出
2022-03-23
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：4小时
学习题目：
遇到的问题：二叉树的递归解题思路
总结：
完全二叉树的性质：左子树深度=右子树深度，代表右子树不满；
左子树深度！=右子树深度，代表右子树满；
每层满的结点数=2^深度-1；
stoi()函数：将字符串数字转化为数字；
to_string()函数：将数字转换为字符串数字；
二叉搜索树要删除结点，要么找右子树的最左结点进行替代，要么找左子树的最有子树替代。
2022-03-24
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：4小时
学习题目：
遇到的问题：二叉树的递归解题思路
总结：
平衡二叉树掌握自底向上的解法（往上传是否平衡）；
左叶子之和，递归求左右子树的左叶子值返回，当时左叶子返回当前值；
找树左下角的值，设定找回操作，左右递归子树，回溯思想，加入深度的参量；
修剪二叉搜索树：利用二叉搜索树性质（当前节点值大于high则右子树都大于high，直接嫁接左子树，然后修剪当前树，反之…)
二叉搜索树的最近公共祖先：利用性质，若是（root值-p值）*（root值-q值）>0代表在同一侧，反之不在同侧返回当前结点，在判断p在哪一侧，反复判断
二叉搜索树的最小绝对差：二叉搜索树中序遍历完后为递增的数组，计算两两插值更新最小值
2022-03-25
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：4小时
学习题目：
#143 重排链表
#876 链表的中间结点
#654 最大二叉树
遇到的问题：二叉树的递归解题思路，快慢指针的应用
总结：
利用快慢指针求取链表中点。slow指向的结点即为中点；
找到最大索引，左右递归建立最大子树
2022-03-28
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：5小时
学习题目：
遇到的问题：#4寻找两个正序数组的中位数
总结：
二分的过程就是一个不断移动right和left的过程，直到查到到满足条件的mid，根据题目不同设置的移动条件不同，同时注意边界范围的判断；
搜索二维矩阵有两种方法1、拉成移位数组，mid/列数=在二维矩阵的行数索引，mid%列数=在二维矩阵的列数索引；2、从左下角开始遍历，i–，j++；
做二分的题目注意索引的变化。
2022-03-29
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：5小时
学习题目：
遇到的问题：
总结：
二分法画图找判断条件，注意边界处理，最后返回什么；left和right初始值可以适当调整根据题目条件；
乘法注意超过int整形范围；
二进制运算（1、与自身减1相与或会消去最右边的一个1；2、2的幂次方的二进制只有一个1，与自身减1相与会变为0；3、统计1的个数只需统计可以与自身减1相与几次）
2022-03-30
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：5小时
学习题目：
遇到的问题：回溯问题
总结：
位运算查找一个出现一次的数字采用建立32长度数组，查找值为1的索引，进行复原；（右移j位与1相&即可只该位是否为1/0）（1左移i位累加即可返回二进制转换的十进制）；查找两个出现一次的数字先异或再分组（以最低有效位置来分组，lsp=(sumINT_MIN)?INT_MIN:sum&(-sum););字符串（不含有公共字母）将abcd…z化为26长度的二进制，有a则值为1，通过c=ch-‘a’和bit|=(1<<c)来将字符串生成26长度的二进制流，若相&为0代表没有公共字母；
回溯算法：设定另外的数组来判断是否已经占用，遍历原网格满足条件执行dfs操作，生成4个方向的坐标dx={-1,1,0,0},dy={0,0,-1,1};八个方向的坐标dx={-1,-1,-1,0,0,1,1,1},dy={-1,0,1,-1,1,-1,0,1},扩展方向newx=x+i*dx[j],newy=y+dy[j];若要回退需要保存上一状态，然后递归，回退上一状态。总而言之就是不断试探，不行就返回上一层
2022-03-31
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：5小时
学习题目：
遇到的问题：回溯问题
总结：
1.画出递归树
2.根据题意，确定结束条件
3.找准选择列表
4.判断是否需要剪枝（递归树可以看出）
5.做出选择，递归调用，进入下一层
6.撤销选择
常用去重操作可以在循环里面加上一个是否等于上一个元素的判断
2022-04-01
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：5小时
学习题目：
遇到的问题：回溯问题
总结：
2022-04-02
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：3小时
学习题目：
#1287 有序数组中出现次数超过25%的元素
#剑指offer39 数组中出现次数超过一半的数字
遇到的问题：
总结：
获取vector的值再最左边的位置auto l=lowewr_bound(arr.begin(),arr.end(),arr[i]),同理获取最右的位置upper_bound；
2022-04-03
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：5小时
学习题目：
遇到的问题：动态规划
总结：
DP五部曲：
1、确定dp数组以及下标的含义；
2、确定递推公式；
3、dp数组如何初始化；
4、确定遍历顺序；
5、距离推导dp数组。
完全背包：有n种物品，每种物品有无限个；
0-1背包：有n种物品，每种物品只有1个；暴力破解方法即回溯。
组合不强调元素之间的顺序，排列强调元素之间的顺序；
如果求组合数就是外层for循环遍历物品，内层for循环遍历背包；
如果求排列数就是外层for循环遍历背包，内层for循环遍历物品；
获取vector最大值的写法：auto maxidx=max_element(arr);cout<<*maxidx<<endl;
2022-04-04
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：3小时
学习题目：
#1287 有序数组中出现次数超过25%的元素
#剑指offer39 数组中出现次数超过一半的数字
遇到的问题：
总结：
获取vector的值再最左边的位置auto l=lowewr_bound(arr.begin(),arr.end(),arr[i]),同理获取最右的位置upper_bound；
2022-04-05
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：5小时
学习题目：
#72 编辑距离
#121 买卖股票的最佳时机
#122 买卖股票的最佳时机Ⅱ
#123 买卖股票的最佳时机Ⅲ
#188 买卖股票的最佳时机Ⅳ
#309 买卖股票的最佳时机含冷冻期
#714 买卖股票的最佳时机含手续费
遇到的问题：动态规划
总结：
一、编辑距离注意三个操作的步骤，构建二维数组，dp表示word1前i个字符变为word2前j个字符使用的最少操作次数；
二、买卖股票的最佳时机，限定交易次数k=1；买卖股票的最佳时机Ⅱ，交易次数无限次k=∞；买卖股票的最佳时机Ⅲ，交易次数为k=2次；买卖股票的最佳时机Ⅳ，最多为k次；买卖股票的最佳时机含冷冻期，多了一个状态（冷冻期）；买卖股票的最佳时机含手续费，在每次交易的时候需要扣除手续费；
构建三维数组dp[i][k][0/1]，[0]表示在第i天，最多进行了k次交易后不持有股票，收盘后的收益；[1]表示在第i天，最多进行了k次交易持有股票的，收盘后的收益；多一个状态[2]即冷冻期，冷冻期只和前一天持有股票状态有关；当k无限制时，不考虑k维度，构建二维数组即可；递推dp数组与前天[i-1]状态持有和不持有的关系；
2022-04-06
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：5小时
学习题目：
遇到的问题：动态规划
总结：
完全平方数并不显示的给出nums数组，需要自己构建，解体思路与找零钱相同；
当正向DP思路发现有多个变量影响时，注意反向DP思路，从尾到头求解；
2022-04-07
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：5小时
学习题目：
遇到的问题：动态规划
总结：
分割等和子集有个继承的技巧，同时取决于上一层能不能拼凑出j-nums[i]的数字或者直接用上一层存在的数字；
打家劫舍2：循环数组，考虑两种情况分成两种数组，第一个是只考虑偷了第一家最后一家不能偷的情况，因此数组长度为(nums.begin(),nums.end()-1);第二个是偷了最后一家，第一家就不能偷的情况因此数组长度为(nums.begin()+1,nums.end())，然后对这两个数组分别执行求最大值dp，取两者最大；
打家劫舍3：二叉树的情况，为每个结点设定两种状态[0/1]偷还是不偷，递归左右结点，若是空则返回{0,0}，不然考虑选还是不选，选了的话,左右节点就不能选dp[1]=left[0]+right[0]+node->val，没选的话左右节点可以考虑选还是不选，取最大的来dp[0]=max(left(0),left(1))+max(right(0),right(1));最后返回dp求得根节点的状态量取最大；
2022-04-08、09
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：5小时
学习题目：
遇到的问题：动态规划
总结：
·括号生成有个值传递的点，注意看看；backtrack函数可以不用for循环当循环列表很少的情况，可以直接考虑双递归完成函数功能；
·最长连续递增序列：dp[i]表示第i个元素的最长连续递增序列；
·最长公共子序列：dp[i][j]为text1前i个字符和text2前j个字符最长的子序列。如果第
i个字符和第j个字符相同，则查找区间(i+1~j-1)的dp值+1，不然取左上最大值。
·！最长重复子数组：子数组必须是要连续的。dp[i][j]表示长度为i，末尾项为n1[i-1]和子数组和长度为j，末尾项为n2[j-1]的子数组两者的最长重复子数组。两者元素相同则取长度为i-1和j-1的最长公共子数组+1；dp定义很重要
·最长回文子序列：dp[i][j]第i个字符到第j个字符的最长回文子串。i从后往前，j从i往后，若是s[i]s[j]，则取第i+1个字符到第j-1个字符的最长回文子串数+2(因为两个字符相等）；否则取第i+1到j的最长回文子序列值或者第i到j-1的最长回文子序列值即max(dp[i+1][j], dp[i][j-1]);
·最长回文子串：dp[i][j]=true/false：第i个字符到第j个字符是不是回文串。i从后往前，j从i+1往后，如果s[i]s[j]，并且i+1到j-1是回文子串，则dp[i][j]=true，否则=false（有特殊情况即长度为2的情况，需要单独处理为true）记录长度和起始位置，不断更新。
总而言之：
1、处理字符串的时候需要从后往前遍历，一般dp含义为第i个字符到第j个字符是不是或最大××。
2、处理子数组和子序列，子数组需要连续。子序列不需要连续；子序列可以想当然，子数组需要设定不同的dp含义。
2022-04-11
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：4小时
学习题目：
遇到的问题：递归
总结：
二分查找的运用，递归的运用，深度搜索的运用。
当dfs函数有返回值时注意返回值的编写；
2022-04-12
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：4小时
学习题目：
遇到的问题：二叉树递归
总结：
树的子结构问题：分割子问题为以当前结点为根是否包含B子树；
·对称的二叉树：对比左子树的左节点和右子树的右节点满足条件与否，对比左子树的右节点和右子树的左节点满足条件与否；
·包含min函数的栈：构建一个最小栈，每次入栈元素比当前最小栈栈顶小则入栈，反之不入栈；
2022-04-13
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：4小时
学习题目：
#剑指offer系列
#33 二叉搜索树的后序遍历序列
#35 复杂链表的复制
#36 二叉搜索树与双向链表
#40 最小的k个数
#41 数据流的中位数
#42 连续子数组的最大和
遇到的问题：递归问题，快排不够熟练，二叉搜索树的特性
总结：
·二叉搜索树的后续遍历序列中，最后一个必定是根节点，左子树和右子树成片的出现，找到第一个右子树起点，判断后面的结点是否大于根值，不是返回false，直到没有结点判断；
·复杂链表的复制：掌握好哈希映射关系；
·二叉搜索树与双向链表：需要head和pre两个全局结点用于指向开头元素和最后一个元素，当pre为空时当前结点为头结点，当pre不为空时进行双向连接操作pre->right=cur，然后将cur->left连接到pre，左子树就完成，pre指向cur结点进行右子树递归；
·最小的k个数：按照快排写法，只是在quicksort函数里进行不同的判断，当midk-1时直接返回当前序列，当mid<k-1时递归排序mid+1~right部分，反之则递归排序left~mid-1部分；
·数据流的中位数：建立大顶堆和小顶堆，保持递增的方向，保证小顶堆的元素比大顶堆多一个，通过两个堆的size来确定先进入哪个堆再弹出进入到另一个堆；
·连续子数组的最大和：dp[i]表示以i为结尾的子数组的最大和，当前面dp[i-1]为负数时，dp[i]=nums[i]，否则dp[i]=dp[i-1]+nums[i]；
2022-04-15
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：4小时
学习题目：
遇到的问题：快排思想
总结：
·。把数组拍成最小的数：利用快排思想，选取0索引位置进行拼接，比较字符串组成的数字不断移位，利用str1.compare（str2）来比较组成的数字大小，然后对两边同样执行操作即可。
·把数字翻译成字符串：通过距离找准状态方程dp[i]=dp[i-1]+dp[i-2];同时要注意考虑前面是0的情况；
·最长不含重复字符的子字符串：利用哈希表+DP实现索引位置的记录，若是哈希表没记录当前元素则dp[i]=dp[i-1]+1,已经记录的话则比较dp[i-1]+1和i-mp[s[i]]两者的最小值，出现的情况有两种：1\abbcd，两个连在一起；2、abcdba不连在一起，罗列出来即可得到状态转移方程
2022-04-18
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：4小时
学习题目：
遇到的问题：
总结：
·扑克牌中的顺子：一、排序记录0的个数，查看非0元素的差值与0个数的比较；二、哈希表，记录最大值与最小值，遇0则不做处理，重复元素返回fasle，最后若是最大值和最小值相差<5则返回true；
·滑动窗口的最大值：新建递增序列，对头存储最大值，每次入队时与队尾元素进行比较，如果小于队尾元素则直接入队，如果大于队尾元素，则不断弹出直到队尾大于当前元素或队空，通过下标[i-k]来获取要出队的元素，若是出队元素是队头元素则对头元素也许出队；
·左旋字符串：原地变化一般都采用局部反转再全局反转或者全局反转再局部反转，此题进行一次全局反转再进行两次局部反转；
·和为s的连续正数序列：因为序列排序可考虑比哈希表更佳的方法，利用滑动窗口，不断维护窗口的长度，利用累和公式(a0+an)n/2来进行左区间和右区间的移动，若是大于sum则左区间++，若是小于sum则右区间++，等于sum则记录该答案；vector求和函数：accumulate(arr.begin(),arr.end(),num)，num为起始值；
·和为s的两个数字：双指针计算，若是大于target则right–，否则left++，相等则返回；
·平衡二叉树：利用自底向上的做法，再计算深度的时候，若发现已经有非平衡二叉树则直接返回-1，当出现-1时则直接判断为false；
2022-04-19
今天是否学习了训练营的内容：
答案：有
原因：pass
学习时长：4小时
学习题目：
遇到的问题：
总结：
·数组中数字出现的次数：当需要寻找两个数字时，考虑使用分组方法，找出两者异或的最低有效位lsp=(sumINT_MIN)? sum : sum&(-sum); 然后再通过遍历一遍元素，若与lsp相与为0则为一组，其余为一组；
·二叉树的最近公共祖先：利用二叉树的递归性质，记录左边是否找到pq结点，记录右边是否找到pq结点，判断四种情况，1若是left和right都为空则返回空，2若left空则返回找到的right，3若right空则返回找到的left，若两者都找到了则返回当前结点，因为再当前结点的左右子树中找到了pq；
·二叉搜索树的最近公共祖先：利用搜索二叉树的性质，大于根结点的值分布在右子树，小于根结点的值在左子树，如果p值-root值乘q值-root值0则根据p值-root值大于或小于0来决定递归左子树还是右子树，当p值-root值小于0，代表pq都在左子树，此时递归左子树找祖先；p值-root值大于0则递归右子树找祖先；
·构建乘积数组：构建左乘积数组和右乘积数组，分别代表当前元素的左元素乘积值和右元素乘积值，需要初始化边界为1；
·股票的最大利润：设定三维数组dp[i][j][0/1],代表在第i天的收盘时候最多进行了j次交易的持有或不持有股票的最大收益，dp[i][j][0]取决于两种情况1前天也不持有，2前天持有但是卖了，取两者最大值;dp[i][j][1]取决于两种情况1前天持有不变，2前天不持有但是买入了第i天的股票；初始化所有dp[0][j][0]=0和dp[0][j][1]=-prices[0];
·圆圈中最后剩下的数字：通过理解约瑟夫环，从后往前推导f(n,m)=(f(n-1)+m)%n，最后胜利者的下标为0因为只剩下了一个人；
·求1+2+。。。+n：因为使用递归f=n+f(n-1)可以得出答案，但是由于不能使用if语句判断终止条件，因此利用&&和||的短路性质，当A&&B时，A为false时，B将不会执行；A||B当A为true时B不会执行，因此利用 n && (n+=sum_n-1);return n;
