PHPを利用して『剣指offer』のチェーンテーブルを実現する(データ構造とアルゴリズム実戦)

必ず真剣に分析|注釈|テーマの要求を見なければなりません
Question 1
タイトル説明:チェーンテーブルを入力し、チェーンテーブルの各ノードの値を末尾から印刷します.
解析:チェーンテーブルは現在のノードを知ってこそ次のノードを知ることができるため、直接後ろから印刷することはできません.この逆シーケンスのアルゴリズム(ポリシー)は、スタックというデータ構造で解決するためによく使われています.そのため、チェーンテーブルをスタックに押し込んでからポップアップします.しかし、このようにするには、2回遍歴してから答えを出す必要があります.より奇妙な解決策は、ノード値を配列のヘッダに挿入することで、問題の要求を満たすことができます.コードは以下の通りです.

val = $x;
    }
}*/

function printListFromTailToHead($head)
{
    $stack = [];
    if(!$head){
        return $stack;
    }
    while($head){
        array_unshift($stack,$head->val);   #array_unshift            
        $head = $head->next;
    }
    return $stack;
}

テストアドレス:https://www.nowcoder.com/prac...
Question 2
タイトル説明:チェーンテーブルを入力し、チェーンテーブルの最後からk番目のノードを出力します.
分析:前提:チェーンテーブルは動的に割り当てられており、事前にチェーンテーブルの総長さを知ることができない一般的な考え方:チェーンテーブルを遍歴し、長さを導出し、結点面接の考え方を出力する:2つのポインタを準備し、最初のポインタがn-1(すなわちチェーンテーブルの末尾)、2番目のポインタが逆数kの位置に行くと、両者の間に差(n-1)-(n-k)=k-1があり、まず1つのポインタをk-1に行かせ、2番目のポインタはその場で待っていて、2番目のポインタと1番目のポインタを同時に歩かせて、最後まで歩いて、kを見つけて、コードは以下の通りです.

next != null){
                $head = $head->next;
            }else{
                 /*      ：          ，            k，     k-1          ，            */
                return null;
            }
        }
        /*            k-1     ，           ，        n-1   ，            k   ，       */
        while($head->next != null){
            $head = $head->next;
            $behind = $behind->next;
        }
        return $behind;
    }

テストアドレス:https://www.nowcoder.com/prac...
Question 3
タイトル説明:チェーンテーブルを入力し、チェーンテーブルを反転した後、チェーンテーブルのすべての要素を出力します.
分析:図面を描くのに最適なのは主に一時ノードを用いて注釈を見ることだ.

next;    #                   
            $pHead->next = $cur;    #                  

            $cur = $pHead;          #               
            $pHead = $tmp;          #              
        }
        return $cur;
    }

テストアドレス:https://www.nowcoder.com/prac...
Question 4
タイトルの説明:2つの単調に増加するチェーンテーブルを入力して、2つのチェーンテーブルの合成後のチェーンテーブルを出力して、もちろん私たちは合成後のチェーンテーブルが単調で減少しない規則を満たす必要があります.
分析:図面を描くのはまず頭の結点で大きさを比較して、小さい圧入の配列、大きいと小さい後の1位は引き続き比較します

val = $x;
    }
}*/
function MergeList($pHead1, $pHead2)
{
    // write code here
    /*
                  ，      ，             
    */
    if($pHead1 == null && $pHead2 == null){
        return null;
    }
    if($pHead1 == null){
        return $pHead2;
    }
    if($pHead2 == null){
        return $pHead1;
    }

    $target = array();

    if($pHead1 != null && $pHead2 != null){     #                            
        if($pHead1->val >= $pHead2->val){
            $target = $pHead2;
            $target->next = MergeList($pHead1,$pHead2->next);
        }else{
            $target = $pHead1;
            $target->next = MergeList($pHead1->next,$pHead2);
        }
    }
    return $target;
    
}

テストアドレス:https://www.nowcoder.com/prac...
Question 5
タイトルの説明:チェーンテーブルを指定

1.        
2.      （    ）

分析:最近segmentイラストに問題があるようですが、リンクバーリングチェーンテーブルをあげます.

function EntryNodeOfLoop($pHead)
{
    // write code here
    if($pHead == null){
        return null;
    }
    $fast = $pHead;
    $slow = $pHead;
    
    while($fast != null && $fast->next != null){
        $fast = $fast->next->next;
        $slow = $slow->next;
        if($fast == $slow){  #   
            $slow = $pHead;
            while($fast != $slow){ #  slow    
                $fast = $fast->next;
                $slow = $slow->next;
            }
            if($fast == $slow){
                    return $fast;
                }
   
        }
    }
   
    return null;
}

Question 6
テーマの説明:“ジョセフの環”は1つの数学の応用問題です:1群のサルが1周に並んで、1,2,...,n順に番号をつけます.そして1匹目から数えて、m匹目まで数えて、それを輪から蹴り出して、その後ろから数えて、m匹目まで数えて、それを蹴り出して...、このようにひっきりなしに進んで、最後にサルが1匹しか残っていないまで、そのサルは大王と呼ばれていました.このプロセスをプログラミングしてシミュレーションし、m、nを入力し、最後の王の番号を出力する必要があります.
分析:最初に出たサルはa[1]=m(mod)nに違いないが、このときあるサルの新しい番号をiとし、彼の元の番号は(i+a[1])%nである.

/**
* @param  $monkeys Array     
* @param  $m.    Int。         
* @param  $cur.  Int。     
*/
function JosephCircle($monkeys , $m , $current = 0){
    $number = count($monkeys);
    $num = 1;
    if(count($monkeys) == 1){
        echo $monkeys[0];
        return;
    }
    else{
        while($num++ < $m){
            $current++ ;
            $current = $current%$number;
        }
        echo $monkeys[$current];
        array_splice($monkeys , $current , 1);  #  
        JosephCircle($monkeys , $m , $current);
    }
}