LeetCode C++ 52. N-Queens II【回溯】困难
发布日期:2021-07-01 02:53:42
浏览次数:3
分类:技术文章
本文共 1727 字,大约阅读时间需要 5 分钟。
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n
, return the number of distinct solutions to the n-queens puzzle.
Example:
Input: 4Output: 2Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."]]
题意:计算合法的N皇后方案个数。
解法1 回溯法
这种题目做过很多次了,代码如下:
class Solution { private: vectorcolExist; vector colOfRows; //colOfRows记录每一行使用的列号 int ans = 0, maxRow, maxCol; //通过curRow的变化防止行的重复,通过colExist防止列的重复,通过check和colOfRows防止对角线的重复 bool check(int curRow, int col) { for (int i = 0; i < curRow; ++i) if (abs(colOfRows[i] - col) == abs(i - curRow)) return true; return false; } void dfs(int curRow) { if (curRow >= maxRow) { ++ans; return; } for (int i = 0; i < maxCol; ++i) { if (colExist[i] || check(curRow, i)) continue; colExist[i] = true; //选择了第i列 colOfRows[curRow] = i; //记录第i列的使用 dfs(curRow + 1); colExist[i] = false; } }public: int totalNQueens(int n) { maxRow = maxCol = n; colExist.resize(n); colOfRows.resize(n); dfs(0); return ans; }};
提交后结果如下:
执行用时:4 ms, 在所有 C++ 提交中击败了82.83% 的用户内存消耗:6.3 MB, 在所有 C++ 提交中击败了30.69% 的用户
解法二 打表
最快的方法:
class Solution { public: const int table[20] = { 0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712}; int totalNQueens(int n) { return table[n]; }};
提交后结果如下:
执行用时:0 ms, 在所有 C++ 提交中击败了100.00% 的用户内存消耗:5.9 MB, 在所有 C++ 提交中击败了67.39% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/109140148 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年05月02日 02时32分03秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
有了这些 Chrome 插件,效率提升10倍(建议收藏)
2019-05-01
只有1%的程序员搞懂过浮点数陷阱
2019-05-01
一名 Google 工程师的大数据处理经验
2019-05-01
命名难,难于上青天
2019-05-01
没钱没公司,怎么做一款付费产品
2019-05-01
代码整洁之道-编写 Pythonic 代码
2019-05-01
树莓派程序开机自启动
2019-05-01
连锁门店无线通信方案
2019-05-01
配置Lotus Domino集群视频详解
2019-05-01
Linux软件万花筒
2019-05-01
全球开源软件发展趋势分析
2019-05-01
Linux常用的安全工具
2019-05-01
python 多进程之进程池的操作
2019-05-01
flask整理之 flask程序中的debug模式
2019-05-01
比特币,父母这一辈能接受吗?
2019-05-01
SnapEx的新感觉,对新手很友好
2019-05-01
首个聚合器怎么产生的,并运用领域在什么
2019-05-01
区块链技术应用,最先医疗行业
2019-05-01
新币上市旧币会降价吗
2019-05-01