つらい面接の質問、つらい面接の質問_PHP チュートリアル-PHPチュートリアル-php.cn

辛い面接の質問、辛い面接の質問

昨日、面接の質問を2つ見ました。最初の質問に答えた人は多かったですが、2番目の質問に答えた人はほとんどいませんでした。最近 PHP を勉強しているので、この記事では PHP をベースにして 2 回目の分析をお届けします。

面接での 2 つの質問を添付します:

1: ホールには 100 個のライトがあり、それぞれのライトには 1 から 100 までの番号が付いています。各ライトはスイッチによって制御されます。（スイッチを1回押すとライトが点灯し、もう一度押すと消灯します。スイッチの番号は制御されているライトと同じです。）最初はすべてのライトが消灯しています。次のルールに従ってスイッチを押してください。
初めてすべてのライトを点灯します。
2回目は2の倍数のスイッチをすべて押します。
3 回目は、3 の倍数のスイッチをすべて押します。
などなど。 N 回目は、N の倍数のスイッチをすべて押します。
ボタンを 100 回押した後、ホールにまだ点灯している照明が何個あるかを尋ねます。

2:27cmの細い木の棒があり、3cm、7cm、11cm、17cm、23cmの5つの位置にそれぞれアリがいます。木の棒は非常に細いので、同時にアリを通過することはできません。初めは、アリの頭が左を向いているか右を向いているかは任意で、アリは前進するか振り向くだけで、後退することはありませんでした。二匹のアリが出会うと、向きを変えて同時に反対方向に歩きます。アリが毎秒 1 センチメートル歩くことができると仮定します。すべてのアリが木の棒から離れる最小時間と最大時間を見つけるプログラムを作成してください。

1 つ目は比較的単純なので詳しくは説明しませんが、2 つ目は見ているだけで頭痛がしてしまいます。

この質問を簡単に分析してみましょう。

質問自体から判断すると、5 匹のアリの位置を同時に考えるのは非常に混乱しているようです。幸いなことに、質問の最後の文は、すべてのアリが木の棒から離れる最大時間と最小時間です。細い棒を水平軸として使用します。アリの位置が指定されています。最後に離れるアリの位置が =27 の場合、すべてのアリが木の棒から離れます。 (これはナンセンスのようです。)

秒速1メートル、この問題設定でも十分快適です。結局のところ、アリがここで移動する時間は、アリが移動する距離と数値的に同じです。 (すべてのアリが木の棒から離れ、元の速度で移動し続けるとみなした場合)。そしてそれらは同時に動いています。

アリの移動方向は左右の 2 方向のみです。座標軸の実際の状況を考慮して、右への移動を 1 とすると、同等の左への移動は -1 となります。このステップをコンピューターのバイナリの世界で考えることが重要です。

わかったかどうかは別として、ここからはもっと重要な内容です。

最大時間と最小時間を見つけることは、数字の山の中から最大値と最小値を見つけるのと同じです。この種のことは難しいことではありません。重要なのは、最後に比較を行った時期を見つけることです。時間は何かと何の関係があるのでしょうか？タイトルのデザインから判断すると、各アリの初期運動状態にのみ関係しているはずです。期間中のある瞬間における、あるアリの移動状況については、気にする必要があるでしょうか？必要なし。それは問題を複雑にするだけです。

アリの初期状態はいくつありますか? 2^5=32。明らかに、これら 32 種類のそれぞれの計算には時間がかかりますが、単純なループを使用できます。

アリの移動状況に注目する変数は位置と方向の２つだけです。そこで、ここでは単純に 2 つの配列 $arr と $b を紹介します。前者は特定の点の現在位置を表すために使用され、後者は現在の方向を表すために使用されます。 $b[i]

前述したように、値は -1 または 1 のみである必要があります。

