Open noogel opened 5 years ago
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
...
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class SolveNQueens {
public static void main(String[] args) {
SolveNQueens queens = new SolveNQueens();
System.out.println(queens.solveNQueens(5));
}
public List<List<String>> solveNQueens(int n) {
List<List<String>> resp = new ArrayList<>();
Set<Integer> cols = new HashSet<>();
Set<Integer> pie = new HashSet<>();
Set<Integer> na = new HashSet<>();
dfs(n, 0, new ArrayList<>(), resp, cols, pie, na);
return resp;
}
public void dfs(int max, int row, List<String> curState, List<List<String>> resp,
Set<Integer> cols, Set<Integer> pie, Set<Integer> na) {
// 终结条件
if (row >= max) {
if (curState.size() == max) {
resp.add(curState);
}
return;
}
// 循环列
for (int col = 0; col < max; col++) {
if (cols.contains(col) || pie.contains(row + col) || na.contains(row - col)) {
continue;
}
cols.add(col);
pie.add(row + col);
na.add(row - col);
curState.add(trans(col, max));
int size = curState.size();
List<String> newState = (max - row == 1) ? new ArrayList<String>() {{
addAll(curState);
}} : curState;
// 递归层
dfs(max, row + 1, newState, resp, cols, pie, na);
cols.remove(col);
pie.remove(row + col);
na.remove(row - col);
curState.remove(size - 1);
}
}
public String trans(int point, int max) {
char[] chars = new char[max];
for (int i = 0; i < max; i++) {
chars[i] = i == point ? 'Q' : '.';
}
return String.valueOf(chars);
}
}
给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
例如,给出 n = 3,生成结果为:
[---
title: 51. N皇后
date: 2019-08-20
tags: [算法, leetcode]
id: 1
---
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
根据递归做暴力处理,同时进行剪枝操作。
import java.util.ArrayList;
import java.util.List;
public class GenerateParenthesis {
public static void main(String[] args) {
GenerateParenthesis obj = new GenerateParenthesis();
List<String> stringList = obj.generateParenthesis(3);
System.out.println(stringList);
}
public List<String> generateParenthesis(int n) {
List<String> collect = new ArrayList<>();
gen(collect, "", n, n);
return collect;
}
public void gen(List<String> collect, String cur, int left, int right) {
if (left == 0 && right == 0) {
collect.add(cur);
return;
}
if (left > 0) {
gen(collect, cur + "(", left - 1, right);
}
if (right > 0 && right > left) {
gen(collect, cur + ")", left, right - 1);
}
}
}
实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert("apple"); trie.search("apple"); // 返回 true trie.search("app"); // 返回 false trie.startsWith("app"); // 返回 true trie.insert("app"); trie.search("app"); // 返回 true 说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。 保证所有输入均为非空字符串。
前缀树 Trie 字典树
public class Trie {
private final int SIZE = 26;
private Node root;
private class Node {
private boolean isStr;
private int num;
private Node[] child;
public Node() {
child = new Node[SIZE];
isStr = false;
num = 1;
}
}
public Trie() {
root = new Node();
}
public void insert(String word) {
if (null == word || word.isEmpty()) {
return;
}
Node pNode = this.root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (pNode.child[index] == null) {
Node tmp = new Node();
pNode.child[index] = tmp;
} else {
pNode.child[index].num++;
}
pNode = pNode.child[index];
}
pNode.isStr = true;
}
public boolean search(String word) {
if (null == word || word.isEmpty()) {
return false;
}
Node pNode = this.root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (pNode.child[index] == null || (word.length() - i == 1 && pNode.child[index].isStr == false)) {
return false;
}
pNode = pNode.child[index];
}
return true;
}
public boolean startsWith(String prefix) {
if (null == prefix || prefix.isEmpty()) {
return false;
}
Node pNode = this.root;
for (int i = 0; i < prefix.length(); i++) {
int index = prefix.charAt(i) - 'a';
if (pNode.child[index] == null) {
return false;
}
pNode = pNode.child[index];
}
return true;
}
}
数据结构
算法思想
分治法
分治法是基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
例子:快排、归并排序、MapReduce
贪心算法
贪心算法就是在每一步的选择中都按照当前最优的选择,从而希望最终结果得到最优解。贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说,问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。 贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。
例子:最小生成树、哈夫曼编码
动态规划(Dynamic Programming)
动态规划通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。常常适用于有重叠子问题和最优子结构性质的问题。 若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
适用情况:
例子:背包问题
https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92 https://www.zhihu.com/question/23995189/answer/613096905
回溯法(backtracking)
回溯法采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:
在最坏的情况下,回溯法会导致一次复杂度为指数时间的计算。
例子:八皇后问题
https://zh.wikipedia.org/wiki/%E5%9B%9E%E6%BA%AF%E6%B3%95 https://www.cnblogs.com/zuzZ/p/8178950.html
分支界限法
与贪婪算法一样,这种方法也是用来为组合优化问题设计求解算法的,所不同的是它在问题的整个可能解空间搜索,所设计出来的算法虽其时间复杂度比贪婪算法高,但它的优点是与穷举法类似,都能保证求出问题的最佳解,而且这种方法不是盲目的穷举搜索,而是在搜索过程中通过限界,可以中途停止对某些不可能得到最优解的子空间进一步搜索(类似于人工智能中的剪枝),故它比穷举法效率更高。
例子: N皇后问题 括号生成
概率算法
例子: 数值随机化算法 蒙特卡罗(Monte Carlo)算法 拉斯维加斯(Las Vegas)算法 舍伍德(Sherwood)算法
https://zhuanlan.zhihu.com/p/42619498