高级进阶版1

image.png
推荐思路：如果数组长度为n，选出数组中的最小min值和最大值max，将max-min的差值平分成n+1个桶，
这样就必然会出现空桶，且空桶不在首尾位置，（ps：注意这就天然产生了一个“平凡解”）
再将数组的数据依次填充到n+1个桶中，由于空桶的“平凡解”存在，所以最终答案（排序相邻最大差值）不可能出现在同一个桶内，因为存在空桶两侧的桶left、桶right
必定存在：桶right的minValue - 桶left的 maxValue > 任意一个桶的maxValue - minValue，
所以，最终答案（排序相邻最大差值）一定在桶与桶之间产生

构造平凡解:
image.png
优化成只关心桶里的最大值和最小值即可
image.png
代码:
image.png
image.png

image.png
推荐思路：
子数组问题：套路来了，
当你面对子数组的问题，你就想以每个位置结尾的情况下，答案是什么，如果有答案的话答案一定会在其中，这是我们经常听到的一句话，你会以后一定会经常听到

记录每个元素的前缀异或和

image.png

假设答案法：
image.png
image.png
image.png
image.png
推荐思路：m面值可以分成，a面值来自于n1种普通币，b面值来源于n2纪念币，
a+b=m，0<=a,b<=m，a,b为整数
假设a面值来自于n1种普通币可能性有 f(a)种
假设b面值来自于n2种纪念币可能性有 g(b)种
所以答案是
左程云leetcode--高级进阶版 - 图12
image.png
所以问题求解就变成了 求：f(a),g(b)的通用公式
用n1种普通币组合成a面值，很明显的背包问题啦~！
想到背包问题很明显的二位数组变量，使用前i个普通币组合成面值为j的组合有多少种dp[i][j]
image.png
image.png

image.png
约瑟夫环问题，有通用公式

image.png
初始思路：两个指针指向A、B的头，谁小移动谁，数到第k个即完成，时间复杂度O(k)
image.png
推荐思路：中位数二分
image.png

高级进阶版2

image.png

image.png
image.png
初始思路: 滑动窗口即可，因为数组全是整数，
当数组有负数时，就不行了，需要动态规划，子数据问题
image.png

发散题：
1.数组有正数、负数、零的情况下，求出子数组和为k的最大子数组长度
2.数组有正数、负数、零的情况下，求出子数组小于等于k的最大子数组长度

image.png
image.png
image.png
image.png

利用第0号位置求出的答案，舍弃部分解

image.png
image.png
image.png
经典博弈论问题：直接记结论，
将数组的所有元素一起异或求和，如果异或和不为0，先手赢，如果异或和为0，后手赢
image.png
image.png
k伪进制：3进制取值范围是[0-2]，3伪进制取值范围是[1-3]
image.png
推荐思路：26伪进制，先从低位依次填1，直到高位，再从高位向低位贪心拿最多的值
image.png
image.png

高级进阶版3

image.png

image.png
推荐思路：
本题是求经典迷宫最短路径的问题的升级版
经典迷宫最短路径回顾
从已知迷宫的起点[0][0]位置，找到迷宫的出口[m][n]已知位置的最短路径和，每次只能向右或者向下走一步
先递归分析，再改成带缓存的动归
dp[i][j]=min{d[i-1][j], dp[i][j-1]}+input[i][j]

改动点:
1.迷宫的起点位置不确定，结束的位置也不确定
2.可以改变一次数组任意位置的值

针对改动点1：for循环枚举出所有的起点和终点，其中起点不太关心
针对改动点2：扩展存储状态
dp[i][j].no表示到达第i行，第j列的位置没有使用过超能力
只能是以前没用过能力，本次也不用能力
dp[i][j].yes表示到达第i行，第j列的位置使用过一次超能力
可以是以前没使用过能力，本次使用能力
或者以前使用过能力，本次不使用能力

dp[i][j].no = max{ dp[i-1][j-1].no, dp[i][j-1].no, dp[i][j-1].no } + input[i][j]
dp[i][j].yes = max { max{ dp[i-1][j-1].no, dp[i][j-1].no, dp[i][j-1].no } + (-input[i][j]),
max{ dp[i-1][j-1].yes, dp[i][j-1].yes, dp[i][j-1].yes} + input[i][j] }

image.png
image.png
image.png
image.png
高级进阶班5,1:02:00

image.png
推荐思路：看到子数组，子序列问题，就想到以某某某结尾的情况下，该怎么办
炒鸡最优解：后缀数组解法，to be continue

ps：空间压缩就先不学了，对付面试够用了

由于是公共子串，所以如dp[i][j]只依赖 dp[i-1][j-1]的值
image.png
image.png
推荐思路：看到子数组，子序列问题，就想到以某某某结尾的情况下，该怎么办
因为是子序列，所以不要求子序列必须都已以i，j结尾，
有可能str1: 0~
image.png

image.png
初始思路：先排序，再贪心，以limit/2 分成两部分，
推荐思路：
image.png
image.png
image.png
image.png
image.png
image.png
初始思路：将str逆序，然后求正序串和逆序串的最长公共子序列，ok！对付面试够用了
推荐思路：新解法, 范围尝试模型 str[i…j]

一切以范围尝试的模型，一定要重点讨论开头和结尾，讨论以i开头，以j结尾
image.png
由1,2,3,4中可能性，决定了dp[i][j] 依赖于 dp[i+1][j-1], dp[i+1][j], dp[i][j-1]，从而决定了二位表的填写顺序
image.png
image.png
image.png
推荐思路：在范围上尝试的模型，str[i…j]到底需要添加几个能变成回文串，
一切以范围尝试的模型，一定要重点讨论开头和结尾，讨论以i开头，以j结尾
image.png
image.png
image.png
image.png
image.png
image.png
image.png
推荐思路：f(0)=”a”+f(1) or “aa”+f(2) or “aabaa”+f(5)
image.png
image.png
image.png
推荐思路：新解法, 范围尝试模型 str[i…j]

