【剣指offer】抽象的な問題を具体化

1.min関数を含むスタック

スタックのデータ構造を定義し、スタックに含まれる最小要素を得ることができるmin関数(時間複雑度はO(1))をこのタイプで実装します.

構想

1.2つのスタックを定義、1つのスタックはデータを格納し、もう1つのスタックはデータがスタックに入るたびにスタックの最小値を格納する.
2.データがスタックに入るたびに、このデータを最小値スタックのスタックトップ要素と比較する、両者の比較した小さい値を再び最小値スタックに格納する.
4.データスタックはスタックを出し、最小値スタックもスタックを出ます.
3.このような最小値スタックのスタックトップは、常に現在のスタックの最小値である.

コード#コード#

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.スタックの圧入、イジェクトシーケンス

2つの整数シーケンスを入力します.最初のシーケンスはスタックの圧入順序を表します.2番目のシーケンスがスタックのポップアップ順序である可能性があるかどうかを判断してください.スタックに押し込まれたすべての数字が等しくないと仮定します.例えば、シーケンス1,2,3,4,5は、あるスタックの押し込み順序であり、シーケンス4,5,3,2,1は、そのスタックシーケンスに対応するポップアップシーケンスであるが、4,3,5,1,2は、そのスタックシーケンスのポップアップシーケンスであることは不可能である.(注:この2つのシーケンスの長さは等しい)

構想

1.補助スタックを使用してデータを格納します.
2.pushVのデータを順次スタックに入れる.
3.スタックを出るのは任意の一回のスタックに入る後に行うことができて、スタックを出るデータがスタックの頂上に位置しない時、スタックに入ることを継続する.
4.したがって、インデックスを設定し、現在のスタックの位置を記録し、スタックインデックス+1を毎回出力します.
5.すべてのデータのスタックが完了した場合、スタックの順序が正しい場合、補助スタックは空であるべきである.

コード#コード#

    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.問題二叉木の後続遍歴

整数配列を入力し、その配列が二叉探索ツリーの後順に遍歴した結果であるかどうかを判断します.もしそうであればYesを出力し、そうでなければNoを出力します.入力された配列の任意の2つの数字が互いに異なると仮定します.

構想

1.後順遍歴:3つの部分に分けられる:最後のノードはヒールノードであり、第2の部分は左サブツリーの値がヒールノードよりも小さく、第3の部分は右サブツリーの値がヒールノードよりも大きい.
2.左サブツリーを先に検出し、左がノードより小さい値を左サブツリーと判定する.
3.最後のノード以外と左のサブツリー以外の値が右のサブツリーで、右のサブツリーがノードより小さい場合はfalseを返します.
4.存在する場合、左、右のサブツリーは、左、右のサブツリーが複合仕様であるかどうかを再帰的に検出します.

コード#コード#

    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.ツリーと値のパス

ツリーのヒールノードと整数を入力し、ツリーのノード値と入力整数のすべてのパスを印刷します.パスは、ツリーのルートノードからリーフノードまで続くノードがパスを形成するように定義されます.(注:戻り値のリストでは、配列長の大きい配列が先頭になります)

構想

1.前のパスを使用
2.現在のパスのデータを格納するために補助スタックを使用する
3.現在のパスの合計を記録します.
4.現在のノードを巡回した後、現在の値をパススタックに入力し、現在の値を加算
5.再帰左子右子ノード
6.ノードを巡回して、前のノードに戻り、パススタックから現在の値を除去し、現在の値を減算します.

コード#コード#

    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();
    }