用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的下标