これを念頭に置いて、考え方を整理して、配列 '$arr' と '$b' に初期値を割り当てることができます。時間 '$i' を使用してループを作成し、各アリが毎秒移動した後、'$arr[$k]==$arr[$k-1]' のときに、一致する状態値 '$b[k ]' を変更します。価値。すべての「$arr」の「値」が <=0 または >=27 の場合、ループを停止し、「$i」を返します。ループトラバーサルが多用されます。もちろん、簡単にするために、'$arr[$k]' がポール上になくなったら、unset() 関数を使用してそれを削除できます。最後に、'$arr'が空であると判断してループを終了します。

メインの内容について話した後、まだ細かい部分に対処する必要がありますが、アリの移動状態を記述する配列「$b」を生成する方法?

手動で生成することはできません。5 つのアリの場合は 32 の状況があり、10 つのアリの場合は 1024 の状況があります。手動で生成するのは非常に困難です。ただし、32 個の配列を生成する必要があることは明らかなので、それを使用する必要があります。したがって、10 進数を長さ 5 の 2 進数に変換することは容易に考えられます。次に、この 2 進数の 0 を -1 に置き換えます。置換された文字列を配列に変換します。

対応するコードを貼り付けます:

リーリー

これはルーチンであり、ルールに従い、段階的に実行していきますが、確かに非常に困難です。

----------------------------------------------- ---ゴージャスディバイダー--------------------------------------------------- ------ ----------------------------------

　　　在我一本正经地胡说八道后，就没有更加好的想法？

　　那就是相遇的时候，两只蚂蚁开始掉头。如果不掉头直接走呢？和他们掉头后有什么差别？结果是没有差别！每只蚂蚁开头拿一个接力棒，碰头后，两人交换接力棒，虽然蚂蚁掉头了，但接力棒可是一直往初始方向走哦~所以解题前景变得无比明朗。知道某只蚂蚁的初始状态，就知道他开始拿的接力棒最后走了多久！至于接力棒是不是亲生的，那你管哩。反正最后一个接力棒离开杆子，最后一只蚂蚁也离开杆子。

　　因而获得某种初始状态下的时间还可以这样写：

<span>function</span> getRes(<span>$b</span><span>){
    </span><span>$arr</span>=<span>array</span>(3,7,11,17,23<span>);
    </span><span>for</span>(<span>$i</span>=1;;<span>$i</span>++<span>){

        </span><span>foreach</span> (<span>$arr</span> <span>as</span> <span>$k</span> => <span>$val</span><span>) {
            </span><span>$arr</span>[<span>$k</span>]=<span>$val</span>+<span>$b</span>[<span>$k</span><span>];

            </span><span>if</span> ((<span>$arr</span>[<span>$k</span>]>=27)||(<span>$arr</span>[<span>$k</span>]<=0<span>)) {
                </span><span>unset</span>(<span>$arr</span>[<span>$k</span><span>]);
            }
        }

        </span><span>if</span> (<span>empty</span>(<span>$arr</span><span>)) {
            </span><span>return</span> <span>$i</span><span>;
        }


    }


}</span>

ログイン後にコピー

------------------------------------- ---华丽的分隔线------------------------------------------------------------------------------------------- 　　

　　当然问题可以更加简化，连上面的代码都用不到了。

　　通过上面分析可以看做每只蚂蚁直接走互不影响。到最后求最大值最小值的时候实际上可以先算出每只蚂蚁到两端的距离。形成五组数字。(3,24),(7,20),(11,16),(10,17),(4,23)在五组数每组数中较小值形成的5个数中最大的一个是最后结果的最小值。五组数每组数中较大的5个数中最大的那个是结果的最大值。很容易看出来是11和24。为什么呢？典型的木桶效应啊。最后一只蚂蚁走出去了才能算完成整个事情。五只蚂蚁全部最短路径出去，得到结果才可能是最快的，五只蚂蚁全部最长路径出去，耗时才能是最慢的。

　　ps:应该不会有更快的想法了吧。

　　　最后感谢@randeng在本问题上的指点~