1、Kmp匹配算法：开始的时候还是遍历targetstring ，根据findstring的每个字符去查找，这样需要遍历所有的字符，而每个字符的匹配都需要进行findstring里面的字符进行比对，那么我们kmp所起的作用是，根据findstring字符来得到字符的排布规则，知道某些字符是否是已经重复了，从而得到findstring的规则，当一次对比不成功的时候就根据对比到哪一位后再进行比对的字符位置来进行对于targetstring的偏移，这样咱们就可以省去不需要的比对次数；具体的finstring的规则是前缀和后缀查找交集，得到的交集的字符串的长度就是权值，这时候偏移量为findstring长度减去权值，这时候就疑问了为什么？这里详细说下思路，权值的作用是为了知道当前这一字符与前面重复的字符的所在位，比如abcabc 对应的就是000123 ,红色的abc是没有重复了，蓝色的abc是和前面的组合重复的，所以蓝色abc对应的是123，这样有什么作用呢，如果我比对的时候abca满足了到b的时候不满足，应该下一次的比对了，我发现abc都是0代表是和我自己其他部分和这个部分是不相同的，既然是不相同了也就可以不比对了，如果还是不明白，举个例子，abcaz是targetstring，abcabc是findstring，我比对的时候黄色部分是相同的，到了abca的位置，这时候我们发现a是可以比对的位置因为我开头的就是a，那么我们终于发现了，每次我们都是比对完了，再去下一个字符z，但是我们不知道findstring自己重复的位置，那么就需要减去重复的位数，这也是前缀和后缀进行比对的作用。这就是kmp匹配算法。
2、快速排序是一种进行数组分割的算法，减少对比次数来优化比较次数的算法，一般把第一个元素当做基准数，我们的目的就是把基准数当做小数数组与大数数组的分割元素，办法就是分辨从原始数组两端进行遍历，左边寻找比基准数大的数，右边寻找比基准数小的数，当这两个数组相遇的时候，相遇的数字就是我们知道的小数与大数的边界，由于我们以首元素当做基准数，那么就说明基准数默认被分配在了小数数组，所以左边开始查找比基准数大的操作是不能包括比基准数大的数的，因为按照我们的设计，基准数是小数数组的尾元素。
所以这里有两种办法来达到（这两种都不考虑相遇前交换）：
a、左边先开始，当我们找到一个比基准数大的数时候，因为我们找的是小数数组的元素，不能比基准数大，所以我们就退回到前一位。（ps：如果是不考虑相遇前的交换其实不必开启大数数组的查找了，这里为了逻辑的对仗也写上大数的查找操作）
b、右边开始，当我们找到一个比基准数小的数时候，因为我们找的是小数数组，那么这比基准数小的肯定是小数，那么就直接与基准数交换就成功了（ps：因为我们不考虑相遇前交换。）
上面是不考虑相遇前交换的过程的，如果我们要考虑相遇前需要交换的数组，那么1方法就比较麻烦了，我们需要考虑是否是相遇了，具体操作是，找到大于基准数的元素不先不回退到上一位，直到两个数组相遇的时候，这时候把相遇的数组再向前回退一位，再进行与基准数的交换，发现没总是需要退回一步。
而第二种，先从右边开始，保持了小数数组的数据纯洁，与基准数交换后就变成了中间元素，满足了我们的需求。
还是第二种方式比较省事省心，所以我们一般是从右边开始遍历。
3、动态规划，LIS背包问题：一个包里面的空间是有限的，现在有几个物品，大小不同，价值不同，求包装满物品的最大值是多少。这个就是典型的动态规划问题，先说简单理解再总结公式；随便找一个物品，考虑装不装这个物品，比对装与不装的状态哪种选择价值最大，分解为两个问题的表达式，装与不装的表达式，这个表达式会继续进行分解为更多的表达式，这些表达式都是同一种结构，就是比对是否装与不装，直到出现装了就超过背包负载的情况的时候，就不再继续向下比对了。那么咱们公式就可以总结为 d(i) = MAX(d(i-1)+m(i):{s >S(i),s-S(i)},d(i-1)); :{s >S(i),s-S(i)}的是总空间减去i的空间（s代表总空间），并且总空间要>S(i)的情况下,要不空间就成了负数了,m()的意思就是获取物品的金额。直到不满足:{s >S(i),s-S(i)}的条件出现的时候停止，开始统计各个选择的物品的金额，在代码里面表示就是，当条件不满足的时候递归开始出栈。
4、在二分查找的变种问题时候，允许出现重复，但是需要找到从左开始第一个key对于的index，这时候需要做的操作就是在找到key的时候继续向左进行查找，这样查找下去，总会出现左边没有key的情况，这时候high变成了最后一个key的index-1（也就是middle是key了），只时候就会让low进行增加的操作，而这是徒劳的，肯定会出现low和high相同的情况，这样middle index就是high了，当然这个数也是不满足的，所以会让low = mid +1 操作，这样low index对应的value就是刚刚的hight+1的key了，所以说low index就是最开始出现的key（从左到右）。
5、标记法，如果要区分是否满足所有的给定非重复元素都会使用的这个题设，那么简单的做法就是标记法，就是在一个新的数组里面，按照对应的下标进行赋值权值，e.g. 现在要知道0-9，保证每个数字只出现一次，a：[Int] ，那么a需要排列组合一下，我只需要把循环a[i]存到book:[Int]里面 book[a[i]] = 1 ,这样book的对应数字下标的值为1，这样计算book数组的元素和是否为0-9的数字数目，这样就判断0-9的数字是否都用上了。
6、深度优先搜索简单的理解为，现在这一步怎么做，因为下一步也是需要这么去做的，所以当前这一步的处理是非常重要的，这里以3个盒子和3个数为例写一下思路，首先需要判断当前盒子能放几种数，所以针对这一盒子需要循环去遍历，而下一个盒子是，当前盒子的数-1的，所以咱们标记当前盒子，这下一个盒子知道了当前盒子是不能用的，也就不会去遍历，然后下个盒子以此类推最终会到盒子数组的边缘，这时候只需要判断边缘，这时候就说明这种情况下，全排列的盒子里面方的数都完成了，所以进行打印，然后返回递归，开始下一种排列。理解起来这个好像就是动态规划的思想，通过递归不断的缩小空间不断的去代入最后一个空间解决了，递归后就全都解决了，这样的思想对于处理当前数会动态改变而影响后面计算的时候 ，可以说是无往不利，所以总结一下 1、要寻找当前对后面的影响关系。 2、寻找递归的跳出条件。 3、一次解决循环的逻辑。 由此就可以看出，咱们的全排列问题，1 当前箱子用了一个数后面不能用了 2 箱子都用完了就是最后结果 3 操作逻辑每次去往箱子里填数（当然还要考虑递归的时候，清除当前箱子填充状态的操作）
7、广度优先搜索，与深度优先搜索不同，这里不使用递归，而是通过标记法，根据当前点进行逐层递进，把递进的点都放到一个queue里面（忽略重复的），这样把所有的点都放到队列里面，根据队列里的点进行条件的判断，只要满足条件退出后就可得解，这里不像深度优先一样使用递归，而是根据当前点把下一步应该走的都遍历出来存放到队列里，这种方式和递归有什么区别呢？我的理解是递归使用的时候每次都去走对应的递归逻辑直到找到点，通过这样一层一层的迭代来找到解，而广度优先并不是要一层一层计算，他不需要连贯性，也就是这个不需要刚刚节点的信息，广度优先只是一直向下找直到找到结束后根据记录的值来算一下解，所以这两个的区别就是广度占用内存较多（因为需要不停的去记录），而深度是每层都去重新去遍历，不需要队列来记录，将要走的点，更形象一点，深度是往下穿每次都去根据下一个点的未标记点进行逐层递进，而广度是把紧邻的点先遍历再从周围的点向外逐渐查找（有点像辐射），更形象一下（深度像个贪吃蛇，一直往前走；广度像是辐射工兵，一点一点辐射掉范围。） 深度优先就是，从初始点出发，不断向前走，如果碰到死路了，就往回走一步，尝试另一条路，直到发现了目标位置。这种不撞南墙不回头的方法，即使成功也不一定找到一条好路，但好处是需要记住的位置比较少。广度优先就是，从初始点出发，把所有可能的路径都走一遍，如果里面没有目标位置，则尝试把所有两步能够到的位置都走一遍，看有没有目标位置；如果还不行，则尝试所有三步可以到的位置。这种方法，一定可以找到一条最短路径，但需要记忆的内容实在很多，要量力而行。所以深度优先很快会发现一个解，而广度优先要比深度慢发现解。
8、Dijkstra算法是一种广度优先的算法，单源求最短路径，要从这个点开始寻找离这个顶点最近的顶点，然后去寻找这个最近的点相邻的顶点，把当前点到相邻的点的路径和原点到相邻点的路径进行比对，如果是比原点到邻点的距离小，那么就更新这个点，所以会把这个节点所能触及的点都进行更新(如比到原点的距离更小），然后开始下一次循环，还是会找距离原点最近的点开始，这样一直循环下去直到找满这个数组。为什么要这样呢？因为”确定值“这个设定，寻找的都是距离原点最近的顶点，所以这个点就是确定距离最近的点，如果每次松弛找到的点不是最短的路径，自然是由相邻的点去计算，但是总归有一个最近的点是会更新一个最短的松弛，那么这时候这个点就是最短的权值了，这样就能得到原点的最短距离的数组了。感觉上这个算法就像无孔不入的水一样，一直在寻找距离原点最近的点进行遍历，慢慢的把所有的点都确定值，一直在做的事就是根据最短确定值去确定后面的值，而且是最短的顶点去确定的，即使你这个点有很多边，那也没关系，因为总有最短的一条，这样就不断的趋近最短结果，最终成功。更加形象的比喻一下，这个求最短的确认值就是一根绳子，以这根绳子的去扫描点，这时候以绳子顶点去扫描出一些点，这些点进行和原点和确认值点进行比对，取min后的值，而且每次确认值的点都是在最短路径里面找的，这就相当于绳子又增加一些长度继续去寻找其他的顶点的最短路径，只要你能和原点通过边直接或间接连起来，那么你就有相连的顶点会走这个程序，你这个点就能确定最短路径，其实就像咱们为了扫中所有的顶点就不断伸长绳子，去扫顶点一样，这个比喻很形象，而绳子的加长就是确认值的确定过程，一直找的是最短也就是这个绳子最短的邻点作为绳子下一步的生长点，这样绳子不断生长直到所有的点成为确认点（在绳子的覆盖范围内）。这是不是就是贪心算法？？有待解答！其实这个算法可以形象的说是一个由原点开始最短边组成的三角形，对边和临边的和是否小于斜边的问题，如果小于就进行更新顶点的最短距离权值，并把当前顶点设置为确认值点，后面就是循环去查找最短边。
9、并查集的作用是解决找出图的连通性问题上的，根据给出的连通条件找出所有顶点的连通方案，简单的说就是要把顶点分群，找到群主，判断每个顶点的群主是否相同，群主相同则代表在一个群，群主不同继续下次循环，直到所有的点遍历完毕，在结果数组里面，找到多少个不同的数就是多少个群主。具体实现上就是一个边的数组，不断的把这些边进行并查集操作找出群主的过程。
10、最小生成树，先把所有的边进行快速排序，进行并查集（确保顶点之间的连通性），从小到大去把边的两端去进行并查集操作，如果是同一个群主，那么就忽略，继续进行查找，直到找到的边数为n-1次跳出循环，结果集可以写到数组里也可以只记录边的周长。这样我们发现要找到最小生成树，需要遍历所有的边，我们可以借鉴前面学习的dijkstra单源最短路径的思想来实现，只不过现在不是单源的，而是每次都要求出这个顶点对于群最短距离边进行松弛，这样一直进行松弛，一直进行确认点，最终循环完毕，组成的数组就是最小生成树。再次，我们可以用堆来优化快排的时间复杂度，其实道理也是一样，但是每次都去把最小堆进行梳理，最后n-1次得到的结果就是最小生成树。
11、选择排序，还是和冒泡比较相似，循环每个点，“选择”当前点和后面数组里的最小点进行交换，由此叫做选择排序，而冒泡排序是每次遍历得出一个最大值往最后放，直到遍历完成，其实差别都不是很大，只是选择排序是直接找到最小的值和当前值进行一次交换，而冒泡是比对过程中可能进行很多次交换。
12、插入排序，插入排序是先选定数组的前半段为一个子数组，变量所有的点都放到这个子数组里面，但是每次都是使用“插入”的方式把当前点放到子数组里面的方法，直到这个子数组囊括了所有的点，所以这个叫做插入排序，插入排序的好处是不用每次都去寻找最小数，而是把你的目标数插入到一个有序的数组内，所以就不用遍历剩下的所有点寻找最小值。
13、归并排序，主要思想就是递归的思想来解决排序，先这样想，把目标数组分成两个有序数组，然后合并有序数组，成为一个有序的数组，而如何形成有序数组呢，我们再递归的去思考这个问题可以把当前非有序的数组再分成两个有序的数组进行排序，这样不断分解下去，直到成为一个元素的数组，这时候我们认为这个1个元素的数组就是有序的，就问题成为了合并有序数组的过程，递归只需要写合并数组的操作就可以了，然后递归调用，很是easy，然后关注一下怎么去合并数组，先是分为3个数组，分别是前半部分、后半部分、结果数组，把前俩数组合到结果数组就算成功，直接的取这俩数组的元素去比对，小的就放到结果数组里，谁小谁就向后拨动指针，大的指针不变，但是有个情况就是当遍历完了一个数组后，发现另外一个数组还没有结束，这时候把另外一个数组的所有元素都放到结果数组里面（因为是有序），总结一下这个排序算法，就是利用有序数组不用每次都去比对的特性，节省比对次数。归并排序重点在于合并。
14、双路快排和一般的用一个for循环写的快排的区别是在于如果出现大量的重复元素的时候，会出现无法找到平衡点，就会找到一个非常大的前组或者后组，这样算法就和有序数组所造成的一个样变成了O（n^2)的算法复杂度，有序是使用随机快排来解决，遇到大量重复的元素就使用双路快排，前后两个数组，把与目标值相等的值分到两个数组里面然后进行排序，这样就又能差不多平衡分配两个数组，就又可以进行快速排序了。记住了双路的作用是把与目标值相等的元素分配到两个数组里面，这样就不会出现单纯的遍历会把与目标值相同的元素放到同一个数组中的情况，以保持两个数组的大小平衡，这样才能确保运算的速度。快速排序的重点在于确定目标元素的位置。
15、再说递归，递归其实是解决问题的好办法，就像击鼓传花一样，这样传下去只有两个可能，找到和找不到，递归只是在一个结构上进行传递，最终找到再返回上一层的一个手段，还是需要深入的思考，灵活的使用。只要是递归就可以带着当前函数到达最底层，如果一个函数里面调用了两次递归（类似二叉树前序遍历），那么由left到达了最左端的子树，那么继续往下走的时候就是用的当前node节点的来计算right，所以递归就是把node不停向下走的过程，只要node往下走这个递归过程就结束了，也就是第一次递归是递归的入口，另外一个的递归调用也就是那一层的调用了；当回溯到了最上层的时候，这时候函数执行了一半了开始继续向下进行就是right开始执行又一次的递归开始了，这样是右边开始向下一直递归，和左边类似。我看到了递归就是一个树的结构，所以解决问题的时候要根据两点 1、根据不同条件来进行递归，这样有助于形成统一的遍历“公式” 2、找到树的尽头，也就是找到递归的跳出条件。
16、最小生成树，prim是一种根据切分定理通过顶点来筛选有权边的思想，prim筛选有权边并根据最小索引堆来寻找最小横切边，直到索引堆为空，说白了就是索引堆来维护着寻找最短边的责任。，而kruskal也是要筛选边，只不过是先排序边后，通过树中不能有环的性质，采用并查集来判断顶点是否满足最小生成树，最终得到最小生成树。
17、关于求最中间数的问题，公式是（r-l)/2 + l ,不管是在什么情况下都是成立的，即使是0为起点或者1为起点都一样，因为这个是忽略了起点的一种公式，可以理解为r-l是中间的差值，差值/2 分为两个情况，差值分别为奇数偶数，当差值为奇数的时候说明从l到r的个数为偶数（因为是差值么，所以是没有计算l位元素的），这时候我们程序是int值除以2是省略小数点的，比如5是差值，现在5/2是2.5，结果变为了2，我们是从1开始计算的也就是1-6的中间值，那么前面开始的部分已经占用了1，我除以二舍去了小数，也就是让另外一部分加上了1（更简单的理解是奇数分配一方总会比另一方面多1，那么前面部分在剪发的时候拿到了1，那再次平均的时候让后面比前面多1，这样除以后的值是省略小数的，加上前面占用的l位置的1，这样左右两边个数就对等了），然后我把l加上差值/2就是最后的mid，那么再来想一下差值是6，现在计算1-7的中间值，本身就是7个数，这是一个奇数分配，那么本身最中间的数就是平衡的数，所以当我们计算r-l的时候已经先把这个数占位放到了左边，而且因为奇数减了1，剩下的除以二就是整除了，正好是平衡的单边的数字个数，所以l（占位）+平衡的单边数字个数，这个位置就是mid，关于迷惑点对于0和1开始的问题，其实可以这样去考虑，从0开始的话用尺子刻度去理解，0元素的末尾位置就是0起始位置是-1，1元素的起始位置是0，末尾位置是1，不管是不是减去0我都是在进行数学计算，所以可以推断一下，对于整数来说加减是无所谓的。
18、其实对于数组的计算位置，其实只需要知道将要计算的区间是否是闭合的，就可以很好的计算，位移的长度是不包含当前所在元素位置的，所以如果在一个闭合的区间内，现在是0位置移动2元素位置，就是很简单的到了2元素位置，什么时候忘了可以回来再看看找找感觉。
19、递归的一些想法：在递归前面的时候写的代码是属性结构up to bottom ，而递归完成后写的代码是 bottom to up的一个过程，也就是在递归前面写的逻辑是正常递归 ，在递归后写的是回溯的逻辑。就比如LeetCode 129号问题，可以参照自己写的练习代码。
20、学完了递归的对dfs和bfs有更多的感悟，其实都是把数据塞入到一个容器，bfs是遵循先进先进行处理，而dfs是后进的先进行处理。
21、排列问题是和顺序有关系的，比如某某队列多少种排法A（x,y），也需要去重比如1，1，2多次出现211的情况；组合问题是和顺序没有关系的，操作的时候需要做一些先后去重的2，1，5 和1，2，5。干脆的说排列是已知一些数组有多少种排法，组合是根据数据取出数据去组合满足条件。排列的重复是顺序完全一样，组合的重复是内容一样，顺序无所谓。
22、关于动态规划中二维数组的使用，很多时候key只是标注着某种两种情况下的值是多少，其实我自己想不明白是因为，我没有经常使用多维数组去记录东西，其实记录的就是多种情况下的一个值而已，比如memo[index][sum]就表示的index元素的时候sum是和的时候的值是多少，只要这样去用就好了。其实就是自己用二维数组描述的情况下比较少无知而已。
23、冒泡排序的外层循环是只需要循环n-1次，因为剩下一次肯定是有序的所以不需要排序了，内层循环-1的目的是因为j默认是前一个数来和j+1进行比较的，所以表示前一个数的话，就没必要遍历全部数组元素了，只需要n-1。
24、三路快排的时候，为何array[i]小于array[left]的时候需要交换，是因为有可能前面出现了等于left的元素，所以如果要是只增加lt那就不满足lt的定义（小于left的边界）。
网友评论