n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解:# 超级简单的套模板回溯法(Python)
如果采取完全暴力,时间复杂度是N^N肯定是不能通过的。
符合直觉的想法是剪枝, 比如选取了第一行,我们直接排除横竖斜三条线,然后继续选择。 关于如何排除,我们可以使用hashmap记录三个方向即可。 当不满足题意的时候,我们继续从头开始。
实际上回溯法和这个做法类似,只是每次不是从头,而是回退一步,继续尝试,不行的话继续回退一步。。。
以下是我经常使用解题模板,很多题目我都在用
# Code
```python
#
# @lc app=leetcode.cn id=51 lang=python3
#
# [51] N皇后
#
# @lc code=start
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res = []
empty = [['.'] * n for _ in range(n)]
row = set()
col = set()
ldiagonal = set()
rdiagonal = set()
def backtrack(result, temp, i, j, cnt):
if cnt == n:
return result.append([''.join(row) for row in temp])
for ii in range(i, n):
for jj in range(j, n):
if jj in col or ii + jj in ldiagonal or ii - jj in rdiagonal:
continue
temp[ii][jj] = 'Q'
row.add(ii)
col.add(jj)
ldiagonal.add(ii + jj)
rdiagonal.add(ii - jj)
backtrack(result, temp, ii + 1, 0, cnt + 1)
row.remove(ii)
col.remove(jj)
ldiagonal.remove(ii + jj)
rdiagonal.remove(ii - jj)
temp[ii][jj] = '.'
backtrack(res, empty, 0, 0, 0)
return res
# @lc code=end
```
给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。示例:输入: [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。说明:假设你总是可以到达数…
LeetCode题解140. 单词拆分 II批注: 由于"可以重复使用字典中的单词", 因此稍微难一点定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。说明:分隔时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1:输入:s = "catsanddog"wordDict = […
LeetCode题解计算机为什么是基于二进制的?可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制
LeetCode题解深度优先遍历和回溯的关系?深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。
LeetCode题解盲人买袜子。他们都各自买了两对黑袜和两对白袜,八对袜子的布质、大小完全相同,而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢?题解:暴力破解, 把袜子都拆开 一人一只 哈哈