찾다
백엔드 개발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으로 문의하세요.
PHP의 의존성 주입 : 일반적인 함정을 피하십시오PHP의 의존성 주입 : 일반적인 함정을 피하십시오May 16, 2025 am 12:17 AM

의존성 (di) inphpenhancescodeflexibility 및 testability는 decouplingdependencycreation fromusage.toimplementDieffectically : 1) addicontainersjudicuelyToavoidover-Engineering.2) indhe. 3) adhe

PHP 웹 사이트 속도를 높이는 방법 : 성능 조정PHP 웹 사이트 속도를 높이는 방법 : 성능 조정May 16, 2025 am 12:12 AM

toimproveyourphpwebsite의 성능, UsetheseStrospations : 1) ubstractOpCodeCachingWithOpCaceToSpeedUpscriptScriptIngretation.2) 최적화 된 AabaseQueriesBysElectingOnlynecessaryFields.3) UsecachingsystemsLikeredSormcedUcedUcedUcedALOW

PHP와 함께 대량 이메일 보내기 : 가능합니까?PHP와 함께 대량 이메일 보내기 : 가능합니까?May 16, 2025 am 12:10 AM

예, itispossibletosendmassemailswithphp.1) uselibraries -lifephpmailerorswiftmailerforfficialemailsending.2) emubledelaysbetemailstoavoidspamflags.3) personalizeemailsingdynamiccontenttoimproveengement.4) usequeuesystemslikerbitmbitmquredisb

PHP에서 의존성 주입의 목적은 무엇입니까?PHP에서 의존성 주입의 목적은 무엇입니까?May 16, 2025 am 12:10 AM

의존성 (di) inphpisadesignpatternthatachievesinversionofcontrol (ioc) by ancelociestobeinjectedintoclasses, 향상 모듈 성, 테스트 가능성 및 flexibility.didecouplesssclassessfromspecificimplementations, codemoremanageableandadapt

PHP를 사용하여 이메일을 보내는 방법?PHP를 사용하여 이메일을 보내는 방법?May 16, 2025 am 12:03 AM

PHP를 사용하여 이메일을 보내는 가장 좋은 방법은 다음과 같습니다. 1. 기본 전송에 Php 's Mail () 함수를 사용합니다. 2. phpmailer 라이브러리를 사용하여 더 복잡한 HTML 메일을 보내십시오. 3. Sendgrid와 같은 트랜잭션 메일 서비스를 사용하여 신뢰성 및 분석 기능을 향상시킵니다. 이러한 방법을 사용하면 이메일이받은 편지함에 도달 할뿐만 아니라 수신자를 유치 할 수 있습니다.

PHP 다차원 배열에서 총 요소 수를 계산하는 방법은 무엇입니까?PHP 다차원 배열에서 총 요소 수를 계산하는 방법은 무엇입니까?May 15, 2025 pm 09:00 PM

PHP 다차원 어레이에서 총 요소 수를 계산하는 것은 재귀 적 또는 반복적 인 방법을 사용하여 수행 할 수 있습니다. 1. 재귀 방법은 배열을 가로 지르고 중첩 배열을 재귀 적으로 처리함으로써 계산됩니다. 2. 반복 방법은 스택을 사용하여 깊이 문제를 피하기 위해 재귀를 시뮬레이션합니다. 3. Array_Walk_Recursive 함수도 구현할 수 있지만 수동 계산이 필요합니다.

PHP에서 DO-While 루프의 특성은 무엇입니까?PHP에서 DO-While 루프의 특성은 무엇입니까?May 15, 2025 pm 08:57 PM

PHP에서, do-while 루프의 특성은 루프 본체가 적어도 한 번 실행되도록하고 조건에 따라 루프를 계속할지 여부를 결정하는 것입니다. 1) 조건부 점검 전에 루프 본체를 실행하며, 사용자 입력 확인 및 메뉴 시스템과 같이 작업을 적어도 한 번 수행 해야하는 시나리오에 적합합니다. 2) 그러나, do-while 루프의 구문은 초보자들 사이에서 혼란을 야기 할 수 있으며 불필요한 성능 오버 헤드를 추가 할 수 있습니다.

PHP에서 문자열을 해시하는 방법은 무엇입니까?PHP에서 문자열을 해시하는 방법은 무엇입니까?May 15, 2025 pm 08:54 PM

PHP의 효율적인 해싱 스트링은 다음 방법을 사용할 수 있습니다. 1. 빠른 해싱에 MD5 기능을 사용하지만 비밀번호 저장에는 적합하지 않습니다. 2. SHA256 기능을 사용하여 보안을 향상시킵니다. 3. Password_hash 함수를 사용하여 비밀번호를 처리하여 최고 보안과 편의성을 제공하십시오.

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

Video Face Swap

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

VSCode Windows 64비트 다운로드

VSCode Windows 64비트 다운로드

Microsoft에서 출시한 강력한 무료 IDE 편집기

ZendStudio 13.5.1 맥

ZendStudio 13.5.1 맥

강력한 PHP 통합 개발 환경