成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

解--頭條的算法面試題-圓環(huán)開關(guān)燈

RayKr / 2576人閱讀

摘要：開關(guān)燈規(guī)則，觸發(fā)一個(gè)燈的開關(guān)會(huì)影響旁邊個(gè)燈取反。解題滿足題干的開關(guān)燈規(guī)則開關(guān)燈，實(shí)現(xiàn)圓環(huán)的開關(guān)燈邏輯注意處理一下數(shù)組的邊界情況即可左邊右邊解題算法說明注釋中，表示暗，表示亮。檢驗(yàn)通過檢驗(yàn)不通過測(cè)試測(cè)試結(jié)果，沒進(jìn)黑盒。

1 看看題目 
PS：一個(gè)下午和晚上才完成這道題，雖然知道面試不可能有這么多的時(shí)間，還是抑制不住興奮跟大家分享一下，歡迎提提改善意見。

1.1題干分析

1、這是個(gè)圓環(huán)，所以沒有邊界，要處理好數(shù)組的邊界問題。
2、100個(gè)燈泡，燈的數(shù)量是肯定的，這數(shù)組的長(zhǎng)度可以保證。
3、開關(guān)燈規(guī)則，觸發(fā)一個(gè)燈的開關(guān)會(huì)影響旁邊2個(gè)燈（取反）。
4、要所有燈泡都亮，那么最后一次觸發(fā)肯定是3個(gè)連續(xù)暗的燈泡在一起的情況。

2 解題 2.1滿足題干的開關(guān)燈規(guī)則 
// 開關(guān)燈，實(shí)現(xiàn)圓環(huán)的開關(guān)燈邏輯,注意處理一下數(shù)組的邊界情況即可
function trigger(index, list) {
    var len = list.length;
    if(index>=len) {
        index = index -len
    }
    // 左邊
    var left = index - 1;
    left = left >= 0 ? left : len - 1;

    // 右邊
    var right = index + 1;
    right = right >= len ? right - len : right;

    list[left] = !list[left];
    list[index] = !list[index];
    list[right] = !list[right];
    return list
}
2.2解題算法

說明：

注釋中，0表示暗，1表示亮。

算法復(fù)雜度為n。

// 注釋中，0表示暗，1表示亮。
function init(list) {
    var len = list.length;
    /*
    * 1、算法難度為n
    * 2、循環(huán)一遍，遇到暗燈就利用規(guī)則在下個(gè)位置觸發(fā)開關(guān)燈,不考慮對(duì)后面的影響，因?yàn)闀?huì)循環(huán)到
    * */
    for (var i = 0; i < len; i++) {
        if(!list[i]){
            list = trigger(i+1, list)
        }
    }

    /*
    * 循環(huán)結(jié)束后，最后可能出現(xiàn)4種情況(索引0-1，1表示亮，0表示滅)：00，01，10，11
    * 將前3情況預(yù)處理成（..0100...）的模式，我們要處理成..000...的情況，最后將燈點(diǎn)亮
    * Forward的index 是0100中的00的起始索引位置，請(qǐng)記住進(jìn)入Forward時(shí)，list最后3個(gè)暗燈是0100的排列的
    * */
    if(!list[0]&&!list[1]){            //  001111...
        list = trigger(2,list)  //  010011...
        return Forward(2,list)
    } else if(!list[0]&&list[1]) {     //  0111111...
        list = trigger(1,list)  //  1001111...
        list = trigger(3,list)  //  1010011...
        return Forward(3,list)
    } else if(list[0]&&!list[1]) {     //  101111111...
        list = trigger(2,list)  //  110011111...
        list = trigger(4,list)  //  110100111...
        return Forward(4,list)
    } else {
        return list
    }
}

/*
* 最后1次開燈要為連續(xù)的3個(gè)暗燈（即000，其余為1），才能讓所有燈都亮了，它就是做這件事的。
* 讓0100中的00繞一圈到左邊來=>0001=>全部點(diǎn)亮了
* */
function Forward(index, list, num) {
    num = num ? +num : 0
    var len = list.length
    var i0 = (index + 2) >= len ? index + 2 - len : index + 2;
    var i1 = (index + 3) >= len ? index + 3 - len : index + 3;
    // 防止死循環(huán),正常情況不會(huì)超過list.length次的遞歸。
    if(num > list.length*1000) {
        return console.error("Forward 可能出現(xiàn)死循環(huán)！")
    }
    // 如果第3個(gè)位置是1就繼續(xù)偏移
    if(list[i0]){
        // 這樣的操作可以將連續(xù)的00的位置偏移3
        list = trigger(index+1,list)
        list = trigger(i1,list)

        return Forward(i1,list, num+1)
    } else {
        return trigger(index+1,list)
    }
}
3 測(cè)試 3.1 測(cè)試準(zhǔn)備

寫了一個(gè)隨機(jī)生成數(shù)組的方法,來隨機(jī)生成亮暗隨機(jī)的100個(gè)燈。

