[LeetCode] N-Queens II
LeetCode II queens
2023-09-11 14:17:25 时间
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
思路:和 N-queens 一样,不过只统计个数而言,更加简单了
class Solution { vector<int> x; int m_res; bool checkTwoPoints(int i, int j, int xi, int xj) { //cout << "check i\t" << i << endl; //cout << "check j\t" << j << endl; if(xi == xj) // same column return false; if( abs(xi-xj) == abs(i-j)) // diag return false; return true; } bool check(vector<int> x, int n) // check x[n] and x[0 .. n-1] { for(int i = 0; i < n; i++) { if(!checkTwoPoints(i, n, x[i], x[n])) return false; } return true; } void dfs(int n) { if(n == x.size() ) { //printVector(x); m_res ++; return; } for(int i = 0; i < x.size(); i++) { x[n] = i; // check if x[n] is available if(check(x, n)) dfs(n+1); } } public: int totalNQueens(int n) { x.resize(n); m_res = 0; dfs(0); return m_res; } };
相关文章
- Leetcode: Minimum Moves to Equal Array Elements II
- Leetcode: Number of Islands II && Summary of Union Find
- Leetcode: H-Index II
- LeetCode——Remove Duplicates from Sorted List II
- LeetCode高频题66. 加一,给你一个数组表示数字,则加1返回结果
- [LeetCode] Unique Paths
- [LeetCode]620. 有趣的电影
- LeetCode 146. LRU 缓存机制
- 179、【动态规划】leetcode ——115. 不同的子序列(C++版本)
- 158、【动态规划】leetcode ——518. 零钱兑换 II:二维数组+一维滚动数组(C++版本)
- 153、【动态规划】leetcode ——1049. 最后一块石头的重量 II:滚动数组(C++版本)
- 105、【树与二叉树】leetcode ——530. 二叉搜索树的最小绝对差:中序遍历递归法+迭代法(C++版本)
- 【LeetCode】Pascal's Triangle II (杨辉三角)
- 【LeetCode】154. Find Minimum in Rotated Sorted Array II (3 solutions)
- Leetcode Best Time to Buy and Sell Stock II
- Remove Duplicates from Sorted Array II -- LeetCode
- leetcode-combination sum and combination sum II
- [LeetCode] 1317. Convert Integer to the Sum of Two No-Zero Integers 将整数转换为两个无零整数的和
- [LeetCode] 1032. Stream of Characters 字符流
- [LeetCode] 998. Maximum Binary Tree II 最大二叉树之二
- [LeetCode] 850. Rectangle Area II 矩形面积之二
- [LeetCode] 711. Number of Distinct Islands II 不同岛屿的个数之二
- [LeetCode] Self Dividing Numbers 自整除数字
- [LeetCode] Arithmetic Slices II - Subsequence 算数切片之二 - 子序列
- [LeetCode] Find Leaves of Binary Tree 找二叉树的叶节点
- [LeetCode] Word Break II 拆分词句之二
- [LeetCode] 126. Word Ladder II 词语阶梯之二
- [LeetCode] 90. Subsets II 子集合之二
- [LeetCode] 103. Binary Tree Zigzag Level Order Traversal 二叉树的之字形层序遍历
- [LeetCode] Best Time to Buy and Sell Stock II 买股票的最佳时间之二
- [LeetCode] 113. Path Sum II 二叉树路径之和之二