成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

【刷算法】棧的壓入、彈出序列

CarlBenjamin / 1382人閱讀

摘要：題目描述輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。

題目描述

輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4，5,3,2,1是該壓棧序列對應(yīng)的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）

分析

其實該題就是考察一個進(jìn)棧序列能否和一個出棧序列對應(yīng)起來，但是棘手的地方在于：一個進(jìn)棧序列可能會有多個出棧的順序，所以還是得好好想一想。


可以從一個簡單的例子開始：

序列A：1,2,3

序列B：2,3,1

1先進(jìn)棧，B序列中未出棧的第一個數(shù)字是2，說明此時1不能再接著出棧；

2再進(jìn)棧，B序列中未出棧 的第一個數(shù)字是2，說明第一個出棧的數(shù)字是2，那么2就此出棧；

此時棧頂元素為1，B序列中未出棧的第一個數(shù)字是1，說明1是自2出棧后的再一個出棧元素，那么1就此出棧，此時棧為空；

3繼續(xù)進(jìn)棧，此時B序列的中未出棧的第一個數(shù)字是3，說明3是再一個出棧元素，那么3就此出棧，此時棧為空，序列A也全都進(jìn)棧完畢了；

?？樟?，序列A也進(jìn)棧完畢了，說明B就是A的彈出序列。

代碼實現(xiàn)

接著這個思路，可以試著寫代碼了

function IsPopOrder(pushV, popV)
{
    if(pushV.length === 0 || popV.length === 0 || pushV.length !== popV.length)
        return false;
    // 進(jìn)棧序列和出棧序列分別有一個指針，從頭開始
    var curPushIndex = 0, curPopIndex = 0;
    var stack = [];
    
    for(;curPushIndex < pushV.length;curPushIndex++) {
        
        stack.push(pushV[curPushIndex]);
        while(curPopIndex < popV.length && stack[stack.length-1] === popV[curPopIndex]){
        // 棧頂元素和當(dāng)前popIndex指向的數(shù)字一樣的話，stack彈出棧頂元素，且當(dāng)前popIndex指向pop序列的下一個數(shù)字
            stack.pop();
            curPopIndex++;
        }
    }
    // 棧中元素沒有全部彈出，說明兩個序列并不匹配，否則，就是匹配
    return stack.length === 0;
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/95697.html

相關(guān)文章

  • 劍指offer：棧的壓入、彈出序列（Java）

    摘要：題目描述輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。指向壓棧序列的指針指向彈棧序列的指針儲存壓棧序列的輔助空間第一次遍歷把壓棧序列放入輔助空間中如果有相等的就讓彈棧序列指針。 1.題目描述 輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓...

    Zhuxy 評論0 收藏0

  • 【劍指offer】讓抽象問題具體化

    摘要：假設(shè)壓入棧的所有數(shù)字均不相等。注意這兩個序列的長度是相等的思路借助一個輔助棧來存儲數(shù)據(jù)。當(dāng)所有數(shù)據(jù)入棧完成，如果出棧順序正確，那么輔助棧應(yīng)該為空。若存在，左右子樹，遞歸檢測左右子樹是否復(fù)合規(guī)范。 1.包含min函數(shù)的棧 定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧中所含最小元素的min函數(shù)（時間復(fù)雜度應(yīng)為O（1））。 思路 1.定義兩個棧，一個棧用于存儲數(shù)據(jù)，另一個棧用于存儲每次數(shù)...

    Keagan 評論0 收藏0

  • Java數(shù)據(jù)結(jié)構(gòu)與算法[原創(chuàng)]——棧

    摘要：前言數(shù)據(jù)結(jié)構(gòu)與算法專題會不定時更新，歡迎各位讀者監(jiān)督。方法調(diào)用編寫的程序在進(jìn)行方法函數(shù)調(diào)用時，會完成對方法的壓棧操作，等方法執(zhí)行結(jié)束后，對應(yīng)的會完成對方法的彈棧操作。 聲明：碼字不易，轉(zhuǎn)載請注明出處，歡迎文章下方討論交流。 前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會不定時更新，歡迎各位讀者監(jiān)督。本文介紹數(shù)據(jù)結(jié)構(gòu)中的棧的概念、存儲結(jié)構(gòu)、棧的特點以及棧的適用場景，另外會穿插介紹面試中的一些經(jīng)典問題...

    hiyang 評論0 收藏0

  • 棧的實現(xiàn)原理

    摘要：使用棧實現(xiàn)字符串逆序?qū)⒆址崔D(zhuǎn)用兩個棧實現(xiàn)隊列用兩個棧來實現(xiàn)一個隊列，完成隊列的和操作。假設(shè)棧中有個元素，基于簡單數(shù)組實現(xiàn)的棧?？梢钥吹綏Ｊ菍崿F(xiàn)，其實底層也是用數(shù)組來實現(xiàn)的。移除此堆棧頂部的對象，并將該對象作為此函數(shù)的值返回。 目錄介紹 01.棧由簡單數(shù)據(jù)實現(xiàn) 1.1 簡單數(shù)組代碼實現(xiàn) 1.2 可能出現(xiàn)問題 1.3 性能和局限性 02.棧由動態(tài)數(shù)組實現(xiàn) 2.1 基于簡單...

    soasme 評論0 收藏0

  • 2019秋招知識盲點總結(jié)

    摘要：實際上是一個讓出線程的標(biāo)志遇到會立即返回一個狀態(tài)的。一個簡單的防抖函數(shù)如果定時器存在則清除重新開始定時執(zhí)行缺點只能在最后執(zhí)行，不能立即被執(zhí)行，在某些情況下不適用。假設(shè)壓入棧的所有數(shù)字均不相等。接收數(shù)據(jù)不受同源政策限制。 開始 盡管秋招還沒有拿到offer（好難過），但是一些知識點還是要總結(jié)的，既然自己選了這條路，那就一定要堅定不移的走下去...... 注意 new 運(yùn)算符的優(yōu)先級 fu...

    Doyle 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<