首页 > 其他 > 详细

leetcode-回溯②-难题

时间:2019-10-22 18:47:43      阅读:111      评论:0      收藏:0      [点我收藏+]

题10:

技术分享图片

 

 技术分享图片

 

 技术分享图片

 

 回溯:另:动态规划复杂度更低

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        def helper(s,p):
            if not p:
                return not bool(s)
            if len(p)>=2 and p[1]=="*":
                if s and (p[0] == "." or p[0] == s[0]) :
                    return helper(s[1:],p) or helper(s,p[2:])
                else:
                    return helper(s,p[2:])
            else  :
                if s and (p[0] == "." or p[0] == s[0]) :
                    return helper(s[1:],p[1:])
            return False
        return helper(s,p)

题37:

题52:

技术分享图片

 

 技术分享图片

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        s = "." * n
        def backtrack(i, tmp,col,z_diagonal,f_diagonal):
            if i == n:
                res.append(tmp)
                return 
            for j in range(n):
                if j not in col and i + j not in  z_diagonal and i - j not in f_diagonal:
                    backtrack(i+1,tmp + [s[:j] + "Q" + s[j+1:]], col | {j}, z_diagonal |{i + j} , f_diagonal |{i - j}  ) 
            
        backtrack(0,[],set(),set(),set())    
        return res

 

leetcode-回溯②-难题

原文:https://www.cnblogs.com/oldby/p/11721500.html

(1)
(1)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!