28、算法与数据结构 - 实战：卡特兰数、数组累加和问题、矩阵技巧
卡特兰数
假设k(0) = 1, k(1) = 1，满足下面三个公式的其中一个，都是卡特兰数，它们是等价的：
1、 k(n)=k(0)*k(n-1)+k(1)*k(n-2)+…+k(n-2)*k(1)+k(n-1)*k(0)；
2、 k(n)=c(2n,n)/(n+1)；
3、 k(n)=c(2n,n)-c(2n,n-1)；
用处：看一道题
假设给你n个左括号，又给你n个右括号
随意组合，有多少种组合方式满足括号组号的范式
比如(())即使合法，())(就是不合法
这一题可以用卡特兰数的公式解
但是怎么分析出它的解符合卡特兰数呢？
这里直接去推有多少种合法的组合方式，是很难推的
可以反过来看，有多少种组合方式是不合法的，然后总的组合方式数减去不合法数，就是答案
总的组合数 c(2n, n)
那么不合法的方式有多少种呢？
首先看一个规律：
假设有A集合，B集合，它们是两个不相干的集合，
但是如果A集合中的每个元素都存在某种关系使得他在B集合中，都有一个元素与之一对一对应
而反过来B集合中的每个元素都存在某种关系使得他在A集合中，都有一个元素与之一对一对应
那么可以肯定，这两个结合的元素个数一定相等
根据这个规律，再回过头来看
在n个左括号和n个右括号自由组合的不合法方式中，总有一个前缀是右括号比左括号多一个的，那么后半部分就是左括号比右括号多一个，把后半部分括号反转，整体就是右括号比左括号多两个。所以可以得知，n个左括号和n个右括号自由组合的不合法方式中，每种不合法的组合方式，都对应一种n-1个左括号和n+1个右括号的一种组合方式，而且对应关系是唯一的（因为不合法前缀是各不相同的）。
而反过来，n-1个左括号和n+1个右括号的每种组合方式，都在n个左括号和n个右括号自由组合的不合法方式中，有一种不合法的组合方式与之对应：找到右括号比左括号多一个的左半部分，然后后半部分括号反转，就变成了一种n个左括号和n个右括号自由组合的不合法方式。这种对应关系也是唯一的（因为对应回n个左括号和n个右括号中，不合法前缀是各不相同的）
那么求n个左括号和n个右括号自由组合的不合法方式有多少种，就可以转化为n-2个左括号和n+2个右括号有多少种不同的组合方式。C(2n, n+1)或者C(2n, n-1)。
那么求n个左括号和n个右括号自由组合的合法方式有多少种，就是c(2n, n) - C(2n, n-1)，符合卡特兰数的公式。因此确定可以用卡特兰数求解，利用第一个公式（最简单）就可以了。
/**
* k(0) = 1, k(1) = 1
*
* 满足下面三个公式的其中一个的数列，都是卡特兰数，它们是等价的：
*
* k(n) = k(0) * k(n - 1) + k(1) * k(n - 2) + ... + k(n - 2) * k(1) + k(n - 1) * k(0)
* 或者
* k(n) = c(2n, n) / (n + 1)
* 或者
* k(n) = c(2n, n) - c(2n, n-1)
*
* Created by huangjunyi on 2022/12/9.
*/
public class CatalanNumber {
public static long num1(int N) {
if (N < 0) {
return 0;
}
if (N < 2) {
return 1;
}
long[] dp = new long[N + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= N; i++) {
for (int leftSize = 0; leftSize < i; leftSize++) {
dp[i] += dp[leftSize] * dp[i - 1 - leftSize];
}
}
return dp[N];
}
}
类似括号问题的题目还有：
1、 有n个数字，要进栈，有多少种合理的进出栈方式？例如4个数字，进进出出（合法），出进进出（不合法）其实进就是左括号，出就是右括号；
2、 假设某公司股票的波动要么往上45°，要么往下45°，一共做n次交易，一共有多少种交易方式，不会过X轴一下其实往上45°就是左括号，往下45°就是右括号；
3、 n个节点，组成二叉树，有多少中组合方式头节点占1一个节点，剩下n-1个节点，分左树和右树考虑左0右n-1，左1右n-2，左2右n-3，…，左n-1右0还是卡特兰数；
数组累加和问题
题目一
给定一个正整数组成的无序数组arr，给定一个正整数值k
找到arr的所有子数组里，哪个子数组的累加和等于k，并且长度最大的
返回其长度
这一题可以使用窗口求解
因为数组都是正整数，存在一种单调性，就是窗口往右扩，窗口内的数的累加和变大，窗口往右缩，窗口内的数的累加和变小
1、 所以可以定义一个窗口，L指针和R指针，表示左边界和右边界，一开始都是0，表示只有arr[0]一个数在窗口内；
2、 如果窗口内的数的累加和sum，小于k，则R指针往右移动，窗口扩大；
3、 如果窗口内的数的累加和sum，大于k，则L指针往右移动，窗口缩小；
4、 如果窗口内的数的累加和sum，等于k，则抓到一个答案，和最大长度PK一下，PK过了则更新最大长度；
/**
* 给定一个数组，只有正整数，返回累加和等于k的所有子数组中的最大长度子数组的长度
* Created by huangjunyi on 2022/9/11.
*/
public class ArrSum01 {
public static int getMaxLen(int[] arr, int k) {
int l = 0; // 窗口左边界
int r = 0; // 窗口右边界
int sum = arr[0]; // 当前窗口内累加和
int max = 0; // 子数组为k的最大长度
while (r < arr.length) {
if (sum == k) {
// 窗口累计和等于k，收集答案，PK一下
max = Math.max(max, r - l + 1);
sum -= arr[l++];
continue;
}
if (sum > k) {
// 窗口累计和大于k，左指针右移，窗口缩小
sum -= arr[l++];
continue;
}
if (sum < k) {
// 窗口累计和大于k，右指针右移，窗口扩大
r++;
if (r < arr.length) {
sum += arr[r];
}
}
}
return max;
}
}
题目二
给定一个整数组成的无序数组arr，值可能正、可能负、可能0
给定一个正数值k
找到arr的所有子数组里，哪个子数组的累加和等于k，并且是长度最大的
返回其长度
在遇到这种子数组相关的问题时，一定要马上想到以每个下标为结尾的子数组求一个答案，或者以每个下标为开头的子数组求一个答案
比如这一题，
以0位置结尾的子数组，累加和为k的，如果有，收一个答案
以1位置结尾的子数组，累加和为k的，如果有，收一个答案
以2位置结尾的子数组，累加和为k的，如果有，收一个答案
以3位置结尾的子数组，累加和为k的，如果有，收一个答案
…
而子数组累加和，又可以转化为数组前缀和来求解
那么假设以位置5结尾前缀和为10，那么怎么求以位置5结尾并且累加和为k的子数组呢
只要看前面有没有10-k的前缀和，假设以位置2结尾的数组前缀和就是10-k，那么以位置5结尾并且累加和为k的子数组就是3~5
但是题目要求返回累加和等于k，并且是长度最大的子数组的长度
那么当遍历到某个位置，累加到某个前缀和preSum，要求出以当前下标为结尾并且累加和为k并且长度最长的子数组，就要看是否存在前缀和为k-preSum的位置，并且是最早的
因此要建立一个map，记录前缀和为key，value为最早出现该前缀和的位置
遍历数组收集答案的同时，要同时记录map，如果当前前缀和在map中没有记录，则记录到map中，如果已经记录过了，则不更新
/**
* 给定一个数组，有正有负有0，返回累加和等于k的所有子数组中的最大长度子数组的长度
* Created by huangjunyi on 2022/9/11.
*/
public class ArrSum02 {
public static int getMaxLen(int[] arr, int k) {
if (arr == null || arr.length == 0) return 0;
// key 前缀和，value 最早出现该前缀和的位置
Map<Integer, Integer> sumIndexMap = new HashMap<>();
// 预先塞一条前缀和为0的记录，前缀和0最早出现在-1位置，
// 如果遇到前缀和就是k的情况，就可以收集答案
// 如果不垫这一条记录，遇到前缀和就是k的情况时，就会错过
sumIndexMap.put(0, -1);
int sum = 0; // 前缀和
int len = 0; // 最长长度
for (int i = 0; i < arr.length; i++) {
sum += arr[i]; // 累加前缀和
int diff = sum - k; // 计算得到k的差值前缀和
if (sumIndexMap.containsKey(diff)) {
// 如果map中存在该差值前缀和，则可以收集一个答案PK一下
len = Math.max(len, i - sumIndexMap.get(diff));
}
// 如果map中存在该差值前缀和，不更新
if (sumIndexMap.containsKey(sum)) continue;
// 如果map中不存在该差值前缀和，记录
sumIndexMap.put(sum, i);
}
return len;
}
}
题目三
给定一个整数组成的无序数组arr，值可能正，可能负，可能0
给定一个整数值k
找到arr的所有子数组里，哪个子数组的累加和<=k，并且是长度最大的
返回其长度
解法： 1、 准备两个长度与arr一样的的数组，minSum，minSumEnd；minSum[i]记录从i位置为开头，往右扩出的子数组累加和最小的，最小累加和是多少；minSumEnd[i]表示从i位置为开头，往右扩出的子数组累加和最小的，右边界到哪里；
2、 从右往左遍历arr，初始化minSum和minSumEnd，遍历到arr[i]，计算minSum[i]和minSumEnd[i]，只需要看i+1位置即可，如果minSum[i+1]<0，则i位置可以往右扩，minSum[i]就是arr[i]+minSum[i]，minSumEnd[i]就是minSumEnd[i+1]；
3、 初始化完minSum和minSumEnd后，再从左往右遍历arr，以窗口的方式，根据minSum和minSumEnd求每个位置能推多远依然累加和<=k的，推到无法再推，则窗口往右缩，累加和减去出窗口的数；
/**
* 给定一个数组，返回累加和小于等于k的所有子数组中的最大长度子数组的长度
* Created by huangjunyi on 2022/9/11.
*/
public class ArrSum03 {
public static int getMaxLen(int[] arr, int k) {
if (arr == null || arr.length == 0) return 0;
// minSum[i] 以i开头，往右扩出的累加和最小的子数组 的累加和
int[] minSum = new int[arr.length];
// minSumEnd[i] 以i开头，往右扩出的累加和最小的子数组 的右边界
int[] minSumEnd = new int[arr.length];
minSum[arr.length - 1] = arr[arr.length - 1];
minSumEnd[arr.length - 1] = arr.length - 1;
// 从右往左遍历arr，初始化minSum和minSumEmd
for (int i = arr.length - 2; i >= 0; i--) {
// i + 1位置的累加和小于0，可以往右扩
if (minSum[i + 1] <= 0) {
minSum[i] = arr[i] + minSum[i + 1];
minSumEnd[i] = minSumEnd[i + 1];
}
// 否则不往右扩，自己单独算作minSum[i]
else {
minSum[i] = arr[i];
minSumEnd[i] = i;
}
}
int end = 0; // 扩不到的那个位置
int sum = 0; // 当前窗口累加和
int len = 0; // 抓到的最大长度
for (int start = 0; start < arr.length; start++) {
// 根据minSum和minSumEnd的信息把窗口右边界往右推
while (end < arr.length && sum + minSum[end] <= k) {
sum += minSum[end];
end = minSumEnd[end] + 1;
}
// 推到不能再推，抓一个答案PK
len = Math.max(len, end - start);
// 如果窗口还有长度，则还可以缩，减去将要出窗口的数
if (start < end) sum -= arr[start];
// 窗口没长度了，在左边界++之前，右边界先++
else end = start + 1;
}
return len;
}
}
题目四
给定一个数组arr，给定一个值v
求子数组平均值小于等于v的最长子数组长度
解法： 把数组所有的数减一个v，就变成求数组累加和小于等于0的子数组，最长的长度
这样就转化成了和上面一样的问题
因为所有的数都减去v后，一个子数组累加和大于0，那么每个数加v后，平均值肯定大于v
相反，如果因为所有的数都减去v后，一个子数组累加和小于等于0，那么每个数加v后，平均值肯定也小于等于v
总结
题目一主要技巧：利用单调性优化
题目二主要技巧：利用预处理结构优化
题目三主要技巧：假设答案法+淘汰可能性
矩阵技巧
题目一
用Zigzag扫描打印矩阵matrix
/**
* 用Zigzag扫描打印矩阵matrix
* Created by huangjunyi on 2022/9/11.
*/
public class Matrix01 {
public static void printMatrix(int[][] matrix) {
/*
A点(a,b)
B点(c,d)
A点每次往右走一步，到最右侧了，则每次往下走一步
B点每次往下走一步，到最下方了，则每次往右走一步
那么每次AB两点间，都能全都一条斜线
用一个boolean变量标识本次应该从上午往下打印还是从下往上打印
a ➡ b⬇
c -----------
⬇| |
| |
| |
-----------
d ➡
*/
// A点坐标
int a = 0;
int b = 0;
// B点坐标
int c = 0;
int d = 0;
int endRow = matrix.length - 1;
int endColumn = matrix[0].length - 1;
boolean fromUp = false;
while (b <= endRow) {
// 打印斜线
printMatrix(matrix, a, b, c, d, fromUp);
// A点每次往左走一步，到最右侧了，则每次往下走一步
b = a == endColumn ? b + 1 : b;
a = a == endColumn ? a : a + 1;
// B点每次往下走一步，到最下方了，则每次往右走一步
d = c == endRow ? d + 1 : d;
c = c == endRow ? c : c + 1;
}
}
private static void printMatrix(int[][] matrix, int a, int b, int c, int d, boolean fromUp) {
/*
(a, b)
/
/
/
/
/
/
/
(d, c)
*/
if (fromUp) {
//从右上往左下打印
while (b < matrix.length && a >= 0) System.out.println(matrix[b++][a--]);
} else {
//从左下往右上打印
while (d < matrix[0].length && c >= 0) System.out.println(matrix[c--][d++]);
}
}
}
题目二
转圈打印矩阵
/**
* 转圈打印矩阵
* Created by huangjunyi on 2022/9/11.
*/
public class Matrix02 {
public static void printMatrix(int[][] matrix) {
/*
x ➡
y
⬇
(a, b)
-----------
| |
| |
| |
-----------
(c, d)
*/
// 左上角点坐标
int a = 0;
int b = 0;
// 右下角的左边
int c = matrix[0].length - 1;
int d = matrix.length - 1;
// 分圈，从外往里，一圈一圈的打印
while (a <= c && b <= d) {
printMatrix(matrix, a++, b++, c--, d--);
}
}
private static void printMatrix(int[][] matrix, int a, int b, int c, int d) {
if (a == c) {
while (b <= d) System.out.println(matrix[b++][a]);
return;
}
if (b == d) {
while (a <= c) System.out.println(matrix[b][a++]);
return;
}
int curR = b;
int curC = a;
while (curC < c) System.out.println(matrix[curR][curC++]);
while (curR < d) System.out.println(matrix[curR++][curC]);
while (curC > a) System.out.println(matrix[curR][curC--]);
while (curR > b) System.out.println(matrix[curR--][curC]);
}
}
题目三
旋转矩阵
/**
* 旋转矩阵
* Created by huangjunyi on 2022/9/11.
*/
public class Matrix03 {
public static void rotate(int[][] matrix) {
/*
矩阵分圈，一圈一圈旋转，圈与圈之间是互不影响的
圈内分组，每组就是4个点，循环交换位置
x ➡
y
⬇
(x=a, y=b)
-----------
| |
| |
| |
-----------
(x=c, y=d)
*/
int a = 0;
int b = 0;
int c = matrix[0].length - 1;
int d = matrix.length - 1;
while (a < c) rotate(matrix, a++, b++, c--, d--);
}
private static void rotate(int[][] matrix, int a, int b, int c, int d) {
for (int i = 0; i < c - a; i++) {
int temp = matrix[b][a + i];
matrix[b][a + i] = matrix[d - i][a];
matrix[d - i][a] = matrix[d][c - i];
matrix[d][c - i] = matrix[b + i][c];
matrix[b + i][c] = temp;
}
}
}