搜尋
首頁後端開發php教程一道让人蛋疼的面试题,蛋疼面试题_PHP教程

一道让人蛋疼的面试题,蛋疼面试题

  昨日看到了两道面试题,有两道,第一道很多人都答出来了,第二道却鲜有人回答。我本人最近在学习php,所以本文以php为基础带来今天带来第二道的分析。

  附两道面试题:

  1:大厅里有100盏灯,每盏灯都编了号码,分别为1-100。每盏灯由一个开关来控制。(开关按一下,灯亮,再按一下灯灭。开关的编号与被控制的灯相同。)开始时,灯是全灭的。现在按照以下规则按动开关。
第一次,将所有的灯点亮。
第二次,将所有2的倍数的开关按一下。
第三次,将所有3的倍数的开关按一下。
以此类推。第N次,将所有N的倍数的开关按一下。
问第100次按完以后,大厅里还有几盏灯是亮的。


  2:有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细,不能同时通过一只蚂蚁。开始时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。

 

      第一道比较简单不多说了,第二道看着就让人头疼。

  简单分析一下这道题。

  从题本身来看,貌似同时考虑五个蚂蚁的位置着实让人摸不着头脑。所幸题的最后一句还是很有用的,所有蚂蚁都离开木杆的最大时间和最小时间。将细杆作为一个横向的坐标轴。蚂蚁位置都已经给出。当最后离开的蚂蚁的位置=27的时候,所有蚂蚁离开木杆。(这貌似是废话。)

  每秒1米,这样的题设足够让人舒服。毕竟在此处蚂蚁运动的时间数值上等于蚂蚁运动的路程的数值。(如果考虑所有蚂蚁离开木杆还继续保持原有速度运动的话)。并且它们是同时运动。

  蚂蚁的运动方向只有两个,向左或向右。考虑到坐标轴的实际情况,如果我们假设向右移动为1,那么等价向左移动为-1。在计算机的二元世界这一步考虑是非常重要的。

  好了,前面是铺垫,不管您看懂看不懂,下面是更加重点的内容。

  求最大时间和最小时间,就像我们在一堆数里面找最大数和最小数一样,这种事情应该不是很难。关键是找到最后做比较的时间。 时间和什么有关系?从题设来看,只应该和初始每只蚂蚁的运动状态有关。至于期间某个时刻某只蚂蚁的运动状态我们有必要纠结么?没必要。那样只会将问题复杂化。

  蚂蚁初始状态有几种?2^5=32种。显然这32种每种花费时间都要算,利用一个简单的循环就可以了。

  关注蚂蚁运动状态无非两个变量:位置和方向。因而在此处我简单引入两个数组 $arr和$b 。前者用来描述某个点的当前位置,后者用来当前方向。 $b[i] 

 如前面所描述的,取值只应该是-1或者1。

 

  考虑到这里,我们就可以捋顺思路,给数组'$arr'和'$b'赋予一个初始值。利用时间'$i'做循环,每一秒每只蚂蚁移动后,当'$arr[$k]==$arr[$k-1]'时,改变相匹配的状态值'$b[k]'的值。 当所有的'$arr'的'value'=27时,停止循环,返回'$i'。其中用了大量的循环遍历。当然为了简便,当'$arr[$k]'不再杆子上时,可以利用unset()函数将其删除。最后判断'$arr'为空就可以结束循环。

 

  讲完主体内容,我们还必须处理一个小细节,如何生成描述蚂蚁运动状态的数组"$b"?

  总不能手动生成吧,5只蚂蚁32种情况,10只蚂蚁1024种情况手动生成着实蛋疼。但你明明又知道生成32个数组,不能不利用。因而我们很容易想到将十进制数转化为长度为5的二进制数。再将这个二进制数中的0替换为-1。将替换后的字符串转化为数组。

  贴上相应代码:

<?<span>php
</span><span>for</span>(<span>$j</span>=0;<span>$j</span><32;<span>$j</span>++<span>){

    </span><span>$var</span>=<span>sprintf</span>("%05b", <span>$j</span><span>);

    </span><span>$var</span>=<span>str_replace</span>('1', '1|', <span>$var</span><span>);
    </span><span>$var</span>=<span>str_replace</span>('0', '-1|', <span>$var</span><span>);

    </span><span>$b</span>=<span>explode</span>('|',<span>$var</span><span>);

    </span><span>$res</span>=getRes(<span>$b</span><span>);


    </span><span>if</span> (<span>isset</span>(<span>$min</span><span>)) {
        </span><span>if</span> (<span>$res</span><<span>$min</span><span>) {
            </span><span>$min</span>=<span>$res</span><span>;

        }
    }</span><span>else</span><span>{
        </span><span>$min</span>=<span>$res</span><span>;
    }
    </span><span>if</span> (<span>isset</span>(<span>$max</span><span>)) {
        </span><span>if</span> (<span>$res</span>><span>$max</span><span>) {
            </span><span>$max</span>=<span>$res</span><span>;
        }
    }</span><span>else</span><span>{
        </span><span>$max</span>=<span>$res</span><span>;
    }
    </span><span>print_r</span>(<span>$b</span><span>);
    </span><span>echo</span> "此次结果是".<span>$res</span>.'   $max='.<span>$max</span>.'  $min='.<span>$min</span><span>;
    </span><span>echo</span> "<hr/>"<span>;

}


