题目一：一个字符串可以分解成多种二叉树结构，判断是否互为旋变串
过滤器：字符种类一样，每种字符的个数一样
str1选[L1……]??? K段
str2选[L2……]??? K段
判断是否是旋变串
可能性分类：
str1 ： a1a2a3a4a5
str2：? b1b2b3b4b5
K = 1 时候，判断是否相等
K=5，第一种切法： a1做左部分，a2-a5做右部分
a1和b1 && a2-a5 和 b2 - b5
a1和b5 && a2-a5 和 b1 - b4
俩个有一个成立互为旋变串
俩都是false
判断
a1a2 和 b1b2 && a3-a5 和 b3-b5
a1a2 和 b4b5 && a3-a5 和 b1- b3
逐次递归
public static boolean isScramble(String s1, String s2){
if((s1 == null && s2 != null) || (s1 != null && s2 == null)){
return false;
}
if (s1 == null && s2 == null){
return true;
}
if(s1.equals(s2)){
return true;
}
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
if(!sameTypeSameNumber(str1, str2)){
return false;
}
int N = s1.length;
return process(str1, str2, 0, 0, N);
}
//返回str1[从L1开始往右长度为size的子串]和str2[从L2开始往右长度为size的子串]
//是否互为旋变字符串
//在str1中的这一段和str2中的这一段一定是等长的，所以只用一个参数size
public static boolean process(char[] str1, char[] str2, int L1, int L2, int size){
if(size == 1){
return str[L1] == str[L2];
}
//枚举每一种情况，有一个计算出互为旋变就返回true。都算不出来就返回false
for(int lefrPart = 1; lefrPart < size; leftPart++){
if(
//如果1左对2左，并且1右对2右
(process(str1, str2, L1, L2, leftPart)
&&
process(str1, str2, L1 + leftPart, L2 + leftPart, size - leftPart))
||
//如果1左对2右，并且1右对2左
(process(str1, str2, L1, L2 + size - leftPart, leftPart)
&&
process(str1, str2, L1 + leftPart, L2, size - leftPart))){
return true;
}
}
return false;
}改成递归
同一层的位置不依赖
public static int dpCheck(String str1, String str2){
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
int N = str1.length;
//L1的可能性 L2的可能性 size可能性
boolean[][][] dp = new int[N][N][N + 1]；
for(int L1 = 0; L1 <= N - size; L1++){
for(int L2 = 0; L2 <= N - size; L2++){
dp[L1][L2][1] = str1[L1] == str2[L2];
}
}
for(int size = 2; size <= N; size++){
//本层的东西，不互相依赖
//任何一个dp[i][j][size]都依赖dp[...][...][K] (k < size)
for(int L1 = 0; L1 < N; L1++){
for(int L2 = 0; L2 < N; L2++){
dp[L1][L2][size] = false;
for(int lefrPart = 1; lefrPart < size; leftPart++){
if(
//如果1左对2左，并且1右对2右
(dp[L1][L2][leftPart])
&&
(dp[L1 + leftPart][L2 + leftPart][size - leftPart]))
||
//如果1左对2右，并且1右对2左
(dp[L1][L2 + size - leftPart][leftPart])
&&
dp[L1 + leftPart][L2][size - leftPart]))){
dp[L1][L2][size] = true;
break;
}
}
}
return dp[0]0][N];
}题目二：给定字符串str1和str2，求str1的子串中包含有str2所有字符的最小字串长度
（滑动窗口）
举例子：str2 = babac
??????? str1 =aaaabbcacbba
记录一个欠债表 {a ： b：c：} all
当all为0时，有效，然后停止窗口，窗口缩，周而复始
题目三：LFU 缓存
一个缓存结构需要实现如下功能
void set（int key， int value）：加入或修改key对应的value
int get（int key）：查询key对应的value
黑盒，key value（3条）记录操作的time
超过三次时，替换词频低的数据
二维双向链表
题目四：油车问题
油数组：[ 3? 2? 1? 4? 2]
距离数组 ：[ 4? 1? 3? 2? 1]
环路结构
判断哪个是良好出发点
油数组变成一个纯能数组：加油站的油扣掉距离还剩多少
[-1? 1? -2? 2? 1]加一圈是否有小于0的累加和，判断是否是良好出发点
连通区[? )
rest = 通过连通区后还剩多少油
need 当前的节点接到连通区的头上，需要多少的油
题目五：
正确：中序遍历：升序
不止两次降序，错误的节点不止两个，找到错误的节点后，不可直接交换值
考虑多种情况
题目六：
平面内有n个矩形，第i个矩形的左下角坐标为（x1[i]，y1[i]）,右上角坐标为（x2[i]，y2[i]），如果俩个或者多个矩形有公共区域则认为它们是相互重叠的（不考虑边界和角落）。请你计算出平面内重叠矩形数量最多的对方，有多少个矩形相互重叠。
以开始位置排序，有序表（结尾）