九日集训第11日(矩阵)(幻方)

    没有之前的，懒
    不会吧，不会吧，不会真有人觉得九日集训只有九天吧，就像三角关系必定有第四者[手动狗头]

• 九日算法C++
• 前言
• 一、内容介绍
• 二、练习题目（来自力扣）
• 三、代码思路
• • 1.[840. 矩阵中的幻方](https://leetcode.cn/problems/magic-squares-in-grid/)
  • 2.[1975. 最大方阵和](https://leetcode.cn/problems/maximum-matrix-sum/)
• 晚安玛卡巴卡

2022の夏天，半壶水响叮当的我决定充实一下自我

    看见没写很正常（咸鱼）

思想：滑动窗口遍历，三阶幻方矩阵最小条件
    （1）滑动窗口遍历，注意边界随窗口增大缩小
    （2）三阶幻方矩阵最小条件：中央5，中央十字必然奇数，固定十字与边角，和为1
    （3）数据特征：方差满足，均值满足

class Solution {
    bool number(vector> grid,int a,int b){
        int sum =0;
        for (int i =0; i <3; ++i){
            for (int j =0; j <3; ++j){
                sum += pow( grid[a+i][b+j] - 5 , 2 );
            }
        }
        if( sum ==60 ) {
            return true;
        } else {
            return false;
        }

    }
    int check(vector> grid,int i,int j){ //和15  中央5
        if( (grid[i+1][j+1] !=5) || !(1 &grid[i+1][j] &grid[i][j+1] &grid[i+1][j+2] &grid[i+2][j+1]) ){//中央5 环绕奇数
            return 0;
        }
        if( grid[i+1][j] +grid[i+1][j+1] +grid[i+1][j+2] !=15){ //固定十字
        // if( grid[i][j+1] +grid[i+1][j+1] +grid[i+2][j+1] !=15){ //固定十字
            return 0;
        }
        if( grid[i][j] +grid[i][j+1] +grid[i][j+2] !=15 ){ //固定四角
            return 0; 
        }
        if( grid[i][j] +grid[i+1][j] +grid[i+2][j] !=15 ){ //固定四角
            return 0; 
        }
        if( number(grid , i, j) ){
            return 1;
        } else {
            return 0;
        }
    }
public:
    int numMagicSquaresInside(vector>& grid) {
        int r =grid.size(); //行数
        int c =grid[0].size(); //列数
        if(r <3 || c <3) return 0;
        int ret =0;
        for(int i =0; i 
            for(int j =0; j 
                ret +=check(grid , i ,j);
            }
        }
        return ret;
    }
};

思想：等价划分，将输入矩阵划分为负数计数 奇数， 偶数 与 0 组
    （1）矩阵算法必然绕不开遍历
    （2）计数负数，两两相消
    （3）0组，与奇数组一致处理，偶数组单独处理

class Solution {
public:
// 找0 绝对值和    找负数计数（奇数 最小负/偶数 绝对值和）
    long long maxMatrixSum(vector>& matrix) {
        int n =matrix.size();
        int count = 0 , min1 =100000;
        long long sum =0;
        for(int i =0; i 
            for(int j =0; j 
                if( matrix[i][j] >0){ //正数
                    sum +=matrix[i][j];
                    min1 =min(min1 , abs(matrix[i][j]) );
                } else if ( matrix[i][j] ==0){
                    count = -250*250*2; //超出总数,直接结果必然负数
                } else { //负数
                    ++count;
                    sum -=matrix[i][j];
                    min1 =min(min1 , abs(matrix[i][j]) );
                }
            }
        }

        if( count >0 && (count %2) ){  //无0 && 负数计数奇数
            return sum -min1*2;
        } else {
            return sum;
        }
    }
};

跟刷题大佬（B站英雄在哪里），早上五点等你