Array
定義&初始化
兩種格式含義相等鼠渺，只分配了數(shù)組引用的存儲(chǔ)空間眷细，沒(méi)有分配數(shù)組本身的存儲(chǔ)空間溪椎。
int[] a1;
int a1[];
初始化：
int[] a1 = {1,2,3,4,5};
// 默認(rèn)初始化成空值校读，對(duì)于數(shù)字就是0歉秫，對(duì)于布爾型是false
int[] array = new int[10];
對(duì)象數(shù)組保存的是引用雁芙，基本類(lèi)型數(shù)組直接保存數(shù)組的值兔甘。如下創(chuàng)建了一個(gè)引用數(shù)組：
Integer[] a = new Integer[20];
直到通過(guò)創(chuàng)建新的Integer對(duì)象裂明，并把對(duì)象賦值給引用闽晦，初始化才算結(jié)束仙蛉。
復(fù)制
有三種方法荠瘪，都是淺復(fù)制（Shallow Copy）
1.Arrays.copyOf(AnyType[] arr, int len)
2.System.arraycopy
3.arr.clone() 會(huì)聲明新數(shù)組
多維數(shù)組
int[][] a = {{1,2,3}, {4,5,6}}
int[][] dir = new int[][] {(0,1),(0,-1),(1,0),(-1,0)};
int[][] dir = new int[][] {{0,1},{0,-1},{1,0},{-1,0}};
求長(zhǎng)度
所有數(shù)組都有一個(gè)固有成員length哀墓，可以獲取數(shù)據(jù)元素的數(shù)量篮绰，但不能修改吠各。
array.length
排序
1.實(shí)現(xiàn)Comparable接口贾漏，并且使用標(biāo)準(zhǔn)類(lèi)庫(kù)的方法Arrays.sort()
2.創(chuàng)建一個(gè)實(shí)現(xiàn)了Comparator的單獨(dú)的類(lèi)
public class Interval {
int start;
int end;
}
Interval[] intervals;
Arrays.sort(intervals, new Comparator<Interval>() {
public int compare(Interval i1, Interval i2) {
return i1.start - i2.start;
}
});
查找
如果數(shù)組已經(jīng)排好序了纵散，就可以使用Arrays.binarySearch()執(zhí)行快速查找伍掀。
List
Collection是一個(gè)高級(jí)接口符匾，包括List, Set, Queue三個(gè)子接口瘩例。
實(shí)現(xiàn)List接口的常用類(lèi)有ArrayList, LinkedList, Vector, Stack, 其中前三種支持?jǐn)?shù)據(jù)的線性存儲(chǔ)和定位焰坪。
ArrayList
擴(kuò)容：
Reverse linked list
兩種解法：1.Iterative 2.Recursive
LinkedList:
方法：
addFirst(object)
addLast(object)
getFirst()
getLast()
removeFirst()
removeLast()
LinkedList<Integer> q = new LinkedList<Integer>();
q.pollFirst();
q.pollLast();
q.peekFirst();
Thread Safe Lists
Java提供了兩種方便的機(jī)制：
1.Collections.sychronizedList
2.Vector
Stack:
實(shí)現(xiàn)
Java中的棧是線程安全的數(shù)據(jù)結(jié)構(gòu)
構(gòu)造
Deque<Integer> stack = new ArrayDeque<Integer>();
方法push, pop
相關(guān)題目
Min Stack
程序里檢測(cè)括號(hào)是否對(duì)稱(chēng)
Queue:
Java中Queue接口主要方法是poll()和offer()
Queue的實(shí)現(xiàn)方法：
1.用LinkedList，維護(hù)head和rear
2.用Array炬守，維護(hù)頭尾兩個(gè)index减途，頭尾相碰時(shí)進(jìn)行resize
3.用Stack鳍置，相關(guān)題目：Implement queue using stacks
注意
1.Queue不是線程安全的怕轿，Java中線程安全的Queue是Blocking Queue
Java中的阻塞隊(duì)列
2.Deque接口是Stack和Queue的結(jié)合撤卢，可以通過(guò)它在線性結(jié)構(gòu)頭尾兩段自由地存取元素放吩。ArrayDeque可以自動(dòng)擴(kuò)容，但不是線程安全的惕澎，實(shí)現(xiàn)原理就是循環(huán)數(shù)組，因而比Stack和LinkedList快八孝。
ArrayDeque接口：
addFirst(object)
addLast(object)
getFirst()
getLast()
removeFirst()
removeLast()
構(gòu)造
Deque<Integer> queue = new ArrayDeque<Integer>();
queue.add, queue.poll
queue.addLast()
queue.pollFirst()
Queue的應(yīng)用
BFS里用到queue祟绊，用queue做逐層記錄牧抽。
Heap：
Min heap:最大的k個(gè)數(shù)
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> (a.val > b.val ? 1 : -1)); 小根堆记舆？
final PriorityQueue<Integer> pq = new PriorityQueue<>();//minHeap
final PriorityQueue<Integer> pq = new PriorityQueue<>(1000, Collections.reverseOrder());//maxHeap
pq.add(), pq.poll(), pq.peek()
ArrayList:
Object[] = list.toArray()
HashMap:
map.getOrDefault(n,0)
map.containsKey()
Tree
BitSet:
bitset.set()
bitset.get()
bitset.nextClearBit()
bitset.clear()
String:
char charAt(int index);
char[] toCharArray();
String.substring(int beginIndex, int endIndex);
StringBuilder vs StringBuffer
問(wèn)題：HashTable的實(shí)現(xiàn)
線程安全的List
