力扣周赛165

思路：一开始写麻烦了，其实这题很简单，因为这个一个33的矩阵，只需要O(n)遍历一个给你的数组，然后离线处理，分别判断5个点的坐标即 只需要判断这5个坐标是否对应的方向是否有3个相同的数字就行了，具体看一下代码，不太好用语言描述，我这个题代码写复杂了，一开始没看到是33的矩阵

class Solution {
public:
    int maze[100][100]={0};
    bool check(int x,int y){
        return maze[x][y]==maze[x-1][y]&&maze[x-1][y]==maze[x+1][y]||
            maze[x][y]==maze[x][y-1]&&maze[x][y-1]==maze[x][y+1]||
            maze[x][y]==maze[x-1][y+1]&&maze[x-1][y+1]==maze[x+1][y-1]||
            maze[x][y]==maze[x+1][y+1]&&maze[x+1][y+1]==maze[x-1][y-1];
    }
    string tictactoe(vector<vector<int>>& moves) {
        int n=moves.size();
        string ans;
        for(int i=0;i<n;i++){
            int x=moves[i][0];
            int y=moves[i][1];
            if(i&1){
                maze[x][y]=-1;
            }else {
                maze[x][y]=1;
            }
        }
        for(int i=0;i<=2;i++){
            for(int j=0;j<=2;j++){
                if(i==0&&j==0||i==0&&j==2||i==2&&j==0||i==2&&j==2)continue;
                if(i==0&&j==1||i==2&&j==1){
                    if(maze[i][j]==maze[i][j-1]&&maze[i][j-1]==maze[i][j+1]){
                        if(maze[i][j]==-1)ans="B";
                       else if(maze[i][j]==1)ans="A";
                    }
                }else if(i==1&&j==0||i==1&&j==2){
                    if(maze[i][j]==maze[i+1][j]&&maze[i+1][j]==maze[i-1][j]){
                        if(maze[i][j]==-1)ans="B";
                       else if(maze[i][j]==1)ans="A";
                    }
                }
                  else if(check(i,j)){
                       if(maze[i][j]==-1)ans="B";
                       else if(maze[i][j]==1)ans="A";
                   }
            }
        }
        if(ans=="B"||ans=="A")return  ans;
        else{
            for(int i=0;i<=2;i++){
                for(int j=0;j<=2;j++){
                    if(maze[i][j]==0)return "Pending";
                }
            }
        }
        return "Draw";
    }
};

思路：列一个一元二次方程，射小汉堡数量x，大汉堡数量y有：
4x + 2y =tomato
x + y cheese
解得 x=( tomato - 2 cheese ) / 2
y=cheese - x
另外判断一下是否整除或者负数的情况，这些情况说明不能合理分配，返回空就行了。
代码：

class Solution {
public:
    vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        if((tomatoSlices-2*cheeseSlices)%2!=0)return {};
        if((tomatoSlices-2*cheeseSlices)<0)return {};
        int x=(tomatoSlices-2*cheeseSlices)/2;
        if(cheeseSlices-x<0)return {};
        int y=cheeseSlices-x;
        return  {x,y};
    }
};

思路：二维前缀和
用树状数组维护一下二维前缀和，然后枚举正方形长度，因为正方形四条边相等，容易发现这样一个特点len*len=子矩阵的前缀和
代码：

class Solution {
public:
    int sum[350][350];
    void add(int x,int y){
        for(;x<=300;x+=(x&-x)){
            for(int j=y;j<=300;j+=(j&-j)){
                sum[x][j]+=1;
            }
        }
    }
    int query(int x,int y){
        int s=0;
        for(;x;x-=(x&-x)){
            for(int j=y;j;j-=(j&-j)){
                s+=sum[x][j];
            }
        }
        return s;
    }
    int get(int x1,int y1,int len){
        int x2=x1+len-1;
        int y2=y1+len-1;
        return query(x2,y2)-query(x2,y1-1)-query(x1-1,y2)+query(x1-1,y1-1);

    }
    int countSquares(vector<vector<int>>& matrix) {
        memset(sum,0,sizeof(sum));
        int n=matrix.size();
        int m=matrix[0].size();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(matrix[i][j]){
                    add(i+1,j+1);
                }
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                for(int len=1;len<=n-i+1&&len<=m-j+1;len++){
                    if(get(i,j,len)==len*len)ans++;else break;
                }
            }
        }
        return ans;
    }
};

最后一题DP下学期在做