【每日刷题】Day152

🥕个人主页：开敲🍉

🔥所属专栏：每日刷题🍍

🌼文章目录🌼

1. LCR 176. 判断是否为平衡二叉树 - 力扣（LeetCode）

2. 最大子矩阵_牛客题霸_牛客网

3. A-小葱的01串_牛客挑战赛54

1. LCR 176. 判断是否为平衡二叉树 - 力扣（LeetCode）

//思路：递归

//本题难点主要在于：在判断节点左、右子树是否为平衡二叉树后，需要返回一个 bool 值给上一层，同时需要返回 int 值的左、右子树的高度。

//这里我们用 -1 代表当前左、右子树不满足平衡二叉树，非 -1 就是左、右子树高度。

class Solution {

public:

    int IsBalanceTree(TreeNode* root)

    {

        if(!root) return 0;

        int left = IsBalanceTree(root->left);//计算左子树高度

        if(left==-1) return -1;//如果左子树不满足平衡二叉树，直接返回 -1

        int right = IsBalanceTree(root->right);

        if(right==-1) return -1;//同上

        return abs(left-right)<=1?max(left,right)+1:-1;//判断左右子树高度差不超过1，则满足平衡二叉树，返回子树高度；否则返回-1。

    }

    bool isBalanced(TreeNode* root)

    {

        return IsBalanceTree(root) !=-1 ;

    }

};

2. 最大子矩阵_牛客题霸_牛客网

//思路：二位前缀和

//本题就是二位前缀和模板，具体解法看 Day135 中的 "【模板】二位前缀和" 这道题，思路、代码都是完全一样的。

class Solution {

public:

    int getMaxMatrix(vector<vector<int> >& matrix)

    {

        int n = matrix.size(),m = matrix[0].size(),ans = INT_MIN;

        vector<vector<int>> dp(n+1,vector<int>(m+1));

        for(int i = 1;i<=n;i++)

            for(int j = 1;j<=m;j++)

                dp[i][j] = matrix[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];

        for(int x1 = 1;x1<=n;x1++)

            for(int y1 = 1;y1<=m;y1++)

                for(int x2 = x1;x2<=n;x2++)

                    for(int y2 = y1;y2<=m;y2++)

                        ans = max(ans,dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]);

        return ans;

    }

};

3. A-小葱的01串_牛客挑战赛54

//思路：滑动窗口

//本题想到用滑动窗口来解决还是比较容易的，难在本题的字符串是一个环形字符串，这就意味着，窗口会出现下面的情况：

//因此我们需要用一个小方法来解决这个问题：

//解决了滑动窗口维护字符串首尾的情况后，剩下的就很简单了：判断窗口内和窗口外的 '0'、'1' 字符数量是否相同，相同时，当前窗口就是一个染色方法，结果 + 1。

#include <iostream>
#include <vector>
using namespace std;

int n;
string s;

int main()
{
    int ans = 0;
    cin>>n;
    cin>>s;
    int out0 = 0,out1 = 0,in0 = 0,in1 = 0;
    for(auto c:s)//初始字符串中字符都为白色，记录白色 '0' 和白色 '1' 的数量
    {
        if(c=='1') out1++;
        else out0++;
    }
    
    int size = s.size();
    for(int i = 0;i<size/2-1;i++)//对字符串 s 进行改动，解决滑动窗口维护首尾的问题
        s+=s[i];
    
    int left = 0,right = 0;
    while(right<s.size())//剩下的就是维护窗口了
    {
        if(s[right]=='1')
        {
            in1++;
            out1--;
        }
        else
        {
            in0++;
            out0--;
        }
        
        if(in0==out0&&in1==out1) ans++;
        while(in0>out0||in1>out1)
        {
            if(s[left]=='1')
            {
                out1++;
                in1--;
            }
            else
            {
                out0++;
                in0--;
            }
            
            if(in0==out0&&in1==out1) ans++;
            left++;
        }
        
        right++;
    }
    
    cout<<ans;
    return 0;
}