136 Single Number
258 Add Digits
292 Nim Game
136 Single Number
问题描述：
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
思路：
从数组中找出只出现一次的元素，一般的想法是利用哈希表（字典）统计每个元素出现的次数，找出出现次数为1的元素。由于其他元素都出现了2次，而要找的元素只出现了1次，所以字典的值可以简化为布尔类型。但无论怎样，都不满足不使用额外空间的要求。
另一种办法是先排序，然后每次将两个元素之间进行比较，例如($a_1,a_2$)，($a_3,a_4$)，$\cdots$，如果不相同，则说明要找的元素在这组中。但最好的排序算法时间复杂度仍为$O(n\log n)$，不符合题目规定的线性运行时间。
符合要求的解法是利用异或运算符^，注意到有：
a^a=0 $\quad$0^a=a
另外，异或具有交换律。
所以对于一个数组 [1,2,5,2,1]，进行运算：
1^2^5^2^1 = (1^1)^(2^2)^5 = 5
这样就得到了我们想要的5，因为其他出现两次的元素在异或运算后都变成了0。
Python实现：
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
s = nums[0]
i = 1
while i < len(nums):
s = s ^ nums[i]
i += 1
return s
小结：
- 需注意单元素数组的情况
- 使用递归在某些测试样例上会造成内存超限
- 使用while循环比使用for in 循环速度要快
258 Add Digits
问题描述：
Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
For example:
Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.
Follow up:
Could you do it without any loop/recursion in O(1) runtime?
思路：
用循环肯定不符合$O(1)$的要求，将前40的数字以及他们对应的函数返回值写在纸上，便可以很容易发现规律：
| 函数值 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | ||
| 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | ||
| 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | ||
| 37 | 38 | 39 | 40 |
可以发现，与对9取余有很大关系，进一步总结规律如下：
- 如果num为0，那么返回0
- 如果num不为0，且num%9结果不为0，则返回num%9
- 如果num不为0，且num%9结果为0，则返回9
Python实现：
class Solution(object):
def addDigits(self, num):
"""
:type num: int
:rtype: int
"""
return (num % 9 or 9) if num else 0
小结：
- 同样的算法不一样的实现效果也区别很大
- 重新认识了Python中的逻辑运算符：or 和 and 均返回决定表达式真值的那个表达式的值。即：对于x and y，如果x为真，则y决定表达式的真值，返回y的值；如果x为假，则x决定了表达式的真值，返回x的值。or 运算符同理。
292 Nim Game
问题描述：
You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.
思路
这个问题乍看起来很复杂，但对小的情形分析后就能发现规律。假设有两个人A和B，A先报数，用●表示A赢，用○表示A输。则对于数字为1，2，3，4时的情形有：
| 1 | 2 | 3 | 4 |
|---|---|---|---|
| ● | ● | ● | ○ |
这很好理解，下面来看n=5，6，7，8时的情况：
| 5 | 6 | 7 | 8 |
|---|---|---|---|
| ● | ● | ● | ○ |
现在就需要解释一下。若n=5，则A第一次报1就可以保证胜利，因为B报数的范围为2~4，而不论哪种情况，A接下来都可以报到5。若n=6，A第一次报2即可；若n=7，A第一次报3即可。若n=8，A不论第一次报几，B只需要将数报到4，然后让A再开始报，A不论报几都无法报到8，而B一定能报出8，相当于重现了开始的状态。
最基础的一点是：当n=4时，先报的人一定会输。当数字增加时，只不过是这种情况的变化。如果n=5,6,7，那么A可以对应地报1,2,3，来使得B面对一种n=4且先报的局面，故而B就一定会输。而当n=8时，A不论第一次报几，B都可以报到4来使A面对那样的必输局面。数字更大的时候，依次类推。
则原题的答案就是：当4能整除n时，输；否则胜。
Python实现：
class Solution(object):
def canWinNim(self, n):
"""
:type n: int
:rtype: bool
"""
return bool(n%4)
小结：
- 先尝试小的情形