当前位置：首页 > ds >正文

【今日三题】判断是不是平衡二叉树(递归) / 最大子矩阵(二维前缀和) / 小葱的01串(滑动窗口)

ds 2025/7/18 23:51:22

⭐️个人主页：@小羊 ⭐️所属专栏：每日两三题很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

动图描述

判断是不是平衡二叉树(递归)

判断是不是平衡二叉树

在这里插入图片描述

判断一个二叉树是不是平衡二叉树，我们需要知道其左子树和右子树是不是平衡二叉树，并且左右子树的高度差不超过1。
但是返回值只有一个，因此我们规定如果当前子树不是平衡二叉树，返回-1；如果是平衡二叉树则返回其高度。
整个过程是后序遍历。

class Solution {
public:bool IsBalanced_Solution(TreeNode* pRoot) {return dfs(pRoot) != -1;}int dfs(TreeNode* root){if (root == nullptr) return 0;int left = dfs(root->left);if (left == -1) return -1; // 剪枝int right = dfs(root->right);if (right == -1) return -1;return abs(right - left) <= 1 ? max(left, right) + 1 : -1;}
};

最大子矩阵(二维前缀和)

最大子矩阵

在这里插入图片描述

二维前缀和模板题。

#include <iostream>
using namespace std;int pre[101][101];
int n, res = -0x3f3f3f3f;int main()
{cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){int x;cin >> x;pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + x;}}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){for (int k = i; k <= n; k++){for (int l = j; l <= n; l++){res = max(res, pre[k][l] - pre[i - 1][l] - pre[k][j - 1] + pre[i - 1][j - 1]);}}}}cout << res << endl;return 0;
}

小葱的01串(滑动窗口)

小葱的01串

在这里插入图片描述

也就是在字符串上维护一段长度为n/2的窗口，当窗口内的0和1的个数和外面0和1的个数相等时更新结果；
字符串成环，当从字符串中找到一段区间满足要求时，实际上找到了两个结果；
需要注意的是：当枚举到字符串边界时，其实另一边已经算过了，因此我们只能枚举一个边界。

在这里插入图片描述

#include <iostream>
#include <string>
using namespace std;int n, res;
string s;int main()
{cin >> n >> s;int x = 0, y = 0;for (auto ch : s){if (ch == '0') x++;else y++;}if (x % 2) res = 0;else{x /= 2, y /= 2;for (int l = 0, r = 0; r < n - 1; r++){if (s[r] == '0') x--;else y--;while (r - l + 1 > n / 2){if (s[l++] == '0') x++;else y++;}if (r - l + 1 == n / 2){if (x == 0 && y == 0){res++;}}}}cout << res * 2 << endl;return 0;
}