解--头条的算法面试题-圆环开关灯

RayKr 发布于2019-08-23 15:38 / 2545人阅读

摘要：开关灯规则，触发一个灯的开关会影响旁边个灯取反。解题满足题干的开关灯规则开关灯，实现圆环的开关灯逻辑注意处理一下数组的边界情况即可左边右边解题算法说明注释中，表示暗，表示亮。检验通过检验不通过测试测试结果，没进黑盒。

1 看看题目

PS：一个下午和晚上才完成这道题，虽然知道面试不可能有这么多的时间，还是抑制不住兴奋跟大家分享一下，欢迎提提改善意见。

1.1题干分析

1、这是个圆环，所以没有边界，要处理好数组的边界问题。
2、100个灯泡，灯的数量是肯定的，这数组的长度可以保证。
3、开关灯规则，触发一个灯的开关会影响旁边2个灯（取反）。
4、要所有灯泡都亮，那么最后一次触发肯定是3个连续暗的灯泡在一起的情况。

2 解题 2.1满足题干的开关灯规则

// 开关灯，实现圆环的开关灯逻辑,注意处理一下数组的边界情况即可
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表示亮。

算法复杂度为n。

// 注释中，0表示暗，1表示亮。
function init(list) {
    var len = list.length;
    /*
    * 1、算法难度为n
    * 2、循环一遍，遇到暗灯就利用规则在下个位置触发开关灯,不考虑对后面的影响，因为会循环到
    * */
    for (var i = 0; i < len; i++) {
        if(!list[i]){
            list = trigger(i+1, list)
        }
    }

    /*
    * 循环结束后，最后可能出现4种情况(索引0-1，1表示亮，0表示灭)：00，01，10，11
    * 将前3情况预处理成（..0100...）的模式，我们要处理成..000...的情况，最后将灯点亮
    * Forward的index 是0100中的00的起始索引位置，请记住进入Forward时，list最后3个暗灯是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次开灯要为连续的3个暗灯（即000，其余为1），才能让所有灯都亮了，它就是做这件事的。
* 让0100中的00绕一圈到左边来=>0001=>全部点亮了
* */
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;
    // 防止死循环,正常情况不会超过list.length次的递归。
    if(num > list.length*1000) {
        return console.error("Forward 可能出现死循环！")
    }
    // 如果第3个位置是1就继续偏移
    if(list[i0]){
        // 这样的操作可以将连续的00的位置偏移3
        list = trigger(index+1,list)
        list = trigger(i1,list)

        return Forward(i1,list, num+1)
    } else {
        return trigger(index+1,list)
    }
}

3 测试 3.1 测试准备

写了一个随机生成数组的方法,来随机生成亮暗随机的100个灯。

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

写了个校验最终结果的方法,100个值看不过来。

function auth(list) {
    console.log(list);
    var status = true;
    for(var i =0; i
3.2 测试
var data = getData(100)
// console.log(JSON.parse(JSON.stringify(data)))
auth(init(data))
3.3 测试结果，没进黑盒。
在线看：https://codepen.io/FreadChen/...

GPU云服务器云服务器字符串算法面试题面试c语言算法编程题 linux的面试题 js的基础面试题

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/102359.html

对一道【脉脉】上头条算法面试题的思考

摘要：偶然间在脉脉上看到了一道头条的算法面试题按照题目的理解，简单的写了一个网页开始学的不仅是技术，更是梦想得到了如下效果图得到如题可以进行开关的示例在最后一个灯特殊处理，链接第一个灯，形成环经过测试发现只要从序号开始，如偶然间在脉脉上看到了一道头条的算法面试题 showImg(https://segmentfault.com/img/bVboxvT?w=1148&h=1080); 按照题...

tyheist 2019-08-23 15:18 评论0 收藏0
对一道【脉脉】上头条算法面试题的思考

摘要：偶然间在脉脉上看到了一道头条的算法面试题按照题目的理解，简单的写了一个网页开始学的不仅是技术，更是梦想得到了如下效果图得到如题可以进行开关的示例在最后一个灯特殊处理，链接第一个灯，形成环经过测试发现只要从序号开始，如偶然间在脉脉上看到了一道头条的算法面试题 showImg(https://segmentfault.com/img/bVboxvT?w=1148&h=1080); 按照题...

xuxueli 2019-07-31 10:05 评论0 收藏0
面试逻辑题

摘要：分享一下今天看到的几道逻辑题一群人开舞会，每人头上都戴着一顶帽子。根据题意可知，号码为的灯，拨开关的次数等于的约数的个数，约数个数是奇数，则一定是平方数。因为的平方等于，可知以内共有个平方数，即，最后关熄状态的灯共有盏，编号为。分享一下今天看到的几道逻辑题一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其它人帽子的颜色，却看不到自己的。主持人先...

renweihub 2019-08-20 16:41 评论0 收藏0
从简历被拒到收割今日头条 offer，我用一年时间破茧成蝶！

摘要：正如我标题所说，简历被拒。看了我简历之后说头条竞争激烈，我背景不够，点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收，也不过个月的时间，但这都是建立在我过去一年的积累啊。本文是无精疯同学投稿的面试经历关注微信公众号：进击的java程序员K，即可获取最新BAT面试资料一份在此感谢无精疯同学的分享目录：印象中的头条面试背景准备面试 ...

tracymac7 2019-08-15 17:57 评论0 收藏0
从简历被拒到收割今日头条 offer，我用一年时间破茧成蝶！

摘要：正如我标题所说，简历被拒。看了我简历之后说头条竞争激烈，我背景不够，点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收，也不过个月的时间，但这都是建立在我过去一年的积累啊。本文是无精疯同学投稿的面试经历关注微信公众号：进击的java程序员K，即可获取最新BAT面试资料一份在此感谢无精疯同学的分享目录：印象中的头条面试背景准备面试头条一面（Java+项目）头条...

wdzgege 2019-08-19 11:43 评论0 收藏0