089 gray code
89. Gray Code
题目: https://leetcode.com/problems/gray-code/
难度: Medium
思路：
首先不是从任何一个数开始都是有效的，所以naive的想法是从任何一个开始，然后如果能到2^n位，那么说明是有效的，问题解决.
A gray code sequence must begin with 0. ->简化了一点
先写了一段代码：
def nextCode(curCode, res, n):
if curCode not in res:
res.append(curCode)
else:
return
if len(res) == pow(2,n):
return res
for i in range(n):
nCode = curCode[:]
nCode[i] = 1 if curCode[i] == 0 else 0
nextCode(nCode,res,n)
res = []
nextCode([0,0,0],res,3)
print res
#[[0, 0, 0], [1, 0, 0], [1, 1, 0], [0, 1, 0], [0, 1, 1], [1, 1, 1], [1, 0, 1], [0, 0, 1]]
实际上问题是这段代码的时间复杂度感觉很高，但是试试
不失所望，到11就超时
class Solution(object):
def grayCode(self, n):
"""
:type n: int
:rtype: List[int]
"""
def nextCode(curCode, res, n):
if curCode not in res:
res.append(curCode)
else:
return
if len(res) == pow(2,n):
return res
for i in xrange(n):
nCode = curCode[:]
nCode[i] = 1 if curCode[i] == 0 else 0
nextCode(nCode, res, n)
def listoVal(curCode,n):
val = 0
for i in range(n-1,-1,-1):
val += pow(2,i) * curCode[i]
return val
res = []
nextCode([0]*n, res, n)
# print res
val = []
for i in res:
val.append(listoVal(i,n))
return val
然后居然有这个东西： Gray code，要用位运算！瞑目
https://en.wikipedia.org/wiki/Gray_code
服气，这个待研究
class Solution(object):
def grayCode(self, n):
"""
:type n: int
:rtype: List[int]
"""
result = [(i>>1)^i for i in range(pow(2,n))]
return results
