Leetcode刷题第八天-回溯
22:括号生成
括号是一对,所以每一次递归结束条件是字符串长度=2*n
有效括号判断:'('个数==')'个数时,当前必须是'(','('个数==n时,必须是')',其他情况当前位置遍历两边,既可以是'('又可以是')'
1 class Solution: 2 def generateParenthesis(self, n: int) -> List[str]: 3 if not n : return [] 4 re=[] 5 6 self.backtracking(2*n,re,"",0) 7 return re 8 def backtracking(self,n,re,path,index): 9 if(len(path)==n): 10 re.append(path) 11 return 12 for i in range(index,n): 13 num=self.isValid(path,i,n) 14 if(num): self.backtracking(n,re,path+num,i+1) 15 else: 16 self.backtracking(n,re,path+'(',i+1) 17 self.backtracking(n,re,path+')',i+1) 18 19 def isValid(self,path,index,n): 20 count1,count2=path.count('('),path.count(')') 21 if(count1==count2 ): return '(' 22 if(count1==n//2): return ')' 23 return 0
89:格雷编码
天哪噜,谁敢信这么个玩意做了一下午😢想复杂了,原本是想预设置一个'0'*n的字符串,然后挨个回溯,直到前一个结果只有一个字符和当前结果对应位置的字符不同,但是,我忘了“第一个 和 最后一个 整数的二进制表示 恰好一位不同”这么个条件😓
n是n-1结果加上n-1结果倒序挨个加上2^n
1 class Solution: 2 def grayCode(self, n: int) -> List[int]: 3 if(not n ): return [] 4 re=[0] 5 self.backtracking(re,n-1) 6 return re 7 def backtracking(self,re,n): 8 if(n==-1): return 9 self.backtracking(re,n-1) 10 lens=len(re)-1 11 for i in range(lens,-1,-1): 12 num=re[i]+2**n 13 re.append(num)
timeout版本:
1 class Solution: 2 def grayCode(self, n: int) -> List[int]: 3 if(not n ): return [] 4 num='0'*n 5 re=[num] 6 self.backtracking(re,num,n,0) 7 re=[self.get_result(i) for i in re] 8 return re 9 def backtracking(self,re,num,n,index): 10 if(index==n): index=0 11 if(len(re)==2**n): 12 if(re[len(re)-1].count("1")==1): return True 13 else: return False 14 tmp=num 15 for i in range(index,n): 16 if(num[i]=='0'): 17 num=num[:i]+'1'+num[i+1:] 18 else: 19 num=num[:i]+'0'+num[i+1:] 20 if(num[::-1] in re): 21 num=tmp 22 continue 23 re.append(num[::-1]) 24 if(self.backtracking(re,num,n,i+1)): return True 25 else: 26 num=tmp 27 re.pop() 28 return False 29 def get_result(self,num): 30 re=0 31 for i in range(len(num)-1,-1,-1): 32 re+=2**(len(num)-1-i)*int(num[i]) 33 return re
😢😢😢😢😢😢😢😢😢😢妈耶,今天一天才做两道,卡树杈子上了😢😢😢😢😢😢😢😢😢😢
下班下班,周末愉快
热门相关:惊艳人生 妖夏 护花猎王 神秘老公,晚上见! 与校花同居:高手风流