刷题笔记8.5-8.9

刷题顺序依照labuladong算法小抄

两数之和(8.5)

1. 初始化数组：
   int[] num = new int;
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 list = Array.asList(array); // 转换为长度不可变的Arraylist

或者直接赋值

List 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 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 arr = new ArrayList();

for (int i = 0; i 

3. 广义的（双指针）链表
   数据结构体定义

private static class Node {
    E val; // 结点存储的数值
    Node next; // 当前结点指向的下一个
    Node prev; // 当前结点指向的上一个

    Node(Node prev, E element, Node 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 pq = new MyPriorityQueue();
    for (int x : arr)
        pq.push(x);
    // 元素出堆的顺序是有序的
    for (int i = 0; i 

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

PriorityQueue 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)时跟随判断