《算法集训传送门》

  👉引言

---

💖 ❄️我们的算法之路❄️💖

   众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
              ☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
   💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs)，💝宽度优先搜索（bfs），💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉

---

今日主题：链表

---

 👉⭐️第一题💎

   ✨题目

      1975. 最大方阵和

   ✨思路：

我首先想到的是DFS’深度优先搜索，但是写着写着就感觉到了不对劲，因为不管负数数量是奇数还是偶数，无论使用何种翻法，最终总是会留下一个负数以上，所以这题直接模拟就可以了，记录下矩阵里绝对值最小的数，根本不需要爆搜了

   ✨代码：

class Solution {
public:
    long long maxMatrixSum(vector<vector<int>>& matrix) {
        int minn = abs(matrix[0][0]);
        long long ans = 0;
        bool flag = false;
        for(auto &vec: matrix)
            for(int num: vec){
                if(num < 0){  
                    flag = !flag;  
                    num = -num;  
                }
                ans += num; 
                minn = min(num, minn);  小值
            }
        if(flag) 
        return ans - 2 * minn;
        return ans;
    }
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

 👉⭐️第二题💎

   ✨题目

      840. 矩阵中的幻方

   ✨思路：

由于

8 1 6   8 3 4   6 1 8   6 7 2
3 5 7   1 5 9   7 5 3   1 5 9
4 9 2   6 7 2   2 9 4   8 3 4
    
4 9 2   4 3 8   2 9 4   2 7 6
3 5 7   9 5 1   7 5 3   9 5 1
8 1 6   2 7 6   6 1 8   4 3 8

1
2
3
4
5
6
7
8

• 这道题一开始想到的是暴力搜索，因为数据规模不大，但是看了题解发现果然是人外有人，这里贴出一个比较好的解法：

• 三阶幻方总共有8种可能，每种可能有9位数字，每位数字最大为9，可以编码在一个 int 中，如第一个可以编码为 816357492,然后把幻方右下角即坐标{2, 2}点作为基准，用3x3的框遍历矩阵，以对幻方相同的编码方式，编码3x3框内的数字，对满足幻方的3x3框计数。

   ✨代码：

class Solution {
public:
    int numMagicSquaresInside(const vector<vector<int>>& grid) {
        const unordered_set<int> s{816357492, 834159672, 618753294, 672159834,
                                   492357816, 438951276, 294753618, 276951438};
        const int offset[][2] = {{-2, -2}, {-2, -1}, {-2, 0},
                                 {-1, -2}, {-1, -1}, {-1, 0},
                                 { 0, -2}, { 0, -1}, { 0, 0}};
        int ans = 0;
        for (int i = 2; i < grid.size(); ++i) {
            for (int j = 2; j < grid.size(); ++j) {
                int sum = 0;
                for (int k = 0; k < 9; ++k) {
                    sum *= 10;
                    sum += grid[i + offset[k][0]][j + offset[k][1]];
                }
                ans += s.count(sum);
            }
        }
        return ans;
    }    
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

🌹写在最后💖：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！🌹🌹🌹