NimGame

NimGame游戏的制胜策略

只要保证自己取走子后的游戏是平衡游戏就能保证自己胜利。

例子

如果有两个玩家，每一次取走的石子数量为1~3，那么请问初始石子数量是多少时，第一个玩家一定能获胜？且其取石子的策略是什么？

答案：只要石子的数量不能被4整除，第一个玩家一定能获胜，且获胜的策略是，先取石子，使得剩下石子的数量是4的倍数。以后每一次玩家2取完之后，玩家1都取一定数量的石子令剩余石子是4的倍数就可以了。

拓展

假如总共有K个石子, 每一次每个玩家可以取得石子数量为 n1~n2,求如何制胜。

玩家1的策略是每一次自己取完剩余石子的数量都是n1+n2的整数倍，就一定能获胜。所以第一局所取石子的个数为 K%(n1+n2)。

参考链接

红黑联盟组合数学，NimGame

#Valid Anagram(异序词)


    class Solution(object):
        def isAnagram(self, s, t):
            """
            :type s: str
            :type t: str
            :rtype: bool
            """
            fre = {}
            for char in s:
                char = char.lower()
                if fre.has_key(char):
                    fre[char] += 1
                else:
                    fre[char] = 1
            for char in t:
                char = char.lower()
                if not fre.has_key(char):
                    return False
                else:
                    fre[char] -= 1
            for val in fre.values():
                if val != 0:
                    return False
            return True

Climbing Stairs

一个楼梯有N层，每一次可以爬1层或者2层，请问，爬N层楼梯有多少中爬法？

归纳推理的过程

N = 1，那么只有1种。 N = 2, 有2种。（1+1,or 2) N = 3, N=3时爬的方式有：1. 先爬到1层（N-2），再走两层。2. 先爬到2层（N-1），再走两层。
总共的爬楼方式是 1+2 = 3种。 N = 4，等于 2+3等于5种。 N = 5，等于 3+5等于8种。

所以N层楼梯的爬楼方式有 Fibonacci(N-1)+Fibonacci(N-2) = Fibonacci(N)种。 所以这个问题完全转化成一个求斐波那契数列的问题
参考链接

Number of 1 bits

这个问题其实是求一个整数的2进制数的哈密顿距离，虽然比较简单但是解决问题的过程中出现了一些有趣的事实。本人从前到后写出的程序有4种，如下。进行分别分析

版本1 （64ms）

  def hammingWeight(self, n):
      s=bin(n)
      i=0
      for x in s[2:]:
          if x=='1':
              i+=1
      return i

版本2（56ms）

  def hammingWeight(self, n):
      ham = 0
      while(n > 0):
          if n%2==1:
              ham += 1
          n = n / 2
      return ham

版本3（52ms）

  def hammingWeight(self, n):
      ham = 0
      while(n > 0):
          if n%4 == 1 or n%4==2:
              ham += 1
          elif n%4 ==3:
              ham += 2
          else:
              pass
          n = n / 4
      return ham

版本4（52ms）

  def hammingWeight(self, n):
      return str(bin(n)).count('1')

可以看到不同版本的程序的运行时间，代码数量和可读性不同。第四个版本只用了一行代码就完成了同样的功能。

LintCode

OUTLINES

FEATURED TAGS