笔试——Day24

第一题

题目

判断是不是平衡二叉树

思路

递归

• 声明一个dfs函数，当返回值为-1时表示子树不为平衡二叉树，其他值表示子树的高度；
• 当子树不等于-1时，再判断当前节点是否为平衡二叉树；

代码

第二题

题目：

最大子矩阵

思路

模拟 + 前缀和

• 初始化⼆维前缀和矩阵；
• 枚举所有的⼦矩阵，求出最⼤⼦矩阵

• 二维数组前缀和初始化[i, j]位置，sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + a[i][j];

• 利用二维数组前缀和求[x1, y1]和[x2, y2]所围的和sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]

代码

第三题

题目：

小葱的01串

思路

滑动窗口

代码