用python寫leetcode的腦筋急轉彎題目

如有問題或建議請發郵箱[email protected]

三個腦筋急轉彎 更文時間：2018/11/04

用python刷leecode的題目

NIM遊戲

桌子上有一堆石頭，每次你們輪流拿掉 1 - 3 塊石頭。 拿掉最後一塊石頭的人就是獲勝者。你作為先手。編寫一個函數，來判斷你是否可以在給定石頭數量的情況下赢得遊戲。

我們可以假設一下,如果桌子上隻有1-3塊石頭,你第一次就可以全收走,一定會赢.而如果桌子上有4塊石頭,那麼,你不管先拿多少塊都不能赢.

是以,如果想赢的話,隻要在最後一輪的時候桌子上有4塊石頭,這時候正好輪到對方拿,就可以了.

怎麼樣控制呢?其實隻要我們先手的時候能讓桌子上剩餘的石頭是4的倍數就可以了,這時候無論對方拿多少個,你都拿4減去他的個數,這樣最後一定是剩下4個,而那時候正好該他拿了.

但是如果剛開始的時候,石頭個數正好是4的倍數,那麼如果對方很聰明的話,輸的人就是你了.

燈泡開關

初始時有 n 個燈泡關閉。 第 1 輪，你打開所有的燈泡。 第 2 輪，每兩個燈泡你關閉一次。 第 3 輪，每三個燈泡切換一次開關（如果關閉則開啟，如果開啟則關閉）。第 i 輪，每 i 個燈泡切換一次開關。 對于第 n 輪，你隻切換最後一個燈泡的開關。 找出 n 輪後有多少個亮着的燈泡。

假設一下,隻有十個燈會怎麼樣,第一輪,所有的燈都開;第二輪,2,4,6,8,10關閉,第三輪切換3,6,9的開關…

很容易發現,10号燈隻在1 2 5 10 這三輪會被切換開關,也就是燈号的公約數.而一個燈如果被切換了偶數次,他是關着的,若被切換了奇數次,他是開的.

而公約數總是成對出現的,是以最後開的燈一定是可開方的數字.比如9的公約數是1 3 9 其中3就是重疊的那個.

這樣就不難看出解法了,求出小于n的所有的平方數個數即可.

LR字元串交換位置

在一個由 'L' , 'R' 和 'X' 三個字元組成的字元串（例如"RXXLRXRXL"）中進行移動操作。一次移動操作指用一個"LX"替換一個"XL"，或者用一個"XR"替換一個"RX"。現給定起始字元串start和結束字元串end，請編寫代碼，當且僅當存在一系列移動操作使得start可以轉換成end時， 傳回True。

這個題意有點複雜,簡單來說就是,L隻能左移,R隻能右移,由于有X的存在,LR也是不能轉成RL的

這樣不難看出start能轉化成end的兩個重要條件了

1.去掉X後的兩個字元串必須一樣

2.start中的R的位置要比end中的R靠左,start中的L的位置要比end中的L靠前右

代碼思路:先把不符合條件1的篩掉,再用雙指針同時周遊兩個清單,遇到不是X的停下,比較兩者L/R的下标