silennn
请教一下c语言数组问题？是什么问题导致程序一会能行一会不行？
需求：实现将数组中所有元素调整为左右两部分，左边为奇数，右边为偶数。（c语言）
int main(){
int size;
printf("enter the size of arr:");
scanf("%d",&size);
int arr[size];
for(int i;i 需求：编制C/C++程序，利用顺序存储方式实现下列功能：从键盘输入数据建立一个线性表（整数），并输出该线性表；然后根据屏幕提示，进行数据的插入或删除等操作，并在插入或删除数据后输出线性表。
代码出现问题，无法运行，错误提醒是delete那块红了，估计是它出问题。
未知是什么原因，望指教。
typedef struct {
int data[MAX_SIZE];
int length;
} SeqList;
void init(SeqList *list) {
list->length = 0;
}
void insert(SeqList *list, int position, int value) {
if (position list->length || list->length == MAX_SIZE) {
printf("The insert position is invalid or the linear table is full:\n");
return;
}
for (int i = list->length - 1; i >= position; i--) {
list->data[i + 1] = list->data[i];
}
list->data[position] = value;
list->length++;
}
void delete(SeqList *list, int position) {
if (position = list->length) {
printf("Invalid delete location:\n");
return;
}
for (int i = position; i length - 1; i++) {
list->data[i] = list->data[i + 1];
}
list->length--;
}
void print(SeqList *list) {
printf("Linear table contents:");
for (int i = 0; i length; i++) {
printf("%d ", list->data[i]);
}
printf("\n");
}
int main() {
SeqList list;
init(&list);
printf("Please enter the length of the linear table:");
scanf("%d", &list.length);
if (list.length > MAX_SIZE) {
printf("The linear table length exceeds the maximum value:\n");
return 0;
}
printf("Enter the elements of the linear table:");
for (int i = 0; i < list.length; i++) {
scanf("%d", &list.data[i]);
}
print(&list);
int operation, position, value;
printf("\nplese select:\n"); printf("1. insect the data:\n");
printf("2. delete the data\n");
printf("0. exit\n");
while (1) {
printf("\nplease enter the ops:");
scanf("%d", &operation);
if (operation == 1) {
printf("Please enter insert position and insert value (separated by space)：");
scanf("%d %d", &position, &value);
insert(&list, position, value);
} else if (operation == 2) {
printf("Please enter the deletion location:");
scanf("%d", &position);
delete(&list, position);
} else if (operation == 0) {
break;
} else {
printf("Invalid operation number:\n");
}
print(&list);
}
return 0;
}
顺便提问一句我的DEVC++底下变成这样，应该怎么恢复到初始可以看见报错原因的状态？
"image.png" (https://wmprod.oss-cn-shanghai.aliyuncs.com/images/20241228/8f98052c1059aa39d58623656470276e.png)
菜鸟上路，万分感谢指教。 1 数组1) 概述定义在计算机科学中，数组是由一组元素（值或变量）组成的数据结构，每个元素有至少一个索引或键来标识In computer science, an array is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key因为数组内的元素是连续存储的，所以数组中元素的地址，可以通过其索引计算出来，例如：int[] array = {1,2,3,4,5}小测试byte[] array = {1,2,3,4,5}
已知 array 的数据的起始地址是 0x7138f94c8，那么元素 3 的地址是什么？答：0x7138f94c8 + 2 * 1 = 0x7138f94ca空间占用例如int[] array = {1, 2, 3, 4, 5};的大小为 40 个字节，组成如下8 + 4 + 4 + 5*4 + 4(alignment)随机访问性能即根据索引查找元素，时间复杂度是 O ( 1 ) O(1)O(1)2) 动态数组java 版本public class DynamicArray implements Iterable<Integer> {
private int size = 0; // 逻辑大小
private int capacity = 8; // 容量
private int[] array = {};
/**
* 向最后位置 [size] 添加元素
*
* @param element 待添加元素
*/
public void addLast(int element) {
add(size, element);
}
/**
* 向 [0 .. size] 位置添加元素
*
* @param index 索引位置
* @param element 待添加元素
*/
public void add(int index, int element) {
checkAndGrow();
// 添加逻辑
if (index >= 0 && index < size) {
// 向后挪动, 空出待插入位置
System.arraycopy(array, index,
array, index + 1, size - index);
}
array[index] = element;
size++;
}
private void checkAndGrow() {
// 容量检查
if (size == 0) {
array = new int[capacity];
} else if (size == capacity) {
// 进行扩容, 1.5 1.618 2
capacity += capacity >> 1;
int[] newArray = new int[capacity];
System.arraycopy(array, 0,
newArray, 0, size);
array = newArray;
}
}
/**
* 从 [0 .. size) 范围删除元素
*
* @param index 索引位置
* @return 被删除元素
*/
public int remove(int index) { // [0..size)
int removed = array[index];
if (index < size - 1) {
// 向前挪动
System.arraycopy(array, index + 1,
array, index, size - index - 1);
}
size--;
return removed;
}
/**
* 查询元素
*
* @param index 索引位置, 在 [0..size) 区间内
* @return 该索引位置的元素
*/
public int get(int index) {
return array[index];
}
/**
* 遍历方法1
*
* @param consumer 遍历要执行的操作, 入参: 每个元素
*/
public void foreach(Consumer<Integer> consumer) {
for (int i = 0; i < size; i++) {
// 提供 array[i]
// 返回 void
consumer.accept(array[i]);
}
}
/**
* 遍历方法2 - 迭代器遍历
*/
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
int i = 0;
@Override
public boolean hasNext() { // 有没有下一个元素
return i < size;
}
@Override
public Integer next() { // 返回当前元素,并移动到下一个元素
return array[i++];
}
};
}
/**
* 遍历方法3 - stream 遍历
*
* @return stream 流
*/
public IntStream stream() {
return IntStream.of(Arrays.copyOfRange(array, 0, size));
}
}这些方法实现，都简化了 index 的有效性判断，假设输入的 index 都是合法的插入或删除性能3) 二维数组int[][] array = {
{11, 12, 13, 14, 15},
{21, 22, 23, 24, 25},
{31, 32, 33, 34, 35},
};
内存图如下小测试Java 环境下（不考虑类指针和引用压缩，此为默认情况），有下面的二维数组byte[][] array = {
{11, 12, 13, 14, 15},
{21, 22, 23, 24, 25},
{31, 32, 33, 34, 35},
};已知 array 对象起始地址是 0x1000，那么 23 这个元素的地址是什么？答：起始地址 0x1000外层数组大小：16字节对象头 + 3元素 * 每个引用4字节 + 4 对齐字节 = 32 = 0x20第一个内层数组大小：16字节对象头 + 5元素 * 每个byte1字节 + 3 对齐字节 = 24 = 0x18第二个内层数组，16字节对象头 = 0x10，待查找元素索引为 2最后结果 = 0x1000 + 0x20 + 0x18 + 0x10 + 2*1 = 0x104a4) 局部性原理这里只讨论空间局部性cpu 读取内存（速度慢）数据后，会将其放入高速缓存（速度快）当中，如果后来的计算再用到此数据，在缓存中能读到的话，就不必读内存了缓存的最小存储单位是缓存行（cache line），一般是 64 bytes，一次读的数据少了不划算啊，因此最少读 64 bytes 填满一个缓存行，因此读入某个数据时也会读取其临近的数据，这就是所谓空间局部性对效率的影响比较下面 ij 和 ji 两个方法的执行效率int rows = 1000000;
int columns = 14;
int[][] a = new int[rows][columns];
StopWatch sw = new StopWatch();
sw.start("ij");
ij(a, rows, columns);
sw.stop();
sw.start("ji");
ji(a, rows, columns);
sw.stop();
System.out.println(sw.prettyPrint());ij 方法public static void ij(int[][] a, int rows, int columns) {
long sum = 0L;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
sum += a[i][j];
}
}
System.out.println(sum);
}ji 方法public static void ji(int[][] a, int rows, int columns) {
long sum = 0L;
for (int j = 0; j < columns; j++) {
for (int i = 0; i < rows; i++) {
sum += a[i][j];
}
}
System.out.println(sum);
}执行结果0
0
StopWatch '': running time = 96283300 ns
---------------------------------------------
ns % Task name
---------------------------------------------
016196200 017% ij
080087100 083% ji可以看到 ij 的效率比 ji 快很多，为什么呢？缓存是有限的，当新数据来了后，一些旧的缓存行数据就会被覆盖如果不能充分利用缓存的数据，就会造成效率低下举一反三I/O 读写时同样可以体现局部性原理数组可以充分利用局部性原理，那么链表呢？答：链表不行，因为链表的元素并非相邻存储5) 越界检查java 中对数组元素的读写都有越界检查，类似于下面的代码bool is_within_bounds(int index) const
{
return 0 <= index && index < length();
}代码位置：openjdk\src\hotspot\share\oops\arrayOop.hpp只不过此检查代码，不需要由程序员自己来调用，JVM 会帮我们调用练习E01. 合并有序数组 - 对应 Leetcode 88将数组内两个区间内的有序元素合并例[1, 5, 6, 2, 4, 10, 11]可以视作两个有序区间[1, 5, 6] 和 [2, 4, 10, 11]合并后，结果仍存储于原有空间[1, 2, 4, 5, 6, 10, 11]方法1递归每次递归把更小的元素复制到结果数组merge(left=[1,5,6],right=[2,4,10,11],a2=[]){
merge(left=[5,6],right=[2,4,10,11],a2=[1]){
merge(left=[5,6],right=[4,10,11],a2=[1,2]){
merge(left=[5,6],right=[10,11],a2=[1,2,4]){
merge(left=[6],right=[10,11],a2=[1,2,4,5]){
merge(left=[],right=[10,11],a2=[1,2,4,5,6]){
// 拷贝10，11
}
}
}
}
}
}代码public static void merge(int[] a1, int i, int iEnd, int j, int jEnd,
int[] a2, int k) {
if (i > iEnd) {
System.arraycopy(a1, j, a2, k, jEnd - j + 1);
return;
}
if (j > jEnd) {
System.arraycopy(a1, i, a2, k, iEnd - i + 1);
return;
}
if (a1[i] < a1[j]) {
a2[k] = a1[i];
merge(a1, i + 1, iEnd, j, jEnd, a2, k + 1);
} else {
a2[k] = a1[j];
merge(a1, i, iEnd, j + 1, jEnd, a2, k + 1);
}
}测试int[] a1 = {1, 5, 6, 2, 4, 10, 11};
int[] a2 = new int[a1.length];
merge(a1, 0, 2, 3, 6, a2, 0);方法2代码public static void merge(int[] a1, int i, int iEnd,
int j, int jEnd,
int[] a2) {
int k = i;
while (i <= iEnd && j <= jEnd) {
if (a1[i] < a1[j]) {
a2[k] = a1[i];
i++;
} else {
a2[k] = a1[j];
j++;
}
k++;
}
if (i > iEnd) {
System.arraycopy(a1, j, a2, k, jEnd - j + 1);
}
if (j > jEnd) {
System.arraycopy(a1, i, a2, k, iEnd - i + 1);
}
}测试int[] a1 = {1, 5, 6, 2, 4, 10, 11};
int[] a2 = new int[a3.length];
merge(a1, 0, 2, 3, 6, a2); 2.8 阻塞队列之前的队列在很多场景下都不能很好地工作，例如大部分场景要求分离向队列放入（生产者）、从队列拿出（消费者）两个角色、它们得由不同的线程来担当，而之前的实现根本没有考虑线程安全问题队列为空，那么在之前的实现里会返回 null，如果就是硬要拿到一个元素呢？只能不断循环尝试队列为满，那么再之前的实现里会返回 false，如果就是硬要塞入一个元素呢？只能不断循环尝试因此我们需要解决的问题有用锁保证线程安全用条件变量让等待非空线程与等待不满线程进入等待状态，而不是不断循环尝试，让 CPU 空转有同学对线程安全还没有足够的认识，下面举一个反例，两个线程都要执行入队操作（几乎在同一时刻）public class TestThreadUnsafe {
private final String[] array = new String[10];
private int tail = 0;
public void offer(String e) {
array[tail] = e;
tail++;
}
@Override
public String toString() {
return Arrays.toString(array);
}
public static void main(String[] args) {
TestThreadUnsafe queue = new TestThreadUnsafe();
new Thread(()-> queue.offer("e1"), "t1").start();
new Thread(()-> queue.offer("e2"), "t2").start();
}
}执行的时间序列如下，假设初始状态 tail = 0，在执行过程中由于 CPU 在两个线程之间切换，造成了指令交错线程1线程2说明array[tail]=e1线程1 向 tail 位置加入 e1 这个元素，但还没来得及执行 tail++array[tail]=e2线程2 向 tail 位置加入 e2 这个元素，覆盖掉了 e1tail++tail 自增为1tail++tail 自增为2最后状态 tail 为 2，数组为 [e2, null, null …]糟糕的是，由于指令交错的顺序不同，得到的结果不止以上一种，宏观上造成混乱的效果1) 单锁实现Java 中要防止代码段交错执行，需要使用锁，有两种选择synchronized 代码块，属于关键字级别提供锁保护，功能少ReentrantLock 类，功能丰富以 ReentrantLock 为例ReentrantLock lock = new ReentrantLock();
public void offer(String e) {
lock.lockInterruptibly();
try {
array[tail] = e;
tail++;
} finally {
lock.unlock();
}
}只要两个线程执行上段代码时，锁对象是同一个，就能保证 try 块内的代码的执行不会出现指令交错现象，即执行顺序只可能是下面两种情况之一线程1线程2说明lock.lockInterruptibly()t1对锁对象上锁array[tail]=e1lock.lockInterruptibly()即使 CPU 切换到线程2，但由于t1已经对该对象上锁，因此线程2卡在这儿进不去tail++切换回线程1 执行后续代码lock.unlock()线程1 解锁array[tail]=e2线程2 此时才能获得锁，执行它的代码tail++另一种情况是线程2 先获得锁，线程1 被挡在外面要明白保护的本质，本例中是保护的是 tail 位置读写的安全事情还没有完，上面的例子是队列还没有放满的情况，考虑下面的代码（这回锁同时保护了 tail 和 size 的读写安全）ReentrantLock lock = new ReentrantLock();
int size = 0;
public void offer(String e) {
lock.lockInterruptibly();
try {
if(isFull()) {
// 满了怎么办?
}
array[tail] = e;
tail++;
size++;
} finally {
lock.unlock();
}
}
private boolean isFull() {
return size == array.length;
}之前是返回 false 表示添加失败，前面分析过想达到这么一种效果：在队列满时，不是立刻返回，而是当前线程进入等待什么时候队列不满了，再唤醒这个等待的线程，从上次的代码处继续向下运行ReentrantLock 可以配合条件变量来实现，代码进化为ReentrantLock lock = new ReentrantLock();
Condition tailWaits = lock.newCondition(); // 条件变量
int size = 0;
public void offer(String e) {
lock.lockInterruptibly();
try {
while (isFull()) {
tailWaits.await(); // 当队列满时, 当前线程进入 tailWaits 等待
}
array[tail] = e;
tail++;
size++;
} finally {
lock.unlock();
}
}
private boolean isFull() {
return size == array.length;
}条件变量底层也是个队列，用来存储这些需要等待的线程，当队列满了，就会将 offer 线程加入条件队列，并暂时释放锁将来我们的队列如果不满了（由 poll 线程那边得知）可以调用 tailWaits.signal() 来唤醒 tailWaits 中首个等待的线程，被唤醒的线程会再次抢到锁，从上次 await 处继续向下运行思考为何要用 while 而不是 if，设队列容量是 3操作前offer(4)offer(5)poll()操作后[1 2 3]队列满，进入tailWaits 等待[1 2 3][1 2 3]取走 1，队列不满，唤醒线程[2 3][2 3]抢先获得锁，发现不满，放入 5[2 3 5][2 3 5]从上次等待处直接向下执行[2 3 5 ?]关键点：从 tailWaits 中唤醒的线程，会与新来的 offer 的线程争抢锁，谁能抢到是不一定的，如果后者先抢到，就会导致条件又发生变化这种情况称之为虚假唤醒，唤醒后应该重新检查条件，看是不是得重新进入等待最后的实现代码/**
* 单锁实现
* @param <E> 元素类型
*/
public class BlockingQueue1<E> implements BlockingQueue<E> {
private final E[] array;
private int head = 0;
private int tail = 0;
private int size = 0; // 元素个数
@SuppressWarnings("all")
public BlockingQueue1(int capacity) {
array = (E[]) new Object[capacity];
}
ReentrantLock lock = new ReentrantLock();
Condition tailWaits = lock.newCondition();
Condition headWaits = lock.newCondition();
@Override
public void offer(E e) throws InterruptedException {
lock.lockInterruptibly();
try {
while (isFull()) {
tailWaits.await();
}
array[tail] = e;
if (++tail == array.length) {
tail = 0;
}
size++;
headWaits.signal();
} finally {
lock.unlock();
}
}
@Override
public void offer(E e, long timeout) throws InterruptedException {
lock.lockInterruptibly();
try {
long t = TimeUnit.MILLISECONDS.toNanos(timeout);
while (isFull()) {
if (t <= 0) {
return;
}
t = tailWaits.awaitNanos(t);
}
array[tail] = e;
if (++tail == array.length) {
tail = 0;
}
size++;
headWaits.signal();
} finally {
lock.unlock();
}
}
@Override
public E poll() throws InterruptedException {
lock.lockInterruptibly();
try {
while (isEmpty()) {
headWaits.await();
}
E e = array[head];
array[head] = null; // help GC
if (++head == array.length) {
head = 0;
}
size--;
tailWaits.signal();
return e;
} finally {
lock.unlock();
}
}
private boolean isEmpty() {
return size == 0;
}
private boolean isFull() {
return size == array.length;
}
}public void offer(E e, long timeout) throws InterruptedException 是带超时的版本，可以只等待一段时间，而不是永久等下去，类似的 poll 也可以做带超时的版本，这个留给大家了注意JDK 中 BlockingQueue 接口的方法命名与我的示例有些差异方法 offer(E e) 是非阻塞的实现，阻塞实现方法为 put(E e)方法 poll() 是非阻塞的实现，阻塞实现方法为 take()2) 双锁实现单锁的缺点在于：生产和消费几乎是不冲突的，唯一冲突的是生产者和消费者它们有可能同时修改 size冲突的主要是生产者之间：多个 offer 线程修改 tail冲突的还有消费者之间：多个 poll 线程修改 head如果希望进一步提高性能，可以用两把锁一把锁保护 tail另一把锁保护 headReentrantLock headLock = new ReentrantLock(); // 保护 head 的锁
Condition headWaits = headLock.newCondition(); // 队列空时，需要等待的线程集合
ReentrantLock tailLock = new ReentrantLock(); // 保护 tail 的锁
Condition tailWaits = tailLock.newCondition(); // 队列满时，需要等待的线程集合先看看 offer 方法的初步实现@Override
public void offer(E e) throws InterruptedException {
tailLock.lockInterruptibly();
try {
// 队列满等待
while (isFull()) {
tailWaits.await();
}
// 不满则入队
array[tail] = e;
if (++tail == array.length) {
tail = 0;
}
// 修改 size （有问题）
size++;
} finally {
tailLock.unlock();
}
}上面代码的缺点是 size 并不受 tailLock 保护，tailLock 与 headLock 是两把不同的锁，并不能实现互斥的效果。因此，size 需要用下面的代码保证原子性AtomicInteger size = new AtomicInteger(0); // 保护 size 的原子变量
size.getAndIncrement(); // 自增
size.getAndDecrement(); // 自减代码修改为@Override
public void offer(E e) throws InterruptedException {
tailLock.lockInterruptibly();
try {
// 队列满等待
while (isFull()) {
tailWaits.await();
}
// 不满则入队
array[tail] = e;
if (++tail == array.length) {
tail = 0;
}
// 修改 size
size.getAndIncrement();
} finally {
tailLock.unlock();
}
}对称地，可以写出 poll 方法@Override
public E poll() throws InterruptedException {
E e;
headLock.lockInterruptibly();
try {
// 队列空等待
while (isEmpty()) {
headWaits.await();
}
// 不空则出队
e = array[head];
if (++head == array.length) {
head = 0;
}
// 修改 size
size.getAndDecrement();
} finally {
headLock.unlock();
}
return e;
}下面来看一个难题，就是如何通知 headWaits 和 tailWaits 中等待的线程，比如 poll 方法拿走一个元素，通知 tailWaits：我拿走一个，不满了噢，你们可以放了，因此代码改为@Override
public E poll() throws InterruptedException {
E e;
headLock.lockInterruptibly();
try {
// 队列空等待
while (isEmpty()) {
headWaits.await();
}
// 不空则出队
e = array[head];
if (++head == array.length) {
head = 0;
}
// 修改 size
size.getAndDecrement();
// 通知 tailWaits 不满（有问题）
tailWaits.signal();
} finally {
headLock.unlock();
}
return e;
}问题在于要使用这些条件变量的 await()， signal() 等方法需要先获得与之关联的锁，上面的代码若直接运行会出现以下错误java.lang.IllegalMonitorStateException那有同学说，加上锁不就行了吗，于是写出了下面的代码发现什么问题了？两把锁这么嵌套使用，非常容易出现死锁，如下所示因此得避免嵌套，两段加锁的代码变成了下面平级的样子性能还可以进一步提升代码调整后 offer 并没有同时获取 tailLock 和 headLock 两把锁，因此两次加锁之间会有空隙，这个空隙内可能有其它的 offer 线程添加了更多的元素，那么这些线程都要执行 signal()，通知 poll 线程队列非空吗？每次调用 signal() 都需要这些 offer 线程先获得 headLock 锁，成本较高，要想法减少 offer 线程获得 headLock 锁的次数可以加一个条件：当 offer 增加前队列为空，即从 0 变化到不空，才由此 offer 线程来通知 headWaits，其它情况不归它管2. 队列从 0 变化到不空，会唤醒一个等待的 poll 线程，这个线程被唤醒后，肯定能拿到 headLock 锁，因此它具备了唤醒 headWaits 上其它 poll 线程的先决条件。如果检查出此时有其它 offer 线程新增了元素（不空，但不是从0变化而来），那么不妨由此 poll 线程来唤醒其它 poll 线程这个技巧被称之为级联通知（cascading notifies），类似的原因3. 在 poll 时队列从满变化到不满，才由此 poll 线程来唤醒一个等待的 offer 线程，目的也是为了减少 poll 线程对 tailLock 上锁次数，剩下等待的 offer 线程由这个 offer 线程间接唤醒最终的代码为public class BlockingQueue2<E> implements BlockingQueue<E> {
private final E[] array;
private int head = 0;
private int tail = 0;
private final AtomicInteger size = new AtomicInteger(0);
ReentrantLock headLock = new ReentrantLock();
Condition headWaits = headLock.newCondition();
ReentrantLock tailLock = new ReentrantLock();
Condition tailWaits = tailLock.newCondition();
public BlockingQueue2(int capacity) {
this.array = (E[]) new Object[capacity];
}
@Override
public void offer(E e) throws InterruptedException {
int c;
tailLock.lockInterruptibly();
try {
while (isFull()) {
tailWaits.await();
}
array[tail] = e;
if (++tail == array.length) {
tail = 0;
}
c = size.getAndIncrement();
// a. 队列不满, 但不是从满->不满, 由此offer线程唤醒其它offer线程
if (c + 1 < array.length) {
tailWaits.signal();
}
} finally {
tailLock.unlock();
}
// b. 从0->不空, 由此offer线程唤醒等待的poll线程
if (c == 0) {
headLock.lock();
try {
headWaits.signal();
} finally {
headLock.unlock();
}
}
}
@Override
public E poll() throws InterruptedException {
E e;
int c;
headLock.lockInterruptibly();
try {
while (isEmpty()) {
headWaits.await();
}
e = array[head];
if (++head == array.length) {
head = 0;
}
c = size.getAndDecrement();
// b. 队列不空, 但不是从0变化到不空，由此poll线程通知其它poll线程
if (c > 1) {
headWaits.signal();
}
} finally {
headLock.unlock();
}
// a. 从满->不满, 由此poll线程唤醒等待的offer线程
if (c == array.length) {
tailLock.lock();
try {
tailWaits.signal();
} finally {
tailLock.unlock();
}
}
return e;
}
private boolean isEmpty() {
return size.get() == 0;
}
private boolean isFull() {
return size.get() == array.length;
}
}双锁实现的非常精巧，据说作者 Doug Lea 花了一年的时间才完善了此段代码 2.2 链表1) 概述定义在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next.可以分类为[^5]单向链表，每个元素只知道其下一个元素是谁双向链表，每个元素知道其上一个元素和下一个元素循环链表，通常的链表尾节点 tail 指向的都是 null，而循环链表的 tail 指向的是头节点 head链表内还有一种特殊的节点称为哨兵（Sentinel）节点，也叫做哑元（ Dummy）节点，它不存储数据，通常用作头尾，用来简化边界判断，如下图所示public class SinglyLinkedList {
private Node head; // 头部节点
private static class Node { // 节点类
int value;
Node next;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
}
Node 定义为内部类，是为了对外隐藏实现细节，没必要让类的使用者关心 Node 结构定义为 static 内部类，是因为 Node 不需要与 SinglyLinkedList 实例相关，多个 SinglyLinkedList实例能共用 Node 类定义头部添加public class SinglyLinkedList {
// ...
public void addFirst(int value) {
this.head = new Node(value, this.head);
}
}如果 this.head == null，新增节点指向 null，并作为新的 this.head如果 this.head != null，新增节点指向原来的 this.head，并作为新的 this.headwhile 遍历public class SinglyLinkedList {
// ...
public void loop() {
Node curr = this.head;
while (curr != null) {
// 做一些事
curr = curr.next;
}
}
}for 遍历public class SinglyLinkedList {
// ...
public void loop() {
for (Node curr = this.head; curr != null; curr = curr.next) {
// 做一些事
}
}
}以上两种遍历都可以把要做的事以 Consumer 函数的方式传递进来Consumer 的规则是一个参数，无返回值，因此像 System.out::println 方法等都是 Consumer调用 Consumer 时，将当前节点 curr.value 作为参数传递给它迭代器遍历public class SinglyLinkedList implements Iterable<Integer> {
// ...
private class NodeIterator implements Iterator<Integer> {
Node curr = head;
public boolean hasNext() {
return curr != null;
}
public Integer next() {
int value = curr.value;
curr = curr.next;
return value;
}
}
public Iterator<Integer> iterator() {
return new NodeIterator();
}
}hasNext 用来判断是否还有必要调用 nextnext 做两件事返回当前节点的 value指向下一个节点NodeIterator 要定义为非 static 内部类，是因为它与 SinglyLinkedList 实例相关，是对某个 SinglyLinkedList 实例的迭代递归遍历public class SinglyLinkedList implements Iterable<Integer> {
// ...
public void loop() {
recursion(this.head);
}
private void recursion(Node curr) {
if (curr == null) {
return;
}
// 前面做些事
recursion(curr.next);
// 后面做些事
}
}尾部添加public class SinglyLinkedList {
// ...
private Node findLast() {
if (this.head == null) {
return null;
}
Node curr;
for (curr = this.head; curr.next != null; ) {
curr = curr.next;
}
return curr;
}
public void addLast(int value) {
Node last = findLast();
if (last == null) {
addFirst(value);
return;
}
last.next = new Node(value, null);
}
}注意，找最后一个节点，终止条件是 curr.next == null分成两个方法是为了代码清晰，而且 findLast() 之后还能复用尾部添加多个public class SinglyLinkedList {
// ...
public void addLast(int first, int... rest) {
Node sublist = new Node(first, null);
Node curr = sublist;
for (int value : rest) {
curr.next = new Node(value, null);
curr = curr.next;
}
Node last = findLast();
if (last == null) {
this.head = sublist;
return;
}
last.next = sublist;
}
}先串成一串 sublist再作为一个整体添加根据索引获取public class SinglyLinkedList {
// ...
private Node findNode(int index) {
int i = 0;
for (Node curr = this.head; curr != null; curr = curr.next, i++) {
if (index == i) {
return curr;
}
}
return null;
}
private IllegalArgumentException illegalIndex(int index) {
return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
}
public int get(int index) {
Node node = findNode(index);
if (node != null) {
return node.value;
}
throw illegalIndex(index);
}
}同样，分方法可以实现复用插入public class SinglyLinkedList {
// ...
public void insert(int index, int value) {
if (index == 0) {
addFirst(value);
return;
}
Node prev = findNode(index - 1); // 找到上一个节点
if (prev == null) { // 找不到
throw illegalIndex(index);
}
prev.next = new Node(value, prev.next);
}
}插入包括下面的删除，都必须找到上一个节点删除public class SinglyLinkedList {
// ...
public void remove(int index) {
if (index == 0) {
if (this.head != null) {
this.head = this.head.next;
return;
} else {
throw illegalIndex(index);
}
}
Node prev = findNode(index - 1);
Node curr;
if (prev != null && (curr = prev.next) != null) {
prev.next = curr.next;
} else {
throw illegalIndex(index);
}
}
}第一个 if 块对应着 removeFirst 情况最后一个 if 块对应着至少得两个节点的情况不仅仅判断上一个节点非空，还要保证当前节点非空3) 单向链表（带哨兵）观察之前单向链表的实现，发现每个方法内几乎都有判断是不是 head 这样的代码，能不能简化呢？用一个不参与数据存储的特殊 Node 作为哨兵，它一般被称为哨兵或哑元，拥有哨兵节点的链表称为带头链表public class SinglyLinkedListSentinel {
// ...
private Node head = new Node(Integer.MIN_VALUE, null);
}具体存什么值无所谓，因为不会用到它的值加入哨兵节点后，代码会变得比较简单，先看几个工具方法public class SinglyLinkedListSentinel {
// ...
// 根据索引获取节点
private Node findNode(int index) {
int i = -1;
for (Node curr = this.head; curr != null; curr = curr.next, i++) {
if (i == index) {
return curr;
}
}
return null;
}
// 获取最后一个节点
private Node findLast() {
Node curr;
for (curr = this.head; curr.next != null; ) {
curr = curr.next;
}
return curr;
}
}findNode 与之前类似，只是 i 初始值设置为 -1 对应哨兵，实际传入的 index 也是 [ − 1 , ∞ ) findLast 绝不会返回 null 了，就算没有其它节点，也会返回哨兵作为最后一个节点这样，代码简化为public class SinglyLinkedListSentinel {
// ...
public void addLast(int value) {
Node last = findLast();
/*
改动前
if (last == null) {
this.head = new Node(value, null);
return;
}
*/
last.next = new Node(value, null);
}
public void insert(int index, int value) {
/*
改动前
if (index == 0) {
this.head = new Node(value, this.head);
return;
}
*/
// index 传入 0 时，返回的是哨兵
Node prev = findNode(index - 1);
if (prev != null) {
prev.next = new Node(value, prev.next);
} else {
throw illegalIndex(index);
}
}
public void remove(int index) {
/*
改动前
if (index == 0) {
if (this.head != null) {
this.head = this.head.next;
return;
} else {
throw illegalIndex(index);
}
}
*/
// index 传入 0 时，返回的是哨兵
Node prev = findNode(index - 1);
Node curr;
if (prev != null && (curr = prev.next) != null) {
prev.next = curr.next;
} else {
throw illegalIndex(index);
}
}
public void addFirst(int value) {
/*
改动前
this.head = new Node(value, this.head);
*/
this.head.next = new Node(value, this.head.next);
// 也可以视为 insert 的特例, 即 insert(0, value);
}
}对于删除，前面说了【最后一个 if 块对应着至少得两个节点的情况】，现在有了哨兵，就凑足了两个节点4) 双向链表（带哨兵）public class DoublyLinkedListSentinel implements Iterable<Integer> {
private final Node head;
private final Node tail;
public DoublyLinkedListSentinel() {
head = new Node(null, 666, null);
tail = new Node(null, 888, null);
head.next = tail;
tail.prev = head;
}
private Node findNode(int index) {
int i = -1;
for (Node p = head; p != tail; p = p.next, i++) {
if (i == index) {
return p;
}
}
return null;
}
public void addFirst(int value) {
insert(0, value);
}
public void removeFirst() {
remove(0);
}
public void addLast(int value) {
Node prev = tail.prev;
Node added = new Node(prev, value, tail);
prev.next = added;
tail.prev = added;
}
public void removeLast() {
Node removed = tail.prev;
if (removed == head) {
throw illegalIndex(0);
}
Node prev = removed.prev;
prev.next = tail;
tail.prev = prev;
}
public void insert(int index, int value) {
Node prev = findNode(index - 1);
if (prev == null) {
throw illegalIndex(index);
}
Node next = prev.next;
Node inserted = new Node(prev, value, next);
prev.next = inserted;
next.prev = inserted;
}
public void remove(int index) {
Node prev = findNode(index - 1);
if (prev == null) {
throw illegalIndex(index);
}
Node removed = prev.next;
if (removed == tail) {
throw illegalIndex(index);
}
Node next = removed.next;
prev.next = next;
next.prev = prev;
}
private IllegalArgumentException illegalIndex(int index) {
return new IllegalArgumentException(
String.format("index [%d] 不合法%n", index));
}
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
Node p = head.next;
@Override
public boolean hasNext() {
return p != tail;
}
@Override
public Integer next() {
int value = p.value;
p = p.next;
return value;
}
};
}
static class Node {
Node prev;
int value;
Node next;
public Node(Node prev, int value, Node next) {
this.prev = prev;
this.value = value;
this.next = next;
}
}
}5) 环形链表（带哨兵）双向环形链表带哨兵，这时哨兵既作为头，也作为尾参考实现public class DoublyLinkedListSentinel implements Iterable<Integer> {
@Override
public Iterator<Integer> iterator() {
return new Iterator<>() {
Node p = sentinel.next;
@Override
public boolean hasNext() {
return p != sentinel;
}
@Override
public Integer next() {
int value = p.value;
p = p.next;
return value;
}
};
}
static class Node {
Node prev;
int value;
Node next;
public Node(Node prev, int value, Node next) {
this.prev = prev;
this.value = value;
this.next = next;
}
}
private final Node sentinel = new Node(null, -1, null); // 哨兵
public DoublyLinkedListSentinel() {
sentinel.next = sentinel;
sentinel.prev = sentinel;
}
/**
* 添加到第一个
* @param value 待添加值
*/
public void addFirst(int value) {
Node next = sentinel.next;
Node prev = sentinel;
Node added = new Node(prev, value, next);
prev.next = added;
next.prev = added;
}
/**
* 添加到最后一个
* @param value 待添加值
*/
public void addLast(int value) {
Node prev = sentinel.prev;
Node next = sentinel;
Node added = new Node(prev, value, next);
prev.next = added;
next.prev = added;
}
/**
* 删除第一个
*/
public void removeFirst() {
Node removed = sentinel.next;
if (removed == sentinel) {
throw new IllegalArgumentException("非法");
}
Node a = sentinel;
Node b = removed.next;
a.next = b;
b.prev = a;
}
/**
* 删除最后一个
*/
public void removeLast() {
Node removed = sentinel.prev;
if (removed == sentinel) {
throw new IllegalArgumentException("非法");
}
Node a = removed.prev;
Node b = sentinel;
a.next = b;
b.prev = a;
}
/**
* 根据值删除节点
* <p>假定 value 在链表中作为 key, 有唯一性</p>
* @param value 待删除值
*/
public void removeByValue(int value) {
Node removed = findNodeByValue(value);
if (removed != null) {
Node prev = removed.prev;
Node next = removed.next;
prev.next = next;
next.prev = prev;
}
}
private Node findNodeByValue(int value) {
Node p = sentinel.next;
while (p != sentinel) {
if (p.value == value) {
return p;
}
p = p.next;
}
return null;
}
} 一. 初识算法1.1 什么是算法？定义在数学和计算机科学领域，算法是一系列有限的严谨指令，通常用于解决一类特定问题或执行计算In mathematics and computer science, an algorithm (/ˈælɡərɪðəm/) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation.[^1]Introduction to Algorithm[^2]不正式的说，算法就是任何定义优良的计算过程：接收一些值作为输入，在有限的时间内，产生一些值作为输出。Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output in a finite amount of time.1.2 什么是数据结构？定义在计算机科学领域，数据结构是一种数据组织、管理和存储格式，通常被选择用来高效访问数据In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to dataIntroduction to Algorithm[^2]数据结构是一种存储和组织数据的方式，旨在便于访问和修改A data structure is a way to store and organize data in order to facilitate access and modifications可以说，程序 = 数据结构 + 算法，它们是每一位程序员的基本功，下来我们通过对一个非常著名的二分查找算法的讲解来认识一下算法1.3 二分查找 [^3]二分查找算法也称折半查找，是一种非常高效的工作于有序数组的查找算法。后续的课程中还会学习更多的查找算法，但在此之前，不妨用它作为入门。1) 基础版需求：在有序数组 A AA 内，查找值 t a r g e t targettarget如果找到返回索引如果找不到返回 − 1 -1−1算法描述前提给定一个内含 n 个元素的有序数组 A，满足 A0≤A1≤A2≤⋯≤An−1，一个待查target1设置 i=0，j=n−12如果 i>j，结束查找，没找到3设置 m = m=floor(i+j/2) ，m 为中间索引，floor 是向下取整（≤2i+j 的最小整数）4如果 target<Am 设置 j=m−1，跳到第2步5如果 Am<target 设置 i=m+1，跳到第2步6如果 Am=target，结束查找，找到了P.S.对于一个算法来讲，都有较为严谨的描述，上面是一个例子后续讲解时，以简明直白为目标，不会总以上面的方式来描述算法java 实现public static int binarySearch(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) { // 在左边
j = m - 1;
} else if (a[m] < target) { // 在右边
i = m + 1;
} else {
return m;
}
}
return -1;
}
i , j 对应着搜索区间 [0,a.length−1]（注意是闭合的区间），i < = j 意味着搜索区间内还有未比较的元素，i , j 指向的元素也可能是比较的目标m 对应着中间位置，中间位置左边和右边的元素可能不相等（差一个），不会影响结果如果某次未找到，那么缩小后的区间内不包含 m 2) 改变版另一种写法public static int binarySearch(int[] a, int target) {
int i = 0, j = a.length;
while (i < j) {
int m = (i + j) >>> 1;
if (target < a[m]) { // 在左边
j = m;
} else if (a[m] < target) { // 在右边
i = m + 1;
} else {
return m;
}
}
return -1;
}
i , j i对应着搜索区间 [[0,a.length)（注意是左闭右开的区间），i < j 意味着搜索区间内还有未比较的元素，j 指向的一定不是查找目标思考：为啥这次不加i==j 的条件了？回答：这回j指向的不是查找目标，如果还加i条件，就意味着j指向的还会再次比较，找不到时，会死循环如果某次要缩小右边界，那么 j = m，因为此时的 m 已经不是查找目标了1.4 衡量算法好坏时间复杂度下面的查找算法也能得出与之前二分查找一样的结果，那你能说出它差在哪里吗？public static int search(int[] a, int k) {
for (
int i = 0;
i < a.length;
i++
) {
if (a[i] == k) {
return i;
}
}
return -1;
}
考虑最坏情况下（没找到）例如 [1,2,3,4] 查找 5int i = 0 只执行一次i < a.length 受数组元素个数 n 的影响，比较 n + 1 次i++ 受数组元素个数 n 的影响，自增 n 次a[i] == k 受元素个数 n 的影响，比较 n 次return -1，执行一次粗略认为每行代码执行时间是 t tt，假设 n = 4 那么总执行时间是(1+4+1+4+4+1)∗t=15t可以推导出更一般地公式为，T=(3∗n+3)t如果套用二分查找算法，还是 [1,2,3,4] 查找 5public static int binarySearch(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) { // 在左边
j = m - 1;
} else if (a[m] < target) { // 在右边
i = m + 1;
} else {
return m;
}
}
return -1;
}
int i = 0, j = a.length - 1 各执行 1 次i <= j 比较floor(log2(n)+1) 再加 1 次(i + j) >>> 1 计算 floor(log2(n)+1) 次接下来 if() else if() else 会执行 3∗floor(log2(n)+1) 次，分别为if 比较else if 比较else if 比较成立后的赋值语句return -1，执行一次结果：总执行时间为 (2+(1+3)+3+3∗3+1)∗t=19t更一般地公式为(4+5∗floor(log2(n)+1))∗t注意：左侧未找到和右侧未找到结果不一样，这里不做分析两个算法比较，可以看到 n 在较小的时候，二者花费的次数差不多但随着 n 越来越大，比如说 n=1000 时，用二分查找算法（红色）也就是 54t ，而蓝色算法则需要 3003t画图采用的是 Desmos | 图形计算器计算机科学中，时间复杂度是用来衡量：一个算法的执行，随数据规模增大，而增长的时间成本不依赖于环境因素如何表示时间复杂度呢？假设算法要处理的数据规模是 n ，代码总的执行行数用函数 f ( n ) 来表示，例如：线性查找算法的函数f(n)=3∗n+3二分查找算法的函数f(n)=(floor(log2(n))+1)∗5+4为了对 f ( n ) 进行化简，应当抓住主要矛盾，找到一个变化趋势与之相近的表示法大 O 表示法[^4]其中c,c1,c2 都为一个常数f ( n ) 是实际执行代码行数与 n 的函数g ( n ) 是经过化简，变化趋势与 f ( n ) 一致的 n 的函数渐进上界渐进上界（asymptotic upper bound）：从某个常数 n0开始，c∗g(n) 总是位于 f(n) 上方，那么记作O(g(n))代表算法执行的最差情况例1f(n)=3∗n+3g(n)=n取 c = 4，在n0 = 3之后，g(n) 可以作为f(n) 的渐进上界，因此表示法写作 O(n)例2f(n)=5∗floor(log2(n))+9g(n)=log2(n)O(log2(n))已知 f ( n ) f(n)f(n) 来说，求g(n)表达式中相乘的常量，可以省略，如f(n)=100∗n ^2中的100多项式中数量规模更小（低次项）的表达式，如f(n)=n2+n中的nf(n)=n^3+n^2中的n^2不同底数的对数，渐进上界可以用一个对数函数 logn 表示例如：log2(n) 可以替换为log10(n)，因为log2(n)=log10(n)/log10(2)，1/log10(2)可以省略类似的，对数的常数次幂可省略如：log(nc)=c∗log(n)常见大 O OO 表示法按时间复杂度从低到高黑色横线 O(1)，常量时间，意味着算法时间并不随数据规模而变化绿色O(log(n))，对数时间蓝色 O(n)，线性时间，算法时间与数据规模成正比橙色 O(n∗log(n))，拟线性时间红色O(n2) 平方时间黑色朝上 O(2n) 指数时间没画出来的 O(n!)渐进下界渐进下界（asymptotic lower bound）：从某个常数n0开始，c∗g(n) 总是位于 f(n) 下方，那么记作)Ω(g(n))渐进紧界渐进紧界（asymptotic tight bounds）：从某个常数n0开始，f(n) 总是在 c1∗g(n) 和 c2∗g(n) 之间，那么记作 Θ(g(n))空间复杂度与时间复杂度类似，一般也使用大 O表示法来衡量：一个算法执行随数据规模增大，而增长的额外空间成本public static int binarySearchBasic(int[] a, int target) {
int i = 0, j = a.length - 1; // 设置指针和初值
while (i <= j) { // i~j 范围内有东西
int m = (i + j) >>> 1;
if(target < a[m]) { // 目标在左边
j = m - 1;
} else if (a[m] < target) { // 目标在右边
i = m + 1;
} else { // 找到了
return m;
}
}
return -1;
}
二分查找性能下面分析二分查找算法的性能时间复杂度最坏情况：O(logn)最好情况：如果待查找元素恰好在数组中央，只需要循环一次 O(1)空间复杂度需要常数个指针 i,j,m ，因此额外占用的空间是O(1)1.5 再看二分查找1) 平衡版public static int binarySearchBalance(int[] a, int target) {
int i = 0, j = a.length;
while (1 < j - i) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m;
} else {
i = m;
}
}
return (a[i] == target) ? i : -1;
}
思想：左闭右开的区间，i 指向的可能是目标，而 j 指向的不是目标不奢望循环内通过 m 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的（通过i）改变 i 边界时，它指向的可能是目标，因此不能 m+1循环内的平均比较次数减少了时间复杂度 Θ(log(n))2) Java 版private static int binarySearch0(long[] a, int fromIndex, int toIndex,
long key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
long midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
例如 [1,3,5,6] 要插入 2 那么就是找到一个位置，这个位置左侧元素都比它小插入点取负是为了与找到情况区分-1 是为了把索引 0 位置的插入点与找到的情况进行区分3) Leftmost 与 Rightmost有时我们希望返回的是最左侧的重复元素，如果用 Basic 二分查找对于数组 [1,2,3,4,4,5,6,7]，查找元素4，结果是索引3对于数组[1,2,4,4,4,5,6,7]，查找元素4，结果也是索引3，并不是最左侧的元素public static int binarySearchLeftmost1(int[] a, int target) {
int i = 0, j = a.length - 1;
int candidate = -1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else if (a[m] < target) {
i = m + 1;
} else {
candidate = m; // 记录候选位置
j = m - 1; // 继续向左
}
}
return candidate;
}
如果希望返回的是最右侧元素public static int binarySearchRightmost1(int[] a, int target) {
int i = 0, j = a.length - 1;
int candidate = -1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else if (a[m] < target) {
i = m + 1;
} else {
candidate = m; // 记录候选位置
i = m + 1; // 继续向右
}
}
return candidate;
}
应用对于 Leftmost 与 Rightmost，可以返回一个比 -1 更有用的值Leftmost 改为public static int binarySearchLeftmost(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target <= a[m]) {
j = m - 1;
} else {
i = m + 1;
}
}
return i;
}
leftmost 返回值的另一层含义：<target 的元素个数小于等于中间值，都要向左找Rightmost 改为public static int binarySearchRightmost(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else {
i = m + 1;
}
}
return i - 1;
}
大于等于中间值，都要向右找几个名词求最近邻居：前任和后任距离更近者 2.5 栈1) 概述计算机科学中，stack 是一种线性的数据结构，只能在其一端添加数据和移除数据。习惯来说，这一端称之为栈顶，另一端不能操作数据的称之为栈底，就如同生活中的一摞书先提供一个栈接口public interface Stack<E> {
/**
* 向栈顶压入元素
* @param value 待压入值
* @return 压入成功返回 true, 否则返回 false
*/
boolean push(E value);
/**
* 从栈顶弹出元素
* @return 栈非空返回栈顶元素, 栈为空返回 null
*/
E pop();
/**
* 返回栈顶元素, 不弹出
* @return 栈非空返回栈顶元素, 栈为空返回 null
*/
E peek();
/**
* 判断栈是否为空
* @return 空返回 true, 否则返回 false
*/
boolean isEmpty();
/**
* 判断栈是否已满
* @return 满返回 true, 否则返回 false
*/
boolean isFull();
}2) 链表实现public class LinkedListStack<E> implements Stack<E>, Iterable<E> {
private final int capacity;
private int size;
private final Node<E> head = new Node<>(null, null);
public LinkedListStack(int capacity) {
this.capacity = capacity;
}
@Override
public boolean push(E value) {
if (isFull()) {
return false;
}
head.next = new Node<>(value, head.next);
size++;
return true;
}
@Override
public E pop() {
if (isEmpty()) {
return null;
}
Node<E> first = head.next;
head.next = first.next;
size--;
return first.value;
}
@Override
public E peek() {
if (isEmpty()) {
return null;
}
return head.next.value;
}
@Override
public boolean isEmpty() {
return head.next == null;
}
@Override
public boolean isFull() {
return size == capacity;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
Node<E> p = head.next;
@Override
public boolean hasNext() {
return p != null;
}
@Override
public E next() {
E value = p.value;
p = p.next;
return value;
}
};
}
static class Node<E> {
E value;
Node<E> next;
public Node(E value, Node<E> next) {
this.value = value;
this.next = next;
}
}
}3) 数组实现public class ArrayStack<E> implements Stack<E>, Iterable<E>{
private final E[] array;
private int top = 0;
@SuppressWarnings("all")
public ArrayStack(int capacity) {
this.array = (E[]) new Object[capacity];
}
@Override
public boolean push(E value) {
if (isFull()) {
return false;
}
array[top++] = value;
return true;
}
@Override
public E pop() {
if (isEmpty()) {
return null;
}
return array[--top];
}
@Override
public E peek() {
if (isEmpty()) {
return null;
}
return array[top-1];
}
@Override
public boolean isEmpty() {
return top == 0;
}
@Override
public boolean isFull() {
return top == array.length;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int p = top;
@Override
public boolean hasNext() {
return p > 0;
}
@Override
public E next() {
return array[--p];
}
};
}
}4) 应用模拟如下方法调用public static void main(String[] args) {
System.out.println("main1");
System.out.println("main2");
method1();
method2();
System.out.println("main3");
}
public static void method1() {
System.out.println("method1");
method3();
}
public static void method2() {
System.out.println("method2");
}
public static void method3() {
System.out.println("method3");
}模拟代码public class CPU {
static class Frame {
int exit;
public Frame(int exit) {
this.exit = exit;
}
}
static int pc = 1; // 模拟程序计数器 Program counter
static ArrayStack<Frame> stack = new ArrayStack<>(100); // 模拟方法调用栈
public static void main(String[] args) {
stack.push(new Frame(-1));
while (!stack.isEmpty()) {
switch (pc) {
case 1 -> {
System.out.println("main1");
pc++;
}
case 2 -> {
System.out.println("main2");
pc++;
}
case 3 -> {
stack.push(new Frame(pc + 1));
pc = 100;
}
case 4 -> {
stack.push(new Frame(pc + 1));
pc = 200;
}
case 5 -> {
System.out.println("main3");
pc = stack.pop().exit;
}
case 100 -> {
System.out.println("method1");
stack.push(new Frame(pc + 1));
pc = 300;
}
case 101 -> {
pc = stack.pop().exit;
}
case 200 -> {
System.out.println("method2");
pc = stack.pop().exit;
}
case 300 -> {
System.out.println("method3");
pc = stack.pop().exit;
}
}
}
}
}习题E01. 有效的括号-Leetcode 20一个字符串中可能出现 [] () 和 {} 三种括号，判断该括号是否有效有效的例子()[]{}
([{}])
()无效的例子[)
([)]
([]思路遇到左括号, 把要配对的右括号放入栈顶遇到右括号, 若此时栈为空, 返回 false，否则把它与栈顶元素对比若相等, 栈顶元素弹出, 继续对比下一组若不等, 无效括号直接返回 false循环结束若栈为空, 表示所有括号都配上对, 返回 true若栈不为空, 表示右没配对的括号, 应返回 false答案（用到了课堂案例中的 ArrayStack 类）public boolean isValid(String s) {
ArrayStack<Character> stack = new ArrayStack<>(s.length() / 2 + 1);
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(')');
} else if (c == '[') {
stack.push(']');
} else if (c == '{') {
stack.push('}');
} else {
if (!stack.isEmpty() && stack.peek() == c) {
stack.pop();
} else {
return false;
}
}
}
return stack.isEmpty();
}
E02. 后缀表达式求值-Leetcode 120后缀表达式也称为逆波兰表达式，即运算符写在后面从左向右进行计算不必考虑运算符优先级，即不用包含括号示例输入：tokens = ["2","1","+","3","*"]
输出：9
即：(2 + 1) * 3
输入：tokens = ["4","13","5","/","+"]
输出：6
即：4 + (13 / 5)题目假设数字都视为整数数字和运算符个数给定正确，不会有除零发生代码public int evalRPN(String[] tokens) {
LinkedList<Integer> numbers = new LinkedList<>();
for (String t : tokens) {
switch (t) {
case "+" -> {
Integer b = numbers.pop();
Integer a = numbers.pop();
numbers.push(a + b);
}
case "-" -> {
Integer b = numbers.pop();
Integer a = numbers.pop();
numbers.push(a - b);
}
case "*" -> {
Integer b = numbers.pop();
Integer a = numbers.pop();
numbers.push(a * b);
}
case "/" -> {
Integer b = numbers.pop();
Integer a = numbers.pop();
numbers.push(a / b);
}
default -> numbers.push(Integer.parseInt(t));
}
}
return numbers.pop();
}E03. 中缀表达式转后缀public class E03InfixToSuffix {
/*
思路
1. 遇到数字, 拼串
2. 遇到 + - * /
- 优先级高于栈顶运算符 入栈
- 否则将栈中高级或平级运算符出栈拼串, 本运算符入栈
3. 遍历完成, 栈中剩余运算符出栈拼串
- 先出栈,意味着优先运算
4. 带 ()
- 左括号直接入栈
- 右括号要将栈中直至左括号为止的运算符出栈拼串
| |
| |
| |
_____
a+b
a+b-c
a+b*c
a*b+c
(a+b)*c
*/
public static void main(String[] args) {
System.out.println(infixToSuffix("a+b"));
System.out.println(infixToSuffix("a+b-c"));
System.out.println(infixToSuffix("a+b*c"));
System.out.println(infixToSuffix("a*b-c"));
System.out.println(infixToSuffix("(a+b)*c"));
System.out.println(infixToSuffix("a+b*c+(d*e+f)*g"));
}
static String infixToSuffix(String exp) {
LinkedList<Character> stack = new LinkedList<>();
StringBuilder sb = new StringBuilder(exp.length());
for (int i = 0; i < exp.length(); i++) {
char c = exp.charAt(i);
switch (c) {
case '+', '-', '*', '/' -> {
if (stack.isEmpty()) {
stack.push(c);
} else {
if (priority(c) > priority(stack.peek())) {
stack.push(c);
} else {
while (!stack.isEmpty()
&& priority(stack.peek()) >= priority(c)) {
sb.append(stack.pop());
}
stack.push(c);
}
}
}
case '(' -> {
stack.push(c);
}
case ')' -> {
while (!stack.isEmpty() && stack.peek() != '(') {
sb.append(stack.pop());
}
stack.pop();
}
default -> {
sb.append(c);
}
}
}
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.toString();
}
static int priority(char c) {
return switch (c) {
case '(' -> 0;
case '*', '/' -> 2;
case '+', '-' -> 1;
default -> throw new IllegalArgumentException("不合法字符:" + c);
};
}
}E04. 双栈模拟队列-Leetcode 232给力扣题目用的自实现栈，可以定义为静态内部类class ArrayStack<E> {
private E[] array;
private int top; // 栈顶指针
@SuppressWarnings("all")
public ArrayStack(int capacity) {
this.array = (E[]) new Object[capacity];
}
public boolean push(E value) {
if (isFull()) {
return false;
}
array[top++] = value;
return true;
}
public E pop() {
if (isEmpty()) {
return null;
}
return array[--top];
}
public E peek() {
if (isEmpty()) {
return null;
}
return array[top - 1];
}
public boolean isEmpty() {
return top == 0;
}
public boolean isFull() {
return top == array.length;
}
}参考解答，注意：题目已说明调用 push、pop 等方法的次数最多 100public class E04Leetcode232 {
/*
队列头 队列尾
s1 s2
顶 底 底 顶
abc
push(a)
push(b)
push(c)
pop()
*/
ArrayStack<Integer> s1 = new ArrayStack<>(100);
ArrayStack<Integer> s2 = new ArrayStack<>(100);
public void push(int x) {
s2.push(x);
}
public int pop() {
if (s1.isEmpty()) {
while (!s2.isEmpty()) {
s1.push(s2.pop());
}
}
return s1.pop();
}
public int peek() {
if (s1.isEmpty()) {
while (!s2.isEmpty()) {
s1.push(s2.pop());
}
}
return s1.peek();
}
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}E05. 单队列模拟栈-Leetcode 225给力扣题目用的自实现队列，可以定义为静态内部类public class ArrayQueue3<E> {
private final E[] array;
int head = 0;
int tail = 0;
@SuppressWarnings("all")
public ArrayQueue3(int c) {
c -= 1;
c |= c >> 1;
c |= c >> 2;
c |= c >> 4;
c |= c >> 8;
c |= c >> 16;
c += 1;
array = (E[]) new Object[c];
}
public boolean offer(E value) {
if (isFull()) {
return false;
}
array[tail & (array.length - 1)] = value;
tail++;
return true;
}
public E poll() {
if (isEmpty()) {
return null;
}
E value = array[head & (array.length - 1)];
head++;
return value;
}
public E peek() {
if (isEmpty()) {
return null;
}
return array[head & (array.length - 1)];
}
public boolean isEmpty() {
return head == tail;
}
public boolean isFull() {
return tail - head == array.length;
}
}参考解答，注意：题目已说明调用 push、pop 等方法的次数最多 100每次调用 pop 和 top 都能保证栈不为空public class E05Leetcode225 {
/*
队列头 队列尾
cba
顶 底
queue.offer(a)
queue.offer(b)
queue.offer(c)
*/
ArrayQueue3<Integer> queue = new ArrayQueue3<>(100);
int size = 0;
public void push(int x) {
queue.offer(x);
for (int i = 0; i < size; i++) {
queue.offer(queue.poll());
}
size++;
}
public int pop() {
size--;
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
} 2.3 递归1) 概述定义计算机科学中，递归是一种解决计算问题的方法，其中解决方案取决于同一类问题的更小子集In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.比如单链表递归遍历的例子：void f(Node node) {
if(node == null) {
return;
}
println("before:" + node.value)
f(node.next);
println("after:" + node.value)
}说明：自己调用自己，如果说每个函数对应着一种解决方案，自己调用自己意味着解决方案是一样的（有规律的）每次调用，函数处理的数据会较上次缩减（子集），而且最后会缩减至无需继续递归内层函数调用（子集处理）完成，外层函数才能算调用完成原理假设链表中有 3 个节点，value 分别为 1，2，3，以上代码的执行流程就类似于下面的伪码// 1 -> 2 -> 3 -> null f(1)
void f(Node node = 1) {
println("before:" + node.value) // 1
void f(Node node = 2) {
println("before:" + node.value) // 2
void f(Node node = 3) {
println("before:" + node.value) // 3
void f(Node node = null) {
if(node == null) {
return;
}
}
println("after:" + node.value) // 3
}
println("after:" + node.value) // 2
}
println("after:" + node.value) // 1
}思路确定能否使用递归求解推导出递推关系，即父问题与子问题的关系，以及递归的结束条件例如之前遍历链表的递推关系为深入到最里层叫做递从最里层出来叫做归在递的过程中，外层函数内的局部变量（以及方法参数）并未消失，归的时候还可以用到2) 单路递归 Single RecursionE01. 阶乘用递归方法求阶乘代码private static int f(int n) {
if (n == 1) {
return 1;
}
return n * f(n - 1);
}拆解伪码如下，假设 n 初始值为 3f(int n = 3) { // 解决不了,递
return 3 * f(int n = 2) { // 解决不了,继续递
return 2 * f(int n = 1) {
if (n == 1) { // 可以解决, 开始归
return 1;
}
}
}
}E02. 反向打印字符串用递归反向打印字符串，n 为字符在整个字符串 str 中的索引位置递：n 从 0 开始，每次 n + 1，一直递到 n == str.length() - 1归：从 n == str.length() 开始归，从归打印，自然是逆序的递推关系代码为public static void reversePrint(String str, int index) {
if (index == str.length()) {
return;
}
reversePrint(str, index + 1);
System.out.println(str.charAt(index));
}拆解伪码如下，假设字符串为 “abc”void reversePrint(String str, int index = 0) {
void reversePrint(String str, int index = 1) {
void reversePrint(String str, int index = 2) {
void reversePrint(String str, int index = 3) {
if (index == str.length()) {
return; // 开始归
}
}
System.out.println(str.charAt(index)); // 打印 c
}
System.out.println(str.charAt(index)); // 打印 b
}
System.out.println(str.charAt(index)); // 打印 a
}E03. 二分查找（单路递归）public static int binarySearch(int[] a, int target) {
return recursion(a, target, 0, a.length - 1);
}
public static int recursion(int[] a, int target, int i, int j) {
if (i > j) {
return -1;
}
int m = (i + j) >>> 1;
if (target < a[m]) {
return recursion(a, target, i, m - 1);
} else if (a[m] < target) {
return recursion(a, target, m + 1, j);
} else {
return m;
}
}E04. 冒泡排序（单路递归）public static void main(String[] args) {
int[] a = {3, 2, 6, 1, 5, 4, 7};
bubble(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
private static void bubble(int[] a, int low, int high) {
if(low == high) {
return;
}
int j = low;
for (int i = low; i < high; i++) {
if (a[i] > a[i + 1]) {
swap(a, i, i + 1);
j = i;
}
}
bubble(a, low, j);
}
private static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}low 与 high 为未排序范围j 表示的是未排序的边界，下一次递归时的 high发生交换，意味着有无序情况最后一次交换（以后没有无序）时，左侧 i 仍是无序，右侧 i+1 已然有序视频中讲解的是只考虑 high 边界的情况，参考以上代码，理解在 low … high 范围内的处理方法E05. 插入排序（单路递归）public static void main(String[] args) {
int[] a = {3, 2, 6, 1, 5, 7, 4};
insertion(a, 1, a.length - 1);
System.out.println(Arrays.toString(a));
}
private static void insertion(int[] a, int low, int high) {
if (low > high) {
return;
}
int i = low - 1;
int t = a[low];
while (i >= 0 && a[i] > i) {
a[i + 1] = a[i];
i--;
}
if(i + 1 != low) {
a[i + 1] = t;
}
insertion(a, low + 1, high);
}已排序区域：[0 … i … low-1]未排序区域：[low … high]视频中讲解的是只考虑 low 边界的情况，参考以上代码，理解 low-1 … high 范围内的处理方法扩展：利用二分查找 leftmost 版本，改进寻找插入位置的代码E06. 约瑟夫问题[^16]（单路递归）n 个人排成圆圈，从头开始报数，每次数到第 m 个人（m 从 1 开始）杀之，继续从下一个人重复以上过程，求最后活下来的人是谁？方法1根据最后的存活者 a 倒推出它在上一轮的索引号f(n,m)本轮索引为了让 a 是这个索引，上一轮应当这样排规律f(1,3)0x x x a(0 + 3) % 2f(2,3)1x x x 0 a(1 + 3) % 3f(3,3)1x x x 0 a(1 + 3) % 4f(4,3)0x x x a(0 + 3) % 5f(5,3)3x x x 0 1 2 a(3 + 3) % 6f(6,3)0x x x a方法2设 n 为总人数，m 为报数次数，解返回的是这些人的索引，从0开始f(n, m)解规律f(1, 3)0f(2, 3)0 1 => 13%2=1f(3, 3)0 1 2 => 0 13%3=0f(4, 3)0 1 2 3 => 3 0 13%4=3f(5, 3)0 1 2 3 4 => 3 4 0 13%5=3f(6, 3)0 1 2 3 4 5 => 3 4 5 0 13%6=3下面的表格列出了数列的前几项F0F1F2F3F4F5F6F7F8F9F10F11F12F1301123581321345589144233实现public static int f(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return f(n - 1) + f(n - 2);
}执行流程绿色代表正在执行（对应递），灰色代表执行结束（对应归）递不到头，不能归，对应着深度优先搜索时间复杂度1.更多 Fibonacci 参考[8][9][^10]2.以上时间复杂度分析，未考虑大数相加的因素变体1 - 兔子问题[^8]第一个月，有一对未成熟的兔子（黑色，注意图中个头较小）第二个月，它们成熟第三个月，它们能产下一对新的小兔子（蓝色）所有兔子遵循相同规律，求第 n 个月的兔子数分析n跳法规律1(1)暂时看不出2(1,1) (2)暂时看不出3(1,1,1) (1,2) (2,1)暂时看不出4(1,1,1,1) (1,2,1) (2,1,1)(1,1,2) (2,2)最后一跳，跳一个台阶的，基于f(3)最后一跳，跳两个台阶的，基于f(2)5……因此本质上还是斐波那契数列，只是从其第二项开始对应 leetcode 题目 70. 爬楼梯 - 力扣（LeetCode）E02. 汉诺塔[^13]（多路递归）Tower of Hanoi，是一个源于印度古老传说：大梵天创建世界时做了三根金刚石柱，在一根柱子从下往上按大小顺序摞着 64 片黄金圆盘，大梵天命令婆罗门把圆盘重新摆放在另一根柱子上，并且规定一次只能移动一个圆盘小圆盘上不能放大圆盘下面的动图演示了4片圆盘的移动方法使用程序代码模拟圆盘的移动过程，并估算出时间复杂度思路假设每根柱子标号 a，b，c，每个圆盘用 1，2，3 … 表示其大小，圆盘初始在 a，要移动到的目标是 c如果只有一个圆盘，此时是最小问题，可以直接求解如果有两个圆盘，那么如果有三个圆盘，那么如果有四个圆盘，那么题解public class E02HanoiTower {
/*
源 借 目
h(4, a, b, c) -> h(3, a, c, b)
a -> c
h(3, b, a, c)
*/
static LinkedList<Integer> a = new LinkedList<>();
static LinkedList<Integer> b = new LinkedList<>();
static LinkedList<Integer> c = new LinkedList<>();
static void init(int n) {
for (int i = n; i >= 1; i--) {
a.add(i);
}
}
static void h(int n, LinkedList<Integer> a,
LinkedList<Integer> b,
LinkedList<Integer> c) {
if (n == 0) {
return;
}
h(n - 1, a, c, b);
c.addLast(a.removeLast());
print();
h(n - 1, b, a, c);
}
private static void print() {
System.out.println("-----------------------");
System.out.println(a);
System.out.println(b);
System.out.println(c);
}
public static void main(String[] args) {
init(3);
print();
h(3, a, b, c);
}
}E03. 杨辉三角[^6]分析把它斜着看 1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
题解public static void print(int n) {
for (int i = 0; i < n; i++) {
if (i < n - 1) {
System.out.printf("%" + 2 * (n - 1 - i) + "s", " ");
}
for (int j = 0; j < i + 1; j++) {
System.out.printf("%-4d", element(i, j));
}
System.out.println();
}
}
public static int element(int i, int j) {
if (j == 0 || i == j) {
return 1;
}
return element(i - 1, j - 1) + element(i - 1, j);
}优化1是 multiple recursion，因此很多递归调用是重复的，例如recursion(3, 1) 分解为recursion(2, 0) + recursion(2, 1)而 recursion(3, 2) 分解为recursion(2, 1) + recursion(2, 2)这里 recursion(2, 1) 就重复调用了，事实上它会重复很多次，可以用 static AtomicInteger counter = new AtomicInteger(0) 来查看递归函数的调用总次数事实上，可以用 memoization 来进行优化：public static void print1(int n) {
int[][] triangle = new int[n][];
for (int i = 0; i < n; i++) {
// 打印空格
triangle[i] = new int[i + 1];
for (int j = 0; j <= i; j++) {
System.out.printf("%-4d", element1(triangle, i, j));
}
System.out.println();
}
}
public static int element1(int[][] triangle, int i, int j) {
if (triangle[i][j] > 0) {
return triangle[i][j];
}
if (j == 0 || i == j) {
triangle[i][j] = 1;
return triangle[i][j];
}
triangle[i][j] = element1(triangle, i - 1, j - 1) + element1(triangle, i - 1, j);
return triangle[i][j];
}优化2public static void print2(int n) {
int[] row = new int[n];
for (int i = 0; i < n; i++) {
// 打印空格
createRow(row, i);
for (int j = 0; j <= i; j++) {
System.out.printf("%-4d", row[j]);
}
System.out.println();
}
}
private static void createRow(int[] row, int i) {
if (i == 0) {
row[0] = 1;
return;
}
for (int j = i; j > 0; j--) {
row[j] = row[j - 1] + row[j];
}
}注意：还可以通过每一行的前一项计算出下一项，不必借助上一行，这与杨辉三角的另一个特性有关，暂不展开了其它题目力扣对应题目，但递归不适合在力扣刷高分，因此只列出相关题目，不做刷题讲解了题号名称Leetcode118杨辉三角Leetcode119杨辉三角II4) 递归优化-记忆法上述代码存在很多重复的计算，例如求 f ( 5 ) f(5)f(5) 递归分解过程Memoization 记忆法（也称备忘录）是一种优化技术，通过存储函数调用结果（通常比较昂贵），当再次出现相同的输入（子问题）时，就能实现加速效果，改进后的代码public static void main(String[] args) {
int n = 13;
int[] cache = new int[n + 1];
Arrays.fill(cache, -1);
cache[0] = 0;
cache[1] = 1;
System.out.println(f(cache, n));
}
public static int f(int[] cache, int n) {
if (cache[n] != -1) {
return cache[n];
}
cache[n] = f(cache, n - 1) + f(cache, n - 2);
return cache[n];
}优化后的图示，只要结果被缓存，就不会执行其子问题改进后的时间复杂度为 O ( n )请自行验证改进后的效果请自行分析改进后的空间复杂度注意1.记忆法是动态规划的一种情况，强调的是自顶向下的解决2.记忆法的本质是空间换时间5) 递归优化-尾递归爆栈用递归做 n + ( n − 1 ) + ( n − 2 ) . . . + 1 public static long sum(long n) {
if (n == 1) {
return 1;
}
return n + sum(n - 1);
}
在我的机器上 n = 12000 时，爆栈了Exception in thread "main" java.lang.StackOverflowError
at Test.sum(Test.java:10)
at Test.sum(Test.java:10)
at Test.sum(Test.java:10)
at Test.sum(Test.java:10)
at Test.sum(Test.java:10)
...为什么呢？每次方法调用是需要消耗一定的栈内存的，这些内存用来存储方法参数、方法内局部变量、返回地址等等方法调用占用的内存需要等到方法结束时才会释放而递归调用我们之前讲过，不到最深不会回头，最内层方法没完成之前，外层方法都结束不了long sum(long n = 3) {
return 3 + long sum(long n = 2) {
return 2 + long sum(long n = 1) {
return 1;
}
}
}尾调用如果函数的最后一步是调用一个函数，那么称为尾调用，例如function a() {
return b()
}下面三段代码不能叫做尾调用function a() {
const c = b()
return c
}因为最后一步并非调用函数function a() {
return b() + 1
}最后一步执行的是加法function a(x) {
return b() + x
}最后一步执行的是加法一些语言[^11]的编译器能够对尾调用做优化，例如function a() {
// 做前面的事
return b()
}
function b() {
// 做前面的事
return c()
}
function c() {
return 1000
}
a()没优化之前的伪码function a() {
return function b() {
return function c() {
return 1000
}
}
}优化后伪码如下a()
b()
c()为何尾递归才能优化？调用 a 时a 返回时发现：没什么可留给 b 的，将来返回的结果 b 提供就可以了，用不着我 a 了，我的内存就可以释放调用 b 时b 返回时发现：没什么可留给 c 的，将来返回的结果 c 提供就可以了，用不着我 b 了，我的内存就可以释放如果调用 a 时不是尾调用，例如 return b() + 1，那么 a 就不能提前结束，因为它还得利用 b 的结果做加法尾递归尾递归是尾调用的一种特例，也就是最后一步执行的是同一个函数尾递归避免爆栈安装 ScalaScala 入门object Main {
def main(args: Array[String]): Unit = {
println("Hello Scala")
}
}Scala 是 java 的近亲，java 中的类都可以拿来重用类型是放在变量后面的Unit 表示无返回值，类似于 void不需要以分号作为结尾，当然加上也对还是先写一个会爆栈的函数def sum(n: Long): Long = {
if (n == 1) {
return 1
}
return n + sum(n - 1)
}Scala 最后一行代码若作为返回值，可以省略 return不出所料，在 n = 11000 n = 11000n=11000 时，还是出了异常println(sum(11000))
Exception in thread "main" java.lang.StackOverflowError
at Main$.sum(Main.scala:25)
at Main$.sum(Main.scala:25)
at Main$.sum(Main.scala:25)
at Main$.sum(Main.scala:25)
...这是因为以上代码，还不是尾调用，要想成为尾调用，那么：最后一行代码，必须是一次函数调用内层函数必须摆脱与外层函数的关系，内层函数执行后不依赖于外层的变量或常量def sum(n: Long): Long = {
if (n == 1) {
return 1
}
return n + sum(n - 1) // 依赖于外层函数的 n 变量
}如何让它执行后就摆脱对 n 的依赖呢？不能等递归回来再做加法，那样就必须保留外层的 n把 n 当做内层函数的一个参数传进去，这时 n 就属于内层函数了传参时就完成累加, 不必等回来时累加sum(n - 1, n + 累加器)改写后代码如下@tailrec
def sum(n: Long, accumulator: Long): Long = {
if (n == 1) {
return 1 + accumulator
}
return sum(n - 1, n + accumulator)
}accumulator 作为累加器@tailrec 注解是 scala 提供的，用来检查方法是否符合尾递归这回 sum(10000000, 0) 也没有问题，打印 50000005000000执行流程如下，以伪码表示 s u m ( 4 , 0 )// 首次调用
def sum(n = 4, accumulator = 0): Long = {
return sum(4 - 1, 4 + accumulator)
}
// 接下来调用内层 sum, 传参时就完成了累加, 不必等回来时累加，当内层 sum 调用后，外层 sum 空间没必要保留
def sum(n = 3, accumulator = 4): Long = {
return sum(3 - 1, 3 + accumulator)
}
// 继续调用内层 sum
def sum(n = 2, accumulator = 7): Long = {
return sum(2 - 1, 2 + accumulator)
}
// 继续调用内层 sum, 这是最后的 sum 调用完就返回最后结果 10, 前面所有其它 sum 的空间早已释放
def sum(n = 1, accumulator = 9): Long = {
if (1 == 1) {
return 1 + accumulator
}
}本质上，尾递归优化是将函数的递归调用，变成了函数的循环调用改循环避免爆栈public static void main(String[] args) {
long n = 100000000;
long sum = 0;
for (long i = n; i >= 1; i--) {
sum += i;
}
System.out.println(sum);
}6) 递归时间复杂度-Master theorem[^14]例7. 二分查找递归int f(int[] a, int target, int i, int j) {
if (i > j) {
return -1;
}
int m = (i + j) >>> 1;
if (target < a[m]) {
return f(a, target, i, m - 1);
} else if (a[m] < target) {
return f(a, target, m + 1, j);
} else {
return m;
}
}例8. 归并排序递归void split(B[], i, j, A[])
{
if (j - i <= 1)
return;
m = (i + j) / 2;
// 递归
split(A, i, m, B);
split(A, m, j, B);
// 合并
merge(B, i, m, j, A);
}例9. 快速排序递归algorithm quicksort(A, lo, hi) is
if lo >= hi || lo < 0 then
return
// 分区
p := partition(A, lo, hi)
// 递归
quicksort(A, lo, p - 1)
quicksort(A, p + 1, hi) 7) 递归时间复杂度-展开求解像下面的递归式，都不能用主定理求解例1 - 递归求和long sum(long n) {
if (n == 1) {
return 1;
}
return n + sum(n - 1);
}例2 - 递归冒泡排序void bubble(int[] a, int high) {
if(0 == high) {
return;
}
for (int i = 0; i < high; i++) {
if (a[i] > a[i + 1]) {
swap(a, i, i + 1);
}
}
bubble(a, high - 1);
} 2.10 二叉树二叉树是这么一种树状结构：每个节点最多有两个孩子，左孩子和右孩子重要的二叉树结构完全二叉树（complete binary tree）是一种二叉树结构，除最后一层以外，每一层都必须填满，填充时要遵从先左后右平衡二叉树（balance binary tree）是一种二叉树结构，其中每个节点的左右子树高度相差不超过 11) 存储存储方式分为两种定义树节点与左、右孩子引用（TreeNode）使用数组，前面讲堆时用过，若以 0 作为树的根，索引可以通过如下方式计算父 = floor((子 - 1) / 2)左孩子 = 父 * 2 + 1右孩子 = 父 * 2 + 22) 遍历遍历也分为两种广度优先遍历（Breadth-first order）：尽可能先访问距离根最近的节点，也称为层序遍历深度优先遍历（Depth-first order）：对于二叉树，可以进一步分成三种（要深入到叶子节点）广度优先本轮开始时队列本轮访问节点[1]1[2, 3]2[3, 4]3[4, 5, 6]4[5, 6]5[6, 7, 8]6[7, 8]7[8]8[]初始化，将根节点加入队列循环处理队列中每个节点，直至队列为空每次循环内处理节点后，将它的孩子节点（即下一层的节点）加入队列注意以上用队列来层序遍历是针对 TreeNode 这种方式表示的二叉树对于数组表现的二叉树，则直接遍历数组即可，自然为层序遍历的顺序深度优先栈暂存已处理前序遍历中序遍历[1]1 ✔️ 左💤 右💤1[1, 2]2✔️ 左💤 右💤1✔️ 左💤 右💤2[1, 2, 4]4✔️ 左✔️ 右✔️2✔️ 左💤 右💤1✔️ 左💤 右💤44[1, 2]2✔️ 左✔️ 右✔️1✔️ 左💤 右💤2[1]1✔️ 左✔️ 右💤1[1, 3]3✔️ 左💤 右💤1✔️ 左✔️ 右💤3[1, 3, 5]5✔️ 左✔️ 右✔️3✔️ 左💤 右💤1✔️ 左✔️ 右💤55[1, 3]3✔️ 左✔️ 右💤1✔️ 左✔️ 右💤3[1, 3, 6]6✔️ 左✔️ 右✔️3✔️ 左✔️ 右💤1✔️ 左✔️ 右💤66[1, 3]3✔️ 左✔️ 右✔️1✔️ 左✔️ 右💤[1]1✔️ 左✔️ 右✔️[]递归实现/**
* <h3>前序遍历</h3>
* @param node 节点
*/
static void preOrder(TreeNode node) {
if (node == null) {
return;
}
System.out.print(node.val + "\t"); // 值
preOrder(node.left); // 左
preOrder(node.right); // 右
}
/**
* <h3>中序遍历</h3>
* @param node 节点
*/
static void inOrder(TreeNode node) {
if (node == null) {
return;
}
inOrder(node.left); // 左
System.out.print(node.val + "\t"); // 值
inOrder(node.right); // 右
}
/**
* <h3>后序遍历</h3>
* @param node 节点
*/
static void postOrder(TreeNode node) {
if (node == null) {
return;
}
postOrder(node.left); // 左
postOrder(node.right); // 右
System.out.print(node.val + "\t"); // 值
}非递归实现前序遍历LinkedListStack<TreeNode> stack = new LinkedListStack<>();
TreeNode curr = root;
while (!stack.isEmpty() || curr != null) {
if (curr != null) {
stack.push(curr);
System.out.println(curr);
curr = curr.left;
} else {
TreeNode pop = stack.pop();
curr = pop.right;
}
}中序遍历LinkedListStack<TreeNode> stack = new LinkedListStack<>();
TreeNode curr = root;
while (!stack.isEmpty() || curr != null) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
} else {
TreeNode pop = stack.pop();
System.out.println(pop);
curr = pop.right;
}
}后序遍历LinkedListStack<TreeNode> stack = new LinkedListStack<>();
TreeNode curr = root;
TreeNode pop = null;
while (!stack.isEmpty() || curr != null) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
} else {
TreeNode peek = stack.peek();
if (peek.right == null || peek.right == pop) {
pop = stack.pop();
System.out.println(pop);
} else {
curr = peek.right;
}
}
}统一写法下面是一种统一的写法，依据后序遍历修改LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode curr = root; // 代表当前节点
TreeNode pop = null; // 最近一次弹栈的元素
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
colorPrintln("前: " + curr.val, 31);
stack.push(curr); // 压入栈，为了记住回来的路
curr = curr.left;
} else {
TreeNode peek = stack.peek();
// 右子树可以不处理, 对中序来说, 要在右子树处理之前打印
if (peek.right == null) {
colorPrintln("中: " + peek.val, 36);
pop = stack.pop();
colorPrintln("后: " + pop.val, 34);
}
// 右子树处理完成, 对中序来说, 无需打印
else if (peek.right == pop) {
pop = stack.pop();
colorPrintln("后: " + pop.val, 34);
}
// 右子树待处理, 对中序来说, 要在右子树处理之前打印
else {
colorPrintln("中: " + peek.val, 36);
curr = peek.right;
}
}
}
public static void colorPrintln(String origin, int color) {
System.out.printf("\033[%dm%s\033[0m%n", color, origin);
}一张图演示三种遍历红色：前序遍历顺序绿色：中序遍历顺序蓝色：后续遍历顺序习题E01. 前序遍历二叉树-Leetcode 144E02. 中序遍历二叉树-Leetcode 94E03. 后序遍历二叉树-Leetcode 145E04. 对称二叉树-Leetcode 101public boolean isSymmetric(TreeNode root) {
return check(root.left, root.right);
}
public boolean check(TreeNode left, TreeNode right) {
// 若同时为 null
if (left == null && right == null) {
return true;
}
// 若有一个为 null (有上一轮筛选，另一个肯定不为 null)
if (left == null || right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
return check(left.left, right.right) && check(left.right, right.left);
}类似题目：Leetcode 100 题 - 相同的树E05. 二叉树最大深度-Leetcode 104后序遍历求解/*
思路：
1. 得到左子树深度, 得到右子树深度, 二者最大者加一, 就是本节点深度
2. 因为需要先得到左右子树深度, 很显然是后序遍历典型应用
3. 关于深度的定义：从根出发, 离根最远的节点总边数,
注意: 力扣里的深度定义要多一
深度2 深度3 深度1
1 1 1
/ \ / \
2 3 2 3
\
4
*/
public int maxDepth(TreeNode node) {
if (node == null) {
return 0; // 非力扣题目改为返回 -1
}
int d1 = maxDepth(node.left);
int d2 = maxDepth(node.right);
return Integer.max(d1, d2) + 1;
}后序遍历求解-非递归/*
思路：
1. 使用非递归后序遍历, 栈的最大高度即为最大深度
*/
public int maxDepth(TreeNode root) {
TreeNode curr = root;
LinkedList<TreeNode> stack = new LinkedList<>();
int max = 0;
TreeNode pop = null;
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
stack.push(curr);
int size = stack.size();
if (size > max) {
max = size;
}
curr = curr.left;
} else {
TreeNode peek = stack.peek();
if(peek.right == null || peek.right == pop) {
pop = stack.pop();
} else {
curr = peek.right;
}
}
}
return max;
}层序遍历求解/*
思路：
1. 使用层序遍历, 层数即最大深度
*/
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int level = 0;
while (!queue.isEmpty()) {
level++;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return level;
}E06. 二叉树最小深度-Leetcode 111后序遍历求解public int minDepth(TreeNode node) {
if (node == null) {
return 0;
}
int d1 = minDepth(node.left);
int d2 = minDepth(node.right);
if (d1 == 0 || d2 == 0) {
return d1 + d2 + 1;
}
return Integer.min(d1, d2) + 1;
}
相较于求最大深度，应当考虑：当右子树为 null，应当返回左子树深度加一当左子树为 null，应当返回右子树深度加一上面两种情况满足时，不应该再把为 null 子树的深度 0 参与最小值比较，例如这样 1
/
2正确深度为 2，若把为 null 的右子树的深度 0 考虑进来，会得到错误结果 1 1
\
3
\
4正确深度为 3，若把为 null 的左子树的深度 0 考虑进来，会得到错误结果 1层序遍历求解遇到的第一个叶子节点所在层就是最小深度例如，下面的树遇到的第一个叶子节点 3 所在的层就是最小深度，其他 4，7 等叶子节点深度更深，也更晚遇到 1
/ \
2 3
/ \
4 5
/
7 代码public int minDepth(TreeNode root) {
if(root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int level = 0;
while (!queue.isEmpty()) {
level++;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null) {
return level;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return level;
}效率会高于之前后序遍历解法，因为找到第一个叶子节点后，就无需后续的层序遍历了E07. 翻转二叉树-Leetcode 226public TreeNode invertTree(TreeNode root) {
fn(root);
return root;
}
private void fn(TreeNode node){
if (node == null) {
return;
}
TreeNode t = node.left;
node.left = node.right;
node.right = t;
fn(node.left);
fn(node.right);
}先交换、再递归或是先递归、再交换都可以E08. 后缀表达式转二叉树static class TreeNode {
public String val;
public TreeNode left;
public TreeNode right;
public TreeNode(String val) {
this.val = val;
}
public TreeNode(TreeNode left, String val, TreeNode right) {
this.left = left;
this.val = val;
this.right = right;
}
@Override
public String toString() {
return this.val;
}
}
/*
中缀表达式 (2-1)*3
后缀（逆波兰）表达式 21-3*
1.遇到数字入栈
2.遇到运算符, 出栈两次, 与当前节点建立父子关系, 当前节点入栈
栈
| |
| |
| |
_____
表达式树
*
/ \
- 3
/ \
2 1
21-3*
*/
public TreeNode constructExpressionTree(String[] tokens) {
LinkedList<TreeNode> stack = new LinkedList<>();
for (String t : tokens) {
switch (t) {
case "+", "-", "*", "/" -> { // 运算符
TreeNode right = stack.pop();
TreeNode left = stack.pop();
TreeNode parent = new TreeNode(t);
parent.left = left;
parent.right = right;
stack.push(parent);
}
default -> { // 数字
stack.push(new TreeNode(t));
}
}
}
return stack.peek();
}E09. 根据前序与中序遍历结果构造二叉树-Leetcode 105先通过前序遍历结果定位根节点再结合中序遍历结果切分左右子树public class E09Leetcode105 {
/*
preOrder = {1,2,4,3,6,7}
inOrder = {4,2,1,6,3,7}
根 1
pre in
左 2,4 4,2
右 3,6,7 6,3,7
根 2
左 4
根 3
左 6
右 7
*/
public TreeNode buildTree(int[] preOrder, int[] inOrder) {
if (preOrder.length == 0) {
return null;
}
// 创建根节点
int rootValue = preOrder[0];
TreeNode root = new TreeNode(rootValue);
// 区分左右子树
for (int i = 0; i < inOrder.length; i++) {
if (inOrder[i] == rootValue) {
// 0 ~ i-1 左子树
// i+1 ~ inOrder.length -1 右子树
int[] inLeft = Arrays.copyOfRange(inOrder, 0, i); // [4,2]
int[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length); // [6,3,7]
int[] preLeft = Arrays.copyOfRange(preOrder, 1, i + 1); // [2,4]
int[] preRight = Arrays.copyOfRange(preOrder, i + 1, inOrder.length); // [3,6,7]
root.left = buildTree(preLeft, inLeft); // 2
root.right = buildTree(preRight, inRight); // 3
break;
}
}
return root;
}
}代码可以进一步优化，涉及新数据结构，以后实现E10. 根据中序与后序遍历结果构造二叉树-Leetcode 106先通过后序遍历结果定位根节点再结合中序遍历结果切分左右子树public TreeNode buildTree(int[] inOrder, int[] postOrder) {
if (inOrder.length == 0) {
return null;
}
// 根
int rootValue = postOrder[postOrder.length - 1];
TreeNode root = new TreeNode(rootValue);
// 切分左右子树
for (int i = 0; i < inOrder.length; i++) {
if (inOrder[i] == rootValue) {
int[] inLeft = Arrays.copyOfRange(inOrder, 0, i);
int[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length);
int[] postLeft = Arrays.copyOfRange(postOrder, 0, i);
int[] postRight = Arrays.copyOfRange(postOrder, i, postOrder.length - 1);
root.left = buildTree(inLeft, postLeft);
root.right = buildTree(inRight, postRight);
break;
}
}
return root;
}代码可以进一步优化，涉及新数据结构，以后实现 2.9 堆以大顶堆为例，相对于之前的优先级队列，增加了堆化等方法public class MaxHeap {
int[] array;
int size;
public MaxHeap(int capacity) {
this.array = new int[capacity];
}
/**
* 获取堆顶元素
*
* @return 堆顶元素
*/
public int peek() {
return array[0];
}
/**
* 删除堆顶元素
*
* @return 堆顶元素
*/
public int poll() {
int top = array[0];
swap(0, size - 1);
size--;
down(0);
return top;
}
/**
* 删除指定索引处元素
*
* @param index 索引
* @return 被删除元素
*/
public int poll(int index) {
int deleted = array[index];
up(Integer.MAX_VALUE, index);
poll();
return deleted;
}
/**
* 替换堆顶元素
*
* @param replaced 新元素
*/
public void replace(int replaced) {
array[0] = replaced;
down(0);
}
/**
* 堆的尾部添加元素
*
* @param offered 新元素
* @return 是否添加成功
*/
public boolean offer(int offered) {
if (size == array.length) {
return false;
}
up(offered, size);
size++;
return true;
}
// 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶
private void up(int offered, int index) {
int child = index;
while (child > 0) {
int parent = (child - 1) / 2;
if (offered > array[parent]) {
array[child] = array[parent];
} else {
break;
}
child = parent;
}
array[child] = offered;
}
public MaxHeap(int[] array) {
this.array = array;
this.size = array.length;
heapify();
}
// 建堆
private void heapify() {
// 如何找到最后这个非叶子节点 size / 2 - 1
for (int i = size / 2 - 1; i >= 0; i--) {
down(i);
}
}
// 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大
private void down(int parent) {
int left = parent * 2 + 1;
int right = left + 1;
int max = parent;
if (left < size && array[left] > array[max]) {
max = left;
}
if (right < size && array[right] > array[max]) {
max = right;
}
if (max != parent) { // 找到了更大的孩子
swap(max, parent);
down(max);
}
}
// 交换两个索引处的元素
private void swap(int i, int j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
public static void main(String[] args) {
int[] array = {2, 3, 1, 7, 6, 4, 5};
MaxHeap heap = new MaxHeap(array);
System.out.println(Arrays.toString(heap.array));
while (heap.size > 1) {
heap.swap(0, heap.size - 1);
heap.size--;
heap.down(0);
}
System.out.println(Arrays.toString(heap.array));
}
}建堆Floyd 建堆算法作者（也是之前龟兔赛跑判环作者）：找到最后一个非叶子节点从后向前，对每个节点执行下潜下面看交换次数的推导：设节点高度为 3本层节点数高度下潜最多交换次数（高度-1）4567 这层41023这层2211这层132Sum[\(40)Divide[Power[2,x],Power[2,i]]*\(40)i-1\(41)\(41),{i,1,x}]习题E01. 堆排序算法描述heapify 建立大顶堆将堆顶与堆底交换（最大元素被交换到堆底），缩小并下潜调整堆重复第二步直至堆里剩一个元素可以使用之前课堂例题的大顶堆来实现int[] array = {1, 2, 3, 4, 5, 6, 7};
MaxHeap maxHeap = new MaxHeap(array);
System.out.println(Arrays.toString(maxHeap.array));
while (maxHeap.size > 1) {
maxHeap.swap(0, maxHeap.size - 1);
maxHeap.size--;
maxHeap.down(0);
}
System.out.println(Arrays.toString(maxHeap.array));E02. 数组中第K大元素-Leetcode 215小顶堆（可删去用不到代码）class MinHeap {
int[] array;
int size;
public MinHeap(int capacity) {
array = new int[capacity];
}
private void heapify() {
for (int i = (size >> 1) - 1; i >= 0; i--) {
down(i);
}
}
public int poll() {
swap(0, size - 1);
size--;
down(0);
return array[size];
}
public int poll(int index) {
swap(index, size - 1);
size--;
down(index);
return array[size];
}
public int peek() {
return array[0];
}
public boolean offer(int offered) {
if (size == array.length) {
return false;
}
up(offered);
size++;
return true;
}
public void replace(int replaced) {
array[0] = replaced;
down(0);
}
private void up(int offered) {
int child = size;
while (child > 0) {
int parent = (child - 1) >> 1;
if (offered < array[parent]) {
array[child] = array[parent];
} else {
break;
}
child = parent;
}
array[child] = offered;
}
private void down(int parent) {
int left = (parent << 1) + 1;
int right = left + 1;
int min = parent;
if (left < size && array[left] < array[min]) {
min = left;
}
if (right < size && array[right] < array[min]) {
min = right;
}
if (min != parent) {
swap(min, parent);
down(min);
}
}
// 交换两个索引处的元素
private void swap(int i, int j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}题解public int findKthLargest(int[] numbers, int k) {
MinHeap heap = new MinHeap(k);
for (int i = 0; i < k; i++) {
heap.offer(numbers[i]);
}
for (int i = k; i < numbers.length; i++) {
if(numbers[i] > heap.peek()){
heap.replace(numbers[i]);
}
}
return heap.peek();
}求数组中的第 K 大元素，使用堆并不是最佳选择，可以采用快速选择算法E03. 数据流中第K大元素-Leetcode 703上题的小顶堆加一个方法class MinHeap {
// ...
public boolean isFull() {
return size == array.length;
}
}题解class KthLargest {
private MinHeap heap;
public KthLargest(int k, int[] nums) {
heap = new MinHeap(k);
for(int i = 0; i < nums.length; i++) {
add(nums[i]);
}
}
public int add(int val) {
if(!heap.isFull()){
heap.offer(val);
} else if(val > heap.peek()){
heap.replace(val);
}
return heap.peek();
}
}求数据流中的第 K 大元素，使用堆最合适不过E04. 数据流的中位数-Leetcode 295可以扩容的 heap, max 用于指定是大顶堆还是小顶堆public class Heap {
int[] array;
int size;
boolean max;
public int size() {
return size;
}
public Heap(int capacity, boolean max) {
this.array = new int[capacity];
this.max = max;
}
/**
* 获取堆顶元素
*
* @return 堆顶元素
*/
public int peek() {
return array[0];
}
/**
* 删除堆顶元素
*
* @return 堆顶元素
*/
public int poll() {
int top = array[0];
swap(0, size - 1);
size--;
down(0);
return top;
}
/**
* 删除指定索引处元素
*
* @param index 索引
* @return 被删除元素
*/
public int poll(int index) {
int deleted = array[index];
swap(index, size - 1);
size--;
down(index);
return deleted;
}
/**
* 替换堆顶元素
*
* @param replaced 新元素
*/
public void replace(int replaced) {
array[0] = replaced;
down(0);
}
/**
* 堆的尾部添加元素
*
* @param offered 新元素
*/
public void offer(int offered) {
if (size == array.length) {
grow();
}
up(offered);
size++;
}
private void grow() {
int capacity = size + (size >> 1);
int[] newArray = new int[capacity];
System.arraycopy(array, 0,
newArray, 0, size);
array = newArray;
}
// 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶
private void up(int offered) {
int child = size;
while (child > 0) {
int parent = (child - 1) / 2;
boolean cmp = max ? offered > array[parent] : offered < array[parent];
if (cmp) {
array[child] = array[parent];
} else {
break;
}
child = parent;
}
array[child] = offered;
}
public Heap(int[] array, boolean max) {
this.array = array;
this.size = array.length;
this.max = max;
heapify();
}
// 建堆
private void heapify() {
// 如何找到最后这个非叶子节点 size / 2 - 1
for (int i = size / 2 - 1; i >= 0; i--) {
down(i);
}
}
// 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大
private void down(int parent) {
int left = parent * 2 + 1;
int right = left + 1;
int min = parent;
if (left < size && (max ? array[left] > array[min] : array[left] < array[min])) {
min = left;
}
if (right < size && (max ? array[right] > array[min] : array[right] < array[min])) {
min = right;
}
if (min != parent) { // 找到了更大的孩子
swap(min, parent);
down(min);
}
}
// 交换两个索引处的元素
private void swap(int i, int j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}题解private Heap left = new Heap(10, false);
private Heap right = new Heap(10, true);
/**
为了保证两边数据量的平衡
<ul>
<li>两边数据一样时,加入左边</li>
<li>两边数据不一样时,加入右边</li>
</ul>
但是, 随便一个数能直接加入吗?
<ul>
<li>加入左边前, 应该挑右边最小的加入</li>
<li>加入右边前, 应该挑左边最大的加入</li>
</ul>
*/
public void addNum(int num) {
if (left.size() == right.size()) {
right.offer(num);
left.offer(right.poll());
} else {
left.offer(num);
right.offer(left.poll());
}
}
/**
* <ul>
* <li>两边数据一致, 左右各取堆顶元素求平均</li>
* <li>左边多一个, 取左边元素</li>
* </ul>
*/
public double findMedian() {
if (left.size() == right.size()) {
return (left.peek() + right.peek()) / 2.0;
} else {
return left.peek();
}
}本题还可以使用平衡二叉搜索树求解，不过代码比两个堆复杂
七安前
顺序存储，线性表的删除和插入中出现问题，未知代码哪里出错？
英勇黄铜
【数据结构与算法】(2)基础数据结构 之 数组 动态数组、二维数组详细示例讲解与局限性原理及越界检查
英勇黄铜
【数据结构与算法】(9)基础数据结构 之 阻塞队列的单锁实现、双锁实现详细代码示例讲解
英勇黄铜
【数据结构与算法】(3)基础数据结构 之 链表 单向链表、双向链表、循环链表详细示例讲解
英勇黄铜
【数据结构与算法】(1)初识算法之什么是算法？什么是数据结构？二分查找代码示例
英勇黄铜
【数据结构与算法】(6)基础数据结构之栈的链表实现、环形数组实现示例讲解
英勇黄铜
【数据结构与算法】(4)基础数据结构 之 递归 单路递归、多路递归示例讲解 附单路递归示例
英勇黄铜
【数据结构与算法】(11)基础数据结构 之 二叉树 二叉树的存储与遍历及相关示例 详细代码讲解
英勇黄铜
【数据结构与算法】(10)基础数据结构 之 堆 建堆及堆排序 详细代码示例讲解