首页  思维导图  详情

左神算法刷题训练营1

2021-12-31 05:52:06   0  举报





AI智能生成

左神算法训练营笔记，包括计算机常用中阶算法

计算机算法

作者其他创作

大纲/内容

滑动窗口

概念

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

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

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

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

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

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

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

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

例题： 假设一个固定大小为W的窗口，依次划过arr，返回每一次滑出状况的最大值。 例如：arr=[4,3,5,4,3,3,6,7], W=3 返回：[5,5,5,4,6,7]

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

例题： 给定一个整型数组arr，和一个整数num。某个arr中的子数组sub，如果想达标，必须满足： sub中最大值 - sub中最小值 <= num, 返回arr中达标子数组的数量。

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

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

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

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

例题：单调栈

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

ChildTopic

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

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

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

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

利用单调栈

斐波那契数列

暴力递归

时间复杂度O(2^N)

动态规划

矩阵方法

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

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

当求解为严格计算方式，如F(n)=F(n-1) + .... + F(n-k), 且k为一个常数时，没有条件转移的表达式， 可以利用线性代数的思想，改写为： | F(n), F(n-1) | = | F(2), F(1) | * 某个二阶矩阵的n-2次方 的形式

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

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

KMP

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

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

N>=M

暴力解：len(str)=N, len(match)=M 则从str的第一个字符出发，依次匹配match字符串。

最差的例子： str：aaaaaaaaaaab match: aaab

时间复杂度O(N*M)

时间复杂度O(N), 当N>=M时

流程

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

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

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

match：“aabaabcaabaabcs" nextarry [ -1, 0, xxxxx]  规定：第一个位置的值为 -1           第二个位置的值为 0

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

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

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

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

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

算法的两个核心点

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

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

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

Manacher算法

解决回文问题(palindrome)，在一个字符串中最长的回文子串的长度 例如："abaaba”就是“abaaba”，则返回最长回文子串6 “abcbabcbabcba”, 则"abcbabcba”,最长回文子串9

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

暴力解

把字符串每一个字符的前后扩展一个特殊字符，例如： 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

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

过程如暴力解一致，比较 i-1 == i+1, 然后 i-2 == i+2

没有优化

R变大

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

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

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

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

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

R不变

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

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

R不变

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

例如：      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外开始扩

R变大

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

Morris遍历及扩展

生成Morris序列流程

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

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

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

如果mostRight的右指针，指向null，mostRight.right=cur, 然后cur=cur.left

mostRight 的右指针指向cur，让mostRight.right = null, cur = cur.right

知道cur=null为止

Morris先序

Morris中序

Morris后序

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

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

线段树

在数组的一段中，进行相应的处理： 例如： void add(L, R, V, arr) 在L到R的范围上都加上V void update(L, R, V, arr) 在L到R的范围上都变成V int getSum（L, R, arr）在L到R的范围上算和

构造一个完整的二叉树

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

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

当的时候，需要补充个数，构造一个的数值（补0）,则此时完全二叉树的空间为 = 4N

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

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

时间复杂度O(logN)

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

实例二

Leecode： There are several squares being dropped onto the X-axis of a 2D plane. You are given a 2D integer array positions where positions[i] = [lefti, sideLengthi] represents the ith square with a side length of sideLengthi that is dropped with its left edge aligned with X-coordinate lefti. Each square is dropped one at a time from a height above any landed squares. It then falls downward (negative Y direction) until it either lands on the top side of another square or on the X-axis. A square brushing the left/right side of another square does not count as landing on it. Once it lands, it freezes in place and cannot be moved. After each square is dropped, you must record the height of the current tallest stack of squares. Return an integer array ans where ans[i] represents the height described above after dropping the ith square.

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

code中需要进行节点的离散化：public HashMap<Integer, Integer> index(int[][] positions)

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

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

ChildTopic

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

SubTopic