文書ディレクトリ

13、配列順序

を調整する.

タイトル説明:

構想一

コード

構想二

コード

14、チェーンテーブルの最後からk番目のノード

タイトル説明

構想一

コード

構想二

コード

15、反転チェーンテーブル

タイトル説明

構想

コード

16、2つの並べ替えられたチェーンテーブル

をマージする

タイトル説明

構想一

コード

構想二

コード

17、木のサブ構造

タイトル説明

構想

コード

18、ツリーミラー

タイトル説明

構想

コード

13、配列順序の調整

タイトルの説明:

整数配列を入力し、すべての奇数が配列の前半に位置し、すべての偶数が配列の後半に位置し、奇数と奇数、偶数と偶数の間の相対位置が変わらないことを保証する関数を実現します.

考え方1

2つの配列を定義し,array 1は奇数,array 2は偶数,配列forEachのループ反復法でパリティがそれぞれ格納されていると判断し,ここで奇数偶数を判断するにはビットアンドメソッドを用いた.

コード#コード#

function reOrderArray(array)
{
    var array1 = [];
    var array2 = [];
    //forEach()              ，           。
    //item    、index        、array           
    array.forEach(function(item,index,array){
        item & 1 ? array1.push(item):array2.push(item);
        //         
        //     
    });
    //concat()              。
    return array1.concat(array2);
}

考え方2

map関数により,各配列要素が偶数であるか否かを判断する.

コード#コード#

function reOrderArray(array)
{
    // write code here
    var arr1=[],arr2=[];
  /* map()          ，                      。
   map()                   。
     ： map()           。
     ： map()         。 */
    array.map(function(a){
      //a     
        a%2==0?arr2.push(a):arr1.push(a);
    })
    return arr1.concat(arr2);
}

14、チェーンテーブルの最後からk番目のノード

タイトルの説明

チェーンテーブルを入力し、チェーンテーブルの最後からk番目のノードを出力します.

考え方1

チェーンテーブルkの前後の長さを決定する.

コード#コード#

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindKthToTail(head, k)
{
    if(head == null || k <= 0) return null;
    var init = head;
    var count = 0;
    while(head != null){
        head = head.next; //       
        count++;  //     
    }
    var rek = count - k; //k    
    if(rek < 0) return null;
    for(var i = 0 ; i < rek ; i++){
        init = init.next;
    }
    return init;
}

考え方2

prevとtailで距離kのセグメントを取得し、tailがチェーンテーブルの最後を指す

コード#コード#

function FindKthToTail(head, k)
{
    // write code here
    if(head==null||k<=0) return null;
    var prev = head;
    var tail = head;

    for(var index=0;index

15、チェーンテーブルの反転

タイトルの説明

チェーンテーブルを入力し、チェーンテーブルを反転した後、チェーンテーブルのすべての要素を出力します.

構想

反転後チェーンヘッダをprevで固定しheadで反転し、残りのチェーンヘッダをnextで指す.

コード#コード#

function ReverseList(pHead)
{
  //  
    if(pHead == null || pHead.next == null) return pHead;
    var prev = null;
    var next = null;
    while(pHead != null){
      //     
        next = pHead.next;
      //                
        pHead.next = prev;
      //     pre pHead next
        prev = pHead;
        pHead = next;
    }
    return prev;
}

16.2つのソートされたチェーンテーブルを結合する

タイトルの説明

2つの単調に増加したチェーンテーブルを入力し、2つのチェーンテーブルの合成後のチェーンテーブルを出力します.もちろん、合成後のチェーンテーブルは単調で減少しない規則を満たす必要があります.

考え方1

非再帰的な方法で、メモリを消費せず、2つのポインタはそれぞれチェーンテーブル要素を指し、2つの要素のサイズを比較し、小さいものは合成後のチェーンテーブルに接続し、1つのチェーンテーブルの末尾に達するまで接続します.次に、どのチェーンテーブルに要素があるかは、合成後のチェーンテーブルの後ろに直接接続すればいいです.プロセス中headはずっとそのheadですが、headが表す位置は最初のheadではありませんが、コンストラクション関数のオブジェクトが参照タイプなので、pheadはまだそのheadで、表す位置もその位置です.2つのポインタはそれぞれチェーンテーブル要素を指し、2つの要素のサイズを比較し、小さいものは合成後のチェーンテーブルに接続され、1つのチェーンテーブルの末尾に達します.次に、どのチェーンテーブルに要素があるかは、合成後のチェーンテーブルの後ろに直接接続すればいいです.

コード#コード#

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function Merge(pHead1, pHead2)
{
    function ListNode(x){
        this.val = x;
        this.next = null;
    }
    var head = new ListNode(0);
    var pHead = head;
    while(pHead1 != null && pHead2 != null){
        if(pHead1.val >= pHead2.val){
            head.next = pHead2;
            pHead2 = pHead2.next;
        }else{
            head.next = pHead1;
            pHead1 = pHead1.next;
        }
        head = head.next;
    }
    if(pHead1 != null){
        head.next = pHead1;
    }
    if(pHead2 != null){
        head.next = pHead2;
    }
    return pHead.next;
}

考え方2

再帰的な方法で、メモリを消費し、自身を使用して比較してマージします.考え1よりよく理解してありますか!

コード#コード#

function Merge(pHead1, pHead2)
{
    if(pHead1 == null) return pHead2;
    if(pHead2 == null) return pHead1;
    var node = null;
    if(pHead1.val > pHead2.val){
        node = pHead2;
        node.next = Merge(pHead1,pHead2.next);
    }else{
        node = pHead1;
        node.next = Merge(pHead1.next,pHead2);
    }
    return node;
}

17.木のサブ構造

タイトルの説明

2本の二叉木A,Bを入力し,BがAのサブ構造であるか否かを判断する.(ps:空の木は任意の木のサブ構造ではないと約束しました)

構想

BがAの子木か、BがAの右の子木か、BがAの左の子木かを比較します.ルート要素が同じ場合は、左サブツリーと右サブツリーの判断を開始します.

コード#コード#

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function isSubtree(pRoot1,pRoot2){
    if(pRoot2 == null) return true;  //pRoot2 null，         
    if(pRoot1 == null) return false;
    if(pRoot1.val == pRoot2.val){
        return isSubtree(pRoot1.left,pRoot2.left) && isSubtree(pRoot1.right,pRoot2.right)
    }else{
        return false;
    }
}
function HasSubtree(pRoot1, pRoot2)
{
    if(pRoot1 == null || pRoot2 == null){
        return false;
    }
    return isSubtree(pRoot1,pRoot2) || HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2);
}

18、ツリーミラー

タイトルの説明

指定したツリーを操作し、ソースツリーのミラーに変換します.

構想

まずルートの左右のノードを交換し,次に再帰呼び出し,左右のサブツリーを別々に処理する.

コード#コード#

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Mirror(root)
{
    // write code here
    if(root==null) return null;
    //          
    var  tmp = root.left;
    root.left=root.right;
    root.right=tmp;
    //  
    Mirror(root.left);
    Mirror(root.right);

}