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

栏目: 编程工具 · 发布时间: 5年前

内容简介:PS:一个下午和晚上才完成这道题,虽然知道面试不可能有这么多的时间,还是抑制不住兴奋跟大家分享一下,欢迎提提改善意见。1、这是个圆环,所以没有边界,要处理好数组的边界问题。

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解题算法

说明:

  1. 注释中,0表示暗,1表示亮。
  2. 算法复杂度为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 测试准备

  1. 写了一个随机生成数组的方法,来随机生成亮暗随机的100个灯。
function getData(num) {
    var list = [];
    for(var i = 0; i< num; i++){
        list[i] = Math.random() > 0.5 ? true : false
    }
    return list
}
  1. 写了个校验最终结果的方法,100个值看不过来。
function auth(list) {
    console.log(list);
    var status = true;
    for(var i =0; i<list.length;i++){
        if(!list[i]) {
            status = false
            break;
        }
    }
    if(status) {
        console.log("success:检验通过")
    } else {
        console.error("error:检验不通过");
    }
}

3.2 测试

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

3.3 测试结果,没进黑盒。

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


以上所述就是小编给大家介绍的《解--头条的算法面试题-圆环开关灯》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Spark SQL内核剖析

Spark SQL内核剖析

朱锋、张韶全、黄明 / 电子工业出版社 / 2018-8 / 69.00元

Spark SQL 是 Spark 技术体系中较有影响力的应用(Killer application),也是 SQL-on-Hadoop 解决方案 中举足轻重的产品。《Spark SQL内核剖析》由 11 章构成,从源码层面深入介绍 Spark SQL 内部实现机制,以及在实际业务场 景中的开发实践,其中包括 SQL 编译实现、逻辑计划的生成与优化、物理计划的生成与优化、Aggregation 算......一起来看看 《Spark SQL内核剖析》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

随机密码生成器
随机密码生成器

多种字符组合密码

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试