Longest Line of Consecutive One in Matrix (Leetcode 562)

第一種方法是直接做搜索汞幢,LC現(xiàn)在感覺(jué)大數(shù)據(jù)的test case少了,所以繁瑣一點(diǎn)也是能過(guò)的.
對(duì)于每一個(gè)點(diǎn)眼溶,朝8個(gè)方向進(jìn)行搜索 (其實(shí)朝前向的四個(gè)方向就可以) 同時(shí)將掃過(guò)的點(diǎn)記錄下來(lái)授药,以便不往回找.

class Solution {
public:
    
    bool isValid(int x, int y, vector<vector<int>>& M, vector<vector<bool>> &visited){
        if(x >= 0 && x < M.size() && y >= 0 && y < M[0].size() && M[x][y] == 1 && !visited[x][y]){
            return true;
        }
        
        return false;
    }
    
    int longestLine(vector<vector<int>>& M) {
        if(M.empty() || M[0].empty()){
            return 0;
        }
        
        int row = M.size(), col = M[0].size();
        vector<vector<bool>> visited(row, vector<bool>(col, false));
        vector<pair<int, int>> directions = {{1, 0}, {0, 1}, {1, 1}, {-1, 1}};
        int max_len = 0;
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(M[i][j] == 0){
                    continue;
                }
                
                for(auto it : directions){
                    int cur_x = i, cur_y = j, cur_len = 1;
                    while(isValid(cur_x + it.first, cur_y + it.second, M, visited)){
                        cur_x += it.first;
                        cur_y += it.second;
                        cur_len += 1;
                    }
                    
                    max_len = max(max_len, cur_len);
                }
            }
        }
        
        return max_len;
    }
};

參照網(wǎng)上,第二種方法是dp凹嘲,這個(gè)dp是要建立三維數(shù)組师倔,不僅僅是行列這兩維,第三維有代表的是連續(xù)1的四個(gè)方向 (前后,上下趋艘,斜疲恢,反斜). 做法也很直接.

class Solution {
public:
    int longestLine(vector<vector<int>>& M) {
        if(M.empty() || M[0].empty()) return 0;
        int row = M.size(), col = M[0].size();
        vector<vector<vector<int>>> dp(row+1, vector<vector<int>>(col+1, vector<int>(4, 0)));
        int max_len = 0;
        for(int i=1; i<=row; i++){
            for(int j=1; j<=col; j++){
                if(M[i-1][j-1] == 0) continue;
                dp[i][j][0] = dp[i-1][j][0] + 1;
                dp[i][j][1] = dp[i][j-1][1] + 1;
                dp[i][j][2] = dp[i-1][j-1][2] + 1;
                if(j != col) dp[i][j][3] = dp[i-1][j+1][3] + 1;
                for(int k=0; k<4; k++){
                    max_len = max(max_len, dp[i][j][k]);
                }
                
            }
        }
        return max_len;
    }
};
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市瓷胧,隨后出現(xiàn)的幾起案子显拳,更是在濱河造成了極大的恐慌,老刑警劉巖搓萧,帶你破解...
    沈念sama閱讀 222,807評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件杂数,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡瘸洛,警方通過(guò)查閱死者的電腦和手機(jī)揍移,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén),熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)反肋,“玉大人那伐,你說(shuō)我怎么就攤上這事∈幔” “怎么了罕邀?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,589評(píng)論 0 363
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)养距。 經(jīng)常有香客問(wèn)我诉探,道長(zhǎng),這世上最難降的妖魔是什么棍厌? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,188評(píng)論 1 300
  • 正文 為了忘掉前任阵具,我火速辦了婚禮,結(jié)果婚禮上定铜,老公的妹妹穿的比我還像新娘阳液。我一直安慰自己,他們只是感情好揣炕,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,185評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布帘皿。 她就那樣靜靜地躺著,像睡著了一般畸陡。 火紅的嫁衣襯著肌膚如雪鹰溜。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 52,785評(píng)論 1 314
  • 那天丁恭,我揣著相機(jī)與錄音曹动,去河邊找鬼。 笑死牲览,一個(gè)胖子當(dāng)著我的面吹牛墓陈,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播,決...
    沈念sama閱讀 41,220評(píng)論 3 423
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼贡必,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼兔港!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起仔拟,我...
    開(kāi)封第一講書(shū)人閱讀 40,167評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤衫樊,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后利花,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體科侈,經(jīng)...
    沈念sama閱讀 46,698評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,767評(píng)論 3 343
  • 正文 我和宋清朗相戀三年炒事,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了臀栈。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,912評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡羡洛,死狀恐怖挂脑,靈堂內(nèi)的尸體忽然破棺而出藕漱,到底是詐尸還是另有隱情欲侮,我是刑警寧澤,帶...
    沈念sama閱讀 36,572評(píng)論 5 351
  • 正文 年R本政府宣布肋联,位于F島的核電站威蕉,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏橄仍。R本人自食惡果不足惜韧涨,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,254評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望侮繁。 院中可真熱鬧虑粥,春花似錦、人聲如沸宪哩。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,746評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)锁孟。三九已至彬祖,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間品抽,已是汗流浹背储笑。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,859評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留圆恤,地道東北人突倍。 一個(gè)月前我還...
    沈念sama閱讀 49,359評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親赘方。 傳聞我的和親對(duì)象是個(gè)殘疾皇子烧颖,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,922評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問(wèn)題, 分享了一些自己做題目的經(jīng)驗(yàn)。 張土汪:刷leetcod...
    土汪閱讀 12,748評(píng)論 0 33
  • Spring Cloud為開(kāi)發(fā)人員提供了快速構(gòu)建分布式系統(tǒng)中一些常見(jiàn)模式的工具(例如配置管理窄陡,服務(wù)發(fā)現(xiàn)炕淮,斷路器,智...
    卡卡羅2017閱讀 134,716評(píng)論 18 139
  • 忽然發(fā)現(xiàn),有沒(méi)有錢(qián)是小事币叹,而有沒(méi)有前途润歉,有沒(méi)有本事才是大事。 十一月已經(jīng)快過(guò)完了颈抚,而我離我的目標(biāo)還很遠(yuǎn)很遠(yuǎn)踩衩。 有點(diǎn)...
    淺淺的箋閱讀 116評(píng)論 0 0
  • 我是覓小金桔 希望你喜歡 520 快樂(lè)
    _覓小金桔閱讀 161評(píng)論 3 6