国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

Keagan / 2780人閱讀

摘要:假設(shè)壓入棧的所有數(shù)字均不相等。注意這兩個序列的長度是相等的思路借助一個輔助棧來存儲數(shù)據(jù)。當(dāng)所有數(shù)據(jù)入棧完成,如果出棧順序正確,那么輔助棧應(yīng)該為空。若存在,左右子樹,遞歸檢測左右子樹是否復(fù)合規(guī)范。

1.包含min函數(shù)的棧

定義棧的數(shù)據(jù)結(jié)構(gòu),請?jiān)谠擃愋椭袑?shí)現(xiàn)一個能夠得到棧中所含最小元素的min函數(shù)(時間復(fù)雜度應(yīng)為O(1))。

思路

1.定義兩個棧,一個棧用于存儲數(shù)據(jù),另一個棧用于存儲每次數(shù)據(jù)進(jìn)棧時棧的最小值.

2.每次數(shù)據(jù)進(jìn)棧時,將此數(shù)據(jù)和最小值棧的棧頂元素比較,將二者比較的較小值再次存入最小值棧.

4.數(shù)據(jù)棧出棧,最小值棧也出棧。

3.這樣最小值棧的棧頂永遠(yuǎn)是當(dāng)前棧的最小值。

代碼
var dataStack = [];
var minStack = [];
 
function push(node)
{
    dataStack.push(node);
    if(minStack.length === 0 ||  node < min()){
        minStack.push(node);
    }else{
        minStack.push(min());
    }
}
function pop()
{
    minStack.pop();
    return dataStack.pop();
}
function top()
{
    var length = dataStack.length;
    return length>0&&dataStack[length-1]
}
function min()
{
    var length = minStack.length;
    return length>0&&minStack[length-1]
}
2.棧的壓入、彈出序列

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

思路

1.借助一個輔助棧來存儲數(shù)據(jù)。

2.將pushV中的數(shù)據(jù)依次入棧。

3.出棧有可能在任意一次入棧后進(jìn)行,當(dāng)出棧數(shù)據(jù)不再位于棧頂,繼續(xù)入棧。

4.所以設(shè)置一個索引,記錄當(dāng)前出棧的位置,每次出棧索引+1。

5.當(dāng)所有數(shù)據(jù)入棧完成,如果出棧順序正確,那么輔助棧應(yīng)該為空。

代碼
    function IsPopOrder(pushV, popV) {
      if (!pushV || !popV || pushV.length == 0 || popV.length == 0) {
        return;
      }
      var stack = [];
      var idx = 0;
      for (var i = 0; i < pushV.length; i++) {
        stack.push(pushV[i]);
        while (stack.length && stack[stack.length - 1] == popV[idx]) {
          stack.pop();
          idx++;
        }
      }
      return stack.length == 0;
    }
3.題二叉樹的后續(xù)遍歷

輸入一個整數(shù)數(shù)組,判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個數(shù)字都互不相同。

思路

1.后序遍歷:分成三部分:最后一個節(jié)點(diǎn)為跟節(jié)點(diǎn),第二部分為左子樹的值比跟節(jié)點(diǎn)都小,第三部分為右子樹的值比跟節(jié)點(diǎn)都大。

2.先檢測左子樹,左側(cè)比跟節(jié)點(diǎn)小的值都判定為左子樹。

3.除最后一個節(jié)點(diǎn)外和左子樹外的其他值為右子樹,右子樹有一個比跟節(jié)點(diǎn)小,則返回false。

4.若存在,左、右子樹,遞歸檢測左、右子樹是否復(fù)合規(guī)范。

代碼
    function VerifySquenceOfBST(sequence) {
      if (sequence && sequence.length > 0) {
        var root = sequence[sequence.length - 1]
        for (var i = 0; i < sequence.length - 1; i++) {
          if (sequence[i] > root) {
            break;
          }
        }
        for (let j = i; j < sequence.length - 1; j++) {
          if (sequence[j] < root) {
            return false;
          }
        }
        var left = true;
        if (i > 0) {
          left = VerifySquenceOfBST(sequence.slice(0, i));
        }
        var right = true;
        if (i < sequence.length - 1) {
          right = VerifySquenceOfBST(sequence.slice(i, sequence.length - 1));
        }
        return left && right;
      }
    }
4.二叉樹中和為某一值的路徑

輸入一顆二叉樹的跟節(jié)點(diǎn)和一個整數(shù),打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑。(注意: 在返回值的list中,數(shù)組長度大的數(shù)組靠前)

思路

1.使用前序遍歷