function getData(num) {
    var list = [];
    for(var i = 0; i< num; i++){
        list[i] = Math.random() > 0.5 ? true : false
    }
    return list
}

寫了個(gè)校驗(yàn)最終結(jié)果的方法,100個(gè)值看不過來。

function auth(list) {
    console.log(list);
    var status = true;
    for(var i =0; i
3.2 測(cè)試

var data = getData(100)
// console.log(JSON.parse(JSON.stringify(data)))
auth(init(data))

3.3 測(cè)試結(jié)果，沒進(jìn)黑盒。

在線看：https://codepen.io/FreadChen/...

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/102359.html

相關(guān)文章

  • 對(duì)一道【脈脈】上 頭條 算法面試題的思考

    摘要：偶然間在脈脈上看到了一道頭條的算法面試題按照題目的理解，簡(jiǎn)單的寫了一個(gè)網(wǎng)頁(yè)開始學(xué)的不僅是技術(shù)，更是夢(mèng)想得到了如下效果圖得到如題可以進(jìn)行開關(guān)的示例在最后一個(gè)燈特殊處理，鏈接第一個(gè)燈，形成環(huán)經(jīng)過測(cè)試發(fā)現(xiàn)只要從序號(hào)開始，如 偶然間在脈脈上看到了一道頭條的算法面試題 showImg(https://segmentfault.com/img/bVboxvT?w=1148&h=1080); 按照題...

    tyheist 評(píng)論0 收藏0

  • 對(duì)一道【脈脈】上 頭條 算法面試題的思考

    摘要：偶然間在脈脈上看到了一道頭條的算法面試題按照題目的理解，簡(jiǎn)單的寫了一個(gè)網(wǎng)頁(yè)開始學(xué)的不僅是技術(shù)，更是夢(mèng)想得到了如下效果圖得到如題可以進(jìn)行開關(guān)的示例在最后一個(gè)燈特殊處理，鏈接第一個(gè)燈，形成環(huán)經(jīng)過測(cè)試發(fā)現(xiàn)只要從序號(hào)開始，如 偶然間在脈脈上看到了一道頭條的算法面試題 showImg(https://segmentfault.com/img/bVboxvT?w=1148&h=1080); 按照題...

    xuxueli 評(píng)論0 收藏0

  • 面試邏輯題

    摘要：分享一下今天看到的幾道邏輯題一群人開舞會(huì)，每人頭上都戴著一頂帽子。根據(jù)題意可知，號(hào)碼為的燈，撥開關(guān)的次數(shù)等于的約數(shù)的個(gè)數(shù)，約數(shù)個(gè)數(shù)是奇數(shù)，則一定是平方數(shù)。因?yàn)榈钠椒降扔冢芍詢?nèi)共有個(gè)平方數(shù)，即，最后關(guān)熄狀態(tài)的燈共有盞，編號(hào)為。 分享一下今天看到的幾道邏輯題 一群人開舞會(huì)，每人頭上都戴著一頂帽子。帽子只有黑白兩種，黑的至少有一頂。每個(gè)人都能看到其它人帽子的顏色，卻看不到自己的。主持人先...

    renweihub 評(píng)論0 收藏0

  • 從簡(jiǎn)歷被拒到收割今日頭條 offer，我用一年時(shí)間破繭成蝶！

    摘要：正如我標(biāo)題所說，簡(jiǎn)歷被拒?？戳宋液?jiǎn)歷之后說頭條競(jìng)爭(zhēng)激烈，我背景不夠，點(diǎn)到為止。。三準(zhǔn)備面試其實(shí)從三月份投遞簡(jiǎn)歷開始準(zhǔn)備面試到四月份收，也不過個(gè)月的時(shí)間，但這都是建立在我過去一年的積累啊。 本文是 無精瘋 同學(xué)投稿的面試經(jīng)歷 關(guān)注微信公眾號(hào)：進(jìn)擊的java程序員K，即可獲取最新BAT面試資料一份 在此感謝 無精瘋 同學(xué)的分享 目錄： 印象中的頭條 面試背景 準(zhǔn)備面試 ...

    tracymac7 評(píng)論0 收藏0

  • 從簡(jiǎn)歷被拒到收割今日頭條 offer，我用一年時(shí)間破繭成蝶！

    摘要：正如我標(biāo)題所說，簡(jiǎn)歷被拒?？戳宋液?jiǎn)歷之后說頭條競(jìng)爭(zhēng)激烈，我背景不夠，點(diǎn)到為止。。三準(zhǔn)備面試其實(shí)從三月份投遞簡(jiǎn)歷開始準(zhǔn)備面試到四月份收，也不過個(gè)月的時(shí)間，但這都是建立在我過去一年的積累啊。 本文是 無精瘋 同學(xué)投稿的面試經(jīng)歷 關(guān)注微信公眾號(hào)：進(jìn)擊的java程序員K，即可獲取最新BAT面試資料一份 在此感謝 無精瘋 同學(xué)的分享目錄：印象中的頭條面試背景準(zhǔn)備面試頭條一面（Java+項(xiàng)目）頭條...

    wdzgege 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<