前置问题
经典问题与算法
-
8皇后问题（92种摆法）——回溯算法
-
字符串匹配问题——KMP算法（取代暴力匹配）
-
汉诺塔游戏问题——分治算法
-
马踏棋盘算法也称骑士周游问题——图的深度优化遍历算法(DFS)+贪心算法优化
-
Josephu——约瑟夫问题（丢手帕问题）
-
修路问题——最小生成树（普里姆算法）
-
最短路径问题——图+弗洛伊德算法
程序员常用十大算法——必会
- 二分查找算法（非递归）
- 分治算法
- 动态规划算法
- KMP算法
- 贪心算法
- 普里姆算法
- 克鲁斯卡尔算法
- 迪杰斯特拉算法
- 弗洛伊德算法
- 马踏棋盘算法
学习步骤
- 应用场景或者说提出问题
- 引出数据结构或算法
- 剖析原理
- 分析问题实现步骤
- 代码实现
概述
程序=数据结构+算法
算法是程序的灵魂，数据结构是算法的基础。
数据结构——data structure
- 稀疏数组
- 单链表
- 单向环形链表
数据结构包括：线性结构和非线性结构。
线性结构——一维
线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。
线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。
一对一的线性关系解释：
节点与对应的存储元素是一对一关系，如数组的下标和储存的元素，而像树的节点分支下面有可能有一个或两个甚至多个的节点，因此不少一对一关系，也就不是线性结构。
顺序存储——数组
顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的（指内存空间中的地址是连续的）
链式存储——链表
链式存储的线性表称为链表，链表中的存储元素不一定是连续的（指内存空间中的地址不一定是连续的，元素之间通过存储指针如下一个元素的地址联系），元素节点中存放数据元素以及相邻元素的地址信息。链表的好处的可以充分利用碎片内存，不需要整块完整的内存空间。
常见线性结构
数组、队列、链表和栈。
非线性结构——二维及以上
常见非线性结构
二维数组，多维数组，广义表，树结构，图结构
稀疏数组——sparse array
当一个数组中大部分元素为０或者为同一个值的数组时（很多是没有意义的数据），可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:
- 第一行记录数组一共有几行几列，有多少个不同的值。
- 从第二行开始，把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。
图解如下：
稀疏数组思路分析
应用示例——五子棋压缩成稀疏数组保存
public class SparseArray {
//有效总数
static AtomicInteger sum = new AtomicInteger();
public static void main(String[] args) {
testSparseArray(buildArr(11, 11));
}
public static int[][] buildArr(int row, int col) {
int[][] chessArr = new int[row][col];
//待完善
//默认0表示没有棋子，1表示黑子 2表示白子
chessArr[1][2] = 1;
chessArr[2][3] = 2;
chessArr[4][7] = 2;
return chessArr;
}
public static void testSparseArray(int[][] chessArr) {
System.out.println("原始数组：");
Arrays.stream(chessArr).forEach(chessrow -> {
//取得每行数据chessrow继续遍历
Arrays.stream(chessrow).forEach(chesscol -> {
System.out.printf("%d\t", chesscol);
if (chesscol != 0) {
sum.incrementAndGet();
}
});
//换行打印
System.out.println();
});
//压缩成稀疏数组
int[][] sparseArr = new int[sum.get() + 1][3];
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum.get();
//第几个有效数据
int count = 1;
for (int i = 0; i < chessArr.length; i++) {
for (int j = 0; j < chessArr.length; j++) {
if (chessArr[i][j] != 0) {
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = chessArr[i][j];
count++;
}
}
}
System.out.println("稀疏数组：");
//打印稀疏数组
printArr(sparseArr);
//存储到磁盘中
try {
Writer writer = new BufferedWriter(new FileWriter(new File("E:\\array.text")));
writer.write(JSON.toJSONString(sparseArr));
writer.flush();
writer.close();
} catch (IOException e) {
e.printStackTrace();
}
//从磁盘中读取数组
try {
BufferedInputStream reader = new BufferedInputStream(new FileInputStream("E:\\array.text"));
byte[] buffer = new byte[1024 * 1024];
int read = reader.read(buffer);
reader.close();
String s = new String(buffer);
int[][] storeArr = JSON.parseObject(s, int[][].class);
System.out.println("获取存储在磁盘中的稀疏数组：");
printArr(storeArr);
} catch (Exception e) {
e.printStackTrace();
}
//还原数组
int[][] reduceArr = new int[sparseArr[0][0]][sparseArr[0][1]];
for (int i = 1; i < sparseArr.length; i++) {
reduceArr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
System.out.println("还原数组：");
printArr(reduceArr);
}
//打印数组
private static void printArr(int[][] sparseArr) {
Arrays.stream(sparseArr).forEach(sparserow -> {
//取得每行数据chessrow继续遍历
Arrays.stream(sparserow).forEach(sparsecol -> {
System.out.printf("%d\t", sparsecol);
});
//换行打印
System.out.println();
});
}
}
输出：
原始数组：
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
稀疏数组：
11 11 3
1 2 1
2 3 2
4 7 2
获取存储在磁盘中的稀疏数组：
11 11 3
1 2 1
2 3 2
4 7 2
还原数组：
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
队列——FIFO
队列的特点就是先进先出。
队列是一个有序列表，可以用数组（顺序存储）或是链表（链式存储）来实现。
场景
涉及排队的场景，如银行排队办理业务取号。
数组实现队列
数组实现一次性队列
思路分析：
代码实现：
//一次性队列，无法重复利用队列，需要使用环形队列优化
public class ArrayQueue<T> {
//数组最大容量大小
private int maxSize;
//模拟队列的数组，存放元素
private Object[] arr;
//队列头
private int front;
//队列尾
private int rear;
//构造函数初始化队列
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
this.arr = new Object[maxSize];
//队列头和队列尾初始化时都指向的是队列的初始位置0的前一个位置，我们用-1表示
this.front = -1;
this.rear = -1;
}
//添加数据到队列中
public void add(T t) throws Exception {
if (isFull()) {
System.out.println("队列已满！");
return;
}
rear++;
arr[rear] = t;
}
public T remove() throws Exception {
if (isEmpty()) {
System.out.println("队列为空，取不到元素！");
return null;
}
front++;
T value = (T) arr[front];
return value;
}
public T peek() throws Exception {
if (isEmpty()) {
System.out.println("队列为空，取不到元素！");
return null;
}
return (T) arr[front + 1];
}
public void list() throws Exception {
if (isEmpty()) {
System.out.println("队列为空，取不到元素！");
}
for (int i = 0; i < arr.length; i++) {
System.out.printf("array[%d]:%d\n", i, (T) arr[i]);
}
System.out.println();
}
//判断队列是否满了
private boolean isFull() {
return rear == (maxSize - 1);
}
//判断队列是否为空
private boolean isEmpty() {
return rear == front;
}
}
public class ArrayQueueTest {
public static void main(String[] args) throws Exception {
ArrayQueue<Integer> queue = new ArrayQueue<Integer>(3);
Scanner scanner = new Scanner(System.in);
boolean runFlag = true;
while (runFlag) {
String next = scanner.next();
switch (next) {
case "a":
System.out.println("请输入添加的元素：");
//避免因输入不是整数而中断测试进程
try {
queue.add(scanner.nextInt());
} catch (Exception e) {
System.out.println("添加元素失败," + e.getMessage());
}
break;
case "r":
System.out.println("取出元素：" + queue.remove());
break;
case "p":
System.out.println("查看头元素：" + queue.peek());
break;
case "l":
queue.list();
break;
case "e":
System.out.println("退出！");
//关闭读取流
scanner.close();
runFlag = false;
break;
}
}
}
}
参考ArrayList的增删
用一个size字段表示当前存放的元素大小，并扩展对数组可以扩容处理会比上面的好点。
新增
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 确保数组大小够不是否，需要扩容不。
/*1 elementData 是Arraylist中存放元素的真正数组，size是当前数组中存了几个元素，而不是数组的长度！！！
*2 把添加的元素放入数组中已存入元素个数的+1位置！
*/
elementData[size++] = e;
return true;
}
删除
删除源码：
//下标范围检测，看是否数组越界
if (index >= size) {
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
}
//启动线程安全问题
modCount++;
//获得要删除的数据
E oldValue = (E) elementData[index];
/**
* 判断需要移动的数据
* a、假设现有数据[1,2,3,4,5]，现在需要把3数据移除，传入的index为2
* b、则需要移动的位数：总位数5-传入的2-1=2
* c、也就是3删除后，4和5两个数左移，numMoved=2
*
*/
int numMoved = size - index - 1;
if (numMoved > 0) {
/**
* 数据移动参数：
* ---源----
* elementData：现有数据
* index + 1：从哪个下标开始往前移
* ---目标----
* elementData：移动到的目标数组是什么
* index：需要往前移到哪个下标开始
* ---移动的个数----
* numMoved：需要移动多少个
*/
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
}
//末位置为null，数组长度不变
elementData[--size] = null;
return oldValue;
数组实现环形队列——通过取模优化
思路分析：
代码实现：
//环形队列，核心在于取模
public class CircleQueue<T> {
//数组最大容量大小(因为预留一个空间约定，所以最大容量为maxSize-1)
private int maxSize;
//模拟队列的数组，存放元素
private Object[] arr;
//队列头 初始化0
private int front;
//队列尾 初始化0
private int rear;
//构造函数初始化队列
public CircleQueue(int maxSize) {
this.maxSize = maxSize;
this.arr = new Object[maxSize];
//队列头和队列尾初始化0，front指向队列第一个元素，arr[0],rear指向最后一个元素的后一个位置，也就是当我们有一个元素arr[0]时，rear为1
this.front = 0;
this.rear = 0;
}
//添加数据到队列中
public void add(T t) throws Exception {
if (isFull()) {
System.out.println("队列已满！");
return;
}
arr[rear] = t;
//rear后移并要求取模，否则数组角标越界导致不能循环利用
rear = (rear + 1) % maxSize;
}
public T remove() throws Exception {
if (isEmpty()) {
System.out.println("队列为空，取不到元素！");
return null;
}
T value = (T) arr[front];
front = (front + 1) % maxSize;
return value;
}
public T peek() throws Exception {
if (isEmpty()) {
System.out.println("队列为空，取不到元素！");
return null;
}
return (T) arr[front];
}
public void list() throws Exception {
if (isEmpty()) {
System.out.println("队列为空，取不到元素！");
}
for (int i = front; i < size() + front; i++) {
System.out.printf("array[%d]:%d\n", i%maxSize, (T) arr[i%maxSize]);
}
System.out.println();
}
//判断队列是否满了
private boolean isFull() {
// (7+1)%4==0
//注意当rear的最大值为maxSize-1,因为数组的下标是从0开始的。因此只要rear+1对maxSize取模得到的值为front=0，则表示满了
return (rear + 1) % maxSize == front;
}
//判断队列是否为空
private boolean isEmpty() {
return rear == front;
}
//当前有效元素个数
private int size() {
//当前的有效个数就是rear-front,因为有一个有效元素，rear就是1，刚好作为计数单位。取模
return (rear + maxSize - front) % maxSize;
}
}
public class CircleQueueTest {
public static void main(String[] args) throws Exception {
//切换成环形队列
CircleQueue<Integer> queue = new CircleQueue<Integer>(4);//有效空间是3，因为有一个空间作为约定
Scanner scanner = new Scanner(System.in);
boolean runFlag = true;
while (runFlag) {
String next = scanner.next();
switch (next) {
case "a":
System.out.println("请输入添加的元素：");
//避免因输入不是整数而中断测试进程
try {
queue.add(scanner.nextInt());
} catch (Exception e) {
System.out.println("添加元素失败," + e.getMessage());
}
break;
case "r":
System.out.println("取出元素：" + queue.remove());
break;
case "p":
System.out.println("查看头元素：" + queue.peek());
break;
case "l":
queue.list();
break;
case "e":
System.out.println("退出！");
//关闭读取流
scanner.close();
runFlag = false;
break;
}
}
}
}
链表
链表是有序的列表，它在内存中的存储如下图，也就是说链表在内存中的各个节点不一定是连续的存储地址空间。
链表逻辑图：
小结:
- 链表是以节点的方式来存储,是链式存储
- 每个节点包含 data 域， next 域：指向下一个节点.
- 如图：发现链表的各个节点不一定是连续存储（存储空间地址上）.
- 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
单链表——单向链表
单链表增删改查思路分析——注意temp节点的位置
单链表面试题
单链表的常见面试题有如下:
求单链表中有效节点的个数
查找单链表中的倒数第k个结点 【新浪面试题】
单链表的反转【腾讯面试题，有点难度】
从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】
合并两个有序的单链表，合并之后的链表依然有序
单链表的反转思路分析
从尾到头打印单链表思路分析
单链表的增删改查及常见面试题示例
//实现Comparable是为了比较用
public class City implements Comparable<City> {
private int no;
private String name;
private String nickName;
public City(int no, String name, String nickName) {
this.no = no;
this.name = name;
this.nickName = nickName;
}
@Override
public String toString() {
return "City{" +
"no=" + no +
", name=\'" + name + \'\\'\' +
", nickName=\'" + nickName + \'\\'\' +
\'}\';
}
@Override
public int compareTo(City o) {
return this.no - o.no;
}
}
//单链表
//E extends Comparable 用于排序对比
public class SingleLinkedList<E extends Comparable> {
//头节点定义
private Node<E> head;
//统计有效元素个数，不包含头节点
private int count;
public Node<E> getHead() {
return head;
}
public SingleLinkedList() {
//标记头结点
head = new Node<E>(null);
}
//从尾到头打印单链表 【百度，要求方式1：反向遍历(不建议，会破坏原来的单链表的结构，除非又执行一次反转再反转回去) 。 方式2：Stack栈】
//此处采用Stack栈,不会改变原来的单链表的结构
public void printReverseLinkedList(SingleLinkedList.Node<E> head) {
if (head.next == null) {
return;
}
Stack<Node<E>> stack = new Stack<>();
Node<E> cur = head.next;
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
while (!stack.empty()) {
System.out.println(stack.pop());
}
// while (stack.size() > 0) {
// System.out.println(stack.pop());
// }
}
//单链表的反转
public void reverseLinkedList(SingleLinkedList.Node<E> head) {
if (head.next == null) {
return;
}
Node<E> reverseHead = new Node<E>(null);
Node<E> cur = head.next;
Node<E> next = null;
while (cur != null) {
//暂存当前节点的下一个节点，避免被覆盖
next = cur.next;
//把当前节点的下一个节点替换为反转后的头结点的第一个元素，这一步相当于链表的头插入的前一步
//把cur的下一个节点指向新的链表的最前端，相当于实现了反转
cur.next = reverseHead.next;
//把当前节点作为头节点赋值给反转后的头结点，而上一步中我们已经将之前反转后的头结点赋值给了当前节点的下一个节点了
//把cur赋值到新的链表头节点上
reverseHead.next = cur;
//继续遍历，把暂存的下一个节点赋值作为当前节点继续循环
cur = next;
}
head.next = reverseHead.next;
}
//查找单链表中的倒数第k个结点，找不到返回null
//k表示倒数第k个结点
public <E> SingleLinkedList.Node<E> getReverseNodeByK(int k, SingleLinkedList.Node<E> head) {
if (head.next == null) {
return null;
}
//倒数第k个结点 = 总的个数-K
//temp作为遍历辅助变量
Node<E> temp = head.next;
int count = getListCount(head);
//校验传入的k值的正确性
if (k <= 0 || k > count) {
return null;
}
for (int i = 0; i < count - k; i++) {
temp = temp.next;
}
return temp;
}
//统计有效元素个数，不包含头节点
public <E> int getListCount(SingleLinkedList.Node<E> head) {
if (head.next == null) {
return 0;
}
//定义辅助变量
Node<E> temp = head.next;
int count = 0;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}
public int getCount() {
return count;
}
/**
* 根据no序号删除元素
*
* @param newElement
*/
public void delete(E newElement) {
//链表为空则无数据删除
if (head.next == null) {
System.out.println("链表为空！");
return;
}
//这里的temp节点设置位置为要删除节点的前一个节点，这样才能做到删除
Node<E> temp = head;
boolean delete = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.item.compareTo(newElement) == 0) {
delete = true;
break;
}
temp = temp.next;
}
if (delete) {
temp.next = temp.next.next;
count--;
} else {
System.out.println("找不到对应的元素可以删除！");
}
}
/**
* 根据no序号修改元素名称等信息
*
* @param newElement
*/
public void update(E newElement) {
//链表为空则无需修改
if (head.next == null) {
System.out.println("链表为空！");
return;
}
Node<E> temp = head.next;
boolean update = false;
while (true) {
if (temp == null) {
break;
}
if (temp.item.compareTo(newElement) == 0) {
update = true;
break;
}
temp = temp.next;
}
if (update) {
temp.item = newElement;
} else {
System.out.println("%d找不到对应的元素可以修改！\n" + newElement);
}
}
/**
* 按添加顺序添加元素
*
* @param e
*/
public void add(E e) {
//head节点不能动，创建一个局部变量辅助遍历
Node temp = head;
while (true) {
//找到链表的最后，新的元素跟在后面
if (temp.next == null) {
break;
}
//没到最后，继续将temp后移
temp = temp.next;
}
//当退出while循环时，表示temp指向了链表的最后一个元素
temp.next = new Node<E>(e);
count++;
}
/**
* 按no大小顺序添加元素,我们让泛型E实现comparable接口，方便我们实现比较判断
* 元素no大小相等表示存在，则添加失败打印提示
*
* @param e
*/
public void addByOrder(E e) {
//head节点不能动，创建一个局部变量辅助遍历
Node<E> temp = head;
//标记条件的元素是否存在，存在则添加失败打印提示
boolean isExist = false;
while (true) {
//主要，因为是单链表，所以我们找的temp节点位置为要添加位置的前一个节点，否则添加不了
//已到链表最后
if (temp.next == null) {
break;
}
//找到了顺序存储的位置，跳出
if (temp.next.item.compareTo(e) > 0) {
break;
}
//相同元素表示存在，也退出
if (temp.next.item.compareTo(e) == 0) {
isExist = true;
break;
}
//没到最后，继续将temp后移
temp = temp.next;
}
if (isExist) {
System.out.printf("%d元素已存在，不能再添加！\n", e);
}
//插入新元素到temp后面，temp.next元素改为跟在newNode节点元素后面
Node<E> newNode = new Node<>(e);
newNode.next = temp.next;
temp.next = newNode;
count++;
}
//遍历
public void list() {
//先判断链表是否有数据
if (head.next == null) {
System.out.println("链表为空！");
return;
}
Node temp = head.next;
while (true) {
if (temp == null) {
break;
} else {
System.out.println(temp);
}
temp = temp.next;
}
}
public static class Node<E> {
private E item;
private Node<E> next;
public Node(E e) {
this.item = e;
}
@Override
public String toString() {
return "Node{" +
"item=" + item +
\'}\';
}
}
}
//测试
public class SingleLinkedListTest {
public static void main(String[] args) {
reverseLinkedListTest();
}
//从尾到头打印单链表
public static void printReverseLinkedListTest() {
SingleLinkedList<City> linkedList = new SingleLinkedList<>();
linkedList.add(new City(1, "北京", "帝都"));
linkedList.add(new City(4, "深圳", "*天堂"));
linkedList.add(new City(3, "广州", "南都"));
linkedList.add(new City(2, "上海", "魔都"));
linkedList.list();
System.out.println("============反转后===================");
linkedList.printReverseLinkedList(linkedList.getHead());
/**
* Node{item=City{no=1, name=\'北京\', nickName=\'帝都\'}}
* Node{item=City{no=4, name=\'深圳\', nickName=\'*天堂\'}}
* Node{item=City{no=3, name=\'广州\', nickName=\'南都\'}}
* Node{item=City{no=2, name=\'上海\', nickName=\'魔都\'}}
* ============反转后===================
* Node{item=City{no=2, name=\'上海\', nickName=\'魔都\'}}
* Node{item=City{no=3, name=\'广州\', nickName=\'南都\'}}
* Node{item=City{no=4, name=\'深圳\', nickName=\'*天堂\'}}
* Node{item=City{no=1, name=\'北京\', nickName=\'帝都\'}}
*/
}
//单链表的反转
public static void reverseLinkedListTest() {
SingleLinkedList<City> linkedList = new SingleLinkedList<>();
linkedList.add(new City(1, "北京", "帝都"));
linkedList.add(new City(4, "深圳", "*天堂"));
linkedList.add(new City(3, "广州", "南都"));
linkedList.add(new City(2, "上海", "魔都"));
linkedList.list();
System.out.println("============反转后===================");
linkedList.reverseLinkedList(linkedList.getHead());
linkedList.list();
/**
* Node{item=City{no=1, name=\'北京\', nickName=\'帝都\'}}
* Node{item=City{no=4, name=\'深圳\', nickName=\'*天堂\'}}
* Node{item=City{no=3, name=\'广州\', nickName=\'南都\'}}
* Node{item=City{no=2, name=\'上海\', nickName=\'魔都\'}}
* ============反转后===================
* Node{item=City{no=2, name=\'上海\', nickName=\'魔都\'}}
* Node{item=City{no=3, name=\'广州\', nickName=\'南都\'}}
* Node{item=City{no=4, name=\'深圳\', nickName=\'*天堂\'}}
* Node{item=City{no=1, name=\'北京\', nickName=\'帝都\'}}
*/
}
//查找单链表中的倒数第k个结点
public static void getReverseNodeByKTest() {
SingleLinkedList<City> linkedList = new SingleLinkedList<>();
linkedList.add(new City(1, "北京", "帝都"));
linkedList.add(new City(4, "深圳", "*天堂"));
linkedList.add(new City(3, "广州", "南都"));
linkedList.add(new City(2, "上海", "魔都"));
System.out.println(linkedList.getReverseNodeByK(1,linkedList.getHead()));
//Node{item=City{no=2, name=\'上海\', nickName=\'魔都\'}}
}
//求单链表中有效节点的个数
public static void getListCountTest() {
SingleLinkedList<City> linkedList = new SingleLinkedList<>();
linkedList.add(new City(1, "北京", "帝都"));
linkedList.add(new City(4, "深圳", "*天堂"));
linkedList.add(new City(3, "广州", "南都"));
linkedList.add(new City(2, "上海", "魔都"));
//方式1：在SingleLinkedList中定义计数count，在新增和删除时做对应操作
System.out.println(linkedList.getCount());
//方式2：
SingleLinkedList.Node<City> head = linkedList.getHead();
System.out.println("单链表中有效节点的个数:" + linkedList.getListCount(head));
/**
* 4
* 单链表中有效节点的个数:4
*/
}
public static void testAdd() {
SingleLinkedList<City> linkedList = new SingleLinkedList<>();
linkedList.add(new City(1, "北京", "帝都"));
linkedList.add(new City(4, "深圳", "*天堂"));
linkedList.add(new City(3, "广州", "南都"));
linkedList.add(new City(2, "上海", "魔都"));
linkedList.list();
/**
*Node{item=City{no=1, name=\'北京\', nickName=\'帝都\'}}
* Node{item=City{no=4, name=\'深圳\', nickName=\'*天堂\'}}
* Node{item=City{no=3, name=\'广州\', nickName=\'南都\'}}
* Node{item=City{no=2, name=\'上海\', nickName=\'魔都\'}}
*/
}
public static void testAddByOrder() {
//测试按照编号插入链表
SingleLinkedList<City> linkedList = new SingleLinkedList<>();
linkedList.addByOrder(new City(1, "北京", "帝都"));
linkedList.addByOrder(new City(4, "深圳", "*天堂"));
linkedList.addByOrder(new City(3, "广州", "南都"));
linkedList.addByOrder(new City(2, "上海", "魔都"));
linkedList.list();
/**
* Node{item=City{no=1, name=\'北京\', nickName=\'帝都\'}}
* Node{item=City{no=2, name=\'上海\', nickName=\'魔都\'}}
* Node{item=City{no=3, name=\'广州\', nickName=\'南都\'}}
* Node{item=City{no=4, name=\'深圳\', nickName=\'*天堂\'}}
*/
}
public static void testUpdate() {
SingleLinkedList<City> linkedList = new SingleLinkedList<>();
linkedList.addByOrder(new City(1, "北京", "帝都"));
linkedList.addByOrder(new City(4, "深圳", "*天堂"));
linkedList.addByOrder(new City(3, "广州", "南都"));
linkedList.addByOrder(new City(2, "上海", "魔都"));
linkedList.list();
linkedList.update(new City(4, "深圳特区", "勇敢*天堂"));
System.out.println("修改后遍历：");
linkedList.list();
linkedList.update(new City(5, "杭州", "奋斗之都"));
/**
Node{item=City{no=1, name=\'北京\', nickName=\'帝都\'}}
Node{item=City{no=2, name=\'上海\', nickName=\'魔都\'}}
Node{item=City{no=3, name=\'广州\', nickName=\'南都\'}}
Node{item=City{no=4, name=\'深圳\', nickName=\'*天堂\'}}
修改后遍历：
Node{item=City{no=1, name=\'北京\', nickName=\'帝都\'}}
Node{item=City{no=2, name=\'上海\', nickName=\'魔都\'}}
Node{item=City{no=3, name=\'广州\', nickName=\'南都\'}}
Node{item=City{no=4, name=\'深圳特区\', nickName=\'勇敢*天堂\'}}
找不到对应的元素可以修改！
*/
}
public static void testDelete() {
SingleLinkedList<City> linkedList = new SingleLinkedList<>();
linkedList.addByOrder(new City(1, "北京", "帝都"));
linkedList.addByOrder(new City(4, "深圳", "*天堂"));
linkedList.addByOrder(new City(3, "广州", "南都"));
linkedList.addByOrder(new City(2, "上海", "魔都"));
linkedList.list();
linkedList.delete(new City(4, "深圳", "*天堂"));
linkedList.delete(new City(1, "北京", "帝都"));
System.out.println("删除后遍历：");
linkedList.list();
linkedList.delete(new City(5, "杭州", "奋斗之都"));
System.out.println(linkedList.getCount());
/**
*Node{item=City{no=1, name=\'北京\', nickName=\'帝都\'}}
* Node{item=City{no=2, name=\'上海\', nickName=\'魔都\'}}
* Node{item=City{no=3, name=\'广州\', nickName=\'南都\'}}
* Node{item=City{no=4, name=\'深圳\', nickName=\'*天堂\'}}
* 删除后遍历：
* Node{item=City{no=1, name=\'北京\', nickName=\'帝都\'}}
* Node{item=City{no=2, name=\'上海\', nickName=\'魔都\'}}
* Node{item=City{no=3, name=\'广州\', nickName=\'南都\'}}
* 找不到对应的元素可以删除！
*
* Process finished with exit code 0
*/
}
}
双向链表
单向链表的缺点:
单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
单向链表不能自我删除，需要靠辅助节点找到要删除的前一个节点 ，而双向链表可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的上一个节点。
双向链表增删改查思路分析
代码示例
public class DDoubleLinkedList<E extends Comparable> {
private Node<E> head;
public DDoubleLinkedList() {
head = new Node<E>(null);
}
public static class Node<E> {
private E item;
//指向下一个节点，默认为null
private Node<E> next;
//指向上一个节点，默认为null
private Node<E> pre;
public Node(E e) {
this.item = e;
}
@Override
public String toString() {
return "Node{" +
"item=" + item +
\'}\';
}
}
//遍历
public void list() {
if (head.next == null) {
System.out.println("链表为空！");
return;
}
Node<E> temp = head.next;
while (temp != null) {
System.out.println(temp);
temp = temp.next;
}
}
//在链表尾添加元素
public void add(E e) {
Node<E> temp = head;
while (temp.next != null) {
temp = temp.next;
}
Node<E> newNode = new Node<>(e);
//形成双向链表
temp.next = newNode;
newNode.pre = temp;
}
/**
* 根据no序号修改元素名称等信息
*
* @param newElement
*/
public void update(E newElement) {
//链表为空则无需修改
if (head.next == null) {
System.out.println("链表为空！");
return;
}
Node<E> temp = head.next;
boolean update = false;
while (true) {
if (temp == null) {
break;
}
if (temp.item.compareTo(newElement) == 0) {
update = true;
break;
}
temp = temp.next;
}
if (update) {
temp.item = newElement;
} else {
System.out.println("%d找不到对应的元素可以修改！\n" + newElement);
}
}
//双向链表删除节点，只需要直接找到要删除的节点，而不是找到要删除节点的前一个节点，因为双向链表可以自我删除
public void delete(E e) {
if (head.next == null) {
System.out.println("链表为空！");
return;
}
Node<E> temp = head.next;
boolean deleteFlag = false;
while (temp != null) {
//如果要用equals进行判断，则需要重写添加元素的equals方法
if (Objects.equals(temp.item, e)) {
deleteFlag = true;
break;
}
temp = temp.next;
}
if (deleteFlag) {
//删除最后一个节点时不需要执行
if (temp.next != null) {
temp.next.pre = temp.pre;
}
temp.pre.next = temp.next;
} else {
System.out.println("找不到对应的元素可以删除！");
}
}
}
//实现Comparable是为了比较用
public class City implements Comparable<City> {
private int no;
private String name;
private String nickName;
public City(int no, String name, String nickName) {
this.no = no;
this.name = name;
this.nickName = nickName;
}
@Override
public String toString() {
return "City{" +
"no=" + no +
", name=\'" + name + \'\\'\' +
", nickName=\'" + nickName + \'\\'\' +
\'}\';
}
@Override
public int compareTo(City o) {
return this.no - o.no;
}
//重写equals和hashCode方法比较相等，用于删除和修改
//我们这里只有no相等就是相等的
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
City city = (City) o;
return no == city.no;
}
@Override
public int hashCode() {
return Objects.hash(no);
}
}
//测试
public class DoubleLinkedListTest {
public static void main(String[] args) {
testUpdate();
}
public static void testUpdate() {
DDoubleLinkedList<City> linkedList = new DDoubleLinkedList<>();
linkedList.add(new City(1, "北京", "帝都"));
linkedList.add(new City(4, "深圳", "*天堂"));
linkedList.add(new City(3, "广州", "南都"));
linkedList.add(new City(2, "上海", "魔都"));
linkedList.list();
linkedList.update(new City(4, "深圳特区", "勇敢*天堂"));
System.out.println("修改后遍历：");
linkedList.list();
linkedList.update(new City(5, "杭州", "奋斗之都"));
/**
* Node{item=City{no=1, name=\'北京\', nickName=\'帝都\'}}
* Node{item=City{no=4, name=\'深圳\', nickName=\'*天堂\'}}
* Node{item=City{no=3, name=\'广州\', nickName=\'南都\'}}
* Node{item=City{no=2, name=\'上海\', nickName=\'魔都\'}}
* 修改后遍历：
* Node{item=City{no=1, name=\'北京\', nickName=\'帝都\'}}
* Node{item=City{no=4, name=\'深圳特区\', nickName=\'勇敢*天堂\'}}
* Node{item=City{no=3, name=\'广州\', nickName=\'南都\'}}
* Node{item=City{no=2, name=\'上海\', nickName=\'魔都\'}}
* %d找不到对应的元素可以修改！
* City{no=5, name=\'杭州\', nickName=\'奋斗之都\'}
*/
}
public static void testAdd() {
DDoubleLinkedList<City> linkedList = new DDoubleLinkedList<>();
linkedList.add(new City(1, "北京", "帝都"));
linkedList.add(new City(4, "深圳", "*天堂"));
linkedList.add(new City(3, "广州", "南都"));
linkedList.add(new City(2, "上海", "魔都"));
linkedList.list();
/**
*Node{item=City{no=1, name=\'北京\', nickName=\'帝都\'}}
* Node{item=City{no=4, name=\'深圳\', nickName=\'*天堂\'}}
* Node{item=City{no=3, name=\'广州\', nickName=\'南都\'}}
* Node{item=City{no=2, name=\'上海\', nickName=\'魔都\'}}
*/
}
public static void testDelete() {
DDoubleLinkedList<City> linkedList = new DDoubleLinkedList<>();
linkedList.add(new City(1, "北京", "帝都"));
linkedList.add(new City(4, "深圳", "*天堂"));
linkedList.add(new City(3, "广州", "南都"));
linkedList.add(new City(2, "上海", "魔都"));
linkedList.list();
linkedList.delete(new City(4, "深圳", "*天堂"));
linkedList.delete(new City(2, "上海", "魔都"));
// linkedList.delete(new City(4, "深圳1", "*天堂1"));
// linkedList.delete(new City(1, "北京1", "帝都1"));
System.out.println("删除后遍历：");
linkedList.list();
linkedList.delete(new City(5, "杭州", "奋斗之都"));
/**
* Node{item=City{no=1, name=\'北京\', nickName=\'帝都\'}}
* Node{item=City{no=4, name=\'深圳\', nickName=\'*天堂\'}}
* Node{item=City{no=3, name=\'广州\', nickName=\'南都\'}}
* Node{item=City{no=2, name=\'上海\', nickName=\'魔都\'}}
* 删除后遍历：
* Node{item=City{no=1, name=\'北京\', nickName=\'帝都\'}}
* Node{item=City{no=3, name=\'广州\', nickName=\'南都\'}}
* 找不到对应的元素可以删除！
*/
}
}
环形链表——单向环形链表——约瑟夫环——Josephu问题——丢手帕问题
应用场景
Josephu(约瑟夫、约瑟夫环) 问题Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。
约瑟夫环示意图
出圈思路分析图
代码示例——使用单向环形链表解决约瑟夫问题
注：也可以用数组取模来解决约瑟夫问题
//单向环形链表
public class CircleSingleLinkedList<E> {
private Node<E> first;
public Node<E> getFirst() {
return first;
}
public CircleSingleLinkedList() {
}
/**
* @param num 表示一个多少个人
* @param k 从第几个人开始数
* @param m 每次数几个人
*/
public static void Josephu(int num, int k, int m) {
if (num < 1 || k > num) {
System.out.println("输入的数据不对！");
}
//创建指定大小num的约瑟夫环
CircleSingleLinkedList linkedList = new CircleSingleLinkedList();
for (int i = 1; i <= num; i++) {
linkedList.add(new Person(i, "小孩" + i));
}
System.out.println("原始环形单向链表初始值：");
linkedList.list();
//创建辅助变量helper，使其指向最后一个节点，相当于单链表中要删除的节点的前一个节点作用
Node helper = linkedList.getFirst();
Node first = linkedList.getFirst();
while (helper.getNext() != linkedList.getFirst()) {
helper = helper.getNext();
}
//从第k个人开始数
for (int i = 0; i < k - 1; i++) {
first = first.next;
helper = helper.next;
}
//开始报数时，让first和helper同时移动m-1次，然后出圈，直到圈内只有一个节点，这时候helper=first
while (true) {
if (first == helper) {
break;
}
for (int j = 0; j < m - 1; j++) {
first = first.next;
helper = helper.next;
}
//每次数完m次报数，这时候first就是要出圈的人
//我们让其出圈
System.out.println("出圈人：" + first);
first = first.next;
helper.next = first;
}
System.out.println("最后出圈人：" + first);
}
public void add(E e) {
if (first == null) {
Node<E> node = new Node<>(e);
//第一个节点自己指向自己，构成环状结构
first = node;
node.next = first;
} else {
Node<E> temp = first;
while (temp != null) {
if (temp.next == first) {
break;
}
temp = temp.next;
}
Node<E> node = new Node<>(e);
temp.next = node;
node.next = first;
}
}
public void list() {
if (first == null) {
System.out.println("链表为空！");
return;
}
Node<E> temp = this.first;
while (temp.next != first) {
System.out.println(temp);
temp = temp.next;
}
//输出最后一个或者只有一个的情况
System.out.println(temp);
}
public static class Node<E> {
private E e;
private Node<E> next;
public E getE() {
return e;
}
public Node<E> getNext() {
return next;
}
public Node(E e) {
this.e = e;
}
@Override
public String toString() {
return "Node{" +
"e=" + e +
\'}\';
}
}
}
//对象
public class Person {
private int no;
private String name;
public Person(int no, String name) {
this.no = no;
this.name = name;
}
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;
}
@Override
public String toString() {
return "Person{" +
"no=" + no +
", name=\'" + name + \'\\'\' +
\'}\';
}
}
//测试
public class CircleSingleLinkedListTest {
public static void main(String[] args) {
CircleSingleLinkedList.Josephu(5,1,2);
}
/**
* 原始环形单向链表初始值：
* Node{e=Person{no=1, name=\'小孩1\'}}
* Node{e=Person{no=2, name=\'小孩2\'}}
* Node{e=Person{no=3, name=\'小孩3\'}}
* Node{e=Person{no=4, name=\'小孩4\'}}
* Node{e=Person{no=5, name=\'小孩5\'}}
* 出圈人：Node{e=Person{no=2, name=\'小孩2\'}}
* 出圈人：Node{e=Person{no=4, name=\'小孩4\'}}
* 出圈人：Node{e=Person{no=1, name=\'小孩1\'}}
* 出圈人：Node{e=Person{no=5, name=\'小孩5\'}}
* 最后出圈人：Node{e=Person{no=3, name=\'小孩3\'}}
*/
}
栈——stack——FILO
栈是一个先入后出(FILO-First In Last Out)的有序列表。
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。
出栈(pop)和入栈(push)
运用场景
请输入一个表达式 -> 计算式:[7*2*2-5+1-5+3-3]
对计算机而言接受到的是个字符串，其计算机底层就是通过栈运算得到结果 。
-
子程序的调用（函数方法的调用）：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
-
处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。 -
二叉树的遍历。
-
图形的深度优先(depth一first)搜索法。
-
子弹夹
栈的增删改查示例——数组实现栈
思路分析
代码实现
public class ArrayStack<E> {
//栈的大小
private int maxSize;
//数组模拟栈，数据放在数组中
private Object[] stack;
//top表示栈顶，初始化为-1
private int top = -1;
public <E> ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new Object[maxSize];
}
//栈满
private boolean isFull() {
return top == maxSize - 1;
}
//栈空
public boolean isEmpty() {
return top == -1;
}
//遍历
public void list() {
if (isEmpty()) {
System.out.println("栈是空的，没有数据");
return;
}
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\t", i, stack[i]);
}
/* while (true) {
if (top == -1) {
break;
}
System.out.println(stack[top]);
top--;
}*/
}
//入栈
public E peek() {
if (isEmpty()) {
System.out.println("栈是空的，没有数据");
return null;
}
return (E) stack[top];
}
//入栈
public void push(E e) {
if (isFull()) {
System.out.println("栈满了");
return;
}
top++;
stack[top] = e;
}
//出栈
public E pop() {
if (isEmpty()) {
System.out.println("栈是空的，没有数据");
return null;
}
E val = (E) stack[top];
top--;
return val;
}
}
public class ArrayStackTest {
public static void main(String[] args) {
testArrayStack();
}
public static void testArrayStack() {
ArrayStack<Integer> stack = new ArrayStack<>(10);
for (int i = 1; i <= 15; i++) {
stack.push(i);
}
//打印stack
stack.list();
}
/**
* 栈满了
* 栈满了
* 栈满了
* 栈满了
* 栈满了
* stack[9]=10 stack[8]=9 stack[7]=8 stack[6]=7 stack[5]=6 stack[4]=5 stack[3]=4 stack[2]=3 stack[1]=2 stack[0]=1
*/
}
注：也可以用个链表实现,头插法实现LIFO。
public class LinkedStack<E> {
private LinkedList<E> linkedList;
public LinkedStack() {
this.linkedList = new LinkedList<E>();
}
public void push(E e) {
linkedList.addFirst(e);
}
public E pop() {
return linkedList.getFirst();
}
public void list(){
while (linkedList.peekFirst()!= null) {
System.out.printf("%d\t",linkedList.poll());
}
}
}
public class ArrayStackTest {
public static void main(String[] args) {
testLinkedStack();
}
public static void testLinkedStack() {
LinkedStack<Integer> stack = new LinkedStack<>();
for (int i = 1; i <= 15; i++) {
stack.push(i);
}
//打印stack
stack.list();
//15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
}
}
栈实现综合计算器——中缀表达式
思路分析
代码实现——多位数计算器
public class Calculator {
//数据栈
private ArrayStack<Integer> numStack;
//符合栈
private ArrayStack<Character> operStack;
//扩展通过正则表达式匹配数据
private String numRegex = "^([1-9][0-9]*)$";
public Calculator() {
numStack = new ArrayStack<Integer>(20);
operStack = new ArrayStack<Character>(20);
}
//计算器，先乘除后加减，从左到右依次运算
public Integer calculate(String expression) {
if (StringUtils.isEmpty(expression)) {
System.out.println("输入的表达式不正确");
return null;
}
int num1 = 0;
int num2 = 0;
int result = 0;
char oper = 0;
String keepNum = "";
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (isOperate(c)) {
if (operStack.isEmpty()) {
operStack.push(c);
} else {
//当操作符优先级小于等于栈中优先级时，先计算栈中的操作符
//注意要用while循环判断，因为可能不止一个
while (operStack.peek() != null && priority(c) <= priority(operStack.peek())) {
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
result = cal(num1, num2, oper);
numStack.push(result);
}
operStack.push(c);
}
} else {
// 个位计算器用， -48或者-\'0\'字符都是为了得到正确的int值
// numStack.push((int) c - 48);
// numStack.push(c - \'0\');
if (i + 1 < expression.length() && !isOperate(expression.charAt(i + 1))) {
keepNum = keepNum + c;
continue;
} else {
keepNum = keepNum + c;
numStack.push(Integer.parseInt(keepNum));
keepNum = "";
}
}
}
//当操作符栈不为空时进行运算
while (!operStack.isEmpty()) {
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
result = cal(num1, num2, oper);
numStack.push(result);
}
return numStack.pop();
}
//判断是否是操作符
private boolean isOperate(char ch) {
return ch == \'+\' || ch == \'-\' || ch == \'*\' || ch == \'/\';
}
//操作符优先级判断，乘除是1，加减是0
private int priority(char ch) {
if (ch == \'*\' || ch == \'/\') {
return 1;
} else if (ch == \'+\' || ch == \'-\') {
return 0;
} else {
return -1;
}
}
//数据运算
private int cal(int num1, int num2, char oper) {
switch (oper) {
case \'+\':
return num1 + num2;
case \'-\':
return num2 - num1;
case \'*\':
return num1 * num2;
case \'/\':
return num2 / num1;
default:
throw new RuntimeException("操作符有误！");
}
}
}
//ArrayStack 参考上面
//测试
public class CalculatorTest {
public static void main(String[] args) {
Calculator calculator = new Calculator();
// Integer calculate = calculator.calculate("3+2*6-2");//13
// Integer calculate = calculator.calculate("113+2*6-2");//123
Integer calculate = calculator.calculate("1+2*6*2-2");//23
System.out.println("计算结果为:" + calculate);
}
}
栈的三种表达式——前缀表达式、中缀表达式、后缀表达式
前缀表达式和后缀表达式之所以适合计算机运算，就是它不包含括号，不需要像中缀表达式那样判断运算符的优先级，这种需要判断对计算机来说并不方便，而是直接从左到右或者从右到左依次运算即可。因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.)
前缀表达式——Prefix Expression——波兰表达式—— Polish Expression
前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前。
比如: - × + 3 4 5 6
前缀表达式的计算机求值
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
- 例如: - × + 3 4 5 6
- 从右至左扫描，将6、5、4、3压入堆栈
- 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素，注意与后缀表达式做比较），计算出3+4的值，得7，再将7入栈
- 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
- 最后是-运算符，计算出35-6的值，即29，由此得出最终结果
中缀表达式——Inffix Expression
中缀表达式就是常见的运算表达式，如(3+4)×5-6 。
也就是我们生活中写的四则运算表达式，是我们最熟悉的运算表达式，是包含括号的。
后缀表达式——Suffix Expression——逆波兰表达式—— Inverse Polish Expression——适合计算机计算
后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后
比如:3 4 + 5 × 6 -
后缀表达式计算机求值
与前缀表达式类似，只是顺序是从左至右：
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
例如后缀表达式“3 4 + 5 × 6 -”：
- 从左至右扫描，将3和4压入堆栈；
- 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做比较），计算出3+4的值，得7，再将7入栈；
- 将5入栈；
- 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
- 将6入栈；
- 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。
注意：在做减法或者除法时，弹出栈中的两个数，第二个数或者说后弹出来的数是被减数和被除数，与前缀表达式相反。
将中缀表达式转换为后缀表达式
与转换为前缀表达式相似，步骤如下：
- 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
- 从左至右扫描中缀表达式；
- 遇到操作数时，将其压s2；
- 遇到运算符时，比较其与s1栈顶运算符的优先级：
- 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
- 否则，若优先级比栈顶运算符的高，也将运算符压入s1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
- 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
- 遇到括号时：
- 如果是左括号“(”，则直接压入s1；
- 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；
- 重复步骤2至5，直到表达式的最右边；
- 将s1中剩余的运算符依次弹出并压入s2；
- 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）
例如，将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下：
| 扫描到的元素 | s2(栈底->栈顶) | s1 (栈底->栈顶) | 说明 |
|---|---|---|---|
| 1 | 1 | 空 | 数字，直接入栈 |
| + | 1 | + | s1为空，运算符直接入栈 |
| ( | 1 | + ( | 左括号，直接入栈 |
| ( | 1 | + ( ( | 同上 |
| 2 | 1 2 | + ( ( | 数字 |
| + | 1 2 | + ( ( + | s1栈顶为左括号，运算符直接入栈 |
| 3 | 1 2 3 | + ( ( + | 数字 |
| ) | 1 2 3 + | + ( | 右括号，弹出运算符直至遇到左括号 |
| × | 1 2 3 + | + ( × | s1栈顶为左括号，运算符直接入栈 |
| 4 | 1 2 3 + 4 | + ( × | 数字 |
| ) | 1 2 3 + 4 × | + | 右括号，弹出运算符直至遇到左括号 |
| - | 1 2 3 + 4 × + | - | -与+优先级相同，因此弹出+，再压入- |
| 5 | 1 2 3 + 4 × + 5 | - | 数字 |
| 到达最右端 | 1 2 3 + 4 × + 5 - | 空 | s1中剩余的运算符 |
因此结果为“1 2 3 + 4 × + 5 -”
逆波兰计算器代码示例
后缀计算器——逆波兰计算器实现
//逆波兰计算器
public class InversePolishExpressionCalculator {
public static void main(String[] args) {
// String suffixExpression = "1 2 3 + 4 * + 5 -";//计算结果为：16
// 50-3*4+(5-3)*2/4 转化 50 3 4 * - 5 3 - 2 * 4 / +
String suffixExpression = "50 3 4 * - 5 3 - 2 * 4 / +";//计算结果为：39
List<String> expressionList = getInversePolishExpressionList(suffixExpression);
int result = InversePolishExpressionCalculate(expressionList);
System.out.println("计算结果为：" + result);
}
//约定大于配置
//约定逆波兰表达式值用空格隔开 1 2 3 + 4 * + 5 -
//把逆波兰表达式值转为List
public static List<String> getInversePolishExpressionList(String suffixExpression) {
String[] expressionArr = suffixExpression.split(" ");
List<String> list = Arrays.asList(expressionArr);
return list;
}
/**
* 逆波兰表达式计算
*
* @param list
* @return
*/
public static int InversePolishExpressionCalculate(List<String> list) {
Stack<String> stack = new Stack<>();
for (String item : list) {
//匹配到的是数字则直接入栈
if (item.matches("\\d+")) {
stack.push(item);
//否则为符号弹出两个数进行运算
} else {
int num1 = Integer.valueOf(stack.pop());
int num2 = Integer.valueOf(stack.pop());
int result = 0;
switch (item) {
case "+":
result = num1 + num2;
break;
//在做减法或者除法时，弹出栈中的两个数，第二个数或者说后弹出来的数是被减数和被除数
case "-":
result = num2 - num1;
break;
case "*":
result = num1 * num2;
break;
case "/":
result = num2 / num1;
break;
default:
throw new RuntimeException("运算符号有误：" + item);
}
//运算结果入栈
stack.push(String.valueOf(result));
}
}
//stack栈顶的数据就是最后的运算结果
return Integer.valueOf(stack.pop());
}
}
中缀表达式转后缀表达式示例
思路分析
代码示例
//中缀表达式转后缀表达式
public class InfixExpression2SuffixExpression {
public static void main(String[] args) {
String infixExpression = "1 + ( ( 2 + 3 ) * 4 ) - 5";
List<String> suffixExpressionList = parseInfixExpression2SuffixExpression(getInfixExpressionList(infixExpression));
System.out.println("中缀表达式转后缀表达式为："+suffixExpressionList);
//中缀表达式转后缀表达式为：[1, 2, 3, +, 4, *, +, 5, -]
}
//约定大于配置
//将中缀表达式字符串转List
//约定中缀表达式字符串用空格隔开
public static List<String> getInfixExpressionList(String infixExpression) {
String[] expressionArr = infixExpression.split(" ");
List<String> list = Arrays.asList(expressionArr);
return list;
}
/**
* 1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
* 2. 从左至右扫描中缀表达式；
* 3. 遇到操作数时，将其压s2；
* 4. 遇到运算符时，比较其与s1栈顶运算符的优先级：
* 1. 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
* 2. 否则，若优先级比栈顶运算符的高，也将运算符压入s1（**注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况**）；
* 3. 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
* 5. 遇到括号时：
* 1. 如果是左括号“(”，则直接压入s1；
* 2. 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；
* 6. 重复步骤2至5，直到表达式的最右边；
* 7. 将s1中剩余的运算符依次弹出并压入s2；
* 8. 依次弹出s2中的元素并输出，**结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）**
*
* @param infixExpressionList
* @return
*/
//中缀表达式转后缀表达式
public static List<String> parseInfixExpression2SuffixExpression(List<String> infixExpressionList) {
//运算符栈
Stack<String> s1 = new Stack<>();
//存放结果的List
ArrayList<String> s2 = new ArrayList<>();
for (String item : infixExpressionList) {
//匹配到的是数字则直接入栈
if (item.matches("\\d+")) {
s2.add(item);
//如果是左括号“(”，则直接压入s1；
} else if (item.equals("(")) {
s1.push(item);
//如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；
} else if (item.equals(")")) {
while (!"(".equals(s1.peek())) {
s2.add(s1.pop());
}
s1.pop();//将(左括号弹出消除左括号
} else {
/**
* 4. 遇到运算符时，比较其与s1栈顶运算符的优先级：
* 1. 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
* 2. 否则，若优先级比栈顶运算符的高，也将运算符压入s1（**注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况**）；
* 3. 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
*/
//对1,2,条件取反就进入3条件，进行while循环判断
while (s1.size() != 0 && !"(".equals(s1.peek()) && OperatorPriorityEnum.getCodeFromDesc(item) <= OperatorPriorityEnum.getCodeFromDesc(s1.peek())) {
s2.add(s1.pop());
}
//还需要将运算符压入栈
s1.push(item);
}
}
//将s1中剩余的运算符依次弹出并压入s2
while (s1.size() > 0) {
s2.add(s1.pop());
}
return s2;
}
}
//枚举
public enum OperatorPriorityEnum {
//枚举定义要放最前面，否则报错
ADD(0, "+"),
SUBSTRACT(0, "-"),
MULTIPLY(1, "*"),
DEVIDE(1, "/");
private int code;
private String desc;
public Integer getCode() {
return code;
}
public String getDesc() {
return desc;
}
OperatorPriorityEnum(int code, String desc) {
this.code = code;
this.desc = desc;
}
public static Integer getCodeFromDesc(String desc) {
for (OperatorPriorityEnum enums : OperatorPriorityEnum.values()) {
if (enums.getDesc().equals(desc)) {
return enums.getCode();
}
}
return null;
}
}
逆波兰计算器完整版
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
import java.util.regex.Pattern;
public class ReversePolishMultiCalc {
/**
* 匹配 + - * / ( ) 运算符
*/
static final String SYMBOL = "\\+|-|\\*|/|\\(|\\)";
static final String LEFT = "(";
static final String RIGHT = ")";
static final String ADD = "+";
static final String MINUS= "-";
static final String TIMES = "*";
static final String DIVISION = "/";
/**
* 加減 + -
*/
static final int LEVEL_01 = 1;
/**
* 乘除 * /
*/
static final int LEVEL_02 = 2;
/**
* 括号
*/
static final int LEVEL_HIGH = Integer.MAX_VALUE;
static Stack<String> stack = new Stack<>();
static List<String> data = Collections.synchronizedList(new ArrayList<String>());
/**
* 去除所有空白符
* @param s
* @return
*/
public static String replaceAllBlank(String s ){
// \\s+ 匹配任何空白字符，包括空格、制表符、换页符等等, 等价于[ \f\n\r\t\v]
return s.replaceAll("\\s+","");
}
/**
* 判断是不是数字 int double long float
* @param s
* @return
*/
public static boolean isNumber(String s){
Pattern pattern = Pattern.compile("^[-\\+]?[.\\d]*$");
return pattern.matcher(s).matches();
}
/**
* 判断是不是运算符
* @param s
* @return
*/
public static boolean isSymbol(String s){
return s.matches(SYMBOL);
}
/**
* 匹配运算等级
* @param s
* @return
*/
public static int calcLevel(String s){
if("+".equals(s) || "-".equals(s)){
return LEVEL_01;
} else if("*".equals(s) || "/".equals(s)){
return LEVEL_02;
}
return LEVEL_HIGH;
}
/**
* 匹配
* @param s
* @throws Exception
*/
public static List<String> doMatch (String s) throws Exception{
if(s == null || "".equals(s.trim())) throw new RuntimeException("data is empty");
if(!isNumber(s.charAt(0)+"")) throw new RuntimeException("data illeagle,start not with a number");
s = replaceAllBlank(s);
String each;
int start = 0;
for (int i = 0; i < s.length(); i++) {
if(isSymbol(s.charAt(i)+"")){
each = s.charAt(i)+"";
//栈为空，(操作符，或者 操作符优先级大于栈顶优先级 && 操作符优先级不是( )的优先级 及是 ) 不能直接入栈
if(stack.isEmpty() || LEFT.equals(each)
|| ((calcLevel(each) > calcLevel(stack.peek())) && calcLevel(each) < LEVEL_HIGH)){
stack.push(each);
}else if( !stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())){
//栈非空，操作符优先级小于等于栈顶优先级时出栈入列，直到栈为空，或者遇到了(，最后操作符入栈
while (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek()) ){
if(calcLevel(stack.peek()) == LEVEL_HIGH){
break;
}
data.add(stack.pop());
}
stack.push(each);
}else if(RIGHT.equals(each)){
// ) 操作符，依次出栈入列直到空栈或者遇到了第一个)操作符，此时)出栈
while (!stack.isEmpty() && LEVEL_HIGH >= calcLevel(stack.peek())){
if(LEVEL_HIGH == calcLevel(stack.peek())){
stack.pop();
break;
}
data.add(stack.pop());
}
}
start = i ; //前一个运算符的位置
}else if( i == s.length()-1 || isSymbol(s.charAt(i+1)+"") ){
each = start == 0 ? s.substring(start,i+1) : s.substring(start+1,i+1);
if(isNumber(each)) {
data.add(each);
continue;
}
throw new RuntimeException("data not match number");
}
}
//如果栈里还有元素，此时元素需要依次出栈入列，可以想象栈里剩下栈顶为/，栈底为+，应该依次出栈入列，可以直接翻转整个stack 添加到队列
Collections.reverse(stack);
data.addAll(new ArrayList<>(stack));
System.out.println(data);
return data;
}
/**
* 算出结果
* @param list
* @return
*/
public static Double doCalc(List<String> list){
Double d = 0d;
if(list == null || list.isEmpty()){
return null;
}
if (list.size() == 1){
System.out.println(list);
d = Double.valueOf(list.get(0));
return d;
}
ArrayList<String> list1 = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
list1.add(list.get(i));
if(isSymbol(list.get(i))){
Double d1 = doTheMath(list.get(i - 2), list.get(i - 1), list.get(i));
list1.remove(i);
list1.remove(i-1);
list1.set(i-2,d1+"");
list1.addAll(list.subList(i+1,list.size()));
break;
}
}
doCalc(list1);
return d;
}
/**
* 运算
* @param s1
* @param s2
* @param symbol
* @return
*/
public static Double doTheMath(String s1,String s2,String symbol){
Double result ;
switch (symbol){
case ADD : result = Double.valueOf(s1) + Double.valueOf(s2); break;
case MINUS : result = Double.valueOf(s1) - Double.valueOf(s2); break;
case TIMES : result = Double.valueOf(s1) * Double.valueOf(s2); break;
case DIVISION : result = Double.valueOf(s1) / Double.valueOf(s2); break;
default : result = null;
}
return result;
}
public static void main(String[] args) {
//String math = "9+(3-1)*3+10/2";
String math = "12.8 + (2 - 3.55)*4+10/5.0";
try {
doCalc(doMatch(math));
} catch (Exception e) {
e.printStackTrace();
}
}
}
算法——algorithm
递归——recursion——俄罗斯套娃
递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。
递归需要遵守的重要规则
- 执行一个方法时，就创建一个新的受保护的独立空间(栈帧空间)
- 方法的局部变量是独立的，不会相互影响, 比如n变量；如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.
- 递归必须向退出递归的条件逼近，否则就是无限递归,出现*Error，死龟了。
- 当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。
场景
- 打印问题
- 阶乘问题
- 走迷宫回溯
- 8皇后问题
- 球和篮子的问题
- 各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等
递归示例
递归调用方法图解分析
代码示例
public class Recursion {
//递归打印
public static void recursionPrint(int n) {
if (n > 1) {
recursionPrint(n - 1);
}
System.out.println("n=" + n);
}
/**
* n=1
* n=2
* n=3
* n=4
* n=5
*/
//递归实现阶乘
public static int factorial(int n) {
if (n > 1) {
return n * factorial(n - 1);//5*4*3*2*1
} else {
return 1;
}
}
//阶乘结果为：120
public static void main(String[] args) {
//recursionPrint(5);
//阶乘结果为：120
System.out.println("阶乘结果为："+factorial(5));
}
}
递归回溯走迷宫代码示例
注：在没有使用算法求最短路径时，最短路径的选择与我们代码中行走的策略有关。
代码示例
/**
* 迷宫原始图：
* 1 1 1 1 1 1 1 1 1 1
* 1 0 0 0 0 0 0 0 0 1
* 1 0 0 0 0 0 0 0 0 1
* 1 0 0 0 0 0 0 0 0 1
* 1 0 1 0 1 1 1 1 0 1
* 1 0 1 0 0 0 0 0 0 1
* 1 0 1 0 0 0 0 0 0 1
* 1 0 1 0 0 0 0 0 0 1
* 1 0 1 0 0 0 0 0 0 1
* 1 1 1 1 1 1 1 1 1 1
* --------------------------------
* 走出迷宫路径：
* 1 1 1 1 1 1 1 1 1 1
* 1 2 0 0 0 0 0 0 0 1
* 1 2 0 0 0 0 0 0 0 1
* 1 2 2 2 0 0 0 0 0 1
* 1 3 1 2 1 1 1 1 0 1
* 1 3 1 2 0 0 0 0 0 1
* 1 3 1 2 0 0 0 0 0 1
* 1 3 1 2 0 0 0 0 0 1
* 1 3 1 2 2 2 2 2 2 1
* 1 1 1 1 1 1 1 1 1 1
* --------------------------------
* 走出迷宫最短路径：
* 1 1 1 1 1 1 1 1 1 1
* 1 2 2 2 2 2 2 2 2 1
* 1 0 0 0 0 0 0 0 2 1
* 1 0 0 0 0 0 0 0 2 1
* 1 0 1 0 1 1 1 1 2 1
* 1 0 1 0 0 0 0 0 2 1
* 1 0 1 0 0 0 0 0 2 1
* 1 0 1 0 0 0 0 0 2 1
* 1 0 1 0 0 0 0 0 2 1
* 1 1 1 1 1 1 1 1 1 1
*/
public class Maze {
public static void main(String[] args) {
int[][] maze = buildMaze();
System.out.println("走出迷宫路径：");
walkMaze(maze, 1, 1);
// System.out.println("走出迷宫最短路径：");
// walkMazeShortcut(maze, 1, 1);
printMaze(maze);
}
/**
* 约定大于配置
* 创建二维数组模拟迷宫
* 使用1表示墙，四周置墙
*/
public static int[][] buildMaze() {
int[][] maze = new int[10][10];
for (int i = 0; i < maze.length; i++) {
//对第0和第9行设置1表示墙
maze[0][i] = 1;
maze[9][i] = 1;
//对第0和第9列设置1表示墙
maze[i][0] = 1;
maze[i][9] = 1;
//设置其他障碍
if (3 < i) {
maze[i][2] = 1;
}
if (i > 3) {
maze[4][i] = 1;
if (i == 8) {
maze[4][i] = 0;
}
}
}
System.out.println("迷宫原始图：");
printMaze(maze);
System.out.println("--------------------------------");
return maze;
}
/**
* 使用递归回溯找路
*
* @param maze 地图
* @param //x坐标
* @param //y坐标
* @return 找到路返回true，否则false
* x,y表示地图位置坐标，最开始位置置为(1,1)
* 约定，从坐标1,1走到8,8表示走出迷宫
* //注意因为我们定义的数组是10,10,最外层的坐标9,9已经被标记为墙，则应该设置终点为8,8才能达到，否则永远都走不通
* //值1表示墙，2表示走完迷宫的路，3表示走不通 0表示没走过
* 寻路策略：先向下->右->上->左
*/
public static boolean walkMaze(int[][] maze, int x, int y) {
if (maze[8][8] == 2) {
return true;
} else {
if (maze[x][y] == 0) {
maze[x][y] = 2;
//向下找,行增加，x+1
if (walkMaze(maze, x + 1, y)) {
return true;
//右
} else if (walkMaze(maze, x, y + 1)) {
return true;
//上
} else if (walkMaze(maze, x - 1, y)) {
return true;
//左
} else if (walkMaze(maze, x, y - 1)) {
return true;
} else {
//走不通
maze[x][y] = 3;
return false;
}
} else {
//不为0的情况
return false;
}
}
}
//修改策略达到最短路径
public static boolean walkMazeShortcut(int[][] maze, int x, int y) {
if (maze[8][8] == 2) {
return true;
} else {
if (maze[x][y] == 0) {
maze[x][y] = 2;
//右
if (walkMazeShortcut(maze, x, y + 1)) {
return true;
//向下找,行增加，x+1
} else if (walkMazeShortcut(maze, x + 1, y)) {
return true;
//上
} else if (walkMazeShortcut(maze, x - 1, y)) {
return true;
//左
} else if (walkMazeShortcut(maze, x, y - 1)) {
return true;
} else {
//走不通
maze[x][y] = 3;
return false;
}
} else {
//不为0的情况
return false;
}
}
}
public static void printMaze(int[][] maze) {
for (int[] intRow : maze) {
for (int column : intRow) {
System.out.printf("%d\t", column);
}
System.out.println();
}
}
}
八皇后问题——回溯算法
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法（一共有92种）。
思路分析
说明：理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} //对应arr 下标 表示第几行，即第几个皇后，arr[i] = val , val 表示第i+1个皇后，放在第i+1行的第val+1列
代码实现——本质上就是暴力匹配
/**
* 0 4 7 5 2 6 1 3
* 0 5 7 2 6 3 1 4
* 0 6 3 5 7 1 4 2
* 0 6 4 7 1 3 5 2
* 1 3 5 7 2 0 6 4
* 1 4 6 0 2 7 5 3
* 1 4 6 3 0 7 5 2
* 1 5 0 6 3 7 2 4
* 1 5 7 2 0 3 6 4
* 1 6 2 5 7 4 0 3
* 1 6 4 7 0 3 5 2
* 1 7 5 0 2 4 6 3
* 2 0 6 4 7 1 3 5
* 2 4 1 7 0 6 3 5
* 2 4 1 7 5 3 6 0
* 2 4 6 0 3 1 7 5
* 2 4 7 3 0 6 1 5
* 2 5 1 4 7 0 6 3
* 2 5 1 6 0 3 7 4
* 2 5 1 6 4 0 7 3
* 2 5 3 0 7 4 6 1
* 2 5 3 1 7 4 6 0
* 2 5 7 0 3 6 4 1
* 2 5 7 0 4 6 1 3
* 2 5 7 1 3 0 6 4
* 2 6 1 7 4 0 3 5
* 2 6 1 7 5 3 0 4
* 2 7 3 6 0 5 1 4
* 3 0 4 7 1 6 2 5
* 3 0 4 7 5 2 6 1
* 3 1 4 7 5 0 2 6
* 3 1 6 2 5 7 0 4
* 3 1 6 2 5 7 4 0
* 3 1 6 4 0 7 5 2
* 3 1 7 4 6 0 2 5
* 3 1 7 5 0 2 4 6
* 3 5 0 4 1 7 2 6
* 3 5 7 1 6 0 2 4
* 3 5 7 2 0 6 4 1
* 3 6 0 7 4 1 5 2
* 3 6 2 7 1 4 0 5
* 3 6 4 1 5 0 2 7
* 3 6 4 2 0 5 7 1
* 3 7 0 2 5 1 6 4
* 3 7 0 4 6 1 5 2
* 3 7 4 2 0 6 1 5
* 4 0 3 5 7 1 6 2
* 4 0 7 3 1 6 2 5
* 4 0 7 5 2 6 1 3
* 4 1 3 5 7 2 0 6
* 4 1 3 6 2 7 5 0
* 4 1 5 0 6 3 7 2
* 4 1 7 0 3 6 2 5
* 4 2 0 5 7 1 3 6
* 4 2 0 6 1 7 5 3
* 4 2 7 3 6 0 5 1
* 4 6 0 2 7 5 3 1
* 4 6 0 3 1 7 5 2
* 4 6 1 3 7 0 2 5
* 4 6 1 5 2 0 3 7
* 4 6 1 5 2 0 7 3
* 4 6 3 0 2 7 5 1
* 4 7 3 0 2 5 1 6
* 4 7 3 0 6 1 5 2
* 5 0 4 1 7 2 6 3
* 5 1 6 0 2 4 7 3
* 5 1 6 0 3 7 4 2
* 5 2 0 6 4 7 1 3
* 5 2 0 7 3 1 6 4
* 5 2 0 7 4 1 3 6
* 5 2 4 6 0 3 1 7
* 5 2 4 7 0 3 1 6
* 5 2 6 1 3 7 0 4
* 5 2 6 1 7 4 0 3
* 5 2 6 3 0 7 1 4
* 5 3 0 4 7 1 6 2
* 5 3 1 7 4 6 0 2
* 5 3 6 0 2 4 1 7
* 5 3 6 0 7 1 4 2
* 5 7 1 3 0 6 4 2
* 6 0 2 7 5 3 1 4
* 6 1 3 0 7 4 2 5
* 6 1 5 2 0 3 7 4
* 6 2 0 5 7 4 1 3
* 6 2 7 1 4 0 5 3
* 6 3 1 4 7 0 2 5
* 6 3 1 7 5 0 2 4
* 6 4 2 0 5 7 1 3
* 7 1 3 0 6 4 2 5
* 7 1 4 2 0 6 3 5
* 7 2 0 5 1 4 6 3
* 7 3 0 2 5 1 6 4
* 一共有92种摆放方法
* 一共有92种摆放方法一共判断了15720次
*/
public class Queen {
public static void main(String[] args) {
Queen queen = new Queen(8);
queen.showQueenMagic();
System.out.printf("一共有%d种摆放方法", queen.getCount());//92
System.out.printf("一共判断了%d次",queen.getJudgeCount());//15720
}
//表示玩的是几个皇后
private int max;
////对应arr 下标 表示第几行，即第几个皇后，arr[i] = val , val 表示第i+1个皇后，放在第i+1行的第val+1列
private int[] arr;
//累计摆放方法数
private int count;
//一共判断了多少次
private int judgeCount;
public int getJudgeCount() {
return judgeCount;
}
public int getCount() {
return count;
}
public Queen(int max) {
this.max = max;
arr = new int[max];
}
public void showQueenMagic() {
//从第1个皇后开始放置
check(0);
}
/**
* n表示放置第n个皇后
* check是每一次递归时，进入check方法都会有 for (int i = 0; i < max; i++)循环，因此会有回溯
* 回溯就在于我们每次都把符合排列的八皇后摆法打印出来，然后程序继续往下走，当第8个皇后摆放完毕到max时已经没有其他的成功结果后，就会回溯到第7个皇后的下一个摆放位置，
* 继续往下深入，当第7个皇后也摆放测试到max位置结束后，就会回溯到第6个皇后摆放位置的下一个，一直到第一个皇后从第1位摆放到第max位
* @param n
*/
public void check(int n) {
//表示进来判断是n如果等于max比如8，则表示目前进来判断的是第九个皇后
//也就是说第八个皇后已经放置好了
if (n == max) {
print();
count++;
return;
}
//依次在0到max中摆放皇后，判断是否冲突
for (int i = 0; i < max; i++) {
//表示对第n个皇后的放置位置从0开始放置，并进行校验位置放置是否满足条件
arr[n] = i;
if (judgePlaceIsOk(n)) {
//满足则继续摆放第n+1个皇后
check(n + 1);
}
//不满足则进入i++继续判断，继续往下摆放
}
}
//n表示放置第n个皇后,他放置的位置与之前的0到n-1位皇后的位置进行比对是否冲突
public boolean judgePlaceIsOk(int n) {
judgeCount++;
for (int i = 0; i < n; i++) {
//斜率k=(y1-y2)/(x1-x2) ，而当两个点在同一个斜线上时k=1，这时候得出(y1-y2) = (x1-x2)
//arr[i] == arr[n]表示在同一列上
//Math.abs(i - n) == Math.abs(arr[i] - arr[n]) 表示在同一斜线上
//同一行不需要对比，因为我们上面的for循环只在不同行上，因此一定不会在同一行上
if (arr[i] == arr[n] || Math.abs(i - n) == Math.abs(arr[i] - arr[n])) {
return false;
}
}
return true;
}
private void print() {
for (int q : arr) {
System.out.printf("%d\t", q);
}
System.out.println();
}
}
扩展：
行差等于列差，表示45°，说明在同一个斜向上。
斜率k=(y1-y2)/(x1-x2) ，而当两个点在同一个斜线上时k=1，这时候得出(y1-y2) = (x1-x2) 。
斜率k=1时的直线： y=x+b，线与x轴夹角为+45度。
排序——Sort Algorithm
排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程。
排序的分类
- 内部排序——内存
指将需要处理的所有数据都加载 到内部存储器中进行排序。
- 外部排序——借助外存
数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。
常见的排序算法分类
衡量一个程序(算法)执行时间的两种方法
事后统计的方法
这种方法可行, 但是有两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, 这种方式，要在同一台计算机的相同状态下运行，才能比较那个算法速度更快。
事前估算的方法
通过分析某个算法的时间复杂度来判断哪个算法更优.
时间复杂度——Ｏ( f(n) ) —— Time Complexity
时间频度——T(N)
时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
时间复杂度的计算规则
- 忽略常数项
- 忽略低次项
- 忽略系数
时间复杂度简介
一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作 T(n)=Ｏ( f(n) )，称Ｏ( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度。
T(n) 不同，但时间复杂度可能相同。 如：T(n)=n²+7n+6 与 T(n)=3n²+2n+2 它们的T(n) 不同，但时间复杂度相同，都为O(n²)。
计算时间复杂度的方法
用常数1代替运行时间中的所有加法常数（ 忽略常数项） T(n)=3n²+7n+6 => T(n)=3n²+7n+1
修改后的运行次数函数中，只保留最高阶项 （忽略低次项） T(n)=3n²+7n+1 => T(n) = 3n²
去除最高阶项的系数（忽略系数） T(n) = 3n² => T(n) = n² => O(n²)
常见的时间复杂度(10种)
- 常数阶O(1)
- 对数阶O(log2^n)
- 线性阶O(n)
- 线性对数阶O(nlog2^n)
- 平方阶O(n^2)
- 立方阶O(n^3)
- k次方阶O(n^k)
- 指数阶O(2^n)
- n的阶乘Ο(n!)
- n的指数阶O(n^n)
常见的算法时间复杂度由小到大排列
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(n^k) ＜Ο(2^n) ＜Ο(n!)
随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低.
对数阶O(log2^n)
对数就是指数的相反操作。
x= loga^n （a>0,a≠1）,x叫做以a为底的n的对数，a为底数，n为真数。
我们要求 log2^1024，其实就是求2的几次方=1024，也就是10。
或者，log22=1,我们可以这样计算：log21024=log22+log22+log22+log22+log22+log22+log22+log22+log22+log22=
1+1+1+1+1+1+1+1+1+1=10
log327=3，因为33=27。注意下面i=i*3,则O(log3^n)
扩展
线性阶O(n)
单层的for循环就是线性阶。
线性对数阶O(nlogn)
时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。
平方阶O(n²)
两层for循环嵌套就是平方阶
平均时间复杂度和最坏时间复杂度
- 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
- 最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。
- 平均时间复杂度和最坏时间复杂度是否一致，和算法有关.
空间复杂度——Space Complexity
类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模n的函数。
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法、基数排序就属于这种情况。
在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间.
冒泡排序——Bubble Sort——O(n^2)
冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。
优化：
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在
排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。
public class BubbleSort {
public static void main(String[] args) {
int[] array = {1, 15, -2, 67, 100, 3, 29};
// int[] array = {1,2,3,46,5};//[1, 2, 3, 5, 46]
System.out.println("排序前：");
System.out.println(Arrays.toString(array));
bubbleSort(array);
System.out.println("排序后：");
System.out.println(Arrays.toString(array));
//[-2, 1, 3, 15, 29, 67, 100]
//测试十万数据冒泡排序耗时
int[] arrTest = new int[10_0000];
for (int i = 0; i < arrTest.length; i++) {
//Math.random()产生0-1之间的随机数，再乘以一百万，产生0-十万之间的随机数，
// 注意要对(Math.random()*10_0000)加括号再强转int类型，否则得到的永远是0
arrTest[i] = (int)(Math.random()*10_0000);
}
long start = System.currentTimeMillis();
bubbleSort(arrTest);
long end = System.currentTimeMillis();
System.out.println("十万数据冒泡排序耗时:"+(end-start));
/**
* 排序前：
* [1, 15, -2, 67, 100, 3, 29]
* 排序后：
* [-2, 1, 3, 15, 29, 67, 100]
* 十万数据冒泡排序耗时:13658
*/
}
/**
* 冒泡排序：时间复杂度 O(n^2)
* @param array
*/
public static void bubbleSort(int[] array) {
//当新的一轮冒泡没有发生交换时我们认为以及排序好了，跳出循环
boolean swapFlag = false;
//一共循环rray.length-1次，因为是两个数比较，最后一次只有一个数，不需要
for (int j = 0; j < array.length-1; j++) {
/**
* 从冒泡排序的规律上看，第一次比较array.length - 1次,
* 第二次一共比较了array.length - 1 -1次，因为最后一个数已经通过冒泡到了最后一个位置，
* 无需再与最后一个数比较，因此减少了一次比较的过程，以此类推，则每次冒泡都减少了j次比较，
* j从0开始。
*/
for (int i = 0; i < array.length - j - 1; i++) {
//如果要从大到小排序则改变比较规则即可
if (array[i] > array[i + 1]) {
int temp = 0;
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
swapFlag = true;
}
}
if (!swapFlag) {
break;
} else {
//重置swapFlag，进行新一轮的判断
swapFlag = false;
}
}
}
//注意这里不能提取方法，因为是值传递，数组元素不会发生改变，如果要提取方法则要直接传入数组array进行操作才行，数组才是引用传递
private static void swap(int x, int y) {
int temp = 0;
temp = x;
x = y;
y = temp;
}
}
选择排序——Select Sort——O(n^2)
选择排序，顾名思义，如果我们是按从小到大对数组进行排序，那么从数组第一位开始遍历到最后一个元素，从中选择出最小的元素与第一位进行交换，这样第一位就得到了最小的那个数；第二位就是从第二个元素开始比较，选出最小的放在第二位，以此类推。
选择排序思想:
选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从arr[0]arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]arr[n-1]中选取最小值，与arr[2]交换，…，第i次从arr[i-1]arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
//选择排序
public class SelectSort {
public static void main(String[] args) {
int [] arr = {101, 34, 119, 1, -1, 90, 123};
//创建要给80000个的随机的数组
// int[] arr = new int[80000];
// for (int i = 0; i < 80000; i++) {
// arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
// }
System.out.println("排序前");
System.out.println(Arrays.toString(arr));
// Date data1 = new Date();
// SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
// String date1Str = simpleDateFormat.format(data1);
// System.out.println("排序前的时间是=" + date1Str);
selectSort(arr);
// Date data2 = new Date();
// String date2Str = simpleDateFormat.format(data2);
// System.out.println("排序前的时间是=" + date2Str);
System.out.println("排序后");
System.out.println(Arrays.toString(arr));
}
//选择排序
public static void selectSort(int[] arr) {
//在推导的过程，我们发现了规律，因此，可以使用for来解决
//选择排序时间复杂度是 O(n^2)
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
int min = arr[i];
for (int j = i + 1; j < arr.length; j++) {
if (min > arr[j]) { // 说明假定的最小值，并不是最小
min = arr[j]; // 重置min
minIndex = j; // 重置minIndex
}
}
// 将最小值与arr[i]交换
if (minIndex != i) {
arr[minIndex] = arr[i];
arr[i] = min;
}
}
}
/**
* 排序前
* [101, 34, 119, 1, -1, 90, 123]
* 排序后
* [-1, 1, 34, 90, 101, 119, 123]
*/
}
其他
解决从其他地方拿到的文件编码有问题导致的乱码问题处理方法
解决方法就是用记事本打开该文件，再另存为一份新的文件，修改保存的文件格式，比如修改为UTF-8编码格式，再把该文件拷贝到想要的项目中或者复制过来即可。
