leetcode刷题笔记8.5-8.9

刷题笔记8.5-8.9

刷题顺序依照labuladong算法小抄
两数之和(8.5)

• 初始化数组：
  int[] num = new int;
  int[] num = {1,2,3,4};
  其中数组名代表指针变量，故不可以直接将数组名a赋值给数组名b
  错误的复制：int[] b = a;
  
• 数组元素复制：
  假设数组nums的元素复制到numsSort中：
  int[] numsSort = (int[])Arrays.copyOf(nums,nums.length)
  意为为numsSort指向的存储区内开辟nums.length长度的空间，并复制nums
  
• 调用Arrays静态类中的方法可以直接操作数组
  1） 数组默认升序排列：Arrays.sort(nums)
  
• 使用arraylist.indexOf(Object o)来定位指定元素索引
  第一步：一个数组大概其他集合类创建一个不可变的 List 集合时，我们可以使用 Arrays.asList() 来方便地转换
  

1. String[] array = {"a","b","c","d"}; // 现有静态数组或集合
2. List<String> list = Array.asList(array); // 转换为长度不可变的Arraylist

复制代码

大概直接赋值

1. 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 等）。
  

1. List<Integer> list = new ArrayList<>();
2. int[] array = {1,2,3};
3. for(int num:array){
4.   list.add(num);
5. }

复制代码

刷题总结(8.6）

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

1. int[] nums = new int[4];

复制代码

Java Golang 这种语言，静态数组创建出来后会自动帮你把元素值都初始化为 0，所以不需要再显式进行初始化。
2. 动态数组底层还是静态数组，只是自动帮我们进行数组空间的扩缩容，并把增删查改操作进行了封装，让我们使用起来更方便而已

1. // 创建动态数组
2. // 不用显式指定数组大小，它会根据实际存储的元素数量自动扩缩容
3. ArrayList<Integer> arr = new ArrayList<>();
5. for (int i = 0; i < 10; i++) {
6.     // 在末尾追加元素，时间复杂度 O(1)
7.     arr.add(i);
8. }
10. // 在中间插入元素，时间复杂度 O(N)
11. // 在索引 2 的位置插入元素 666
12. arr.add(2, 666);
14. // 在头部插入元素，时间复杂度 O(N)
15. arr.add(0, -1);
17. // 删除末尾元素，时间复杂度 O(1)
18. arr.remove(arr.size() - 1);
20. // 删除中间元素，时间复杂度 O(N)
21. // 删除索引 2 的元素
22. arr.remove(2);
24. // 根据索引查询元素，时间复杂度 O(1)
25. int a = arr.get(0);
27. // 根据索引修改元素，时间复杂度 O(1)
28. arr.set(0, 100);
30. // 根据元素值查找索引，时间复杂度 O(N)
31. int index = arr.indexOf(666);

复制代码

• 广义的（双指针）链表
  数据布局体界说
  

1. private static class Node<E> {
2.     E val; // 结点存储的数值
3.     Node<E> next; // 当前结点指向的下一个
4.     Node<E> prev; // 当前结点指向的上一个
6.     Node(Node<E> prev, E element, Node<E> next) {
7.         this.val = element;
8.         this.next = next;
9.         this.prev = prev;
10.     }
11. }

复制代码

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

• 关于优先级队列：
  使用场景：对k个元素排序，将数组/序列抽象为二叉堆
  使用方法：
  

• 优先级队列初始化：
  

1. // 堆排序伪码，对 arr 原地排序
2. // 时间复杂度 O(NlogN)，空间复杂度 O(N)
3. int[] heapSort(int[] arr) {
4.     int[] res = new int[arr.length];
5.     PriorityQueue<int> pq = new MyPriorityQueue<>();
6.     for (int x : arr)
7.         pq.push(x);
8.     // 元素出堆的顺序是有序的
9.     for (int i = 0; i < arr.length; i++)
10.         res[i] = pq.pop();
11.     return res;
12. }

复制代码

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

1. PriorityQueue<ListNode> pq = new PriorityQueue<>(
2.             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)时跟随判断
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。