代码随想录算法训练营第五十天（总结与感想）

1.数组篇

在二分查找题目中学习到了一个新名词：循环不变量。用来定义数组边界的原则，如左闭右闭，左闭右开，左开右开，左开右闭。其中闭：是代表当前区间包含边界，开：是代表不包含当前边界。如：[0,7):实际表示包含0，但是不包含7的区间
在移除元素，有序数组的平方，长度最小子数组中，学习到了双指针的各种形式的应用：同向快慢指针，头尾双向快慢指针，滑动窗口双指针。

在螺旋矩阵II中，对循环不变量更是体现的淋漓尽致。需要在模拟螺旋过程中，保持同一种循环不变量原则。

2.链表篇

在链表篇中，说实话在我这种水平的搬砖佬中着实很少用到，只有无尽的curd。加上php语言对数组的封装便利性，在业务层面上往往很少碰到对应的使用场景所以一刷碰到的时候相对的就会相对生疏。相对的队列与栈也是。在刷道这几篇的时候都有种陌生感同时也有茅塞顿开的感觉，十分神奇。在链表篇中，学习了链表的基础知识与应用：

链表的类型：单链表，双链表，循环列表
链表的结构：节点上存储的元素 + 指向下/上一个节点的指针
链表的增删改查：查和改没啥好说的，控制指针寻找目标值，找到就可以修改了。主要注意的是：增和删。

增加节点
删除节点

链表与数组的区别
链表解题的重要方法：虚拟头结点。目的是：原链表的所有节点就都可以按照统一的方式进行操作了。以移除元素为例：

3.哈希篇

在哈希篇中，由于php数组的语言特性，数组被封装的非常便利：集合了队列，栈，哈希的一些特性。十分强大的同时，也给刷算法题的时候带来了一些不友好。对相应数据类型的应用性上会有一定的迷惑性，不利于理解各种数据类型上的区别。
总结一下，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

4.字符串篇

字符串篇中主要还是考察双指针的一些应用，和对字符串的一些操作。但是这里缺碰到了第一个超纲的算法：KMP。不得不说，确实有点抽象。视频：什么前缀后缀，这样那样然后在这样。诶！就解题了。我：？？？。

5.栈与队列篇

在栈和队列中，也是因为应用的比较少。所以对这块不是那么熟悉，刷起来有点吃力。通过用栈实现队列，用队列实现栈的双重折磨，总算是对这两的概念与逻辑过程有了一定的理解。

6.二叉树篇

二叉树篇应该是最掌握的最不好的一部分了，这部分刚好是过年期间，落下了不少，在后面狂补，掌握程度不高。加上本身对递归的理解不是很好。有机会二刷的话好好再补补！！！
二叉树篇中：主要学习了对各种二叉树的各种遍历解题。层次遍历十分好理解，但是解题适用性上没有递归那么好。一开始偷懒只学了层序遍历，到后面不得不用递归时，发现已经有点力不从心了。还有二叉树中期的构造二叉树，以及后期对二叉树的插入操作，删除操作以及裁剪操作等。都十分考验对二叉树遍历的与结构的熟悉程度。

深度优先遍历

前序遍历（递归法，迭代法）
中序遍历（递归法，迭代法）
后序遍历（递归法，迭代法）

广度优先遍历

层次遍历（迭代法）

7.回溯算法篇

回溯算法，感觉算是对二叉树的一种延伸。总结来说就是遍历 + 递归。对上一篇二叉树中递归的回溯过程进行了详细的讲解与演示，但是相对的也会复杂不少。好在这篇中有卡哥的回溯模版，嘎嘎好用。
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}
遍历过程：

回溯法，一般可以解决如下几种问题：

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

8.贪心算法篇

贪心算法篇：这篇没有特定的解题规律，只能通过刷题来积累对应题型的解法，没有固定的套路。所以整体刷下来的感觉也是，没有之前篇章的联系性强。唯一觉得有套路和联系性的部分就是重叠区间部分。贪心部分题型开始需要有比较好的抽象能力，往往需要从题目中局部，然后再局部中找到最优解，从而推出最优解。这部分中对跳跃游戏这类题型，掌握不太好，没能充分理解；在摆动子序列和根据身高重建队列，分发糖果中，解题思路会让人决定豁然开朗，还能这么解题，思路十分清晰，甚至比中等题跳跃游戏好理解；最后是重叠区间，对边界的动态更新，从而判断持续重叠区间的想法也十分妙。
贪心算法一般分为如下四步：

将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解

9.动态规划篇

动态规划篇：这系列题做下来，真的会对自己的逻辑思维能力感受匮乏。“这题还能这样解？”，“这解法不看题解是能想出来的吗？”这是我刷这系列题出现的最多的感想。感觉上动态规划跟传统意义上的解题有挺大区别的，像是以前高中的规律题，需要先找规律，然后才能推导出最后结果，最后举例验证结果。这部分也是题数最多的一部分，一刷只能说对动态规划有个初步印象和解题思路，也是需要在二刷中继续深入理解。

动态规划题型：

基础问题：斐波那契，爬楼梯，不同路径。
背包问题：01背包，完全背包，多重背包。
打家劫舍：打家劫舍系列。
股票问题：最佳买卖股票时机系列。
子序列问题：子序列，编辑距离，回文串。

动态规划解题五部曲：

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

10.单调栈篇

单调栈篇：主要的解题思路是模拟入栈过程，使得栈内元素保持单调递增或是单调递减的过程。比较考验对栈类的使用和对出入栈流程的熟悉程度。过程不难理解，但是也属于是之前没接触过的一种题型。
主要情况，分析清楚，基本可以解题了：

情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

11.一刷完结感想

没想到最后自己坚持打卡完了，感谢卡哥的开源与内容制作。讲的真的很棒！也感谢公司这段时间的赋闲！不然真的很难坚持的下来。
这是大学从接触CS以来，第一次刷算法题目。不得不说开始的有点晚，很多人想必都是从大学时期就开始接触了。由于自身原因在大学的时候还没知道leetcode这东西（虽然知道了也坚持不下来）。这次一刷完结，接触到了很多没见过的题型和解题思路，眼界开阔了不少。一方面锻炼了自己的编码能力，另一方面也开阔了自己的思维能力，真的受益良多。有机会的话还有参加二刷训练营，因为一刷的过程中其实还有很多理解不到位的地方。希望那时候，也能坚持下来，温故而知新。
一刷下来，发现PHP语言相对其他语言的刷题人数要少很多。不太清楚是啥原因导致的。基本从二叉树章节开始，训练营就基本没有PHP语言的题解了。甚至在leetcode上的题解数量也会比其他语言的要少很多。还有个想吐槽的点就是，leetcode的编辑器似乎对PHP语言的$变量符号不太友好，每次使用联想的变量都需要自己补全$符号，经常忘记导致的运行报错。

php