刷題筆記8.5-8.9 刷題順序依照labuladong演算法小抄 兩數之和(8.5) 初始化數組： int[] num = new int<length>; int[] num = {1,2,3,4}; 其中數組名代表指針變數，故不可以直接將數組名a賦值給數組名b 錯誤的複製：int[] b = a ...
刷題筆記8.5-8.9
刷題順序依照labuladong演算法小抄
兩數之和(8.5)
- 初始化數組：
int[] num = new int<length>;
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() 來方便地轉換
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）
- 靜態數組在創建的時候就要確定數組的元素類型和元素數量，連續記憶體必須一次性分配，分配完了之後就不能隨意增減了
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);
- 廣義的（雙指針）鏈表
數據結構體定義
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)
- 關於優先順序隊列：
使用場景：對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)時跟隨判斷
