稀疏数组
public class Test {public static void main(String[] args) {//原始数组int[][] arr = new int[11][11];arr[1][2] = 1;arr[2][3] = 2;for (int[] row : arr) {for (int data : row) {System.out.printf("%d\t", data);}System.out.println();}System.out.println();//首先知道是有多少个数据，这样就能知道有多少行int sum = 0;for (int i = 0; i < 11; i++) {for (int j = 0; j < 11; j++) {if(arr[i][j] != 0) {sum++;}}}//稀疏数组int[][] sparseArr = new int[sum+1][3];sparseArr[0][0] =11;sparseArr[0][1] = 11;sparseArr[0][2] = sum;//记录遍历到的数据，逐行递增存储到稀疏数组的行中int count = 0;for (int i = 0; i < 11; i++) {for (int j = 0; j < 11; j++) {if(arr[i][j] != 0) {count++;sparseArr[count][0] = i;sparseArr[count][1] = j;sparseArr[count][2] = arr[i][j];}}}//输出稀疏数组for (int[] row : sparseArr) {for (int data : row) {System.out.printf("%d\t", data);}System.out.println();}}}
数组模拟队列
定义
- 队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
模拟思路
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量
- 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示
入队出队操作模拟
当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：
- 将尾指针往后移：rear+1 , 当 front == rear 时，队列为空
- 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。rear == maxSize - 1时，队列满
代码实现
class ArrayQueue {//队列的大小int maxSize;//用数组来实现队列int[] arr;//指向队列首元素的前一个位置int front;//指向队列的尾元素int rear;public ArrayQueue(int maxSize) {this.maxSize = maxSize;arr = new int[this.maxSize];//front指向队列首元素的前一个位置front = -1;rear = -1;}public boolean isFull() {return rear == maxSize - 1;}public boolean isEmpty() {return front == rear;}public void addNum(int num) {if(isFull()) {System.out.println("队列已满，无法在进行入队操作");return;}//队尾标记后移，指向要放入的元素的位置rear++;arr[rear] = num;}public int getNum() {if(isEmpty()) {throw new RuntimeException("队列为空，无法出队");}//队首标记后移，指向队首元素System.out.print("出队元素是：");front++;return arr[front];}public void showQueue() {if(isEmpty()) {throw new RuntimeException("队列为空，无法遍历");}System.out.println("遍历队列");//从front+1开始读取元素for(int start = front+1; start<=rear; start++) {System.out.println(arr[start]);}}}
存在问题
- 目前数组只能使用一次，不能复用。
-
数组模拟环形队列
分析说明
队满：尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定，这个在做判断队列满的时候需要注意
(rear+1) % maxSize = front- 这里取模是为了，当rear+1超过队列的时候，回到队列的开始，保持环形。
4 % 5 = 45 % 5 = 06 % 5 = 17 % 5 = 2
- 队空：
rear == front
- 队列有效个数:
- 当
rear > frontrear - front
- 当
rear < front0 + rearmaxSize - front
- 综上所述：
(rear - front + maxSize) % maxSize
- 当
代码实现
```java public class Demo4 { public static void main(String[] args) {
} }ArrayAroundQueue aroundQueue = new ArrayAroundQueue(5);aroundQueue.addNum(1);aroundQueue.addNum(2);aroundQueue.addNum(3);aroundQueue.addNum(4);aroundQueue.showQueue();System.out.println(aroundQueue.getNum());System.out.println(aroundQueue.getNum());aroundQueue.addNum(5);aroundQueue.addNum(6);aroundQueue.showQueue();aroundQueue.getHead();
class ArrayAroundQueue { //队列的大小 int maxSize; //用数组来实现队列 int[] arr; //指向队列首元素的位置 默认是0 int front; //指向队列的尾元素 默认是0 int rear;
public ArrayAroundQueue(int maxSize) { this.maxSize = maxSize; arr = new int[this.maxSize]; //front指向队列首元素的位置 front = 0; rear = 0; }
public boolean isFull() { return (rear+1)%maxSize == front; }
public boolean isEmpty() { return front == rear; }
public void addNum(int num) { if(isFull()) { System.out.println(“队列已满，无法在进行入队操作”); return; } //先放入元素，在后移队尾标记 arr[rear] = num; rear = (rear+1)%maxSize; }
public int getNum() { if(isEmpty()) { throw new RuntimeException(“队列为空，无法出队”); } //队首标记后移，指向队首元素 System.out.print(“出队元素是：”); int num = arr[front]; front = (front+1)%maxSize; return num; }
public void showQueue() { if(isEmpty()) { throw new RuntimeException(“队列为空，无法遍历”); } System.out.println(“遍历队列”); //当front + 1 == rear时停止遍历 int start = front; while(start != rear) { System.out.println(arr[start]); //移动到下一个元素 start = (start+1)%maxSize; } }
public void getHead() { if(isEmpty()) { throw new RuntimeException(“队列为空”); }
System.out.println("队首元素为："+arr[front]);
} }
<a name="I77KX"></a>
# 单链表
<a name="kaYhE"></a>
## 单链表介绍
- 链表是有序的列表，它在内存中是存储如下的
- 
- 链表是以节点的方式来存储，是链式存储
- 每个节点包含data域
- next域：指向下一个节点
- 如图：发现链表的各个节点不一定是连续存储
- 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
<a name="CrbhM"></a>
### 单链表（带头节点）逻辑结构
<a name="wHnlC"></a>
## 单链表的应用实例
<a name="lrvXr"></a>
### 使用带head头的单向链表实现-水浒英雄排行榜管理
<a name="PYu2f"></a>
#### 直接添加到尾部
<a name="BXA9k"></a>
#### 代码实现
**创建（添加）**
- 先创建一个Head头节点，表示单链表的头
- 后面我们每添加一个节点，就放在链表的最后
**遍历**
- 通过一个辅助变量，来遍历整个链表
**有序插入**
- 先遍历链表，找到应该插入的位置
- 要插入的节点的next指向插入位置的后一个节点
- 插入位置的前一个节点的next指向要插入节点
- 插入前要判断是否在队尾插入
```java
package com.foreign.singleChain;
/**
* @author fangke
* @Description:
* @Package
* @date: 2022/4/9 9:53 上午
* <p>
*/
public class SingleLinkedListDemo {
public static void main(String[] args) {
SingleLinkedList node = new SingleLinkedList();
HeroNode node1 = new HeroNode(1,"宋江","及时雨");
HeroNode node2 = new HeroNode(2,"林冲","豹子头");
HeroNode node3 = new HeroNode(3,"鲁智深","花和尚");
HeroNode node4 = new HeroNode(4,"张三","我也不知道");
node.addHeroNode(node1);
node.addHeroNode(node2);
node.addHeroNode(node3);
node.addHeroNode(node4);
node.listHeroNode();
}
}
class SingleLinkedList {
HeroNode head = new HeroNode(0, "", "");
public void addHeroNode(HeroNode node) {
HeroNode temp = head;
while (temp.getNext() != null) {
temp = temp.getNext();
}
temp.setNext(node);
}
public void listHeroNode() {
while (head.getNext() == null) {
System.out.println("链表为空");
}
HeroNode temp = head;
while (true) {
if(temp.getNext() == null) {
break;
}
System.out.println(temp);
temp = temp.getNext();
}
}
}
class HeroNode {
private int no;
private String name;
private String nickName;
private HeroNode next;
public HeroNode(int no, String name, String nickName) {
this.no = no;
this.name = name;
this.nickName = nickName;
}
}
根据排名将英雄插入指定位置
public void addHeroNodeByOrder(HeroNode node) {
HeroNode temp = head;
Boolean flag =false; //是否有重复的节点
while (true) {
//到末尾了
if(temp.getNext() == null) {
break;
}
//节点重复了
if(temp.getNext().getNo() == node.getNo()) {
flag = true;
break;
}
//找到了第一个大于要插入节点的temp
if(temp.getNext().getNo() > node.getNo()) {
break;
}
temp = temp.getNext();
}
if(flag) {
System.out.println("节点重复了");
} else {
node.setNext(temp.getNext());
temp.setNext(node);
}
}
修改英雄的名称和昵称
public void updateHeroNode(HeroNode node) {
if (head.getNext() == null) {
System.out.println("节点为空");
return;
}
HeroNode temp = head.getNext();
Boolean flag = false;
while (true) {
if (temp == null) { //此时到链表的结尾了
System.out.println("没有找到要修改的节点");
break;
}
if (temp.getNo() == node.getNo()) {
flag = true;
break;
}
temp = temp.getNext();
}
if (flag) {
temp.setName(node.getName());
temp.setNickName(node.getNickName());
} else {
System.out.println("没有找到要修改的英雄节点");
}
}
删除节点
public void deleteHeroNode(int no) {
if(head.getNext() == null) {
System.out.println("无节点可以删除");
return;
}
HeroNode temp = head;
Boolean flag = false;
while (true) {
if(temp.getNext() == null) {
System.out.println("已经到链表最后");
break;
}
if(temp.getNext().getNo() == no) {
//找到了temp节点的下一个节点与no相同
flag = true;
break;
}
temp = temp.getNext();
}
if(flag) {
//删除节点
temp.setNext(temp.getNext().getNext());
}
}
单链表面试题
找到单链表节点的有效个数
//找到节点的有效个数（如果是带head的链表，记得去除）
public int findHeroNodeNum(HeroNode head) {
if(head.getNext() == null) {
return 0;
}
int count = 0;
HeroNode temp = head.getNext();
while (true) {
if(temp != null) {
count++;
temp = temp.getNext();
} else {
break;
}
}
return count;
}
查找单链表中倒数第K个节点
public HeroNode findLastIndexHeroNode(HeroNode head, int index) {
int size = findHeroNodeNum(head);
if(index < 0 || index > size) {
System.out.println("索引越界了");
return null;
}
HeroNode temp = head.getNext();
for (int i = 0; i < size - index ; i++) {
temp = temp.getNext();
}
return temp;
}
单链表的反转
//反转单链表
public void reverseHeroNode(HeroNode head) {
if(head.getNext() == null || head.getNext().getNext() == null) {
return;
}
HeroNode cur = head.getNext();//指向当前节点
HeroNode next = null;//指向当前节点的下一个节点
HeroNode tempHead = new HeroNode(0,"","");//定义一个临时的头节点
while (cur != null) {
next = cur.getNext();//暂时先保存当前节点的下一个节点
cur.setNext(tempHead.getNext());//将当前节点指向链表最前端
tempHead.setNext(cur);//将当前节点连接到新链表上
cur = next;//让当前节点后移
}
head.setNext(tempHead.getNext());
}
从尾到头打印单链表
方式1:先将单链表反转，再遍历即可
-
方式2:可以使用栈结构的先入后出的特点来完成
//利用栈逆序打印单链表数据 public void reversePrint(HeroNode head) { if(head.getNext() == null) { System.out.println("数据为空"); return; } Stack<HeroNode> stack = new Stack<>(); HeroNode temp = head.getNext(); while (temp != null) { stack.push(temp); temp = temp.getNext(); } while (stack.size() != 0) { System.out.println(stack.pop()); } }合并两个有序的单链表、合并之后单链表还是有序状态
递归方式
public static HeroNode mergeTwoHeroNode(HeroNode first, HeroNode second) { HeroNode finalNode = new HeroNode(0, "", ""); if(first.getNext() == null && second.getNext() == null) { return null; } if(first.getNext() == null) { return second; } if(second.getNext() == null) { return first; } if(first.getNo() > second.getNo()) { finalNode = second; finalNode.setNext(mergeTwoHeroNode(first, second.getNext())); } else { finalNode = first; finalNode.setNext(mergeTwoHeroNode(first.getNext(), second)); } return finalNode; }非递归方式
public static ListNode mergeTwoLists(ListNode head1, ListNode head2) { if (head1 == null || head2 == null) { return head1 == null ? head2 : head1; } ListNode head = head1.val <= head2.val ? head1 : head2; ListNode cur1 = head.next; ListNode cur2 = head == head1 ? head2 : head1; ListNode pre = head; while (cur1 != null && cur2 != null) { if (cur1.val <= cur2.val) { pre.next = cur1; cur1 = cur1.next; } else { pre.next = cur2; cur2 = cur2.next; } pre = pre.next; } pre.next = cur1 != null ? cur1 : cur2; return head; }双向链表
图示
实现思路
遍历
和单向链表的遍历相同，需要一个辅助节点来保存当前正在遍历的节点
-
添加
默认添加到双向链表的最后
先找到双向链表的最后这个节点
temp.next = newHeroNode;-
随机插入
先找到要插入节点的前一个位置 temp
- 要插入的节点为 newHeroNode
newHeroNode.pre = temp;newHeroNode.next = temp.next;temp.next.pre = newHeroNode;temp.next = newHeroNode;-
修改
-
删除
因为是双向链表，因此，我们可以实现自我删除某个节点
- 直接找到要删除的这个节点，比如temp
temp.pre.next = temp.next;temp.next.pre = temp.pre;//如果temp是最后一个节点，则不需要执行代码实现
```java package com.foreign.doubleChain;
/**
- @author fangke
- @Description:
- @Package
- @date: 2022/4/18 10:10 上午
*/ public class DoubleLinkedListDemo { public static void main(String[] args) {
DoubleLinkedList list = new DoubleLinkedList(); HeroNode node1 = new HeroNode(1, "宋江", "及时雨"); HeroNode node2 = new HeroNode(2, "林冲", "豹子头"); HeroNode node3 = new HeroNode(3, "鲁智深", "花和尚"); HeroNode node4 = new HeroNode(4, "张三", "我也不知道"); list.addHeroNode(node1); list.addHeroNode(node2); list.addHeroNode(node3); list.addHeroNode(node4); list.listHeroNode(); list.print(); list.deleteHeroNode(3); list.listHeroNode(); list.print(); HeroNode node5 = new HeroNode(2,"林冲2","林冲22"); list.addHeroNodeByOrder(node5); list.listHeroNode(); list.print();} }
class DoubleLinkedList { HeroNode head = new HeroNode(0, “”, “”);
public void addHeroNode(HeroNode node) {
HeroNode temp = head;
while (temp.getNext() != null) {
temp = temp.getNext();
}
temp.setNext(node);
node.setPre(temp);
}
public void updateHeroNode(HeroNode node) {
if (head.getNext() == null) {
System.out.println("节点为空");
return;
}
HeroNode temp = head.getNext();
Boolean flag = false;
while (true) {
if (temp == null) { //此时到链表的结尾了
System.out.println("没有找到要修改的节点");
break;
}
if (temp.getNo() == node.getNo()) {
flag = true;
break;
}
temp = temp.getNext();
}
if (flag) {
temp.setName(node.getName());
temp.setNickName(node.getNickName());
} else {
System.out.println("没有找到要修改的英雄节点");
}
}
public void deleteHeroNode(int no) {
if (head.getNext() == null) {
System.out.println("无节点可以删除");
return;
}
HeroNode temp = head;
Boolean flag = false;
while (true) {
if (temp.getNext() == null) {
System.out.println("已经到链表最后");
break;
}
if (temp.getNext().getNo() == no) {
//找到了temp节点的下一个节点与no相同
flag = true;
break;
}
temp = temp.getNext();
}
if (flag) {
//删除节点
temp.getPre().setNext(temp.getNext());
if(temp.getNext() != null) {
temp.getNext().setPre(temp.getPre());
}
}
}
public void listHeroNode() {
while (head.getNext() == null) {
System.out.println("链表为空");
}
HeroNode temp = head;
while (true) {
if (temp == null) {
break;
}
System.out.println(temp);
temp = temp.getNext();
}
}
public void addHeroNodeByOrder(HeroNode node) {
HeroNode temp = head.getNext();
Boolean flag = false; //是否有重复的节点
while (true) {
//到末尾了
if (temp == null) {
break;
}
//节点重复了
if (temp.getNo() == node.getNo()) {
flag = true;
break;
}
//找到了第一个大于要插入节点的temp
if (temp.getNo() > node.getNo()) {
break;
}
temp = temp.getNext();
}
if (flag) {
System.out.println("节点重复了");
} else {
temp = temp.getPre(); //回到要插入节点的上一个节点
node.setPre(temp);
node.setNext(temp.getNext());
temp.getNext().setPre(node);
temp.setNext(node);
}
}
public void print() {
System.out.println("-----------------------");
}
}
class HeroNode { private int no; private String name; private String nickName; private HeroNode next; private HeroNode pre;
public HeroNode(int no, String name, String nickName) {
this.no = no;
this.name = name;
this.nickName = nickName;
}
@Override
public String toString() {
return "HeroNode{" +
"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;
}
public HeroNode getNext() {
return next;
}
public void setNext(HeroNode next) {
this.next = next;
}
public HeroNode getPre() {
return pre;
}
public void setPre(HeroNode pre) {
this.pre = pre;
}
}
<a name="R5FcV"></a>
# 单向环形链表
<a name="RYAtm"></a>
## 应用场景
<a name="lRDly"></a>
## Josephu问题
<a name="NsmX9"></a>
## 创建环形链表
<a name="MDRSt"></a>
### 
<a name="J2s3S"></a>
## 约瑟夫问题实现
<a name="HZjKy"></a>
## 代码实现
<a name="XZqFH"></a>
### 创建环形链表
```java
package com.foreign.josepfu;
/**
* @author fangke
* @Description:
* @Package
* @date: 2022/4/20 2:13 下午
* <p>
*/
public class Josepfu {
public static void main(String[] args) {
CycleSingleLinkedList boy = new CycleSingleLinkedList();
boy.add(5);
boy.list();
System.out.println("---");
boy.outer(1,2,5);
}
}
class CycleSingleLinkedList {
Boy first = null;
//创建一个当前节点curBoy
Boy curBoy = null;
//创建环形单向链表
public void add(int num) {
Boy boy;
for (int i = 1; i <= num; i++) {
boy = new Boy(i);
if(i == 1) {
first = boy;//first不动
first.setNext(first);//构成环
curBoy = first;//指向第一个小孩
} else {
curBoy.setNext(boy);
boy.setNext(first);//构成环
curBoy = boy;//指向最新加入的小孩
}
}
}
//遍历环形链表
public void list() {
if(first == null) {
return;
}
Boy curBoy = first;
while (true) {
System.out.println(curBoy.getNo());
if(curBoy.getNext() == first) {
break;
}
curBoy = curBoy.getNext();
}
}
//约瑟夫问题：按顺序出圈
//startNo:开始出圈的位置
//countNo:每次数几次
//total:总共的小孩数
public void outer(int startNo, int countNo, int total) {
if(startNo < 0 || countNo > total) {
return;
}
Boy helper = first;
//先让helper到环形链表的最后
while (true) {
if(helper.getNext() == first) {
break;
}
helper = helper.getNext();
}
//计算出helper指针
for (int i = 0; i < startNo - 1; i++) {
helper = helper.getNext();
first = first.getNext();
}
//出圈操作
while (true) {
//到达最后一个节点
if(helper == first) {
break;
}
//每次走几步
for (int i = 0; i < countNo -1; i++) {
helper = helper.getNext();
first = first.getNext();
}
System.out.println(first.getNo());
first = first.getNext();
helper.setNext(first);
}
//出最后一个节点
System.out.println(helper.getNo());
}
}
class Boy {
private int no;
private Boy next;
public Boy(int no) {
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}
栈
栈的介绍
- 栈的英文为stack
- 栈是一个先入后出的有序列表
- 栈是限制线性表中插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底。
根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。
图解出栈和入栈
-
栈的应用场景
子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，知道子程序执行完后再将地址取出，以回到原来的程序中。
- 处理递归调用：和子程序类似，只是除了存储下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
- 表达式的转换[中缀表达式转后缀表达式]与求值。
- 二叉树的遍历。
-
栈的快速入门
用数组模拟栈的使用，由于栈是一种有序列表，当然可以使用数组的结构来存储栈的数据内容，下面用数组模拟栈的出栈、入栈等操作。
图解
-
代码实现
```java package com.foreign.stack;
/**
- @author fangke
- @Description:
- @Package
- @date: 2022/4/21 10:38 上午
*/ public class StackDemo { public static void main(String[] args) {
} }ArrayStack stack = new ArrayStack(5); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); stack.list(); // stack.push(6); // stack.list(); stack.pop(); stack.pop(); stack.pop(); stack.pop(); stack.list();
class ArrayStack { private int maxSize;//栈的大小 private int[] value;//存放数据的数组 private int top = -1;//表示栈顶，初始为-1
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
this.value = new int[maxSize];
}
//判断栈满
public boolean isFull() {
if (maxSize - 1 == top) {
return true;
}
return false;
}
//判断栈空
public boolean isEmpty() {
if(top == -1) {
return true;
}
return false;
}
//出栈
public int pop() {
if(isEmpty()) {
throw new RuntimeException("栈为空");
}
int num = value[top];
top--;
return num;
}
//入栈
public void push(int num) {
if(isFull()) {
throw new RuntimeException("栈满了");
}
top++;
value[top] = num;
}
//查看栈的元素
public void list() {
if(isEmpty()) {
throw new RuntimeException("栈为空");
}
for (int i = top; i >= 0; i--) {
System.out.println(value[i]);
}
}
}
<a name="K7YXs"></a>
## 栈实现综合计算器（中缀表达式）
<a name="DHA8B"></a>
### 图解
<a name="kVyKb"></a>
### 代码实现
```java
package com.foreign.stack;
/**
* @author fangke
* @Description:
* @Package
* @date: 2022/4/26 1:45 下午
* <p>
*/
public class CalculatorDemo {
public static void main(String[] args) {
//假设要计算的数字为 3*2-9+1/3;
String expression = "3*2-2";
CalStack numStack = new CalStack(10);
CalStack operStack = new CalStack(10);
int index = 0; //指针遍历expression
char ch = ' '; //用来接收数据
int operCh = ' ';//用来接收弹出的操作符
int num1 = 0;
int num2 = 0;
int res = 0;
while (true) {
ch = expression.substring(index, index + 1).charAt(0);
//如果是操作符号
if(operStack.isOper(ch)) {
//如果operStack为null 或者 ch > operStack栈顶的符号 直接入栈
if(operStack.isEmpty() || operStack.priority(ch) > operStack.priority(operStack.peek())) {
operStack.push(ch);
} else {
//1、先弹出2个数，再弹出一个操作符号
num1 = numStack.pop();
num2 = numStack.pop();
operCh = operStack.pop();
res = operStack.cal(num1, num2, operCh);
//2、将结果入栈、将从expression取出的符号入栈
numStack.push(res);
operStack.push(ch);
}
} else {
//TODO 如果是多位数，则需要遍历到不为数字的数
numStack.push(ch - 48);
}
index++;
//到字符串的末尾了
if(index >= expression.length()) {
break;
}
}
while (true) {
//如果操作数栈为空，则结束循环 返回res
if(operStack.isEmpty()) {
break;
}
//1、先弹出2个数，再弹出一个操作符号
num1 = numStack.pop();
num2 = numStack.pop();
operCh = operStack.pop();
res = operStack.cal(num1, num2, operCh);
//2、将结果入栈、将从expression取出的符号入栈
numStack.push(res);
}
System.out.println(numStack.pop());
}
}
class CalStack {
private int maxSize;//栈的大小
private int[] value;//存放数据的数组
private int top = -1;//表示栈顶，初始为-1
//判断操作的优先级, 假设只有+-*/ 且数字越大代表操作优先级越高
public int priority(int oper) {
if (oper == '*' || oper == '/') {
return 1;
}
if (oper == '+' || oper == '-') {
return 0;
}
return -1;
}
//判断是数字还是运算符
public boolean isOper(int oper) {
if (oper == '+' || oper == '-' || oper == '*' || oper == '/') {
return true;
}
return false;
}
public int cal(int num1, int num2, int oper) {
int 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:
break;
}
return res;
}
public CalStack(int maxSize) {
this.maxSize = maxSize;
this.value = new int[maxSize];
}
//判断栈满
public boolean isFull() {
if (maxSize - 1 == top) {
return true;
}
return false;
}
//查看栈顶元素
public int peek() {
return value[top];
}
//判断栈空
public boolean isEmpty() {
if (top == -1) {
return true;
}
return false;
}
//出栈
public int pop() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
int num = value[top];
top--;
return num;
}
//入栈
public void push(int num) {
if (isFull()) {
throw new RuntimeException("栈满了");
}
top++;
value[top] = num;
}
//查看栈的元素
public void list() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
for (int i = top; i >= 0; i--) {
System.out.println(value[i]);
}
}
}
逆波兰计算器（后缀表达式）
- 输入一个逆波兰表达式，使用栈，计算其结果
- 支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算
思路分析
代码实现
```java package com.foreign.stack;
import java.util.ArrayList; import java.util.List; import java.util.Stack;
/**
- @author fangke
- @Description:
- @Package
- @date: 2022/4/27 10:19 上午
*/ public class PolandCalculator { public static void main(String[] args) {
} }//(3+4) * 5 - 6 String suffixExpression = "3 4 + 5 * 6 -"; Poland poland = new Poland(); int result = poland.getResult(suffixExpression); System.out.println(result);
class Poland {
public int getResult(String suffixExpression) {
String[] split = suffixExpression.split(“ “);
List
Stack<String> stack = new Stack();
for (String item : list) {
//匹配为数字
if (item.matches("\\d+")) {
stack.push(item);
} else {
int res=0;
int num1;
int num2;
switch (item) {
case "+":
num1 = Integer.parseInt(stack.pop());
num2 = Integer.parseInt(stack.pop());
res = num2 + num1;
break;
case "-":
num1 = Integer.parseInt(stack.pop());
num2 = Integer.parseInt(stack.pop());
res = num2 - num1;
break;
case "*":
num1 = Integer.parseInt(stack.pop());
num2 = Integer.parseInt(stack.pop());
res = num2 * num1;
break;
case "/":
num1 = Integer.parseInt(stack.pop());
num2 = Integer.parseInt(stack.pop());
res = num2 / num1;
break;
default:
break;
}
//将计算后的数字压栈
stack.push("" + res);
}
}
//全部运算完成，栈里面的数字就是结果
return Integer.parseInt(stack.pop());
}
}
<a name="tkQfD"></a>
## 中缀转后缀表达式
<a name="UpOIU"></a>
### 思路分析
<a name="TAAF6"></a>
### 代码实现
```java
/**
* @author Chen Panwen
* @data 2020/6/17 21:07
*/
public class Demo4 {
static Queue<String> queue = new LinkedList<>();
static Stack<String> stack = new Stack<>();
public static void main(String[] args) {
//中缀表达式，加上空格，方便取出
String infixExpression = "1 + ( ( 2 + 3 ) * 4 ) - 5";
String[] expressionArr = infixExpression.split(" ");
//用来保存该运算符的类型
int type;
//取出的字符串
String element;
//弹出栈的字符串
String stackEle;
for(int i=0; i<expressionArr.length; i++) {
element = expressionArr[i];
type = judgeOperator(element);
if(type == 0) {
//数字，直接入队
queue.add(element);
}else if(type == 1) {
//左括号，直接压栈
stack.push(element);
}else if(type == 3) {
//如果右括号，弹出栈顶元素，直到遇见左括号位置再停下来
do {
stackEle = stack.pop();
if(stackEle.equals("(")) {
break;
}
queue.add(stackEle);
//弹出栈中的左括号
}while (!stackEle.equals("("));
}else if(type == 2) {
if(stack.isEmpty()) {
//如果栈为空，直接入栈
stack.push(element);
continue;
}
int priority1 = getPriority(element);
//获得栈顶元素，并判断其优先级
stackEle = stack.peek();
int priority2 = getPriority(stackEle);
if(priority2 == 0) {
//为左括号，运算符直接入栈
stack.push(element);
}else if(priority1 > priority2) {
//该运算符优先级高于栈顶元素优先级，则入栈
stack.push(element);
}else {
stackEle = stack.pop();
queue.add(stackEle);
//重新判断该运算符
i--;
}
}
}
//把最后一个元素出栈并入队
stackEle = stack.pop();
queue.add(stackEle);
//保存队列长度，因为出队过程中队列的长度会被改变
int length = queue.size();
for(int i=0; i<length; i++) {
element = queue.remove();
System.out.print(element);
}
}
/**
* 判断该运算符是不是加减乘除
* @param operation 运算符
* @return true则该运算符为加减乘除
*/
public static boolean firstJudge(String operation) {
return operation.equals("*") || operation.equals("/") || operation.equals("+") || operation.equals("-");
}
/**
* 判断该字符串的类型
* @param operation 要判断的字符串
* @return 3->右括号 2->加减乘除运算符 1->左括号
*/
public static int judgeOperator(String operation) {
if(operation.equals(")")) {
return 3;
}
if(firstJudge(operation)) {
return 2;
}
if(operation.equals("(")) {
return 1;
} else {
return 0;
}
}
/**
* 判断运算符优先级
* @param operator 要判断的运算符
* @return 2代表乘除，1代表加减，0代表左括号
*/
public static int getPriority(String operator) {
if(operator.equals("*") || operator.equals("/")) {
return 2;
}else if(operator.equals("+") || operator.equals("-")) {
return 1;
} else {
return 0;
}
}
}
递归
迷宫问题
分析
- map表示地图
- i，j表示从地图的哪个位置开始出发（1，1）
- 如果小球能到map[6][5]位置，则说明通路找到
- 约定：当map[i][j]为0，表示该点没有走过，当为1表示墙，当为2表示通路可以走，当为3表示该点已经走过，但是走不通。
- 在走迷宫时，需要确定一个策略（方法）下->右->上->左，如果该点走不通，再回溯
代码实现
```java package com.foreign.maze;
/**
- @author fangke
- @Description: 迷宫问题
- @Package
- @date: 2022/5/6 3:00 下午
*/ public class MazeTest { public static void main(String[] args) {
int[][] maze = new int[8][7]; //设置左右的墙 for (int i = 0; i < 8; i++) { maze[i][0] = 1; maze[i][6] = 1; } //设置上下的墙 for (int i = 0; i < 7; i++) { maze[0][i] = 1; maze[7][i] = 1; } //设置中间的墙 maze[3][1] = 1; maze[3][2] = 1; //打印出墙 for (int i = 0; i < 8; i++) { for (int j = 0; j < 7; j++) { System.out.print(maze[i][j] + " "); } System.out.println(); } setWay(maze, 1,1); System.out.println("-----------------"); //打印走过的墙路线 for (int i = 0; i < 8; i++) { for (int j = 0; j < 7; j++) { System.out.print(maze[i][j] + " "); } System.out.println(); }}
/**
- @param maze 迷宫墙
- @param i 开始的位置i
- @param j 开始的位置j
- @return
*/
public static boolean setWay(int[][] maze, int i, int j) {
//假设maze[7][5]为迷宫的出口
if (maze[6][5] == 2) {
} else {return true;
} }//表示没有走过这条路 if (maze[i][j] == 0) { //假设maze[i][j]为开始的位置，并且假设为2 maze[i][j] = 2; //遵从下->右->上->左的方向走 if (setWay(maze, i + 1, j)) {//往下走 return true; } else if (setWay(maze, i, j + 1)) { //往右走 return true; } else if (setWay(maze, i - 1, j)) {//往上走 return true; } else if (setWay(maze, i, j - 1)) {//往左走 return true; } else { maze[i][j] = 3; //否则是死路 return false; } } else { //有可能为 1，2，3 return false; }
}
<a name="u68ID"></a>
### 总结
1. 小球得到的路径和程序员设置的找路策略有关
1. 如何找到最短路径？
<a name="NL4ig"></a>
## 八皇后问题（回溯算法）
在8*8的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法（92）
<a name="SICzY"></a>
### 分析
- 将第一个皇后放在第一行第一列
- 将第二个皇后放在第二行第一列，判断是否会和其他皇后相互攻击，若会相互攻击，则将其放到第三列、第四列…知道不会相互攻击为止
- 将第三个皇后放在第三行第一列，判断是否会和其他皇后相互攻击，若会相互攻击，则将其放到第三列、第四列…知道不会相互攻击为止，并**以此类推**，**在摆放的过程中，有可能会改动前面所放的皇后的位置**
- 当得到一个正确的解时，就会回溯到上一行，由此来找出第一个皇后在第一行第一列的所有解
- 再将第一个皇后放到第一行第二列，并重复以上四个步骤
- **注意**：
- 棋盘本身应该是用二维数组表示，但是因为皇后所在的行数是固定的，所以可以简化为用一个一维数组来表示。其中的值代表皇后所在的列
- 数组下标代表皇后所在行数，所以判断是否在同一行列斜线上时，只需要判断是否在同一列和同一斜线上即可
- 是否同列判断：值是否相同
- 是否同一斜线：行号-行号是否等于列号-列号，且**列号相减要取绝对值**
- 理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题，arr[8]={0,4,7,5,2,6,1,3} 此时，array 的**下标n 表示行数**，**value = array[n] 表示皇后所在的列数**，**(n+1)表示第几个皇后**。
- **下标n表示行数**，所以（n - i）表示的是两皇后所在的行数的差值。
- **value = array[n] 表示皇后所在的列数**，所以（array[n] - array[i]）表示的是两皇后所在的列数的差值。
- 我们用图来理解②式，圆圈表示皇后，此时我们比较两个黑圈的位置
- 因为（n - i）/（array[n] - array[i]）= 1，而且1 = tan 45°（即图中黄色线），
- 
<a name="du8dj"></a>
### 代码实现
```java
public class Demo3 {
/**
* 创建皇后所放位置的数组，数组的下标代表行号，数组中的值代表所在的列号
*/
static int sum = 0;
int max = 8;
int[] arr = new int[max];
public static void main(String[] args) {
Demo3 demo = new Demo3();
//放入第一个皇后，开始求后面的皇后
demo.check(0);
System.out.println("一共有"+sum+"种放法");
}
/**
* 打印数组元素
*/
public void print() {
for(int i = 0; i<arr.length; i++) {
System.out.print(arr[i] + " ");
}
sum++;
System.out.println();
}
/**
* 判断该位置的皇后与前面几个是否冲突
* @param position 需要判断的皇后的位置
* @return true代表冲突，false代表不冲突
*/
public boolean judge(int position) {
for(int i = 0; i<position; i++) {
//如果两个皇后在同一列或者同一斜线，就冲突
//因为数组下标代表行数，所以不会存在皇后在同一行
//所在行数-所在行数 如果等于 所在列数-所在列数，则两个皇后在同一斜线上
if(arr[i] == arr[position] || (position-i) == Math.abs(arr[position]-arr[i])) {
return true;
}
}
return false;
}
/**
* 检查该皇后应放的位置
* @param queen 要检查的皇后
*/
public void check(int queen) {
if(queen == max) {
//所有的皇后都放好了，打印并返回
print();
return;
}
//把皇后放在每一列上，看哪些不会和之前的冲突
for(int i = 0; i<max; i++) {
//把第queen+1个皇后放在第i列
arr[queen] = i;
if(!judge(queen)) {
//不冲突，就去放下一个皇后
check(queen+1);
}
}
}
}
排序
算法的时间复杂度
时间频度和时间复杂度
时间频度T(n)
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
时间复杂度O(n)
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
在T(n)=4n²-2n+2中，就有f(n)=n²，使得T（n)/f(n)的极限值为4，那么O(f(n))，也就是时间复杂度为O(n²)
- 对于不是只有常数的时间复杂度忽略时间频度的系数、低次项常数
- 对于只有常数的时间复杂度，将常数看为1
常见的时间复杂度
常数阶 O(1)
无论代码执行了多少行，只要没有循环等复杂的结构，时间复杂度都是O(1)int i = 1; i++;对数阶O(log2n)
此处i并不是依次递增到n，而是每次都以倍数增长。假设循环了x次后i大于n。则2x = n，x=log2nwhile(i<n) { i = i*2; }线性阶O(n)
这其中，循环体中的代码会执行n+1次，时间复杂度为O(n)for(int i = 0; i<n; i++) { i++; }线性对数阶O(nlog2n)
此处外部为一个循环，循环了n次。内部也是一个循环，但内部f循环的时间复杂度是log2nfor(int i = 0; i<n; i++) { j = 1; while(j<n) { j = j*2; } }
所以总体的时间复杂度为线性对数阶O(nlog2n)平方阶O(n2)
for(int i = 0; i<n; i++) { for(int j = 0; j<n; j++) { //循环体 } }立方阶O(n3)
可以看出平方阶、立方阶的复杂度主要是否循环嵌套了几层来决定的for(int i = 0; i<n; i++) { for(int j = 0; j<n; j++) { for(int k = 0; k<n; k++) { //循环体 } } }
排序算法的时间复杂度
| 排序算法 | 平均时间 | 最差时间 | 稳定性 | 空间复杂度 | 备注 | | —- | —- | —- | —- | —- | —- | | 冒泡排序 | O(n2) | O(n2) | 稳定 | O(1) | n较小时好 | | 交换排序 | O(n2) | O(n2) | 不稳定 | O(1) | n较小时好 | | 选择排序 | O(n2) | O(n2) | 不稳定 | O(1) | n较小时好 | | 插入排序 | O(n2) | O(n2) | 稳定 | O(1) | 大部分已有序时好 | | 基数排序 | O(nk) | O(nk) | 稳定 | O(n) | 二维数组（桶）、一维数组（桶中首元素的位置） | | 希尔排序 | O(nlogn) | O(ns)(1<s<2) | 不稳定 | O(1) | s是所选分组 | | 快速排序 | O(nlogn) | O(n2) | 不稳定 | O(logn) | n较大时好 | | 归并排序 | O(nlogn) | O(nlogn) | 稳定 | O(1) | n较大时好 | | 堆排序 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | n较大时好 |
冒泡排序
概念
对待排序序列从前向后，依次比较相邻元素的值，若发下逆序则交换，使值较大的元素逐渐从前移向后部。
因为排序过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行交换元素，就说明序列有序。因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。
图解
小结
- 一共进行数组大小-1次大的循环
- 每一趟排序的次数在逐渐减少
如果我们发现在某躺排序中，没有发送依次交换，可以提前结束冒泡排序，这个就是优化。
代码实现
基础写法
public class TestBubble { public static void main(String[] args) { int[] arr = {3, 9, -1, 10, 20}; //第一趟排序 int temp = 0; for (int j = 0; j < arr.length - 1 - 0; j++) { if(arr[j] > arr[j+1]) { temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } System.out.println(Arrays.toString(arr)); //第二趟排序 for (int j = 0; j < arr.length - 1 - 1; j++) { if(arr[j] > arr[j+1]) { temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } System.out.println(Arrays.toString(arr)); //第三趟排序 for (int j = 0; j < arr.length - 1 - 2; j++) { if(arr[j] > arr[j+1]) { temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } System.out.println(Arrays.toString(arr)); //第四趟排序 for (int j = 0; j < arr.length - 1 - 3; j++) { if(arr[j] > arr[j+1]) { temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } System.out.println(Arrays.toString(arr)); //总的来说 for (int i = 0; i < arr.length -1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if(arr[j] > arr[j+1]) { temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } } System.out.println(Arrays.toString(arr)); } }优化写法
boolean flag = false; //标识变量，表示是否进行过交换 //总的来说 for (int i = 0; i < arr.length -1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if(arr[j] > arr[j+1]) { temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; flag = true; } } if(flag) { flag = false;//重置flag，进行下次判断 } else { break; } } System.out.println(Arrays.toString(arr));
若有收获，就点个赞吧
0 人点赞
