【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独

简介: 【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独

单词搜索

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        self.m = len(board)
        self.n = len(board[0])
        for i in range(self.m):
            for j in range(self.n):
                if board[i][j] == word[0]:
                    if self.check(board,i,j,word, 0):
                        return True
        return False
    
    def check(self, board, i, j, word, index):
        if i < 0 or i >= self.m or j < 0 or j >= self.n or board[i][j] != word[index]:
            return False
        if index == len(word) - 1:
            return True
        # 把当前坐标的值保存下来,为了在最后复原,回溯
        t = board[i][j]
        # 然后修改当前坐标的值,避免之前找到过的元素又被找到一次
        board[i][j] = '.'
        res = self.check(board,i,j-1,word,index + 1) or self.check(board,i,j+1,word,index + 1) or self.check(board,i-1,j,word,index + 1) or self.check(board,i+1,j,word,index + 1)      
        board[i][j] = t
        return res

N皇后问题

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def isValid(row, col):
            for i in range(row):
                for j in range(n):
                    # 注:左斜对角线上,同一条斜线上的每个位置满足行下标与列下标之差相等
                    # 注:右斜对角线上,同一条斜线上的每个位置满足行下标与列下标之和相等
                    if board[i][j] == 'Q' and (j == col or i + j == row + col or i-j == row-col):
                        return False
            return True
        def backtrack(board, row):
            if row >= n:
                cur_res = [''.join(row) for row in board]
                res.append(cur_res)
                return
            for i in range(n):
                if isValid(row, i, board):
                    board[row][i] = 'Q'
                    backtrack(board, row+1)
                    board[row][i] = '.'
        res = []
        board = [['.'] * n for _ in range(n)]
        backtrack(board,0)
        return res
# 优化,通过集合记录之前放置过元素的正向对角线,负向对角线,及列,判断当前点是否在集合中,在的话说明不满足要求
def solveNQueens(self, n: int) -> List[List[str]]:
        def isValid(row, col):
            # 注:左斜对角线上,同一条斜线上的每个位置满足行下标与列下标之差相等
            # 注:右斜对角线上,同一条斜线上的每个位置满足行下标与列下标之和相等
            if col in col_hash or (row + col) in pie_hash or (row-col) in na_hash:
                return False
            return True
        def backtrack(board, row):
            if row >= n:
                cur_res = [''.join(row) for row in board]
                res.append(cur_res)
                return
            for col in range(n):
                if isValid(row, col, board):
                    board[row][col] = 'Q'
                    pie_hash.add(row + col)
                    na_hash.add(row - col)
                    col_hash.add(col)
                    backtrack(board, row+1)
                    board[row][col] = '.'
                    pie_hash.remove(row + col)
                    na_hash.remove(row-col)
                    col_hash.remove(col)
        res = []
        board = [['.'] * n for _ in range(n)]
        pie_hash = set()
        na_hash = set()
        col_hash = set()
        backtrack(board,0)
        return res

判断有效数独

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row_set = [set() for _ in range(9)]
        col_set = [set() for _ in range(9)]
        square_set = [[set() for _ in range(3)] for _ in range(3)]  #3*3
        for i in range(9):
            for j in range(9):
                if board[i][j] in row_set[i] or board[i][j] in col_set[j] or board[i][j] in square_set[i//3][j//3]:
                    return False
                if board[i][j] != '.':
                    row_set[i].add(board[i][j])
                    col_set[j].add(board[i][j])
                    square_set[i//3][j//3].add(board[i][j])
        return True

解数独

解法一

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        nums = {"1", "2", "3", "4", "5", "6", "7", "8", "9"}
        row = [set() for _ in range(9)]
        col = [set() for _ in range(9)]
        palace = [[set() for _ in range(3)] for _ in range(3)]  # 3*3
        blank = []
        # 初始化,按照行、列、宫 分别存入哈希表
        for i in range(9):
            for j in range(9):
                ch = board[i][j]
                if ch == ".":
                    blank.append((i, j))
                else:
                    row[i].add(ch)
                    col[j].add(ch)
                    palace[i//3][j//3].add(ch)
        def dfs(n):
            if n == len(blank):
                return True
            i, j = blank[n]
            rst = nums - row[i] - col[j] - palace[i//3][j//3]  # 剩余的数字
            ### rst = nums - (row[i] | col[j] | palace[i//3][j//3])  
            if not rst:
                return False
            for num in rst:
                board[i][j] = num
                row[i].add(num)
                col[j].add(num)
                palace[i//3][j//3].add(num)
                if dfs(n+1):
                    return True
                row[i].remove(num)
                col[j].remove(num)
                palace[i//3][j//3].remove(num)
        dfs(0)

解法二

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.board = board
        self.solve()
    
    def findUnassigned(self):
        for row in range(9):
            for col in range(9):
                if self.board[row][col] == ".":
                    return row, col
        return -1, -1
    
    def solve(self):
        row, col = self.findUnassigned()
        #no unassigned position is found, puzzle solved
        if row == -1 and col == -1:
            return True
        for num in ["1","2","3","4","5","6","7","8","9"]:
            if self.isSafe(row, col, num):
                self.board[row][col] = num
                if self.solve():
                    return True
                self.board[row][col] = "."
        return False
            
    def isSafe(self, row, col, ch):
        boxrow = row - row%3
        boxcol = col - col%3
        if self.checkrow(row,ch) and self.checkcol(col,ch) and self.checksquare(boxrow, boxcol, ch):
            return True
        return False
    
    def checkrow(self, row, ch):
        for col in range(9):
            if self.board[row][col] == ch:
                return False
        return True
    
    def checkcol(self, col, ch):
        for row in range(9):
            if self.board[row][col] == ch:
                return False
        return True
       
    def checksquare(self, row, col, ch):
        for r in range(row, row+3):
            for c in range(col, col+3):
                if self.board[r][c] == ch:
                    return False
        return True


相关文章
|
29天前
|
C语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
11 1
|
14天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
1月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
26天前
力扣每日一题 6/11 暴力搜索
力扣每日一题 6/11 暴力搜索
10 0
|
26天前
|
算法
力扣经典150题解析之三十四:有效的数独
力扣经典150题解析之三十四:有效的数独
12 0
|
26天前
|
算法 测试技术 索引
力扣经典150题第三十二题:串联所有单词的子串
力扣经典150题第三十二题:串联所有单词的子串
10 0
|
26天前
|
算法
力扣经典150题第二十一题:反转字符串中的单词
力扣经典150题第二十一题:反转字符串中的单词
13 0
|
26天前
|
算法
力扣经典150题第十九题:最后一个单词的长度
力扣经典150题第十九题:最后一个单词的长度
12 0
|
1月前
|
容器
【LeetCode刷题】栈和队列题目练习~
【LeetCode刷题】栈和队列题目练习~
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(4)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总