数据结构和算法之旅（一）- 数组
没有人可以避免使用数组。
在计算机科学中，数组是由一组元素(值或变量)组成的数据结构，每个元素有至少一个索引来标识；因为数组内元素是连续存储的，所以数组中的元素的地址，可以通过其索引计算出来，例如：
数组的特点：随机访问。即根据索引查找元素，时间复杂度是O(1)。
自定义动态数组
数组是静态数组，不能够动态调整大小。Java是有提供好的动态数组，其实就是ArrayList，但目前是为了学习数据结构，下面自己来实现一个动态数组。
package org.example.datastructure;
import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.IntStream;
/**
* 动态数组
*/
public class DynamicArray implements Iterable<Integer> {
private int size = 0;//逻辑大小
private int capacity = 8;//容量 ,java中arraylist默认是10
// private int[] array = new int[capacity];//延迟加载
private int[] array = {};
/**
* 添加元素到数组末尾
*
* @param element 待添加的元素
*/
public void addLast(int element) {
//array[size] = element;
//size++;
add(size, element);
}
/**
* 添加元素到指定位置
*
* @param index 索引位置
* @param element 待添加的元素
* 时间复杂度
* 头部插入：O(n)
* 中间插入：O(n)
* 尾部插入：O(1)
*/
public void add(int index, int element) {
//扩容检查
checkAndGrow();
//检查index是否合法
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("index:" + index + ",size:" + size);
}
//拷贝，把目标index后的元素都往后移动一位
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;
}
}
/**
* 删除指定位置的元素
*
* @param index
* @return
*/
public int remove(int index) {//[0..size)
int removed = array[index];
if (index < size - 1) {
//拷贝，把目标index后的元素都往前移动一位
System.arraycopy(array, index + 1, array, index, size - index - 1);
size--;
}
return removed;
}
/**
* 查询指定位置的元素
*
* @param index 索引
*
* 时间复杂度：O(1)
*/
public int get(int index) {// [0..size)
return array[index];
}
/**
* 使用函数式接口Consumer,遍历数组，
* 对每个元素执行consumer.accept(array[i])，令调用方执行自定义的操作
*
* @param consumer
*/
public void foreach(Consumer<Integer> consumer) {
for (int i = 0; i < size; i++) {
// 提供array[i]
// 返回void
consumer.accept(array[i]);
}
}
/**
* 迭代器遍历
* 实现Iterable接口，使得DynamicArray可以使用foreach语法
*/
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
private int index = 0;
@Override
public boolean hasNext() {
return index < size;//index < size表示还有元素
}
@Override
public Integer next() {
return array[index++];
}
};
}
/**
* 获取流对象
*/
public IntStream stream() {
return IntStream.of(Arrays.copyOfRange(array, 0, size));
}
}System.arraycopy
注： System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length); - src：源数组，即要复制的数组。 - srcPos：源数组的起始位置，从源数组的哪个索引开始复制。 - dest：目标数组，即复制到的数组。 - destPos：目标数组的起始位置，复制到目标数组的哪个索引位置。 - length：要复制的元素数量。 System.arrayCopy 的主要特点和注意事项： 1. **低级别操作：** 这是一种低级别的数组操作，直接在内存中复制数组内容，效率较高。 2. **复制范围控制：** 你可以控制复制的范围，包括源数组的起始位置、目标数组的起始位置和要复制的元素数量。 3. **原地复制：** 它允许在不创建新数组的情况下，将源数组的一部分复制到目标数组中，适用于需要在原地进行数据移动的情况。 4. **数据类型检查：** `System.arrayCopy` 不会进行数据类型检查，因此要确保源和目标数组的数据类型一致，否则可能会导致运行时异常。 5. **不会自动扩展：** 它不会自动扩展目标数组，如果目标数组长度不足以容纳复制的数据，会导致数组越界异常。 6. **效率高：** 由于是底层操作，因此通常情况下比使用迭代或循环来复制数组要更高效
函数式接口
这个很有趣，推荐平常多使用函数式接口来优化代码，这里总结汇总一下吧。
Runnable 和 Callable
Runnable通常用于多线程编程，用于定义线程要执行的任务。它没有输入参数，也没有返回值。Callable类似于Runnable，但允许任务返回结果。通常与线程池一起使用，可以获得任务执行的结果。
// 使用Runnable创建线程任务
Runnable runnable = () -> {
System.out.println("Hello from Runnable");
};
Thread thread = new Thread(runnable);
thread.start();
// 使用Callable和ExecutorService获取线程任务的返回值
Callable<Integer> callable = () -> {
return 42;
};
ExecutorService executorService = Executors.newSingleThreadExecutor();
Future<Integer> result = executorService.submit(callable);
System.out.println("Result from Callable: " + result.get());
executorService.shutdown();Comparator
Comparator用于比较两个对象的顺序。它通常用于集合的排序操作。- 可以使用
Comparator的comparing方法创建比较器，也可以使用reversed方法反转比较器的顺序。
List<String> names = Arrays.asList("Alice", "Bob", "Charlie");
names.sort((s1, s2) -> s1.compareTo(s2));
// 或者使用Comparator.comparing方法
names.sort(Comparator.comparing(String::length));Consumer
- 直译有"消费者"的含义。
Consumer用于接受一个参数并执行操作，通常没有返回值。它常用于集合的遍历和元素处理。- 可以使用
andThen方法组合多个Consumer，形成一个连续的操作链。
List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5);
Consumer<Integer> printSquare = (num) -> System.out.println(num * num);
numbers.forEach(printSquare);Supplier
- 直译有“供应者”的含义。
Supplier通常不接受参数，用于生成一个值。它可以用于延迟加载或惰性计算。- 可以在需要值的地方调用
get方法来获取值。
Supplier<Double> randomNumberSupplier = () -> Math.random();
double randomValue = randomNumberSupplier.get();
System.out.println("Random Value: " + randomValue);Predicate
- 直译有"谓语"的含义。
Predicate接受一个参数并返回布尔值，用于进行条件判断。它通常用于过滤和筛选数据。- 可以使用
and、or和negate方法来组合多个谓词。
List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5);
Predicate<Integer> isEven = (num) -> num % 2 == 0;
List<Integer> evenNumbers = numbers.stream().filter(isEven).collect(Collectors.toList());Function
Function接受一个参数并返回一个值，用于将输入映射到输出。它通常用于数据转换和处理。- 可以使用
andThen和compose方法来组合多个函数，形成一个函数链。
Function<Integer, String> intToString = (i) -> String.valueOf(i);
String stringValue = intToString.apply(42);
System.out.println("String Value: " + stringValue);BiFunction
BiFunction接受两个参数并返回一个值，用于处理两个输入并产生一个输出。它通常用于需要两个输入的操作。
BiFunction<Integer, Integer, Integer> add = (a, b) -> a + b;
int sum = add.apply(3, 5);
System.out.println("Sum: " + sum);