5.0 图
5.1 图的宽度优先遍历5.2 图的深度优先遍历5.3 拓扑排序算法5.4 prim算法5.5 Kruskal算法5.6 Dijkstra算法（迪杰斯特拉） 6. 前缀树（哈夫曼编码）
6.1 什么是前缀树 7. 贪心算法
7.1 会议问题7.2 解题套路7.3 字典序排序7.4 切金条（哈夫曼编码）7.5 花费和利润7.6 中位数 8.1 N皇后问题
5.0 图图的存储方式：
邻接表（以点为单位，把自己的相邻的点表示出来）
邻接矩阵如何表达图？生成图？有向图？无向图？
描述图
描述点
描述边
如何实现接口函数
跟二叉树的宽度优先遍历有什么区别？ 树是没有环的，而图是可能有环的。
图的宽度优先遍历
1，利用队列实现
2，从源节点开始依次按照宽度进队列，然后弹出
3，每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
4,直到队列变空
== 一个点出来后在处理==
广度优先遍历
1，利用栈实现
2，从源节点开始把节点按照深度放入栈，然后弹出
3，每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
4, 直到栈变空
一个点进去时再处理
适用范围：要求有向图，且有入度为0的节点，且没有环
import包，编译
寻找入度为0的点，然后寻找下一个入度为0 的点。
适用范围：要求无向图
生成最小生成树：一定要保证点的联通性，并且整体边的权值最小
从哪里出发无所谓，所有边都没有被解锁，从第一个点出发，然后进行解锁相邻边，向权重最低的边出发，到达第二个点，在解锁相邻边，依次类推。（如果权重最低的边两个都遍历过了，就找下一个权重最低的边）
package class06;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
// undirected graph only
public class Code05_Prim {
public static class EdgeComparator implements Comparator {
@Override
public int compare(Edge o1, Edge o2) {
return o1.weight - o2.weight;
}
}
public static Set primMST(Graph graph) {
// 解锁的边进入小根堆
PriorityQueue priorityQueue = new PriorityQueue<>(
new EdgeComparator());
HashSet set = new HashSet<>(); // 考察过的点
Set result = new HashSet<>(); // 一次挑选的边在result里
for (Node node : graph.nodes.values()) { // 处理森林问题，不连通的情况
// 随便挑一个点
// node是开始点
if (!set.contains(node)) {
set.add(node);
for (Edge edge : node.edges) { //由一个点，解锁所有相连的边
priorityQueue.add(edge); // 放在优先级队列里
}
while (!priorityQueue.isEmpty()) {
Edge edge = priorityQueue.poll(); // 弹出解锁的边中，最小的边
Node tonode = edge.to; // 可能的一个新的点
if (!set.contains(toNode)) { // 不含有的时候，就是新的点。
set.add(toNode);
result.add(edge);
for (Edge nextEdge : toNode.edges) {
priorityQueue.add(nextEdge);
}
}
}
}
}
return result;
}
5.5 Kruskal算法
1：20：00
适用范围：要求无向图
生成最小生成树：一定要保证点的联通性，并且整体边的权值最小
以边的角度出发，从最小的边出发，加边，然后判断把边加上能不能形成环，形成环的边就不加。（避圈法）
查并集
Dijkstra算法
适用范围：可以有权值为负数的边，不能有累加和为负数的环，单元最短路径算法。
2：04：00
一定要规定出发点，到目标点的最短距离。
先生成：
每一次在这张表中，选距离最短的点，然后该点更新到各点的最短距离，然后该点距离就固定且不用了。然后再挑剩下的距离最短的点，更新该点到各点的最小距离（min（15，3+2））
package class06;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
// no negative weight
public class Code06_Dijkstra {
public static HashMap dijkstra1(Node head) {
//从head出发到所有点的最小距离
//key：从head出发到达key
//value：从head出发到达key的最小距离
//如果在表中，没有T的记录，含义是从head出发到T这个点的距离为正无穷
HashMap distanceMap = new HashMap<>();
distanceMap.put(head, 0);
//已经求过距离的节点，存在selectedNodes中，以后再也不碰
HashSet selectedNodes = new HashSet<>();
Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
while (minNode != null) {
int distance = distanceMap.get(minNode);
for (Edge edge : minNode.edges) {
Node tonode = edge.to;
if (!distanceMap.containsKey(toNode)) {
distanceMap.put(toNode, distance + edge.weight);
}
distanceMap.put(edge.to, Math.min(distanceMap.get(toNode),
distance + edge.weight));
}
selectedNodes.add(minNode);
minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
}
return distanceMap;
}
// 选最小的距离的参数，但是不能是已经选过的点
public static Node getMinDistanceAndUnselectedNode(HashMap distanceMap,
HashSet touchedNodes) {
Node minNode = null;
int minDistance = Integer.MAX_VALUE;
for (Entry entry : distanceMap.entrySet()) {
Node node = entry.getKey();
int distance = entry.getValue();
if (!touchedNodes.contains(node) && distance < minDistance) {
minNode = node;
minDistance = distance;
}
}
return minNode;
}
小根堆方法
系统实现的堆 入堆后 改变不了值。 必须自己手动写
0：12：00
public static class NodeRecord {
public Node node;
public int distance;
public NodeRecord(Node node, int distance) {
this.node = node;
this.distance = distance;
}
}
// 自己改的堆
public static class NodeHeap {
private Node[] nodes; // 所有的节点放在数组里面
private HashMap heapIndexMap; // 任何一个节点在数组上的位置是 value值， 进来了弹出去了标为-1
private HashMap distanceMap; // 到head的值
private int size; // 一共有多少个节点
public NodeHeap(int size) {
nodes = new Node[size];
heapIndexMap = new HashMap<>();
distanceMap = new HashMap<>();
this.size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public void addOrUpdateOrIgnore(Node node, int distance) {
if (inHeap(node)) {
distanceMap.put(node, Math.min(distanceMap.get(node), distance));
insertHeapify(node, heapIndexMap.get(node)); // 往上交换 交换到小了，只能往上
}
if (!isEntered(node)) {// 从来没有进来过
nodes[size] = node;
heapIndexMap.put(node, size);
distanceMap.put(node, distance);
insertHeapify(node, size++);
}
// 进来过却不在堆上 ，啥都不做
}
public NodeRecord pop() {
NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
swap(0, size - 1);// 把堆上最后一个元素拿到堆顶
heapIndexMap.put(nodes[size - 1], -1); // 原本的头节点改为 -1
distanceMap.remove(nodes[size - 1]);
nodes[size - 1] = null;
heapify(0, --size);
return nodeRecord;
}
private void insertHeapify(Node node, int index) {
while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
swap(index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
private void heapify(int index, int size) {
int left = index * 2 + 1;
while (left < size) {
int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left])
? left + 1 : left;
smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
if (smallest == index) {
break;
}
swap(smallest, index);
index = smallest;
left = index * 2 + 1;
}
}
private boolean isEntered(Node node) { // node进没进来过
return heapIndexMap.containsKey(node);
}
private boolean inHeap(Node node) { // 是否在堆上
return isEntered(node) && heapIndexMap.get(node) != -1;
}
private void swap(int index1, int index2) { // 在堆上两个节点要换位置，heapIndexMap，nodes都要交换
heapIndexMap.put(nodes[index1], index2);
heapIndexMap.put(nodes[index2], index1);
Node tmp = nodes[index1];
nodes[index1] = nodes[index2];
nodes[index2] = tmp;
}
}
//改进后的dihkstra算法
// 从head出发，所有head能到达的节点，生成到达每个节点的最小路径记录并返回
public static HashMap dijkstra2(Node head, int size) {
NodeHeap nodeHeap = new NodeHeap(size);
nodeHeap.addOrUpdateOrIgnore(head, 0); // 之前有记录 变小了就更新
HashMap result = new HashMap<>();
while (!nodeHeap.isEmpty()) {
NodeRecord record = nodeHeap.pop();
Node cur = record.node;
int distance = record.distance;
for (Edge edge : cur.edges) {
nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
}
result.put(cur, distance);
}
return result;
}
6. 前缀树（哈夫曼编码）
6.1 什么是前缀树
没有增加，有就复用。
package class07;
public class Code01_TrieTree {
public static class TrieNode {
public int path; // 经过了几次，
public int end; // 是否是结尾的节点，是几个结尾的节点
public TrieNode[] nexts;
// HashMap nexts;
// TreeMap nexts;
public TrieNode() {
path = 0;
end = 0;
nexts[0] == null
//没有走向‘a’的路
//nexts[0]！=nul1有走向‘a'的路
//。。。
//nexts[25]！=nul1有走向‘z’的路
nexts = new TrieNode[26];
}
}
public static class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
if (word == null) {
return;
}
char[] chs = word.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) { // 开始从左往右遍历字符
index = chs[i] - 'a'; // 由字符，对应应走哪条路
if (node.nexts[index] == null) {
node.nexts[index] = new TrieNode();
}
node = node.nexts[index];
node.path++;
}
node.end++;
}
public void delete(String word) {
if (search(word) != 0) { // 确定树中确实加入过word，才删除
char[] chs = word.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (--node.nexts[index].path == 0) {// path为0， 后续节点都要删掉。
// 只有java可以这么写，
node.nexts[index] = null;
return;
}
node = node.nexts[index];
}
node.end--;
}
}
// word这个单词之前加入过几次
public int search(String word) {
if (word == null) {
return 0;
}
char[] chs = word.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
return 0;
}
node = node.nexts[index];
}
return node.end;
}
// 所有加入过的字符中，有几个是以pre这个字符串作为前缀的
public int prefixNumber(String pre) {
if (pre == null) {
return 0;
}
char[] chs = pre.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
return 0;
}
node = node.nexts[index];
}
return node.path;
}
}
public static void main(String[] args) {
Trie trie = new Trie();
System.out.println(trie.search("zuo"));
trie.insert("zuo");
System.out.println(trie.search("zuo"));
trie.delete("zuo");
System.out.println(trie.search("zuo"));
trie.insert("zuo");
trie.insert("zuo");
trie.delete("zuo");
System.out.println(trie.search("zuo"));
trie.delete("zuo");
System.out.println(trie.search("zuo"));
trie.insert("zuoa");
trie.insert("zuoac");
trie.insert("zuoab");
trie.insert("zuoad");
trie.delete("zuoa");
System.out.println(trie.search("zuoa"));
System.out.println(trie.prefixNumber("zuo"));
}
}
7. 贪心算法
贪心算法
在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫作贪心算法。
也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。
局部最优 -？->整体最优
7.1 会议问题一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束的时间（给你一个数组，里面是一个个具体的项目），你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。返回这个最多的宣讲场次。
找贪心策略。（时间优先不行，最短策略也不行）哪个会议结束时间早，就先安排
package class07;
import java.util.Arrays;
import java.util.Comparator;
public class Code04_BestArrange {
public static class Program {
public int start;
public int end;
public Program(int start, int end) {
this.start = start;
this.end = end;
}
}
public static class ProgramComparator implements Comparator {
@Override
public int compare(Program o1, Program o2) {
return o1.end - o2.end;
}
}
public static int bestArrange(Program[] programs, int start) {
Arrays.sort(programs, new ProgramComparator());
int result = 0;
// 从左往右依次遍历所有的会议
for (int i = 0; i < programs.length; i++) {
if (start <= programs[i].start) {
result++;
start = programs[i].end;
}
}
return result;
}
public static void main(String[] args) {
}
}
7.2 解题套路
贪心算法的在笔试时的解题套路
1，实现一个不依靠贪心策略的解法X，可以用最暴力的尝试
2，脑补出贪心策略A、贪心策略B、贪心策略C…
3，用解法X和对数器，去验证每一个贪心策略，用实验的方式得知哪个贪心策略正确
4，不要去纠结贪心策略的证明
策略必须具有传递性，局部最优
a字符串+b字符串 和 b字符串+a字符串进行比较
证明：1：36：00
之证明了具有传递性，接下来证明按照这样的方法排序是由效的。
package class07;
import java.util.Arrays;
import java.util.Comparator;
public class Code02_LowestLexicography {
public static class MyComparator implements Comparator {
@Override
public int compare(String a, String b) {
return (a + b).compareTo(b + a);
}
}
public static String lowestString(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
Arrays.sort(strs, new MyComparator());
String res = "";
for (int i = 0; i < strs.length; i++) {
res += strs[i];
}
return res;
}
public static void main(String[] args) {
String[] strs1 = { "jibw", "ji", "jp", "bw", "jibw" };
System.out.println(lowestString(strs1));
String[] strs2 = { "ba", "b" };
System.out.println(lowestString(strs2));
}
}
7.4 切金条（哈夫曼编码）
package class07;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Code03_LessMoneySplitGold {
public static int lessMoney(int[] arr) {
PriorityQueue pQ = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
pQ.add(arr[i]);
}
int sum = 0;
int cur = 0;
while (pQ.size() > 1) {
cur = pQ.poll() + pQ.poll();
sum += cur;
pQ.add(cur);
}
return sum;
}
public static class MinheapComparator implements Comparator {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2; // < 0 o1 < o2 负数
}
}
public static class MaxheapComparator implements Comparator {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1; // < o2 < o1
}
}
public static void main(String[] args) {
// solution
int[] arr = { 6, 7, 8, 9 };
System.out.println(lessMoney(arr));
int[] arrForHeap = { 3, 5, 2, 7, 0, 1, 6, 4 };
// min heap
PriorityQueue minQ1 = new PriorityQueue<>();
for (int i = 0; i < arrForHeap.length; i++) {
minQ1.add(arrForHeap[i]);
}
while (!minQ1.isEmpty()) {
System.out.print(minQ1.poll() + " ");
}
System.out.println();
// min heap use Comparator
PriorityQueue minQ2 = new PriorityQueue<>(new MinheapComparator());
for (int i = 0; i < arrForHeap.length; i++) {
minQ2.add(arrForHeap[i]);
}
while (!minQ2.isEmpty()) {
System.out.print(minQ2.poll() + " ");
}
System.out.println();
// max heap use Comparator
PriorityQueue maxQ = new PriorityQueue<>(new MaxheapComparator());
for (int i = 0; i < arrForHeap.length; i++) {
maxQ.add(arrForHeap[i]);
}
while (!maxQ.isEmpty()) {
System.out.print(maxQ.poll() + " ");
}
}
}
7.5 花费和利润
堆，
局部：花费最小，利润最大 。 全局： 则最优
复习一下：返回正数，第二个参数排前面；返回负数，第一个参数排前面
leetcode 502
package class07;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Code05_IPO {
public static class Node {
public int p;
public int c;
public Node(int p, int c) {
this.p = p;
this.c = c;
}
}
public static class MinCostComparator implements Comparator {
@Override
public int compare(Node o1, Node o2) {
return o1.c - o2.c;
}
}
public static class MaxProfitComparator implements Comparator {
@Override
public int compare(Node o1, Node o2) {
return o2.p - o1.p;
}
}
public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
Node[] nodes = new Node[Profits.length];
for (int i = 0; i < Profits.length; i++) {
nodes[i] = new Node(Profits[i], Capital[i]);
}
PriorityQueue minCostQ = new PriorityQueue<>(new MinCostComparator());
PriorityQueue maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
// 所有i项目扔到被锁池中，花费组织小根堆
for (int i = 0; i < nodes.length; i++) {
minCostQ.add(nodes[i]);
}
for (int i = 0; i < k; i++) { // 进行K轮
// 力所能及的项目，全解锁
while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
maxProfitQ.add(minCostQ.poll());
}
if (maxProfitQ.isEmpty()) {
return W;
}
W += maxProfitQ.poll().p;
}
return W;
}
}
7.6 中位数
一个数据流中，随时可以取得中位数
堆的题的应用和贪心没关系
大根堆小根堆配合
- 第一个数进大根堆r然后判断下一个数是否小于等于大根堆，如果满足进大根堆，不满足进小根堆比较两个根堆的size是否相差为2，相差为二的话，则从size较大的堆里堆顶弹出一个，进size较少的堆里，效果：较小的一半在大根堆里，较大的一半在小根堆里
package class07;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Code06_MadianQuick {
public static class MedianHolder {
private PriorityQueue maxHeap = new PriorityQueue(new MaxHeapComparator());
private PriorityQueue minHeap = new PriorityQueue(new MinHeapComparator());
private void modifyTwoHeapsSize() {
if (this.maxHeap.size() == this.minHeap.size() + 2) {
this.minHeap.add(this.maxHeap.poll());
}
if (this.minHeap.size() == this.maxHeap.size() + 2) {
this.maxHeap.add(this.minHeap.poll());
}
}
public void addNumber(int num) {
if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.add(num);
} else {
minHeap.add(num);
}
modifyTwoHeapsSize();
}
public Integer getMedian() {
int maxHeapSize = this.maxHeap.size();
int minHeapSize = this.minHeap.size();
if (maxHeapSize + minHeapSize == 0) {
return null;
}
Integer maxHeapHead = this.maxHeap.peek();
Integer minHeapHead = this.minHeap.peek();
if (((maxHeapSize + minHeapSize) & 1) == 0) {
return (maxHeapHead + minHeapHead) / 2;
}
return maxHeapSize > minHeapSize ? maxHeapHead : minHeapHead;
}
}
public static class MaxHeapComparator implements Comparator {
@Override
public int compare(Integer o1, Integer o2) {
if (o2 > o1) {
return 1;
} else {
return -1;
}
}
}
public static class MinHeapComparator implements Comparator {
@Override
public int compare(Integer o1, Integer o2) {
if (o2 < o1) {
return 1;
} else {
return -1;
}
}
}
// for test
public static int[] getRandomArray(int maxLen, int maxValue) {
int[] res = new int[(int) (Math.random() * maxLen) + 1];
for (int i = 0; i != res.length; i++) {
res[i] = (int) (Math.random() * maxValue);
}
return res;
}
// for test, this method is ineffective but absolutely right
public static int getMedianOfArray(int[] arr) {
int[] newArr = Arrays.copyOf(arr, arr.length);
Arrays.sort(newArr);
int mid = (newArr.length - 1) / 2;
if ((newArr.length & 1) == 0) {
return (newArr[mid] + newArr[mid + 1]) / 2;
} else {
return newArr[mid];
}
}
public static void printArray(int[] arr) {
for (int i = 0; i != arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
boolean err = false;
int testTimes = 200000;
for (int i = 0; i != testTimes; i++) {
int len = 30;
int maxValue = 1000;
int[] arr = getRandomArray(len, maxValue);
MedianHolder medianHold = new MedianHolder();
for (int j = 0; j != arr.length; j++) {
medianHold.addNumber(arr[j]);
}
if (medianHold.getMedian() != getMedianOfArray(arr)) {
err = true;
printArray(arr);
break;
}
}
System.out.println(err ? "Oops..what a fuck!" : "today is a beautiful day^_^");
}
}
8.1 N皇后问题
常数优化
2：49：00
package class08;
public class Code09_NQueens {
public static int num1(int n) {
if (n < 1) {
return 0;
}
int[] record = new int[n]; // record[i] -> i行的皇后 ，放在了第几列
return process1(0, record, n);
}
// 潜台词: record[0,,,i-1]的皇后，任何两个皇后一定不共行，不共列，不共斜线
// 目前来到了第i行，
// record[0,,,i-1] 表示之前的行， 放过了皇后的位置
// 整体一共有n行
// 返回值是摆完所有的皇后， 合理的摆法有多少种
public static int process1(int i, int[] record, int n) {
if (i == n) { // 终止行， 比最后一行再往下一行
return 1;
}
int res = 0;
for (int j = 0; j < n; j++) { // 当前行再i行，尝试i行所有的列j、
//当前i行的皇后，放在j列，会不会和之前（0..i-1）的皇后，共行共列或者共斜线，
//如果是，认为无效
//如果不是，认为有效
if (isValid(record, i, j)) {
record[i] = j;
res += process1(i + 1, record, n);
}
}
return res;
}
// record[0...i-1]你需要看，record[i...]不需要看
// 返回i行皇后，放在了j列，是否有效
public static boolean isValid(int[] record, int i, int j) {
for (int k = 0; k < i; k++) { // 之前的某个k行的皇后
if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
return false;
}
}
return true;
}
// 请不要超过32皇后问题
public static int num2(int n) {
if (n < 1 || n > 32) {
return 0;
}
int upperLim = n == 32 ? -1 : (1 << n) - 1;
// 生成二进制的数 8的数 0000‘’‘1111 1111 只使用位信息
// 右侧哪些区域是能进行限制的
return process2(upperLim, 0, 0, 0);
}
//colLim列的限制，1的位置不能放皇后，0的位置可以
//leftDiaLim左斜线的限制，1的位置不能放皇后，0的位置可以
//rightDialim右斜线的限制，1的位置不能放皇后，0的位置可以
// 限制可以进行左移，右移进行限制。
public static int process2(int upperLim, int colLim, int leftDiaLim,
int rightDiaLim) {
if (colLim == upperLim) { // base case 所有的皇后都合法， 皇后填满了
return 1; // 发现一种有效的
}
int pos = 0;
int mostRightOne = 0;
// 所有候选皇后的位置，都在pos上了， 用1表示
pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
int res = 0;
while (pos != 0) {
mostRightOne = pos & (~pos + 1); // 把一个二进制的数，最右侧的1提取出来
pos = pos - mostRightOne; // 试皇后
res += process2(upperLim, colLim | mostRightOne,
(leftDiaLim | mostRightOne) << 1,
(rightDiaLim | mostRightOne) >>> 1);
}
return res;
}
public static void main(String[] args) {
int n = 14;
long start = System.currentTimeMillis();
System.out.println(num2(n));
long end = System.currentTimeMillis();
System.out.println("cost time: " + (end - start) + "ms");
start = System.currentTimeMillis();
System.out.println(num1(n));
end = System.currentTimeMillis();
System.out.println("cost time: " + (end - start) + "ms");
}
}
pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
mostRightOne = pos & (~pos + 1); // 把一个二进制的数，最右侧的1提取出来
