《算法集训传送门》

  👉引言

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

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

今日主题：矩阵

 👉⭐️第一题💎

   ✨题目

      1.螺旋矩阵

   ✨思路：

模拟，将螺旋四步封装在数组里，设定如果没有碰壁，则继续走该步骤

   ✨代码：

class Solution {
private:
    static constexpr int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return {};
        }
        
        int rows = matrix.size(), columns = matrix[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(columns));
        int total = rows * columns;
        vector<int> order(total);

        int row = 0, column = 0;
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            order[i] = matrix[row][column];
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;
    }
};

 👉⭐️第二题💎

   ✨题目

      73. 矩阵置零

   ✨思路：

扫描一遍原数组，将含有0的行列标记，再次扫描进行清算置零

   ✨代码：

class Solution {
public:
    void setZeroes(vector<vector<int>> &matrix)
{
    int n = matrix.size(), m = matrix[0].size();
    set<int> x, y;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (matrix[i][j] == 0)
            {
                x.insert(i);
                y.insert(j);
            }
        }
    }
    for (int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(x.find(i) != x.end()||y.find(j) != y.end()){
                matrix[i][j] = 0;
            }
        }
    }
}
};

 👉⭐️第三题💎

   ✨题目

      3.有序矩阵第K小的元素

   ✨思路：

比较暴力的方法就是 将矩阵的数据全放到数组里，然后排序

   ✨代码：

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        vector<int> rec;
        for (auto& row : matrix) {
            for (int it : row) {
                rec.push_back(it);
            }
        }
        sort(rec.begin(), rec.end());
        return rec[k - 1];
    }
};

 👉⭐️第四题💎

   ✨题目

       4.Ehab Fails to Be Thanos

   ✨代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n; cin>>n;
    vector<int> v(2*n);
    for(int i=0; i<2*n; i++)
    cin>>v[i];
    sort(v.begin(), v.end());
    int j=2*n-1;
    int first=0, last=0;
    for(int i=0; i<n; i++)
    {
        first+=v[i];
        last+=v[j-i];
    }
    if(first==last)
    cout<<-1<<endl;
    else {
    for(auto x: v)
    cout<<x<<" ";
    }
}

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