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 测试结果，没进黑盒。
在线看：https://codepen.io/FreadChen/…