左神算法刷题训练营1

R++ ==>数从右侧入窗口L++ ==> 数从左侧出窗口任何时候L<=R

当涉及 substring 的问题的时候，考虑使用滑动窗口

概念

双端队列头部的值就是此时窗口中的最大值

如果此时形成的窗口状况，不想让R向右动了（即不再增加数了），而让L向右移动（即减少数），双端队列代表的是此时窗口中成为最大值的数的优先级。

加数逻辑：当尾进时，查看是否队列中有比加入的数小的值，如果有，则弹出扔弃（相等时，也弹出旧值）直到比队列中的值小的位置。

减数逻辑（当L向右移动时）：如果L指向的值小于队列中的头节点下标，则直接返回头节点的值。如果L指向的值为队列中的头节点的下标，则则返回头节点的值，且将头节点移除队列

创建一个双端队列(LinkedList) (其实队列中存放arr的下标)只能从尾进，只能从头出维持双端队列中从大到小排列。

找到窗口中的最大值时间复杂度O(1) ==> 指平均时间复杂度。因为：N个数，每个数进一次队列，出一次队列（可能是加数时，淘汰；也可能是减数时，返回且淘汰）一共N个数，所以平均为O(1)

实现：trainingcamp001/src/class01/Code01_SlidingWindowMaxArray.java

实现：trainingcamp001/src/class01/Code02_AllLessNumSubArray.java

此题：数组的范围达标，则数组内部的子数组达标由此：数组范围和滑动窗口建立的单调性映射

问题求解达标子数组的个数。可以转化为求解以0位置开始的达标子数组个数，加上以1位置开始的达标子数组个数，以此类推。由此：建立了问题本身的单调性和滑动窗口的轨迹的单调性联系。

优化总结：1）数据状况是否可以优化2）问题本身是否可以优化

实现：trainingcamp001/src/class01/Code03_MonotonousStack.java

ChildTopic

例题：单调栈

实现：trainingcamp001/src/class01/Code04_AllTimesMinToMax.java

建立一个以0开始的累加和数组：i位置表示0~i的累加和

题目中的“正整数”建立了累加和的单调性映射

利用单调栈

例题：给定一个只包含正整数的数组arr，arr中任何一个子数组sub，一定都可以算出（sub累加和）*（sub中的最小值）是什么，那么所有子数组中，这个值最大是多少？

滑动窗口

时间复杂度O(2^N)

暴力递归

动态规划

矩阵方法

写出斐波那契数列的线性求解O(N)的方式

求解这个二阶矩阵的值，进而最快求出这个二阶矩阵的N-2次方

求斐波那契数列矩阵乘法的方法

代码：trainingcamp001/src/class02/Code01_FibonacciProblem.java

斐波那契数列

子串是连续的，例如：abc1234ef，\"1234\"是子串，但\"123ef\"不是

N>=M

问题：查询一个字符串N中是否包含一个子串M，及位置

最差的例子：str：aaaaaaaaaaabmatch: aaab

时间复杂度O(N*M)

font color=\"#388e3c\

流程基于暴力方法，只是在过程期间有加速==>省去了不必要的匹配尝试

例如：abcabck，对于k而言，其前缀和后缀的最大匹配长度为3

match：“aabaabcaabaabcs\

每一次计算 i 位置的信息依赖 i-1 位置的信息

获得此信息数组的算法复杂度O(M)

对match字符串，算出每个位置对应的前面的最长前缀和后缀匹配长度，并记录到和index相关的数组中供后用。Notes: 1） 取前缀和后缀的时候，指不包含整体的时候            2）和本身这个位置无关

匹配到x和y的时候出现不匹配的情况

y移动到y'位置，继续进行x 和 y'的比较

从头 str 和 match 一一比较；当发生不匹配的位置，标记为x和y；此时指向 string 的 x 位置不变，match 数组的 y 位置，回溯到 y 位置对应的最长前缀的下一个位置 y'；比较x和新位置 z 是否比配，开始向后继续匹配，直到新的不匹配出现，再重复此过程，直到 match 数组的指针指到0位置；如果仍然不匹配，则str的x位置往后移动一个位置做匹配。