</span><span>echo</span> "最大值是".<span>$max</span>."最小值是".<span>$min</span><span>;


</span><span>//</span><span>获得某种情况下的时间</span>
<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><100;<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>]==@<span>$arr</span>[<span>$k</span>-1<span>]) {
                </span><span>$b</span>[<span>$k</span>]=-<span>$b</span>[<span>$k</span><span>];
                </span><span>$b</span>[<span>$k</span>-1]=-@<span>$b</span>[<span>$k</span>-1<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>

  这是按套路出牌的,循规蹈矩,一步一步走过来,但确实也十分辛苦。

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

 

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

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

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

<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在本问题上的指点~

 

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/1049393.htmlTechArticle一道让人蛋疼的面试题,蛋疼面试题 昨日看到了两道面试题,有两道,第一道很多人都答出来了,第二道却鲜有人回答。我本人最近在学习...
陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
您如何防止與會議有關的跨站點腳本(XSS)攻擊?您如何防止與會議有關的跨站點腳本(XSS)攻擊?Apr 23, 2025 am 12:16 AM

要保護應用免受與會話相關的XSS攻擊,需採取以下措施:1.設置HttpOnly和Secure標誌保護會話cookie。 2.對所有用戶輸入進行輸出編碼。 3.實施內容安全策略(CSP)限制腳本來源。通過這些策略,可以有效防護會話相關的XSS攻擊,確保用戶數據安全。

您如何優化PHP會話性能?您如何優化PHP會話性能?Apr 23, 2025 am 12:13 AM

优化PHP会话性能的方法包括:1.延迟会话启动,2.使用数据库存储会话,3.压缩会话数据,4.管理会话生命周期,5.实现会话共享。这些策略能显著提升应用在高并发环境下的效率。

什麼是session.gc_maxlifetime配置設置?什麼是session.gc_maxlifetime配置設置?Apr 23, 2025 am 12:10 AM

theSession.gc_maxlifetimesettinginphpdeterminesthelifespanofsessiondata,setInSeconds.1)它'sconfiguredinphp.iniorviaini_set().2)abalanceisesneededeededeedeedeededto toavoidperformance andunununununexpectedLogOgouts.3)

您如何在PHP中配置會話名?您如何在PHP中配置會話名?Apr 23, 2025 am 12:08 AM

在PHP中,可以使用session_name()函數配置會話名稱。具體步驟如下:1.使用session_name()函數設置會話名稱,例如session_name("my_session")。 2.在設置會話名稱後,調用session_start()啟動會話。配置會話名稱可以避免多應用間的會話數據衝突,並增強安全性,但需注意會話名稱的唯一性、安全性、長度和設置時機。

您應該多久再生一次會話ID?您應該多久再生一次會話ID?Apr 23, 2025 am 12:03 AM

會話ID應在登錄時、敏感操作前和每30分鐘定期重新生成。 1.登錄時重新生成會話ID可防會話固定攻擊。 2.敏感操作前重新生成提高安全性。 3.定期重新生成降低長期利用風險,但需權衡用戶體驗。

如何在PHP中設置會話cookie參數?如何在PHP中設置會話cookie參數?Apr 22, 2025 pm 05:33 PM

在PHP中設置會話cookie參數可以通過session_set_cookie_params()函數實現。 1)使用該函數設置參數,如過期時間、路徑、域名、安全標誌等;2)調用session_start()使參數生效;3)根據需求動態調整參數,如用戶登錄狀態;4)注意設置secure和httponly標誌以提升安全性。

在PHP中使用會議的主要目的是什麼?在PHP中使用會議的主要目的是什麼?Apr 22, 2025 pm 05:25 PM

在PHP中使用會話的主要目的是維護用戶在不同頁面之間的狀態。 1)會話通過session_start()函數啟動,創建唯一會話ID並存儲在用戶cookie中。 2)會話數據保存在服務器上,允許在不同請求間傳遞數據,如登錄狀態和購物車內容。

您如何在子域中分享會議?您如何在子域中分享會議?Apr 22, 2025 pm 05:21 PM

如何在子域名間共享會話?通過設置通用域名的會話cookie實現。 1.在服務器端設置會話cookie的域為.example.com。 2.選擇合適的會話存儲方式,如內存、數據庫或分佈式緩存。 3.通過cookie傳遞會話ID,服務器根據ID檢索和更新會話數據。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

將Eclipse與SAP NetWeaver應用伺服器整合。

MantisBT

MantisBT

Mantis是一個易於部署的基於Web的缺陷追蹤工具,用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。

Atom編輯器mac版下載

Atom編輯器mac版下載

最受歡迎的的開源編輯器

Dreamweaver Mac版

Dreamweaver Mac版

視覺化網頁開發工具

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版