摘要:開關燈規(guī)則,觸發(fā)一個燈的開關會影響旁邊個燈取反。解題滿足題干的開關燈規(guī)則開關燈,實現(xiàn)圓環(huán)的開關燈邏輯注意處理一下數(shù)組的邊界情況即可左邊右邊解題算法說明注釋中,表示暗,表示亮。檢驗通過檢驗不通過測試測試結(jié)果,沒進黑盒。
1 看看題目
PS:一個下午和晚上才完成這道題,雖然知道面試不可能有這么多的時間,還是抑制不住興奮跟大家分享一下,歡迎提提改善意見。1.1題干分析
1、這是個圓環(huán),所以沒有邊界,要處理好數(shù)組的邊界問題。
2、100個燈泡,燈的數(shù)量是肯定的,這數(shù)組的長度可以保證。
3、開關燈規(guī)則,觸發(fā)一個燈的開關會影響旁邊2個燈(取反)。
4、要所有燈泡都亮,那么最后一次觸發(fā)肯定是3個連續(xù)暗的燈泡在一起的情況。
// 開關燈,實現(xiàn)圓環(huá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表示亮。
算法復雜度為n。
// 注釋中,0表示暗,1表示亮。 function init(list) { var len = list.length; /* * 1、算法難度為n * 2、循環(huán)一遍,遇到暗燈就利用規(guī)則在下個位置觸發(fā)開關燈,不考慮對后面的影響,因為會循環(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情況預處理成(..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次開燈要為連續(xù)的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; // 防止死循環(huán),正常情況不會超過list.length次的遞歸。 if(num > list.length*1000) { return console.error("Forward 可能出現(xiàn)死循環(huán)!") } // 如果第3個位置是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 測試 3.1 測試準備
寫了一個隨機生成數(shù)組的方法,來隨機生成亮暗隨機的100個燈。
function getData(num) { var list = []; for(var i = 0; i< num; i++){ list[i] = Math.random() > 0.5 ? true : false } return list }
寫了個校驗最終結(jié)果的方法,100個值看不過來。
function auth(list) { console.log(list); var status = true; for(var i =0; i3.2 測試 var data = getData(100) // console.log(JSON.parse(JSON.stringify(data))) auth(init(data))3.3 測試結(jié)果,沒進黑盒。在線看:https://codepen.io/FreadChen/...
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/102359.html
摘要:偶然間在脈脈上看到了一道頭條的算法面試題按照題目的理解,簡單的寫了一個網(wǎng)頁開始學的不僅是技術,更是夢想得到了如下效果圖得到如題可以進行開關的示例在最后一個燈特殊處理,鏈接第一個燈,形成環(huán)經(jīng)過測試發(fā)現(xiàn)只要從序號開始,如 偶然間在脈脈上看到了一道頭條的算法面試題 showImg(https://segmentfault.com/img/bVboxvT?w=1148&h=1080); 按照題...
摘要:偶然間在脈脈上看到了一道頭條的算法面試題按照題目的理解,簡單的寫了一個網(wǎng)頁開始學的不僅是技術,更是夢想得到了如下效果圖得到如題可以進行開關的示例在最后一個燈特殊處理,鏈接第一個燈,形成環(huán)經(jīng)過測試發(fā)現(xiàn)只要從序號開始,如 偶然間在脈脈上看到了一道頭條的算法面試題 showImg(https://segmentfault.com/img/bVboxvT?w=1148&h=1080); 按照題...
摘要:正如我標題所說,簡歷被拒??戳宋液啔v之后說頭條競爭激烈,我背景不夠,點到為止。。三準備面試其實從三月份投遞簡歷開始準備面試到四月份收,也不過個月的時間,但這都是建立在我過去一年的積累啊。 本文是 無精瘋 同學投稿的面試經(jīng)歷 關注微信公眾號:進擊的java程序員K,即可獲取最新BAT面試資料一份 在此感謝 無精瘋 同學的分享 目錄: 印象中的頭條 面試背景 準備面試 ...
摘要:正如我標題所說,簡歷被拒。看了我簡歷之后說頭條競爭激烈,我背景不夠,點到為止。。三準備面試其實從三月份投遞簡歷開始準備面試到四月份收,也不過個月的時間,但這都是建立在我過去一年的積累啊。 本文是 無精瘋 同學投稿的面試經(jīng)歷 關注微信公眾號:進擊的java程序員K,即可獲取最新BAT面試資料一份 在此感謝 無精瘋 同學的分享目錄:印象中的頭條面試背景準備面試頭條一面(Java+項目)頭條...
閱讀 3094·2021-09-22 15:54
閱讀 3981·2021-09-09 11:34
閱讀 1767·2019-08-30 12:48
閱讀 1161·2019-08-30 11:18
閱讀 3431·2019-08-26 11:48
閱讀 913·2019-08-23 17:50
閱讀 2119·2019-08-23 17:17
閱讀 1240·2019-08-23 17:12