二、线性结构及算法

一、稀疏数组

1.1 实际需求

1.2 基本介绍

1.3 应用实例

package com.gyh.sparsearray;import java.util.Arrays;/*** @author Gao YongHao* @version 1.0*/
public class SparseArray {public static void main(String[] args) {// 创建一个原始的二维数组 11*11// 0: 表示没子  1：表示黑子  2：表示蓝子int[][] chessArr = new int[11][11];chessArr[1][2] = 1;chessArr[2][3] = 2;chessArr[5][6] = 2;// 原始二维数组for (int[] cRaw : chessArr) {for (int c : cRaw) {System.out.print(c + "\t");}System.out.println();}// 稀疏转换后int[][] ints = ToSparseArray(chessArr, 0);for (int[] cRaw : ints) {for (int c : cRaw) {System.out.print(c + "\t");}System.out.println();}// 恢复数组结构int[][] ints1 = restoreArray(ints, 0);for (int[] cRaw : ints1) {for (int c : cRaw) {System.out.print(c + "\t");}System.out.println();}}/*** 还原稀疏数组** @param sparseArray  稀疏数组* @param defaultValue 默认值* @return*/public static int[][] restoreArray(int[][] sparseArray, int defaultValue) {// 1、根据第一行数据创建数组int[][] ints = new int[sparseArray[0][0]][sparseArray[0][1]];// 设置默认值for (int[] anInt : ints) {Arrays.fill(anInt, defaultValue);}// 2. 变量sparseArray还原数组for (int i = 1; i < sparseArray.length; i++) {ints[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];}return ints;}/*** 二维数组转稀疏数组** @param arr          原始数组* @param defaultValue 默认值* @return*/public static int[][] ToSparseArray(int[][] arr, int defaultValue) {// 1、遍历原始二维数组（获取有多少种值）int sum = 0;for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr[i].length; j++) {if (arr[i][j] == defaultValue) continue;sum++;}}// 2. 创建稀疏数组int raw = 1;int[][] SparseArray = new int[sum + 1][3];SparseArray[0][0] = arr.length;SparseArray[0][1] = arr[0].length;SparseArray[0][2] = sum;// 给稀疏数组赋值for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr[i].length; j++) {if (arr[i][j] == defaultValue) continue;SparseArray[raw][0] = i;SparseArray[raw][1] = j;SparseArray[raw][2] = arr[i][j];raw++;}}return SparseArray;}
}

二、队列

2.1 引入

2.2 基本介绍

2.3 数组模拟队列

• 注：队列中 front指向队首元素的前面一个位置，rear指向队尾元素, maxSize表示队列的最大容量

package com.gyh.queue;/*** @author Gao YongHao* @version 1.0*/
public class Queue {public static void main(String[] args) {ArrayQueue arrayQueue = new ArrayQueue(5);arrayQueue.addQueue(1);arrayQueue.addQueue(2);arrayQueue.addQueue(3);arrayQueue.addQueue(4);arrayQueue.addQueue(5);arrayQueue.getQueue();arrayQueue.getQueue();arrayQueue.getQueue();arrayQueue.getQueue();arrayQueue.getQueue();// 出现伪溢出的现象（由于出队列后，空间不保存数据）arrayQueue.addQueue(6);}
}// 使用数组模拟队列---编写一个ArrayQueue
class ArrayQueue {private int maxSize; // 表示数组的最大容量private int front = -1; // 指向队列头（即：队首元素的前一个位置）private int rear = -1; // 指向队尾元素private int[] arr; // 该数组用于存放数据，模拟队列// 创建队列的构造器public ArrayQueue(int maxSize) {this.maxSize = maxSize;arr = new int[maxSize]; // 初始化数组}// 判断队列是否满public boolean isFull() {return rear == maxSize - 1;}// 判断队列是否空public boolean isEmpty() {return front == rear;}// 添加数据到队列public void addQueue(int data) {// 1、判断是否满if (isFull()) {System.out.println("队列满不能加入数据");return;}// 2. 添加数据arr[++rear] = data;}// 获取队列的数据，出队列public int getQueue(){// 判断是否为空if(isEmpty()){System.out.println("队列已空");throw new ArrayIndexOutOfBoundsException("队列为空");}return arr[++front];}// 显示当前队列的所有数据public void showQueue(){if(isEmpty()){System.out.println("队列为空");return;}for (int i : arr) {System.out.println(i);}}}

package com.gyh.queue;/*** @author Gao YongHao* @version 1.0* <p>* 考虑环状顺序(数组)队列*/
public class ArrayQueue2 {public static void main(String[] args) {AnnularArrayQueue annularArrayQueue = new AnnularArrayQueue(5);annularArrayQueue.addQueue(1);annularArrayQueue.addQueue(2);annularArrayQueue.addQueue(3);annularArrayQueue.addQueue(4);annularArrayQueue.getQueue();annularArrayQueue.getQueue();annularArrayQueue.getQueue();annularArrayQueue.addQueue(5);annularArrayQueue.addQueue(6);annularArrayQueue.addQueue(7);annularArrayQueue.showQueue();}
}class AnnularArrayQueue {private final int MAX_SIZE;private int front = 0; // 采用数据结构书中的用法，指向首个数据的位置private int rear = 0; // 采用数据结构书中的用法，指向最后一个数据的下一个private int[] arr;public AnnularArrayQueue(int maxSize) {this.MAX_SIZE = maxSize;arr = new int[maxSize];}public int getQueueLength() {return (rear - front + MAX_SIZE) % MAX_SIZE;}// 判断满public boolean isFull() {// 采用空出一个空间不填充值的方法，判断是否满return (rear + 1) % MAX_SIZE == front;}// 判断空public boolean isEmpty() {return front == rear;}// 添加数据public void addQueue(int data) {if (isFull()) {System.out.println("队列已满");return;}arr[rear] = data;rear = (rear + 1) % MAX_SIZE;}// 出队public int getQueue() {if (isEmpty()) {throw new ArrayIndexOutOfBoundsException("队列已空");}int data = arr[front];front = (front + 1) % MAX_SIZE;return data;}public void showQueue() {if (isEmpty()) {System.out.println("队列为空");return;}if (rear > front) {for (int i = front; i < rear; i++) {System.out.println(arr[i]);}} else {for (int i = 0; i < getQueueLength(); i++) {System.out.println(arr[(front + i) % MAX_SIZE]);}}}}

三、链表

3.1 链表介绍

3.2 单链表的应用实例

package com.gyh.Link;import java.util.Comparator;
import java.util.Objects;/*** @author Gao YongHao* @version 1.0*/
public class SingleLink {public static void main(String[] args) {Hero hero = new Hero(1, "宋江", "及时雨");Hero hero1 = new Hero(2, "卢俊义", "玉麒麟");Hero hero2 = new Hero(3, "吴用", "智多星");Hero hero3 = new Hero(4, "林冲", "豹子头");SLink<Hero> heroSLink = new SLink<>(Comparator.comparingInt(Hero::getNo));// 无排序添加heroSLink.add(hero);heroSLink.add(hero3);heroSLink.add(hero1);heroSLink.add(hero2);
//        heroSLink.list();// 有排序添加
//        heroSLink.addByOrder(hero);
//        heroSLink.addByOrder(hero3);
//        heroSLink.addByOrder(hero1);
//        heroSLink.addByOrder(hero2);// 修改信息
//        heroSLink.update(new Hero(1, "gyh", "sw"));// 删除信息heroSLink.remove(new Hero(1, null, null));heroSLink.list();}
}class SLink<T> {private int length = 0;private final Node<T> head = new Node<>(null, null); // 头指针(考虑有头结点的情况)private Comparator<T> compara;public SLink(Comparator<T> compara) {this.compara = compara;}// 修改结点public void update(T d) {Node<T> c = head;while (c.next != null) {int compare = compara.compare(c.next.getData(), d);if (compare == 0) {c.next.setData(d);break;}c = c.next;}}// 获取链表长度public int getLength() {return length;}//public void addByOrder(T d) {Node<T> c = head;boolean flag = true; // 标注最后是否进行赋值while (c.next != null) {int compare = compara.compare(c.next.getData(), d);if (compare > 0) { // 第一次遍历到比当前值大的值(c为当前值的前一个结点)break;} else if (compare == 0) { // 已经存在，不能添加flag = false;break;}c = c.next;}if (flag) {c.next = new Node<>(d, c.next);length++;} elseSystem.out.println("已经存在不能添加");}// 当不考虑标号的顺序时添加数据public void add(T d) {Node<T> c = head;// 找到最后的结点pwhile (c.next != null) {c = c.next;}c.setNext(new Node<>(d, null));length++;}// 删除public void remove(T d) {Node<T> c = head;int com;while (c.next != null) {com = compara.compare(c.next.getData(), d);if (com == 0) {c.next = c.next.next;break;}c = c.next;}}// 显示遍历链表public void list() {if (head.next == null) {System.out.println("链表为空");return;}Node<T> c = head.next;while (c != null) {System.out.println(c.data);c = c.next;}}}class Node<T> {T data;Node<T> next;public Node(T data, Node<T> next) {this.data = data;this.next = next;}public T getData() {return data;}public void setData(T data) {this.data = data;}public Node<T> getNext() {return next;}public void setNext(Node<T> next) {this.next = next;}
}class Hero {private int no;private String name;private String nickName;public Hero(int no, String name, String nickName) {this.no = no;this.name = name;this.nickName = nickName;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Hero hero = (Hero) o;return no == hero.no &&Objects.equals(name, hero.name) &&Objects.equals(nickName, hero.nickName);}@Overridepublic int hashCode() {return Objects.hash(no, name, nickName);}@Overridepublic String toString() {return "Hero{" +"no=" + no +", name='" + name + '\'' +", nickName='" + nickName + '\'' +'}';}public int getNo() {return no;}public void setNo(int no) {this.no = no;}public String getName() {return name;}public void setName(String name) {this.name = name;}public String getNickName() {return nickName;}public void setNickName(String nickName) {this.nickName = nickName;}
}

3.3 单链表面试题

package com.gyh.Link;import java.util.Stack;/*** @author Gao YongHao* @version 1.0*/
public class Test {public static void main(String[] args) {SLinkList<Hero> heroSLinkList = new SLinkList<>();Hero hero = new Hero(1, "宋江", "及时雨");Hero hero1 = new Hero(2, "卢俊义", "玉麒麟");Hero hero2 = new Hero(3, "吴用", "智多星");Hero hero3 = new Hero(4, "林冲", "豹子头");heroSLinkList.add(hero);heroSLinkList.add(hero1);heroSLinkList.add(hero2);heroSLinkList.add(hero3);//        heroSLinkList.reverseLink();heroSLinkList.printReverseLinkList();
//        heroSLinkList.list();}
}class SLinkList<T> {private int length = 0;private final Node<T> head = new Node<>(null, null); // 头指针(考虑有头结点的情况)public void add(T d) {Node<T> c = head;// 找到最后的结点pwhile (c.next != null) {c = c.next;}c.setNext(new Node<>(d, null));length++;}// 求单链表汇总有效结点的个数（不计头结点）public int getLength() {Node<T> c = head;if (c.next == null) return 0;int n = 0;while (c.next != null) {n++;c = c.next;}return n;}// 查找单链表中的倒数第k个结点// 1. 编写一个方法，接收head结点，同时接收一个index// 2. index 表示是倒数第index个结点// 3. 先把链表从头到尾遍历，得到链表的总长度 size// 4. 得到 size 后，我们从链表的第一个开始遍历（size - index）// 5. 如果找到了则返回该结点，否则返回nullpublic T getNode(int index) {Node<T> c = head;int length = 0;while (c.next != null) {length++;c = c.next;}if (length == 0) return null;c = head.next;for (int i = 0; i < length - index; i++) {c = c.next;}return c.getData();}// 单链表的反转// 先定义一个结点 reverseHead=new Node// 从头到尾遍历原来的链表，每遍历一个结点，就将其取出，并放在新的链表的最前端(头插法)// 原来的链表的 head.next = reverseHead.nextpublic void reverseLink() {// 1. 没有数据或只有一个数据，就不操作if (head.next == null || head.next.next == null) return;// 设置反转链表的头结点Node<T> reverseHead = new Node<>(null, null);Node<T> cur = head.next;// 指向当前的结点Node<T> next; // 指向当前结点[cur]的下一个结点while (cur != null) {// 暂时保存当前结点的下一个结点next = cur.next;// 头插法cur.next = reverseHead.next;reverseHead.next = cur;// 更新当前结点位置cur = next;}head.next = reverseHead.next;}// 从尾到头打印单链表[要求 方式1：反向遍历。方式2：Stack栈]// 上面的题的要求就是逆序打印单链表// 方式1：先将单链表进行反转操作，然后再遍历即可,这样做的问题就是会破坏原来的单链表的结构，不建议// * 方式2：可以利用栈这个数据结构，将各个结点压入栈中，然后利用栈的先进后出的特点，就实现了逆序打印public void printReverseLinkList() {if (head.next == null) return;Stack<T> stack = new Stack<>();// 遍历压栈Node<T> cur = head.next;while (cur != null) {stack.push(cur.getData());cur = cur.next;}// 出栈打印while (stack.size() > 0) {System.out.println(stack.pop());}}// 显示遍历链表public void list() {if (head.next == null) {System.out.println("链表为空");return;}Node<T> c = head.next;while (c != null) {System.out.println(c.data);c = c.next;}}
}

3.4 双向链表应用实例

package com.gyh.Link;import java.util.LinkedList;/*** @author Gao YongHao* @version 1.0*/
public class DoubleLinkedListDemo {public static void main(String[] args) {}
}class DoubleLinkedList<T> {// 头结点private final DuNode<T> head = new DuNode<>();// 删除public void remove(T d) {// 判断空
//        ....DuNode<T> cur = head;while (cur.next != null) {if (d.equals(cur.next.data)) {// 删除操作cur.next = cur.next.next;if (cur.next != null) cur.next.pre = cur;}cur = cur.next;}}// 添加public void add(T d) {DuNode<T> cur = head;while (cur.next != null) {cur = cur.next;}// cur为最后一个元素cur.next = new DuNode<>(d, cur, null);}}class DuNode<T> {T data;DuNode<T> pre;DuNode<T> next;public DuNode() {}public DuNode(T data, DuNode<T> pre, DuNode<T> next) {this.data = data;this.pre = pre;this.next = next;}
}

3.5 单向环形链表

package com.gyh.Link;import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;/*** @author Gao YongHao* @version 1.0*/
public class SingleCircularLinkedListDemo {public static void main(String[] args) {SingleCircularLinkedList<Integer> integerSingleCircularLinkedList = new SingleCircularLinkedList<>();for (int i = 0; i < 10; i++) {integerSingleCircularLinkedList.add(i);}List<Integer> josephu = integerSingleCircularLinkedList.josephu(4, 6);josephu.forEach(System.out::println);}
}/*** 1. 创建尾结点* 2. 每次定位至数到 m 的结点的上一个结点位置（只有这样才可以更新信息）** @param <T>*/
class SingleCircularLinkedList<T> {// 不设置头结点(设置指向尾元素的指针)private Node<T> last;// 判断空public boolean isEmpty() {return last == null;}// 添加数据public void add(T d) {// 为空则直接创建if (isEmpty()) {last = new Node<>(d, null);last.setNext(last);return;}last.next = new Node<T>(d, last.next);last = last.next;}// 链表长度public int getLength() {// 为空则返回if (isEmpty()) return 0;int n = 1;Node<T> cur = last.next;while (cur != last) {n++;cur = cur.next;}return n;}// 约瑟夫问题public List<T> josephu(int k, final int m) {// 1 <= k <= nint n = getLength();assert k >= 1 && k <= n;if (n == 1) return Collections.singletonList(last.getData());// 循环出值List<T> out = new ArrayList<>();// pre初始为最后一个元素Node<T> pre = last;// 定位到 编号为 k 的前面一个人for (int i = 1; i < k; i++) {pre = pre.next;}// 报数到mwhile (true) {if (last.next == last) { // 只有一个元素out.add(last.getData());last = null;break;}// 获取数到m的结点的前面一个结点for (int i = 1; i < m; i++) {pre = pre.next;}// 从循环链表中删除该结点if (pre.next == last) last = pre; // 如果删除的是最后一个结点则将last指向preout.add(pre.next.getData()); // 将删除的结点值保存pre.next = pre.next.next;}return out;}
}

四、栈

4.1 基本介绍

4.2 数组模拟栈

// 数组实现栈
package com.gyh.stack;/*** @author Gao YongHao* @version 1.0*/
public class StackDemo {public static void main(String[] args) {ArrayStack arrayStack = new ArrayStack(5);for (int i = 0; i < 5; i++) {arrayStack.push(i);}arrayStack.list();System.out.println(arrayStack.pop());System.out.println(arrayStack.pop());System.out.println(arrayStack.pop());System.out.println(arrayStack.pop());System.out.println(arrayStack.pop());}
}class ArrayStack {private final int maxSize;private int[] arr;private int stackTop; // stackTop表示最后一个元素的下一个位置public ArrayStack(int size) {this.maxSize = size;this.arr = new int[size];this.stackTop = 0;}// 判满public boolean isFull() {return stackTop == maxSize;}// 判空public boolean isEmpty() {return stackTop == 0;}// 压栈public void push(int n) {if (isFull()) {System.out.println("已满");return;}arr[stackTop++] = n;}// 出栈public int pop() {if (isEmpty()) throw new RuntimeException("栈已空");return arr[--stackTop];}// 遍历栈public void list(){if(isEmpty()) {System.out.println("栈空");return;}for (int i : arr) {System.out.println(i);}}
}

4.3 链表模拟栈

// 链表实现栈
package com.gyh.stack;/*** @author Gao YongHao* @version 1.0*/
public class StackDemo2 {public static void main(String[] args) {LinkedStack<Integer> integerLinkedStack = new LinkedStack<Integer>();for (int i = 0; i < 5; i++) {integerLinkedStack.push(i);}integerLinkedStack.list();System.out.println(integerLinkedStack.pop());System.out.println(integerLinkedStack.pop());System.out.println(integerLinkedStack.pop());System.out.println(integerLinkedStack.pop());System.out.println(integerLinkedStack.pop());}
}class LinkedStack<T> {// 设置栈顶指针private Node<T> stackTop;// 判断空public boolean isEmpty() {return stackTop == null;}// 压栈（使用头插法）public void push(T d) {// 第一个元素if (stackTop == null) {stackTop = new Node<>(d, null);return;}stackTop = new Node<>(d, stackTop);}// 出栈public T pop() {if (isEmpty()) throw new RuntimeException("栈空");T d = stackTop.data;stackTop = stackTop.next;return d;}// 遍历public void list() {if (isEmpty()) System.out.println("栈空");Node<T> cur = stackTop;while (cur != null) {System.out.println(cur.data);cur = cur.next;}}}class Node<T> {T data;Node<T> next;public Node(T data, Node<T> next) {this.data = data;this.next = next;}
}

4.4 栈实现综合计算器

package com.gyh.stack;import java.util.Arrays;
import java.util.List;/*** @author Gao YongHao* @version 1.0*/
public class CalculatorDemo {public static void main(String[] args) {String expression = "70*2*2-5+1-5+3-4";// 创建数栈LinkedStack<Double> numStack = new LinkedStack<>();// 创建操作符栈LinkedStack<Character> operStack = new LinkedStack<>();double n1, n2, res = 0;char oper = ' ', c;char[] chars = expression.toCharArray();int length = chars.length;StringBuffer numBuf = new StringBuffer();for (int i = 0; i < length; i++) {c = chars[i];// 符号栈不为空if (Calculator.isOper(c) && !operStack.isEmpty()) {// 栈顶的操作符oper = operStack.pop();if (Calculator.priority(oper) >= Calculator.priority(c)) { // 需要计算n1 = numStack.pop();n2 = numStack.pop();res = Calculator.cal(n1, n2, oper);// 将计算结果压栈// 当前符号在后面压栈numStack.push(res);} else {// 不操作则把操作符放回去,并执行下面的压栈operStack.push(oper);}}// 如果是符号则压入符号栈中if (Calculator.isOper(c)) {operStack.push(c);} else { // 压入数栈// 观察当前字符的下一个位置是否也为数字(考虑多位数的情况)numBuf.append(c);if (i == length - 1 || Calculator.isOper(chars[i + 1])) {numStack.push(Double.parseDouble(numBuf.toString()));numBuf = new StringBuffer();}}}// 遍历符号栈将最终的结果输出while (operStack.size() > 0) {n1 = numStack.pop();n2 = numStack.pop();res = Calculator.cal(n1, n2, operStack.pop());numStack.push(res); // 结果压栈}System.out.println(expression + "=" + res);}
}class Calculator {private static final List<Character> opters = Arrays.asList('+', '-', '*', '/');public static double cal(double num1, double num2, int oper) {double res = 0; // 用于存放计算的结果switch (oper) {case '+':res = num1 + num2;break;case '-':res = num2 - num1;break;case '*':res = num1 * num2;break;case '/':res = num2 / num1;break;default:throw new RuntimeException("操作符异常");}return res;}public static boolean isOper(int oper) {return isOper((char) oper);}public static boolean isOper(char oper) {return opters.contains(oper);}public static int priority(int oper) {if (!isOper(oper)) {return -1;}switch (oper) {case '*':case '/':return 1;case '+':case '-':return 0;default:return -1;}}
}

4.5 前缀、中缀、后缀表达式（逆波兰表达式）

4.6 逆波兰计算器实现

package com.gyh.stack;/*** @author Gao YongHao* @version 1.0*/
public class InversePolishExpressionDemo {public static void main(String[] args) {String expression = "4 5 * 8 - 60 + 8 2 / +"; // 使用空格区分多位数// 创建数栈LinkedStack<Integer> numStack = new LinkedStack<>();// 从左至右扫描String[] chars = expression.split(" ");int n1, n2, res = 0;for (String c : chars) {// 判断是否为操作符if (Calculator.isOper(c.charAt(0))) {n1 = numStack.pop();n2 = numStack.pop();res = Calculator.cal(n1, n2, c.charAt(0));numStack.push(res); // 计算结果压栈} else { // 为数numStack.push(Integer.parseInt(c));}}System.out.println(expression + "=" + res);}
}

4.7 中缀表达式转后缀表达式(*)

package com.gyh.stack;import java.util.Arrays;/*** @author Gao YongHao* @version 1.0* <p>* 中缀表达式转后缀表达式*/
public class MidToReverseDemo {public static void main(String[] args) {// 中缀表达式String expression = "1 + ( ( 2 + 3 ) * 4 ) - 5";// 按空格读取各字符String[] strs = expression.split(" ");// 创建保存运算符的栈和中间栈LinkedStack<String> linkedStack = new LinkedStack<>();LinkedStack<String> tempStack = new LinkedStack<>();// 遍历字符for (String str : strs) {if (!isNumeric(str)) { // 为运算符while (true) {// 当前栈中没有元素或存在元素 ( , 直接压栈if (str.equals("(") || linkedStack.isEmpty() || linkedStack.peek().equals("("))linkedStack.push(str);else if (str.equals(")")) { // 如果是右括号则依次出栈至 '(' 位置并压入中间栈while (!linkedStack.peek().equals("(")) {tempStack.push(linkedStack.pop());}linkedStack.pop(); // 将对应的左括号弹出} else if (Calculator.priority(str.charAt(0)) > Calculator.priority(linkedStack.peek().charAt(0))) { // 如果当前的字符优先级大于存在的元素则压栈linkedStack.push(str);} else { // 将当前栈顶元素出栈并压入中间栈，并重新将当前的字符作判定tempStack.push(linkedStack.pop());continue;}break;}} else { // 为数// 压入中间栈tempStack.push(str);}}// 若字符栈非空则依次出栈并压入中间栈(此处为便于反向遍历，将中间栈的数据压入运算符栈)while (!tempStack.isEmpty()) {linkedStack.push(tempStack.pop());}// 打印得到后缀表达式while (!linkedStack.isEmpty()) {System.out.print(linkedStack.pop() + " ");}}public static boolean isNumeric(String str) {for (int i = str.length(); --i >= 0; ) {int chr = str.charAt(i);if (chr < 48 || chr > 57)return false;}return true;}
}

五、递归

5.1 递归的应用场景

5.2 递归的调用机制

5.3 递归可以解决的问题

5.4 递归需要遵守的重要规则

5.5 迷宫问题

package com.gyh.recursion;/*** @author Gao YongHao* @version 1.0*/
public class MiGong {public static void main(String[] args) {// 构建迷宫int[][] matrix = new int[8][7];for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[i].length; j++) {if (i == 0 || i == matrix.length - 1 || j == 0 || j == matrix[i].length - 1) {matrix[i][j] = 1;}}}matrix[2][2] = 1;matrix[3][1] = 1;matrix[3][2] = 1;// 打印迷宫for (int[] ints : matrix) {for (int anInt : ints) {System.out.print(anInt + "\t");}System.out.println();}System.out.println("*******************");find(matrix, 1, 1);// 打印路径for (int[] ints : matrix) {for (int anInt : ints) {System.out.print(anInt + "\t");}System.out.println();}}/*** 寻找迷宫出口的方法* 说明* 1. map  表示地图* 2. i,j  表示从地图的哪个位置开始出发* 3. 如果小球能到 map[6][5] 的位置，则表示通路找到* 4. 约定：当 map[i][j] 为 0 时，表示该点没有走过；当为 1 表示是墙；2 表示通路可以走；3 表示该位置已经走过但是走不通* 5. 在走迷宫时，需要确定一个策略（方法）下->右->上->左** @param map 迷宫矩阵* @param i   横坐标值* @param j   纵坐标值*/public static boolean find(int[][] map, int i, int j) {if (map[6][5] == 2) { // 设置终点已找到时return true;}// 墙、前面已经走过（还在测试中）、前面已走过（走不通）if (map[i][j] == 1 || map[i][j] == 2 || map[i][j] == 3) {return false;}// 假定该点可以走通map[i][j] = 2;// 按照策略 下 -> 右 -> 上 -> 左if (find(map, i + 1, j)) {return true;} else if (find(map, i, j + 1)) {return true;} else if (find(map, i - 1, j)) {return true;} else if (find(map, i, j - 1)) {return true;} else {map[i][j] = 3;return false;}}
}

5.6 八皇后问题

package com.gyh.recursion;/*** @author Gao YongHao* @version 1.0*/
public class EightQueenProblem {// 定义一个max表示共有多少个皇后static int max = 8;// 定义数组array,保存皇后放置位置的结果，比如 arr = {0,4,7,5,2,6,1,3}static int[] array = new int[max];static int count = 0;// 编写一个方法，放置第n个皇后// 特别注意：check 是每一个递归时，进入 check 中都有 for (int i = 0; i < max; i++) ,因此会回溯（会把所有情况走一遍）private static void check(int n) {if (n == max) { // n=8 其实第八个皇后就放好了printArray();count++; // 解法+1return;}for (int i = 0; i < max; i++) {// 从第一列的情况开始遍历array[n] = i;if (!isComplicit(n)) {// 不冲突则继续 checkcheck(n + 1);}// 冲突，就继续执行 下一情况}}// 表示是否冲突private static boolean isComplicit(int n) {for (int i = 0; i < n; i++) {// 条件一：比较是否存在同列// 条件二：比较是否存在 行差与列差 相同的元素（即同对角线）if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {return true;}}return false;}private static void printArray() {for (int a : array) {System.out.print(a + "\t");}System.out.println();}public static void main(String[] args) {// 打印最后的摆放结果check(0);System.out.println("一共有" + count + "种算法");}}