流程

x 和 y' 的比较，实质是认为 j 开头的子串一定和match的最长前缀是相等的。

从 i 开始到 j 之前，没有一个位置可以匹配match的最长前缀。否则，最长前缀就不是 y 位置的最长前缀。（反证法）

算法的两个核心点

优化理论：从 i 出发到失败的 x-1 位置都不需要再重新验证从而优化速度

代码：trainingcamp001/blob/master/src/class04/Code01_KMP.java

KMP

作用：目前DNA的对称性，有生理学意义

解决回文问题(palindrome)，在一个字符串中最长的回文子串的长度例如：\

解决查找长度为偶数的回文

添加的特殊字符，可以选择任何字符，即便在本字符串中出现过多字符

把字符串每一个字符的前后扩展一个特殊字符，例如：31211214  ==>  #3#1#2#1#1#2#1#4#

遍历字符串每个字符，以其为中心，向两边扩展，直到左右两边不相等，找到最长的回文个数

找到的最长回文子串的长度，除以2，向下取整

O(N^2)

暴力解

基于暴力解，过程期间加速

回文半径/回文直径/回文区域例如：f#1#a#1#s，对于a而言，半径为4，直径为7，区域为【#1#a#1#】

目的：加速

回文半径数组Parry[]，记录每一次计算的每个字符的最长回文个数

回文最右边界 int R

中心 int C

关键概念

没有优化

R变大

扩展时，移动到的i在R外

一定存在以下关系：[   *          *         *   ]L   i'         c         i    R在L到R的区域里，一定存在i'对应于i

例如： a b [c d c] s t e t s [c d c] b a位置对应        i'          c          i

R不变

此时i的回文区域、半径。直径和i'的值一样pArr[i] = pArr[i']

i'扩展的回文区域在L...R内

此时i的回文区域，即是i到R的距离pArr[i] = i..R

i在R内，i'扩展回文区域在L...R之外

例如：      a b c t c b a t a b c t c b a 位置对应           i'         c         i                 L'              L    R'             R

直接从R'-1的位置和R+1的位置比较，看是否需要扩展回文区域从R外开始扩

i在R内，i'的回文区域左边界和L压线

扩展时，移动到的i在R内

代码：trainingcamp001/src/class05/Code01_Manacher.java时间复杂度O(N)

Manacher算法

当前节点cur，一开始来到整棵树的头

如果cur无左树，cur=cur.right

如果cur有左树，找到左树最右节点mostRight

知道cur=null为止

生成Morris序列流程

Morris先序

Morris中序

Morris后序

判断是否是搜索二叉树（BST）

当流程需要左树和右树的信息的时候，则不能用Morris遍历。因为需要缓存左树的信息和右树比较。如果不需要保留所有的信息，或者说信息可以传递不需要保留，则可能用Morris遍历。

Morris遍历及扩展

构造一个完整的二叉树

当， 则只需要2N空间即可

当的时候，需要补充个数，构造一个span class=\"equation-text\" data-index=\"2\" data-equation=\"2^(n+1)\" contenteditable=\"false\

1+2+4+⋯+2⌈log2n⌉=2⌈log2n⌉+1<4n

N为任意值，最多需要4N个空间去构造完全二叉树

\"懒增加\"和\"懒更新\"是实现O(logN)的核心优化

时间复杂度O(logN)

代码： trainingcamp001/src/class07/Code01_SegmentTree.javahttps://leetcode.com/problems/minimum-falling-path-sum/

代码： https://github.com/edgefree/trainingcamp001/blob/master/src/class07/Code02_FallingSquares.java

TreeSet is one of the most important implementations of the SortedSet interface in Java that uses a Tree for storage.

利用了TreeSet数据结构构建有序节点

外框

实例二

区间范围上查询一个数，父节点需要调用左树和右树的简单加工得到，例如最大最小值，累加和等。但不需要具体左树和右树内部的详细信息。

线段树

SubTopic

算法刷题训练营1