Leetcode刷题第八天-回溯-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode刷题第八天-回溯。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

22：括号生成

链接：22. 括号生成 - 力扣（LeetCode）

括号是一对，所以每一次递归结束条件是字符串长度=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

generateParenthesis

89:格雷编码

链接：89. 格雷编码 - 力扣（LeetCode）

天哪噜，谁敢信这么个玩意做了一下午😢想复杂了，原本是想预设置一个'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)

grayCode

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