本周完成了leetcode热题100中的矩阵部分，来做个总结。

总的来说，矩阵部分的题目均较为简单。

列几个我在做题过程中使用的技巧和可能性：第一，矩阵可以从外围一层层向内部递归；第二，矩阵的每一个位置，都可以作为一个“存储”，从而可以尽量不使用更多的空间，而是利用原地的运算；第三，矩阵的一些旋转可以等价于转置和翻转等的结合；第四，可以列出转换的式子再写代码。

以下记录几个题目的代码和思路：

73.矩阵置零

利用第一行和第一列做存储，再用额外的o（1）空间存储第一行和第一列的情况。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) 
    {
        int m=matrix.size();
        int n=matrix[0].size();
        int flag;
        if(matrix[0][0]==0)
        {
            flag=-3;
        }
        else
        {
            flag=0;
            for(int i=1;i<m;i++)
            {
                if(matrix[i][0]==0)
                {
                    flag=-1;
                    break;
                }
            }
            for(int j=1;j<n;j++)
            {
                if(matrix[0][j]==0)
                {
                    if(flag==-1) 
                    {
                        flag=-3;
                    }
                    else
                    {
                        flag=-2;
                    }
                    break;
                }
            }
        }
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(matrix[i][j]==0)
                {
                    matrix[i][0]=0;
                    matrix[0][j]=0;
                }
            }
        }
        for(int i=1;i<m;i++)
        {
            if(matrix[i][0]==0)
            {
                for(int j=1;j<n;j++)
                {
                    matrix[i][j]=0;
                }
            }
        }
        for(int j=1;j<n;j++)
        {
            if(matrix[0][j]==0)
            {
                for(int i=1;i<m;i++)
                {
                    matrix[i][j]=0;
                }
            }
        }
        if(flag==0)
        {
            return;
        }
        else if(flag==-1)
        {
            for(int i=0;i<m;i++)
            {
                matrix[i][0]=0;
            }
        }
        else if(flag==-2)
        {
            for(int j=0;j<n;j++)
            {
                matrix[0][j]=0;
            }
        }
        else
        {
            for(int i=0;i<m;i++)
            {
                matrix[i][0]=0;
            }
            for(int j=0;j<n;j++)
            {
                matrix[0][j]=0;
            }
        }
    }
};

54.螺旋矩阵

从外向内一层层处理（类似递归的思路）

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) 
    {
        int m=matrix.size();
        int n=matrix[0].size();
        vector<int> ans;
        int bh=0;
        int bl=0;
        while(m>0&&n>0)
        {
            for(int j=bl;j<bl+n;j++)
            {
                ans.push_back(matrix[bh][j]);
            }
            if(m==1) break;
            for(int i=bh+1;i<bh+m;i++)
            {
                ans.push_back(matrix[i][bl+n-1]);
            }
            if(n==1) break;
            for(int j=bl+n-2;j>bl;j--)
            {
                ans.push_back(matrix[bh+m-1][j]);
            }
            for(int i=bh+m-1;i>bh;i--)
            {
                ans.push_back(matrix[i][bl]);
            }
            m-=2;
            n-=2;
            bl++;
            bh++;
        }
        return ans;
    }
};

48.旋转图像

可以一层层，也可以利用翻转完成，或者列出表达式完成

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) 
    {
        int n=matrix.size();
        int start=0;
        while(n>=2)
        {
            for(int i=0;i<n-1;i++)
            {
                int temp;
                temp=matrix[start][start+i];
                matrix[start][start+i]=matrix[start+n-1-i][start];
                matrix[start+n-1-i][start]=matrix[start+n-1][start+n-1-i];
                matrix[start+n-1][start+n-1-i]=matrix[start+i][start+n-1];
                matrix[start+i][start+n-1]=temp;
            }
            /*for(int i=0;i<matrix.size();i++)
            {
                for(int j=0;j<matrix.size();j++)
                {
                    cout<<matrix[i][j]<<" ";
                }
                cout<<endl;
            }*/
            n-=2;
            start++;
        }    
    }
};

240.搜索二维矩阵

观察矩阵内部的顺序特点，按序斜向出发，从而达到o（m+n）的复杂度。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) 
    {
        int x=0;
        int y=matrix[0].size()-1;
        while(x<matrix.size()&&y>=0)
        {
            if(matrix[x][y]>target)
            {
                y--;
            }
            else if(matrix[x][y]<target)
            {
                x++;
            }
            else
            {
                return true;
            }
        }
        return false;
    }
};