Share my deffrient python code solution


  • 1
    D

    easy solution backtrace:

    # f(0) = [0]
    # f(1) = [0,1]
    # f(n+1) = duplicate(f(n)) 
    
    class Solution:
    	# @param A, a list of integer
        # @return an integer
    	def grayCode(self, n):
    		if n == 0:
    			return [0]
    		result = [0,1]
    		for x in range(1, n):
    			result = self.duplicate(result, x)
    		return result
    	def duplicate(self, result, n):
    		mask = 1<<n
    		length = len(result)
    		totalLen = 2*length
    		for x in range(length, 2*length):
    			result.append(result[totalLen-1-x] | mask)
    		return result
    

    at first i used a hard solution. code is below

    class Solution:
    	# @param A, a list of integer
        # @return an integer
    	def grayCode(self, n):
    		self.used = set()
    		self.len  = n
    		self.data = []
    
    		# print "data len " + str(self.len)
    		current = 0
    		self.data.append(current)
    		self.used.add(current)
    		# print "data length is " + str(len(self.data))
    		# print "all data num is " + str(1<<self.len)
    		while len(self.data) < (1<<self.len):		
    			current = self.getNext(current)
    			# if current == None:
    			# 	break
    			self.used.add(current)
    			self.data.append(current)
    		# print self.data
    		return self.data
    	def getNext(self, current):
    		# print "enter getNext"
    		for x in xrange(0,self.len):
    			data = self.changeOneBit(current, x, 1)
    			# print "changeOneBit 1 return :" + str(data)
    			if data not in self.used:
    				return data
    
    			data = self.changeOneBit(current, x, 0)
    			# print "changeOneBit 1 return :" + str(data)
    			if data not in self.used:
    				return data
    
    	def changeOneBit(self, current, offset, setbit):
    		if setbit:
    			mask = 1<<offset
    			return current | mask
    		else:
    			mask = ~(1<<offset)
    			return  current & mask

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.