一切以范围尝试的模型，一定要重点讨论开头和结尾，讨论以i开头，以j结尾

image.png
image.png

歪路：
image.png

image.png

image.png
大名鼎鼎的两个经典算法：BFPRT算法(五个小伙伴算法)，完美洗牌问题， 斜率优化

笔试直接快排搞定，面试可用来吹牛逼BFPRT

快排和BFPRT过程比较：

image.png

BFPRT

image.png
image.png
image.png
image.png

高级进阶版4

image.png
讲过，跳过？

image.png
image.png
image.png
image.png
image.png
image.png
斜率优化：将一条线上的值O(n)转换成某几个固定的值O(1)
image.png

image.png

image.png

本题是最大搜索子树的变种，要求只掌握最大搜索子树就行了

黄金法则：一看到树的题目，就要想到 左子树如何求解，右子树如何求解，根如何根据左右子树的结果求解

初始思路：递归探索树上每个节点，统计符合搜索子树的树节点，每次符合一个节点，拓扑节点个数+1，不太对额~~~

拓扑贡献记录：
image.png
image.png
image.pngimage.png
左子树的右边界：左子树右走到头
有子树的左边界：右子树左走到头
image.png
image.png
image.png
image.png

image.png
image.png
image.png
存在多个环：每个环的出发点规律
image.png
image.png
左程云leetcode--高级进阶版 - 图100：2,8,26
1，当N=7,2N=14时，找到离 左程云leetcode--高级进阶版 - 图101最近的数，且不大于 左程云leetcode--高级进阶版 - 图102，14最近且不大于的数 左程云leetcode--高级进阶版 - 图103=8
2.将L1~L4和R1~R4的数据拼接在一起（对L5~R4使用三次交换法 ），
3.然后将剩下的数据14-8=6：L5~R7的数，重复步骤1,2,3
image.png
image.png
image.png
image.png
变种题：
image.png
如果n为偶数，先排序再完美洗牌
image.png
如果n为奇数，先排序去掉L0，把剩下的完美洗牌，去掉偶数的最后一步
image.png

高级进阶版5

image.png
image.png
主播跳过

image.png
推荐思路：中序遍历，规律：第一次降序的第一个节点，和最后一次降序的第二个节点是错的
image.png
如果，降序的次数大于2次，说明不只2个节点位置错了
找到“两个错误的节点”（第一次降序的第一个节点，和最后一次降序的第二个节点是错的），互换value值

image.png

image.png

image.png

在高级进阶版11集https://www.bilibili.com/video/BV1fR4y1J7mF?p=62

推荐思路：经典算法原型 “线段最大重合问题”

解法：有序表（要求掌握），
高级：线段树
image.png·

有序表，
第一步按线段开始位置（第一个数）排序“数组对”，
第二步遍历“数组对”，把有序表中 小于 “数组对”(第一个数)的 值丢掉，再把“数组对”（第二个数）入有序表，当前有序表的元素个数即是该线段重合的最大次数
有序表可以用TreeMap实现，
image.png
image.png

image.png

再来看矩阵重合问题

image.png
1.先按矩形的底边的从小到大排序，依次 加入容器
2.每当新矩形加入到容器中时，因为底边排过序，所有新矩形的底边肯定高于容器内的所有矩形的底边，然后遍历删除掉容器中矩形的顶边小于等于新矩形的底边的矩形
3.然后把容器中的所有矩形的左右边界抽象成 以新矩形底边为轴的 线段重合问题，求以新矩阵为底的最大线段重合长度，调用线段重合长度的函数原型即可，
4.coding待实现

image.png
image.png

高级进阶版6

image.png
image.png
image.png
image.png
推荐思路：从左往右的尝试模型。si: str[i…end] 是否和ei: express[i…end]匹配

image.png
初始思路：
image.png

推荐思路：经典算法——前缀树，字典树 01TrialTree

带补充
暴力法：O（n3次方）
image.png
预处理优化求和：O（n2次方）
因为：arr[i…j]子数组的异或和=arr[0…i-1] ^ arr[0…j] ，因为存在完全相同的两段arr[0…i-1] 异或后抵消归零
所以先预处理一遍把 数组的前i项异或和都给计算并保存下来
image.png
前缀树，字典树 01TrialTree
推荐思路：
image.png image.png
image.png
image.png
image.png
image.png
image.png
image.png

image.png
推荐思路：范围尝试模型，假设 arr[L…R]上 第i个气球最后爆，且arr[L-1]和arr[R+1]没爆

左程云leetcode--高级进阶版 - 图142
image.png
image.png
进一步优化，缓存L，R位置对应的结果，即是动态规划

image.png
image.png

高级进阶版7

image.png
f(0,3)=f(0,0)f(1,3)+f(0,1)f(2,3)+f(0,2)f(3,3)=12+11+21
其中：f(1,3)=f(1,1)f(2,3)+f(1,2)f(3,3)=2
f(0,2)=f(0,0)f(1,2)+f(0,1)f(2,2)=2
f(a,b)=1，a=b
f(a,b)=1, a=b-1;

image.png
推荐思路：滑动窗口问题，我居然忘了经典滑窗用法
image.png
image.png
推荐思路：hashmap+词频桶，二位桶结构：桶内和桶间都是双向链表（有首尾指针），到达存取都是O(1)

image.png
image.png
image.png
用每个站点的油减去距离，得到 “净利润”，从某个点出发，依次累加每个站点的“净利润”，如果都大于等于0即满足要求，变成前n项累加和为非负数的题
image.png

推荐

image.png