刷题笔记8.5-8.9

刷题顺序依照labuladong算法小抄

两数之和(8.5)

1. 初始化数组：

   <code>int[] num = new int<length>;

   int[] num = {1,2,3,4};

   其中数组名代表指针变量，故不可以直接将数组名a赋值给数组名b

   错误的复制：int[] b = a;

2. 数组元素复制：

   假设数组nums的元素复制到numsSort中：

   int[] numsSort = (int[])Arrays.copyOf(nums,nums.length)

   意为为numsSort指向的存储区内开辟nums.length长度的空间，并复制nums

3. 调用Arrays静态类中的方法可以直接操作数组

   1） 数组默认升序排列：Arrays.sort(nums)

4. 使用arraylist.indexOf(Object o)来定位指定元素索引

   第一步：一个数组或者其他集合类创建一个不可变的 List 集合时，我们可以使用 Arrays.asList() 来方便地转换

String[] array = {"a","b","c","d"}; // 现有静态数组或集合

List<String> list = Array.asList(array); // 转换为长度不可变的Arraylist

或者直接赋值

List<String> list = Arrays.asList("a", "b", "c")

第二步：int index = list.indexOf("b");

【注意】

Arrays.asList() 不支持基本数据类型的数组，只能接受 Object 类型的参数或者数组。基本数据类型（如 int, double, char 等）不是 Object 的子类，所以不能直接作为 Arrays.asList() 的参数。

如果传入一个基本数据类型的数组，Arrays.asList() 会把它当作一个 Object 类型的元素，而不是把它的每个元素当作 Object 类型。这样就会导致返回的 List 只有一个元素，就是原始数组本身。

• 如果想要把一个基本数据类型的数组转换成 List

  使用循环遍历数组，并把每个元素添加到 List 中。这样可以利用自动装箱（autoboxing）的特性，把基本数据类型转换成对应的包装类（如 Integer, Double, Character 等）。

List<Integer> list = new ArrayList<>();

int[] array = {1,2,3};

for(int num:array){

list.add(num);

}

刷题总结(8.6）

1. 静态数组在创建的时候就要确定数组的元素类型和元素数量，连续内存必须一次性分配，分配完了之后就不能随意增减了

int[] nums = new int[4];

Java Golang 这种语言，静态数组创建出来后会自动帮你把元素值都初始化为 0，所以不需要再显式进行初始化。

2. 动态数组底层还是静态数组，只是自动帮我们进行数组空间的扩缩容，并把增删查改操作进行了封装，让我们使用起来更方便而已

// 创建动态数组

// 不用显式指定数组大小，它会根据实际存储的元素数量自动扩缩容

ArrayList<Integer> arr = new ArrayList<>();

for (int i = 0; i < 10; i++) {

// 在末尾追加元素，时间复杂度 O(1)

arr.add(i);

}

// 在中间插入元素，时间复杂度 O(N)

// 在索引 2 的位置插入元素 666

arr.add(2, 666);

// 在头部插入元素，时间复杂度 O(N)

arr.add(0, -1);

// 删除末尾元素，时间复杂度 O(1)

arr.remove(arr.size() - 1);

// 删除中间元素，时间复杂度 O(N)

// 删除索引 2 的元素

arr.remove(2);

// 根据索引查询元素，时间复杂度 O(1)

int a = arr.get(0);

// 根据索引修改元素，时间复杂度 O(1)

arr.set(0, 100);

// 根据元素值查找索引，时间复杂度 O(N)

int index = arr.indexOf(666);

3. 广义的（双指针）链表

   数据结构体定义

<code>private static class Node<E> {

E val; // 结点存储的数值

Node<E> next; // 当前结点指向的下一个

Node<E> prev; // 当前结点指向的上一个

Node(Node<E> prev, E element, Node<E> next) {

this.val = element;

this.next = next;

this.prev = prev;

}

}

一条链表并不需要一整块连续的内存空间存储元素。链表的元素可以分散在内存空间的天涯海角，通过每个节点上的 next, prev 指针，将零散的内存块串联起来形成一个链式结构。

刷题总结(8.8)

1. 关于优先级队列：

   使用场景：对k个元素排序，将数组/序列抽象为二叉堆

   使用方法：

• 优先级队列初始化：

// 堆排序伪码，对 arr 原地排序

// 时间复杂度 O(NlogN)，空间复杂度 O(N)

int[] heapSort(int[] arr) {

int[] res = new int[arr.length];

PriorityQueue<int> pq = new MyPriorityQueue<>();

for (int x : arr)

pq.push(x);

// 元素出堆的顺序是有序的

for (int i = 0; i < arr.length; i++)

res[i] = pq.pop();

return res;

}

• 优先级队列按特定规则比较排序

PriorityQueue<ListNode> pq = new PriorityQueue<>(

lists.length, (a, b)->(a.val - b.val));

(a, b)->(a.val - b.val)是一个lambda表达式，它定义了优先队列中元素的排序规则。在Java中，优先队列默认是一个最小堆，这意味着它将根据提供的比较器来维护元素的顺序，使得队列头部始终是“最小”的元素。

a.val - b.val是一个比较操作，它比较两个ListNode对象的val值。根据这个比较结果，优先队列确定元素的顺序，即 如果a.val - b.val的结果小于0，那么a将被视为比b小，a会排在b前面。

综上，上面这段代码表示：优先队列存储着ListNode类型的元素，但队列是按照ListNode对象的val字段进行排序，确保具有最小val值的ListNode对象始终位于队列的头部。

• 注意：优先级队列中的元素不可为空，否则会报java.lang.NullPointerException，在执行pq.add(x)时跟随判断