lintcode 矩阵问题（最全的面试矩阵问题）

前言

第三周我们计划刷关于矩阵的题目。

此次参与刷题的共五人（嘟嘟、琼琼、东东、大智、博主）。

首次把宿舍的白板用上了。。

正题

28.搜索二维矩阵

每行都是有序的，且下一行第一个元素比上一行最后一个元素大。

我们先对行二分，再对列二分。算法复杂度O（logn*logm）

38.搜索二维矩阵2

每一行从左到右递增，每一列从上至下递增。

本题的难点在于无法比较左下和右上的值谁大。

我们可以直接比较右上角的数字（或者左下角的数字），如果比右上角大，那么排除了第一行；如果比右上角小，排除了第一列。

PS：三角兽面试题

代码：

class Solution {
public:
    /*
     * @param matrix: A list of lists of integers
     * @param target: An integer you want to search in matrix
     * @return: An integer indicate the total occurrence of target in the given matrix
     */
    int searchMatrix(vector<vector<int>> &matrix, int target) {
        // write your code here
        int m = matrix.size(),res=0;
        if(m==0) return res;
        int n = matrix[0].size();
        
        int x=0,y=n-1;
        while(x<m&&y>=0){
            if(matrix[x][y]<target) ++x;
            else if(matrix[x][y]>target) --y;
            else ++res,++x;
        }
        return res;
    }
};

161.旋转图像

四个位置（i,j) (j,n-1-i) (n-1-i,n-1-j) (n-1-j,i)依次交换即可。

162.矩阵归0

挑战是O（1）的空间。

用第一行表示哪一列为0，用第一列表示哪一行为0，但是第一行第一列是表示某一行还是某一列呢？因此需要单加一个变量表示第一行或者第一列是否归0。

PS: 第四范式 面试题。

185.矩阵的之字型遍历

这题是当年考研的预面试题目，当时相当于画了一个状态机做的。可以参考：考研上机题 的第五题。

有四个方向。右、左下、下、右上。

左下和右上可以继续，其他的方向需要改变成下一个。

代码：

class Solution {
public:
    /*
     * @param matrix: An array of integers
     * @return: An array of integers
     */
    
    int dir[4][2] = {{0,1},{1,-1},{1,0},{-1,1}};
    int m,n;
    vector<int> res;
    vector<vector<bool> > vis;
    
    void dfs(vector<vector<int> > matrix,int x,int y,int d){
        int cur_x,cur_y;
        cur_x=x+dir[d][0],cur_y=y+dir[d][1];
        if(cur_x>=0&&cur_x<m&&cur_y>=0&&cur_y<n&&!vis[cur_x][cur_y]){
            res.push_back(matrix[cur_x][cur_y]);
            vis[cur_x][cur_y] = true;
            if(d&1) dfs(matrix,cur_x,cur_y,d);
            dfs(matrix,cur_x,cur_y,(d+1)%4);
            dfs(matrix,cur_x,cur_y,(d+2)%4);
            dfs(matrix,cur_x,cur_y,(d+3)%4);
            //其他方向都不行，只能顺着一个方向
            dfs(matrix,cur_x,cur_y,d);
        }
    }
    
    vector<int> printZMatrix(vector<vector<int>> &matrix) {
        // write your code here
        m = matrix.size();
        if(m==0) return res;
        n = matrix[0].size();
        
        for(int i=0;i<m;++i)
            vis.push_back(vector<bool>(n,false));
        vis[0][0]=true;
        res.push_back(matrix[0][0]);
        dfs(matrix,0,0,0);
        dfs(matrix,0,0,2);
        return res;
    }
};

364.接雨水2（好题！）

我们可以先做363.接雨水，一维的只需要记录每个位置往左边能到的最大值和往右边能到的最大值（里面选一个小的减去当前高度）就是这个位置能接的水，然后把所有位置能接的水加起来即为结果。

代码：

class Solution {
public:
    /*
     * @param heights: a list of integers
     * @return: a integer
     */
    int trapRainWater(vector<int> &heights) {
        // write your code here
        int len = heights.size();
        if(len<3) return 0;
        
        int res=0,tmp=0;
        vector<int> l(len),r(len);
        for(int i=0;i<len;++i){
            l[i]=tmp;
            tmp=max(tmp,heights[i]);
        }
        tmp=0;
        for(int i=len-1;i>=0;--i){
            r[i]=tmp;
            tmp=max(tmp,heights[i]);
        }
        for(int i=1;i<len-1;++i)
            res+=max(min(l[i],r[i])-heights[i],0);
        return res;
    }
};

但是二维的就没这么简单了，如果使用l,r,d,u表示四个方向的最大值的话会出问题（比如水可以从右下漫出。。）

如果一个位置能找到往外流出的路径，那么这个位置不能接水。

我们可以使用BFS+优先队列来解决这个问题。

