N皇后

hollischuang · Dec 22, 2018 · 2aac3f3 · 2aac3f3
1 parent 5224fcf
commit 2aac3f3
Show file tree

Hide file tree

Showing 128 changed files with 96 additions and 0 deletions.
diff --git a/.gitignore b/.gitignore
diff --git a/README.md b/README.md
diff --git a/algorithm/README.md b/algorithm/README.md
diff --git a/algorithm/daily.md b/algorithm/daily.md
diff --git a/algorithm/leetcode/001-twoSum/hatrick.md b/algorithm/leetcode/001-twoSum/hatrick.md
diff --git a/algorithm/leetcode/001-twoSum/official.md b/algorithm/leetcode/001-twoSum/official.md
diff --git a/algorithm/leetcode/015-threeSum/hatrick.md b/algorithm/leetcode/015-threeSum/hatrick.md
diff --git a/algorithm/leetcode/015-threeSum/official.md b/algorithm/leetcode/015-threeSum/official.md
diff --git a/algorithm/leetcode/020-validParentheses/official.md b/algorithm/leetcode/020-validParentheses/official.md
diff --git a/algorithm/leetcode/024-swapNodesInPairs/official.md b/algorithm/leetcode/024-swapNodesInPairs/official.md
diff --git a/algorithm/leetcode/025-reverseNodesInKGroup/bigablecat.md b/algorithm/leetcode/025-reverseNodesInKGroup/bigablecat.md
diff --git a/algorithm/leetcode/025-reverseNodesInKGroup/official.md b/algorithm/leetcode/025-reverseNodesInKGroup/official.md
diff --git a/algorithm/leetcode/036-ValidSudoku/official.md b/algorithm/leetcode/036-ValidSudoku/official.md
diff --git a/algorithm/leetcode/037-SudokuSolver/official.md b/algorithm/leetcode/037-SudokuSolver/official.md
diff --git a/algorithm/leetcode/050-powxN/bigablecat.md b/algorithm/leetcode/050-powxN/bigablecat.md
diff --git a/algorithm/leetcode/051-NQueens/melody-l.md b/algorithm/leetcode/051-NQueens/melody-l.md
@@ -0,0 +1,96 @@
+>精简版答案示例，摘自本题的leetCode官方题解
+
+**051. NQueens**  
+---
+[https://leetcode-cn.com/problems/n-queens/](https://leetcode-cn.com/problems/n-queens/)  
+
+方法一：回溯法
+```java  
+
+public class Solution {
+    public List<List<String>> solveNQueens(int n) {
+        // 构造棋盘
+        char[][] board = new char[n][n];
+        // 初始化棋盘所有的棋子
+        for(int i = 0; i < n; i++)
+            for(int j = 0; j < n; j++)
+                board[i][j] = '.';
+        // 初始化结果集
+        List<List<String>> resultList = new ArrayList<List<String>>();
+        // 从第0列开始搜索所有结果，保存到resultList结果集中
+        search(board, 0, resultList);
+
+        return resultList;
+    }
+
+    /**
+     * 递归获取所有的结果
+     * @param board 棋盘
+     * @param column 所在列
+     * @param resultList 最终结果集
+     */
+    public void search(char[][] board, int column, List<List<String>> resultList) {
+        // 如果最后一列已经遍历完，则将棋盘保存，添加到最终结果集中并返回
+        if(column == board.length) {
+            resultList.add(construct(board));
+            return;
+        }
+
+        // 寻找第column列的哪一行适合放置皇后的位置
+        for(int i = 0; i < board.length; i++) {
+            // 如果在第i行，第column列添加皇后能够满足棋盘的0～column列不冲突
+            if(validate(board, i, column)) {
+                // 第i行，第column列放置一个皇后
+                board[i][column] = 'Q';
+                // 继续探索第column+1列适合放置皇后的位置
+                search(board, column + 1, resultList);
+                // 重置column列的结果，继续探索其他位置的可能性
+                board[i][column] = '.';
+            }
+        }
+    }
+
+    /**
+     * 验证将皇后放在第y列，第x行，是否可行
+     * 由于棋盘的0～y-1列的皇后位置都是有效的，
+     * 所以验证方式为：让0～y-1列的皇后与当前的皇后比，若都不存在冲突，则有效
+     * 冲突检测，正负对角线（测试斜率是否为正负一），是否同一行（不可能同列）
+     * @param board 棋盘
+     * @param x 所在行
+     * @param y 所在列
+     * @return 位置是否有效
+     */
+    public boolean validate(char[][] board, int x, int y) {
+        // 从第i行开始遍历
+        for(int i = 0; i < board.length; i++) {
+            // 从第j列开始遍历
+            for(int j = 0; j < y; j++) {
+                // 如果此位置为皇后，且
+                if(board[i][j] == 'Q' && (x - i == y - j || x - i == j - y || x == i))
+                    return false;
+            }
+        }
+
+        return true;
+    }
+
+    // 产生了一个结果集list序列
+    public List<String> construct(char[][] board) {
+        List<String> result = new LinkedList<String>();
+        for(int i = 0; i < board.length; i++) {
+            String s = new String(board[i]);
+            result.add(s);
+        }
+        return result;
+    }
+}
+
+```  
+
+---
+
+
+**参考资料**  
+
+* 网友推荐题解：  
+[https://leetcode.com/problems/n-queens/discuss/19805/My-easy-understanding-Java-Solution](https://leetcode.com/problems/n-queens/discuss/19805/My-easy-understanding-Java-Solution)  
diff --git a/algorithm/leetcode/051-NQueens/official.md b/algorithm/leetcode/051-NQueens/official.md
diff --git a/algorithm/leetcode/053-maximumSubarray/BambooYH.md b/algorithm/leetcode/053-maximumSubarray/BambooYH.md
diff --git a/algorithm/leetcode/053-maximumSubarray/official.md b/algorithm/leetcode/053-maximumSubarray/official.md
diff --git a/algorithm/leetcode/069-SqrtX/official.md b/algorithm/leetcode/069-SqrtX/official.md
diff --git a/algorithm/leetcode/098-validateBinarySearchTree/BambooYH.md b/algorithm/leetcode/098-validateBinarySearchTree/BambooYH.md
diff --git a/algorithm/leetcode/102-BinaryTreeLevelOrderTraversal/SpecialYang.md b/algorithm/leetcode/102-BinaryTreeLevelOrderTraversal/SpecialYang.md
diff --git a/algorithm/leetcode/102-BinaryTreeLevelOrderTraversal/official.md b/algorithm/leetcode/102-BinaryTreeLevelOrderTraversal/official.md
diff --git a/algorithm/leetcode/104-MaximumDepthOfBinaryTree/official.md b/algorithm/leetcode/104-MaximumDepthOfBinaryTree/official.md
diff --git a/algorithm/leetcode/122-bestTimeToBuyAndSellStockII/SpecialYang.md b/algorithm/leetcode/122-bestTimeToBuyAndSellStockII/SpecialYang.md
diff --git a/algorithm/leetcode/122-bestTimeToBuyAndSellStockII/bigablecat.md b/algorithm/leetcode/122-bestTimeToBuyAndSellStockII/bigablecat.md
diff --git a/algorithm/leetcode/141-linkedListCycle/official.md b/algorithm/leetcode/141-linkedListCycle/official.md
diff --git a/algorithm/leetcode/142-linkedListCycleII/bigablecat.md b/algorithm/leetcode/142-linkedListCycleII/bigablecat.md
diff --git a/algorithm/leetcode/169-majorityElement/SpecialYang.md b/algorithm/leetcode/169-majorityElement/SpecialYang.md
diff --git a/algorithm/leetcode/169-majorityElement/bigablecat.md b/algorithm/leetcode/169-majorityElement/bigablecat.md
diff --git a/algorithm/leetcode/206-reverseLinkedList/official.md b/algorithm/leetcode/206-reverseLinkedList/official.md
diff --git a/algorithm/leetcode/208-implementTriePrefixTree/official.md b/algorithm/leetcode/208-implementTriePrefixTree/official.md
diff --git a/algorithm/leetcode/212-wordSearchII/official.md b/algorithm/leetcode/212-wordSearchII/official.md
diff --git a/algorithm/leetcode/215-KthLargestElementInAnArray/BambooYH.md b/algorithm/leetcode/215-KthLargestElementInAnArray/BambooYH.md
diff --git a/algorithm/leetcode/225-implementStackUsingQueues/hatrick.md b/algorithm/leetcode/225-implementStackUsingQueues/hatrick.md
diff --git a/algorithm/leetcode/225-implementStackUsingQueues/official.md b/algorithm/leetcode/225-implementStackUsingQueues/official.md
diff --git a/algorithm/leetcode/232-implementQueueUsingStacks/hatrick.md b/algorithm/leetcode/232-implementQueueUsingStacks/hatrick.md
diff --git a/algorithm/leetcode/232-implementQueueUsingStacks/official.md b/algorithm/leetcode/232-implementQueueUsingStacks/official.md
diff --git a/algorithm/leetcode/236-lowestCommonAncestorOfABinaryTree/BambooYH.md b/algorithm/leetcode/236-lowestCommonAncestorOfABinaryTree/BambooYH.md
diff --git a/algorithm/leetcode/239-slidingWindowMaximum/official.md b/algorithm/leetcode/239-slidingWindowMaximum/official.md
diff --git a/algorithm/leetcode/242-ValidAnagram/bigablecat.md b/algorithm/leetcode/242-ValidAnagram/bigablecat.md
diff --git a/algorithm/leetcode/295-FindMedianFromDataStream/BambooYH.md b/algorithm/leetcode/295-FindMedianFromDataStream/BambooYH.md
diff --git a/algorithm/leetcode/367-ValidPerfectSquare/official.md b/algorithm/leetcode/367-ValidPerfectSquare/official.md
diff --git a/algorithm/leetcode/455-AssignCookies/SpecialYang.md b/algorithm/leetcode/455-AssignCookies/SpecialYang.md
diff --git a/algorithm/leetcode/455-AssignCookies/bigablecat.md b/algorithm/leetcode/455-AssignCookies/bigablecat.md
diff --git a/algorithm/leetcode/692-TopKFrequentWords/bigablecat.md b/algorithm/leetcode/692-TopKFrequentWords/bigablecat.md
diff --git a/algorithm/leetcode/703-KthLargestElementInAStream/BambooYH.md b/algorithm/leetcode/703-KthLargestElementInAStream/BambooYH.md
diff --git a/algorithm/leetcode/844-BackspaceStringCompare/BambooYH.md b/algorithm/leetcode/844-BackspaceStringCompare/BambooYH.md
diff --git a/algorithm/leetcode/844-BackspaceStringCompare/bigablecat.md b/algorithm/leetcode/844-BackspaceStringCompare/bigablecat.md
diff --git a/algorithm/leetcode/860-lemonadeChange/BambooYH.md b/algorithm/leetcode/860-lemonadeChange/BambooYH.md
diff --git a/algorithm/leetcode/860-lemonadeChange/SpecialYang.md b/algorithm/leetcode/860-lemonadeChange/SpecialYang.md
diff --git a/algorithm/leetcode/860-lemonadeChange/official.md b/algorithm/leetcode/860-lemonadeChange/official.md
diff --git a/algorithm/leetcode/874-walkingRobotSimulation/SpecialYang.md b/algorithm/leetcode/874-walkingRobotSimulation/SpecialYang.md
diff --git a/algorithm/leetcode/874-walkingRobotSimulation/official.md b/algorithm/leetcode/874-walkingRobotSimulation/official.md
diff --git a/algorithm/leetcode/954-ArrayOfDoubledPairs/bigablecat.md b/algorithm/leetcode/954-ArrayOfDoubledPairs/bigablecat.md
diff --git a/algorithm/leetcode/sample/concise.md b/algorithm/leetcode/sample/concise.md
diff --git a/algorithm/leetcode/sample/concise.png b/algorithm/leetcode/sample/concise.png
diff --git a/algorithm/leetcode/sample/full.md b/algorithm/leetcode/sample/full.md
diff --git a/algorithm/leetcode/sample/full.png b/algorithm/leetcode/sample/full.png
diff --git a/algorithm/剑指Offer/README.md b/algorithm/剑指Offer/README.md
diff --git a/contents/3_Java基础.md b/contents/3_Java基础.md
diff --git a/contents/4_JavaWeb.md b/contents/4_JavaWeb.md
diff --git a/contents/5_UML类图与设计模式.md b/contents/5_UML类图与设计模式.md
diff --git a/contents/CLanguageBase/CPlusPlusRelated.md b/contents/CLanguageBase/CPlusPlusRelated.md
diff --git a/contents/CLanguageBase/ConstructorAndDestructor.md b/contents/CLanguageBase/ConstructorAndDestructor.md
diff --git a/contents/CLanguageBase/Other.md b/contents/CLanguageBase/Other.md
diff --git a/contents/ComputerBasicKnowledge/Algorithm.md b/contents/ComputerBasicKnowledge/Algorithm.md
diff --git a/contents/ComputerBasicKnowledge/BigdateProcessing.md b/contents/ComputerBasicKnowledge/BigdateProcessing.md
diff --git a/contents/ComputerBasicKnowledge/ComputerNetworking.md b/contents/ComputerBasicKnowledge/ComputerNetworking.md
diff --git a/contents/ComputerBasicKnowledge/DataStructures.md b/contents/ComputerBasicKnowledge/DataStructures.md
diff --git a/contents/ComputerBasicKnowledge/Database.md b/contents/ComputerBasicKnowledge/Database.md
diff --git a/contents/ComputerBasicKnowledge/OperatingSystem.md b/contents/ComputerBasicKnowledge/OperatingSystem.md
diff --git a/contents/JavaBase/Collections.md b/contents/JavaBase/Collections.md
diff --git a/contents/JavaBase/Exceptions.md b/contents/JavaBase/Exceptions.md
diff --git a/contents/JavaBase/OOPFutures.md b/contents/JavaBase/OOPFutures.md
diff --git a/contents/JavaBase/Other.md b/contents/JavaBase/Other.md
diff --git a/contents/JavaSenior/IO.md b/contents/JavaSenior/IO.md
diff --git a/contents/JavaSenior/JVMUnderlyingTechnology.md b/contents/JavaSenior/JVMUnderlyingTechnology.md
diff --git a/contents/JavaSenior/MultiThreads.md b/contents/JavaSenior/MultiThreads.md
diff --git a/contents/JavaSenior/Other.md b/contents/JavaSenior/Other.md
diff --git a/contents/JavaSenior/hash.md b/contents/JavaSenior/hash.md
diff --git a/contents/JavaSenior/java-NIO-BIO-AIO.md b/contents/JavaSenior/java-NIO-BIO-AIO.md
diff --git a/contents/JavaWeb/CodingProblem.md b/contents/JavaWeb/CodingProblem.md
diff --git a/contents/JavaWeb/DynamicProxy.md b/contents/JavaWeb/DynamicProxy.md
diff --git a/contents/JavaWeb/Http.md b/contents/JavaWeb/Http.md
diff --git a/contents/JavaWeb/MVCFramework.md b/contents/JavaWeb/MVCFramework.md
diff --git a/contents/JavaWeb/Others.md b/contents/JavaWeb/Others.md
diff --git a/contents/JavaWeb/SSM.md b/contents/JavaWeb/SSM.md
diff --git a/contents/JavaWeb/ServiceContainer.md b/contents/JavaWeb/ServiceContainer.md
diff --git a/contents/JavaWeb/Servlet.md b/contents/JavaWeb/Servlet.md
diff --git a/contents/JavaWeb/WebSecurity.md b/contents/JavaWeb/WebSecurity.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/ChainOfResponsibilityPattern.md b/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/ChainOfResponsibilityPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/CommandPattern.md b/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/CommandPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/InterpreterPattern.md b/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/InterpreterPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/IteratorPattern.md b/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/IteratorPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/MediatorPattern.md b/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/MediatorPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/MementoPattern.md b/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/MementoPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/NullObjectPattern.md b/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/NullObjectPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/ObserverPattern.md b/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/ObserverPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/StatePattern.md b/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/StatePattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/StrategyPattern.md b/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/StrategyPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/TemplatePattern.md b/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/TemplatePattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/VisitorPattern.md b/contents/UMLClassDiagramAndDesignPattern/BehavioralPattern/VisitorPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/CreationPattern/AbstractFactoryPattern.md b/contents/UMLClassDiagramAndDesignPattern/CreationPattern/AbstractFactoryPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/CreationPattern/BuilderPattern.md b/contents/UMLClassDiagramAndDesignPattern/CreationPattern/BuilderPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/CreationPattern/FactoryPattern.md b/contents/UMLClassDiagramAndDesignPattern/CreationPattern/FactoryPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/CreationPattern/PrototypePattern.md b/contents/UMLClassDiagramAndDesignPattern/CreationPattern/PrototypePattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/CreationPattern/SingletonPattern.md b/contents/UMLClassDiagramAndDesignPattern/CreationPattern/SingletonPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/StructuralPattern/AdapterPattern.md b/contents/UMLClassDiagramAndDesignPattern/StructuralPattern/AdapterPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/StructuralPattern/BridgePattern.md b/contents/UMLClassDiagramAndDesignPattern/StructuralPattern/BridgePattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/StructuralPattern/CompositePattern.md b/contents/UMLClassDiagramAndDesignPattern/StructuralPattern/CompositePattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/StructuralPattern/DecoratorPattern.md b/contents/UMLClassDiagramAndDesignPattern/StructuralPattern/DecoratorPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/StructuralPattern/FacadePattern.md b/contents/UMLClassDiagramAndDesignPattern/StructuralPattern/FacadePattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/StructuralPattern/FilterCriteriaPattern.md b/contents/UMLClassDiagramAndDesignPattern/StructuralPattern/FilterCriteriaPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/StructuralPattern/FlyweightPattern.md b/contents/UMLClassDiagramAndDesignPattern/StructuralPattern/FlyweightPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/StructuralPattern/ProxyPattern.md b/contents/UMLClassDiagramAndDesignPattern/StructuralPattern/ProxyPattern.md
diff --git a/contents/UMLClassDiagramAndDesignPattern/UMLClassDiagram.md b/contents/UMLClassDiagramAndDesignPattern/UMLClassDiagram.md
diff --git a/contents/img/Aggregation.png b/contents/img/Aggregation.png
diff --git a/contents/img/Association.png b/contents/img/Association.png
diff --git a/contents/img/Composition.png b/contents/img/Composition.png
diff --git a/contents/img/Dependency.png b/contents/img/Dependency.png
diff --git a/contents/img/Generalization.png b/contents/img/Generalization.png
diff --git a/contents/img/Realization.png b/contents/img/Realization.png
diff --git a/java/Thread.md b/java/Thread.md
diff --git a/java/micro-service.md b/java/micro-service.md
diff --git a/java/netty.md b/java/netty.md
diff --git a/java/overview.md b/java/overview.md
diff --git a/java/spring.md b/java/spring.md