Shell脚本 jetbrains js快速排序 二叉树排序 Flutter 分布式服务 function kubernetes tcp oauth postman tinymce Momentjs vue网站模板 大数据驾驶舱 数据库设计规范 js获取月份 a标签去除下划线 git下载项目 flutter优缺点 python计算器 python中的def python查找指定字符 python读取本地文件 java的继承 java编译 java运行环境配置 java基本语法 java正则表达式详解 java的安装 linux简介 php案例 黑客攻防实战入门 redis入门指南 kms神龙版 c语言代码表白 java核心技术 计价软件 黑市商人 地下城怎么双开
当前位置: 首页 > 学习教程  > 编程语言

LeetCode题解(0052):N皇后II(Python)

2021/1/13 20:40:49 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目:原题链接(困难) 标签:回溯算法 解法时间复杂度空间复杂度执行用时Ans 1 (Python)O(N!)O(N!)O(N!)O(N)O(N)O(N)64ms (38.68%)Ans 2 (Python)Ans 3 (Python) 解法一: class Solution:def totalNQueens(self, n: …

题目:原题链接(困难)

标签:回溯算法

解法时间复杂度空间复杂度执行用时
Ans 1 (Python) O ( N ! ) O(N!) O(N!) O ( N ) O(N) O(N)64ms (38.68%)
Ans 2 (Python)
Ans 3 (Python)

解法一:

class Solution:
    def totalNQueens(self, n: int) -> int:
        ans = []

        now = []  # 当前每行中皇后的位置
        columns = set()  # 当前已有皇后的列
        diagonal_right = set()  # 当前已有皇后的从右上到左下的斜线
        diagonal_left = set()  # 当前已有皇后的从左上到右下的斜线

        def track_back(row):
            # 处理已经回溯完成的情况
            if row == n:
                ans.append(["".join(["Q" if now[i] == j else "." for j in range(n)]) for i in range(n)])

            # 处理还没有回溯完成的情况
            else:
                for j in range(n):  # 遍历当前行中所有的列
                    if j in columns:  # 判断当前列是否已被占用
                        continue
                    if j + row in diagonal_right:  # 判断当前从右上到左下的斜线是否已被占用
                        continue
                    if j - row in diagonal_left:  # 判断当前从左上到右下的斜线是否已被占用
                        continue
                    # 继续进入当前分支
                    now.append(j)
                    columns.add(j)
                    diagonal_right.add(j + row)
                    diagonal_left.add(j - row)

                    track_back(row + 1)

                    # 移除当前分支
                    now.pop()
                    columns.remove(j)
                    diagonal_right.remove(j + row)
                    diagonal_left.remove(j - row)

        track_back(0)

        return len(ans)

本文链接: http://www.dtmao.cc/news_show_600396.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?