1.首先把边界的点加入到队列中，每次出队选择高度最低的出队。

2.记录之前的最大值，如果当前值比最大值小，表示可以装水。

【如果可以漫出，那么之前的最大值一定<=当前值】

【队列里的元素和之前最大的元素是边界，都>=之前的最大值】

PS：使用tuple会超时 （换成了pair 压缩行和列）

参考：[LeetCode] Trapping Rain Water II 收集雨水之二

代码：

class Solution {
public:
    /*
     * @param heights: a matrix of integers
     * @return: an integer
     */
    int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    int trapRainWater(vector<vector<int>> &heights) {
        // write your code here
        int m = heights.size();
        if(m<3) return 0;
        int n = heights[0].size();
        if(n<3) return 0;
        
        vector<vector<bool> > vis(m,vector<bool>(n,false));
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
        
        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j)
                if(i==0||i==m-1||j==0||j==n-1){
                    vis[i][j]=true;
                    q.push(make_pair(heights[i][j],i*n+j));
                }
        
        int res=0,max_h=0;
        while(!q.empty()){
            pair<int,int> t = q.top();
            q.pop();
            int x = t.second/n, y=t.second%n, h = t.first;
            res+=max(0,max_h-h);
            max_h = max(max_h,h);
            
            for(int i=0;i<4;++i){
                int cx=x+dir[i][0],cy=y+dir[i][1];
                if(cx>=0&&cx<m&&cy>=0&&cy<n&&!vis[cx][cy]){
                    vis[cx][cy]=true;
                    q.push(make_pair(heights[cx][cy],cx*n+cy));
                }
            }
        }
        return res;
    }
};

374.螺旋矩阵

和185.矩阵的之字型遍历类似，四个方向（右、下、左、上）

389.判断数独是否合法

判断每行、每列、每个格子即可。

401.排序矩阵中的从小到大第k个数

每一行递增，每一列也递增。

把所有的元素排序，找第k个，这样的复杂度是O（n*logn）

而题目的挑战是O(k*logn)。

我们使用最小堆（优先队列）来实现，每次把元素的右边和下边的元素入队（比当前元素大一点点）。其实入队的操作就是在调整最小堆。【最小堆的实现使用数组vector】

405.和为0的子矩阵

我们可以使用dp[i][j]表示【以(0,0)表示左上，(i,j)表示右下】矩阵的面积。

那么dp[i][j] = dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+matrix[i-1][j-1]; (容斥原理，dp[i-1][j-1]算了两遍，故要减去一次)

那么我们可以枚举起点（左上）和终点（右下）的位置，这样的复杂度是O（n^4）。

而题目的挑战是O（n^3）。

我们可以联想到上上篇博客中的138.子数组之和问题。138是要在一维数组中找出和为0的子数组，一般的做法是枚举起始位置和结束位置【复杂度O（n^2）】，而当时的做法是遍历一遍，使用一个map把前缀和存入map中，如果之前存在了，那么已经找到了。【复杂度变为O(n)】

同样的做法可以应用于这个题，我们只需要枚举任意两行（O（n^2）），遍历每一列然后使用map存矩阵的前缀和即可。这样复杂度就变为了O（n^3）

代码：

class Solution {
public:
    /*
     * @param matrix: an integer matrix
     * @return: the coordinate of the left-up and right-down number
     */
    vector<vector<int>> submatrixSum(vector<vector<int>> &matrix) {
        // write your code here
        //dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+a[i][j]
        
        vector<vector<int> > res(2,vector<int>(2));
        int m=matrix.size(),n=matrix[0].size();
        vector<vector<int> > dp(m+1,vector<int>(n+1,0));
        for(int i=1;i<=m;++i)
            for(int j=1;j<=n;++j)
                dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+matrix[i-1][j-1];
        
        map<int,int> mp;
        for(int i=1;i<=m;++i)
            for(int j=i;j<=m;++j){ //枚举任意两行
                mp.clear();
                mp[0]=0;
                for(int k=1;k<=n;++k){
                    int tmp = dp[j][k]-dp[i-1][k];
                    // cout<<i<<" "<<j<<" "<<k<<" "<<tmp<<endl; 
                    if(mp.find(tmp)!=mp.end()){
                        res[0][0]=i-1,res[0][1]=mp[tmp];
                        res[1][0]=j-1,res[1][1]=k-1;
                        return res;
                    }
                    mp[tmp]=k;
                }
            }
    }
};

/*
1 6 13
4 16 15
8 12 20
*/

737.Find Elements in Matrix
寻找在每一行都出现的元素（数据保证只有一个）。

把第一行的放入map，遍历每一行，如果出现过+1。

如果等于m则满足条件。

找到一个trick。

这条数据： [[2,1,3],[3,1,1],[0,3,5]] 没有过（正确是3,我返回的是1，竟然AC了）。。

要防止这个就是在遍历行的时候，每行去个重【可以使用map】即可！