[Day 4] Leetcode 764. Largest Plus Sign (C++)

前言

今天的题目在这里:764. Largest Plus Sign,是一题medium的题目。我直觉把它变成我习惯的dynamic programming格式来写,先来看看我的思路吧!

动态规划

不知道大家知不知道dynamic programming,可以参考这边。简单来说,就是把大问题倒推回去变成前一个状态,有点以前数学演绎法的感觉(?) 最简单的例子就是费氏数列,你要我一口气算f(100)是多少?我一时算不出来,但我知道f(100)会=f(98)+f(99),那f(99)又=f(97)+f(98)...以此倒推回去到f(0)跟f(1)的状态我就可以知道是0和1,就可以算回去了。
但是呢!从後面这样推回去,如果你用recursive是很不划算的,你看看你算f(99)的时候要去算f(97)和f(98)...直接一路算到底算出f(99)了,下一个数字:f(98) 天啊同样的动作又要从头再来推一次?!
聪明如你就可以发现有几个可以优化的地方─把算过的记录下来,而我们也不用从後面开始推,从前面开始记就好啦~
於是有了f(0)和f(1)之後你就可以算出f(2),记下来,下一个f(3)的时候回去找f(1)+f(2),再把f(3)记下来...如此用个for回圈遍历一次到100你就可以获得答案了。当然,你也可以再优化它的空间复杂度,因为我们发现其实每次都只需要前两个值就够了,於是就改成一个prev1,一个prev2,每次都把它更新成当下最新的两个值,就完成啦!
讲了这麽多,跟这题有什麽关系咧?

想法

总之,这题如果我想用O(n^2)的时间去做,肯定需要在遍历的时候一边就更新最新结果,不管怎样,我先把题目的矩阵画出来吧!
我把可以过的地方设为1,有障碍物的地方设为0:

vector<vector<int>>combined(n,vector<int>(n,1));
for(int i=0; i<mines.size();++i){
    combined[mines[i][0]][mines[i][1]] = 0;
}

那我要怎麽算出最大的可能的十字呢?先把问题拆小一点,我们可以想成求最长的直线/横线,是不是就简单很多?
所以我用两个矩阵来储存"包含该格"的最长直线,为什麽要包含该格?因为这样我们才能一直递推,如果包含这格,有障碍的话就是0,没障碍的话就会=前面那个的最长长度+1,如下:

vector<vector<int>>row=combined;
vector<vector<int>>col=combined;
for(int i=0;i<n;++i){
    for(int j=0;j<n;++j){
        if(combined[i][j]==1){
           if(i>0){
               row[i][j] = row[i-1][j]+1;
           } 
           if(j>0){
               col[i][j] = col[i][j-1]+1;
           }
        }

    }
}

这样呢,我们已经完成题目的一半了!
怎麽会?你想想,如果现在题目要求的是找到最长的十字左上半边,是不是就可以直接求出来了XD
若现在我的地图长这样

111
011
111

那我的row跟col分别会长这样

123     111
012     022
123     133

如果要求的是最长的一个」,那是不是就把两边取交集的最大值(min(row, col),代表同时考虑到row和column的话最长可以是多少),就会是结果了?

111
012
123

你比比看,是不是以每一点当作」的右下角,它最长的边就是如图中那样?
不过现在题目要求的是十字,那我们就倒过来再遍历一次:

vector<vector<int>>rowR=combined;
vector<vector<int>>colR=combined;
for(int i=n-1;i>=0;--i){
    for(int j=n-1;j>=0;--j){
        if(combined[i][j]==1){
           if(i<n-1){
               rowR[i][j] = rowR[i+1][j]+1;
           } 
            if(j<n-1){
                colR[i][j] = colR[i][j+1]+1;
            }
        }
    }
}

然後再针对每一点求交集的最大值,就好了!
完整程序码如下:

class Solution {
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        // build the initial matrix
        vector<vector<int>>combined(n,vector<int>(n,1));
        for(int i=0; i<mines.size();++i){
            combined[mines[i][0]][mines[i][1]] = 0;
        }
        
        // save for the longest consecutive 1 including that position
        vector<vector<int>>row=combined;
        vector<vector<int>>col=combined;
        vector<vector<int>>rowR=combined;
        vector<vector<int>>colR=combined;
        
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                if(combined[i][j]==1){
                   // if the position could be included, else remain 0
                   // avoid computing the first row/column, the position should always equal to itself
                   if(i>0){
                       row[i][j] = row[i-1][j]+1;
                       
                   } 
                    if(j>0){
                        col[i][j] = col[i][j-1]+1;
                    }
                    
                }
                
            }
        }
        
        
        for(int i=n-1;i>=0;--i){
            for(int j=n-1;j>=0;--j){
                if(combined[i][j]==1){
                   if(i<n-1){
                       rowR[i][j] = rowR[i+1][j]+1;
                   } 
                    if(j<n-1){
                        colR[i][j] = colR[i][j+1]+1;
                    }
                }
                
            }
        }
        
        // compute for the intersection(min) of each position
        int ans=0;
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                ans = max(ans,{min({row[i][j], col[i][j], rowR[i][j], colR[i][j]})});
           }
                
        }
    return ans;
    }
};

结语

工作好累QQ 可能有点讲不清楚,如果有任何问题欢迎留言提出!


<<:  Day 8:学习资源哪里找?

>>:  【D9】取得加权指数历史资料

30天打造品牌特色电商网站 Day.20 网站图片排版

图片是网站关键的视觉元素,更不用说电商网站了,相信大家都会在图片下功夫,让商品能够更加吸引顾客购买。...

D19 第九周 後端基础 PHP 与 MySQL

这周新接触到 PHP 和 MySQL,然後是第一次使用到 session 机制实作登入功能 我自己的...

15【雷坑】千万别肖想用 APCS 升大学

事实上一现在的情况来看,若是要用 APCS 成绩当作升大学的跳板是完全不建议的,理由如下: 高手独占...

铁人赛开场就决定是你了,Ruby 30 天刷题修行篇第一话

大家好,我叫 A Fei,目前是学习 Ruby 和 JavaScript 约三个月的新手。 在学习过...

食谱搜寻系统资料库简介~~

学习原因 如同icebear在day1里所说的一样,MySQL对於硬体的要求较少,再加上Mysql也...