内容简介: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解题算法
说明:
- 注释中,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<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 测试结果,没进黑盒。
以上所述就是小编给大家介绍的《解--头条的算法面试题-圆环开关灯》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 圆环旋转加显隐的加载效果
- 使用canvas绘制圆环动效
- css点滴3—5种方式实现圆环
- 炫酷的圆环加载及数字滚动效果(上)
- 炫酷的圆环加载及数字滚动效果(下)
- javascript – 谷歌圆环图表,包含未知数量的变量
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。