2.使用一個輔助棧來存儲當(dāng)前路徑里的數(shù)據(jù)

3.記錄一個當(dāng)前路徑的和

4.遍歷到當(dāng)前節(jié)點(diǎn)后,當(dāng)前值入路徑棧,和加當(dāng)前值

5.遞歸左孩子右孩子節(jié)點(diǎn)

6.遍歷完一個節(jié)點(diǎn),退回到上一個節(jié)點(diǎn),從路徑棧中移除當(dāng)前的值,和減當(dāng)前值

代碼
    function FindPath(root, expectNumber) {
      var result = [];
      if (!root) {
        return result;
      }
      findPath(root, expectNumber, [], 0, result);
      return result;
    }

    function findPath(node, expectNumber, vector, sum, result) {
      vector.push(node.val);
      sum += node.val;
      var isLeaf = !node.left && !node.right;
      if (isLeaf && sum === expectNumber) {
        result.push(vector.slice(0));
      }
      if (node.left) {
        findPath(node.left, expectNumber, vector, sum, result);
      }
      if (node.right) {
        findPath(node.right, expectNumber, vector, sum, result);
      }
      vector.pop();
    }

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

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/101756.html

相關(guān)文章

  • 從簡歷被拒到收割今日頭條 offer,我用一年時間破繭成蝶!

    摘要:正如我標(biāo)題所說,簡歷被拒??戳宋液啔v之后說頭條競爭激烈,我背景不夠,點(diǎn)到為止。。三準(zhǔn)備面試其實(shí)從三月份投遞簡歷開始準(zhǔn)備面試到四月份收,也不過個月的時間,但這都是建立在我過去一年的積累啊。 本文是 無精瘋 同學(xué)投稿的面試經(jīng)歷 關(guān)注微信公眾號:進(jìn)擊的java程序員K,即可獲取最新BAT面試資料一份 在此感謝 無精瘋 同學(xué)的分享 目錄: 印象中的頭條 面試背景 準(zhǔn)備面試 ...

    tracymac7 評論0 收藏0
  • 從簡歷被拒到收割今日頭條 offer,我用一年時間破繭成蝶!

    摘要:正如我標(biāo)題所說,簡歷被拒??戳宋液啔v之后說頭條競爭激烈,我背景不夠,點(diǎn)到為止。。三準(zhǔn)備面試其實(shí)從三月份投遞簡歷開始準(zhǔn)備面試到四月份收,也不過個月的時間,但這都是建立在我過去一年的積累啊。 本文是 無精瘋 同學(xué)投稿的面試經(jīng)歷 關(guān)注微信公眾號:進(jìn)擊的java程序員K,即可獲取最新BAT面試資料一份 在此感謝 無精瘋 同學(xué)的分享目錄:印象中的頭條面試背景準(zhǔn)備面試頭條一面(Java+項(xiàng)目)頭條...

    wdzgege 評論0 收藏0
  • 劍指offer】一個數(shù)的二進(jìn)制序列中1的個數(shù)

    摘要:圖解第二種算法圖解代碼示例算法如果為真,說明拿到的是二進(jìn)制序列的個數(shù)為算法為的時候說明已經(jīng)拿完了,循環(huán)終止二進(jìn)制序列中的個數(shù)以上代碼,還可做優(yōu)化在此僅作參考,若有更好的算法,還望能夠私信告知,多謝各位。 ?前言?: 算法是一個程序員的內(nèi)功,能很好的體現(xiàn)程序員的編程思維,通過學(xué)習(xí)和掌握常見的算...

    weknow619 評論0 收藏0
  • 劍指offer》分解復(fù)雜問題更簡單

    摘要:拆分鏈表,將和進(jìn)行拆分,保證原始鏈表不受影響。要求不能創(chuàng)建任何新的結(jié)點(diǎn),只能調(diào)整樹中結(jié)點(diǎn)指針的指向。輸入一個字符串長度不超過可能有字符重復(fù)字符只包括大小寫字母。遞歸,記錄一個當(dāng)前節(jié)點(diǎn)的位置,該位置指向最后一個節(jié)點(diǎn)時記錄一次排列。 1.復(fù)雜鏈表的復(fù)制 輸入一個復(fù)雜鏈表(每個節(jié)點(diǎn)中有節(jié)點(diǎn)值,以及兩個指針,一個指向下一個節(jié)點(diǎn),另一個特殊指針指向任意一個節(jié)點(diǎn)),返回結(jié)果為復(fù)制后復(fù)雜鏈表的hea...

    wawor4827 評論0 收藏0

發(fā)表評論

0條評論

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