題目連結:
給定兩個字串(兩字串長度一樣,且皆不超過 10, 000, 000 個字元),字串裡的字元只會是「0」或是「1」,分別代表一串燈泡的初始狀態與目前狀態。「1」代表對應位置的燈泡為亮著的;「0」則是關閉的。
設一燈泡串為 S1S2S3 ……,而其中的 S1 每 1 秒變換一次狀態(開變關,關變開)、 S2 每 2 秒變換一次、 S3 每 4 秒變換一次、…… 、Sk 每 2 ^ (k - 1) 秒變換一次。
求現在狀態下一秒的狀態為何?
00000
00000
----------------
10111
11111
10000
----------------
01111
其跟二進位制的數字 + 1 是一樣的想法,只是所需的二進位數字被隱藏在初始與目前狀態裡。
該數字實際上為初始狀態與目前狀態的差距。例,初始 = 11100 ,目前 = 10110 ,則其隱含的數字為 01010 (一樣表示沒有變換,不一樣表示有變換)。而根據燈泡變換的規律之定義,即為一個二進位數字。
接著就是將其加一。
加完之後的結果,再利用類似於上面的邏輯,將其轉回燈泡的狀態。並輸出即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。