Array & List
// 排序
int[] array = {3, 4, 1, 2, 5};
Arrays.sort(array); // T = O(n * log2(n))
List<Integer> list = Arrays.asList(array);
Collections.sort(list); // 使用ArrayList的话，T = O(n * log2(n))
list.sort(null); // 上面的函数调用这个函数，其内部实现方法是先把列表转换为数组再排序
// 因为如果是链表，直接排序的时间复杂度为O((n ^ 2) * log2(n))。
// array和list转换
List<String> list = Arrays.asList(array);
String[] array = list.toArray(new String[0]);
// max & min
Map<String, Integer> map = ...;
// 找出具有最大value值的key
String max = Collections.max(
map.entrySet(),
Comparator.comparingInt(Map.Entry<String, Integer>::getValue)).getKey();
// 或者
max = Collections.max(
map.entrySet(),
Map.Entry.comparingByValue()).getKey();
// 这些其实没什么必要，面试时记不住就用循环解决
// string
String str = "aaa bbb ccc";
String[] parts = str.split(" "); // {"aaa", "bbb", "ccc"}
String[] parts1 = str.split(" ", 2); // {"aaa", "bbb ccc"}
String[] parts2 = str.split(" ", -1); // -1的意思是不要删除最后面的空字符
另外，Java的Collection由于只接受对象形式的元素（就是说不能用基本数据类型的元素），加上其维护代码的开销，性能往往比数组差。比如int[]比ArrayList<Integer>要快，尤其是在比拼算法所用时间的情况下尤为明显。
Stack
“Stack”是Java中关于栈的旧API。现在应该使用Deque。LIFO。
Deque<String> stack = new ArrayDeque<>();
stack.push("abc");
String s1 = stack.peek();
String s2 = stack.pop();
Queue
普通的队列，在Java中一般是以LinkedList的方式实现的。Queue常用于广度优先搜索算法。FIFO。
Queue<String> queue = new LinkedList<>();
queue.offer("abc"); // enqueue
String s = queue.poll(); // dequeue
Priority Queue
Priority Queue常被用来在不排序的情况下取最大的或最小的几个值。如果有n个数据元素，要取前k个（k<n）最小的元素，用排序法的话T=O(n * log2(n))，而用Priority Queue的话，则为T=O(n * log2(k))，这样就能快一些。方法是往queue里逐个放入数据元素，如果queue的长度大于k，则把一个元素移出（也就是最大的那个或最小的那个，取决于Priority Queue的设定方式。这样，剩下的就是k个最小的或最大的元素。
Priority Queue的时间复杂度：enqueue和dequeue操作为O(log2(k))，查看（peek）最前面的元素为O(1)。
PriorityQueue<Elem> queue = new PriorityQueue<>(Comparator.comparingInt(Elem::getValue));
for (Elem elem : list) {
queue.offer(elem);
if (queue.size() > k) {
queue.poll();
}
}
上面的代码中的queue.poll()会把Elem.getValue()返回值最小的元素移出。要想移出最大的，则改为Comparator.comparingInt(elem -> -elem.getValue())。
另一个应用的例子：合并k个有序列表。一般的算法为取各列表的第一个元素，找到最小的那个，加入新列表，然后把最小元素的下一个元素作为它原所属列表的第一个元素。不断重复，直到用完所有列表的元素。这样做的话，T=O(N * k)，其中N为所有列表中的元素总数，k为列表个数。因为每次从k各元素中取最小值为O(k)，而对所有元素都要进行一次这样的操作，故为O(N * k)。
可以用Priority Queue进行优化：把各列表的第一个元素加入queue；取出最前面的元素加入新列表，并把它的下一个元素加入queue。这样的话，每次enqueue和dequeue操作为O(log2(k))，对所有元素做这种操作，总体的时间复杂度T=O(N * log2(k))，比上述的O(N * k)要快。
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
if (lists.length == 1) {
return lists[0];
}
PriorityQueue queue = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
for (ListNode node : lists) {
if (node == null) {
continue;
}
queue.offer(node);
}
ListNode dummyHead = new ListNode(0);
ListNode prev = dummyHead;
while (!queue.isEmpty()) {
ListNode node = queue.poll();
prev.next = node;
prev = node;
if (node.next != null) {
queue.offer(node.next);
node.next = null;
}
}
return dummyHead.next;
}
题外话：另一种十分简单的解法是Divide & Conquer：合并两个有序列表（按第一种思路）的时间复杂度是O(n)，n是两个列表中的元素总和。可以把k个列表两两分组，并将其合并成一组更长的列表；然后继续两两分组合并，直到最后只剩一个列表为止。这看起来跟体育比赛分组类似，没什么特别的，但观察一下的话，一共有log2(k)轮的分组，每轮都要遍历所有N个元素，因此，时间复杂度也是O(N * log2(k))。
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
if (lists.length == 1) {
return lists[0];
}
int i = 0;
List mergedList = new ArrayList<>();
// 两两分组合并。merge2()的作用是普通的合并两个有序列表。
while (i < lists.length) {
ListNode node1 = lists[i];
if (++i < lists.length) {
mergedList.add(merge2(node1, lists[i++]));
} else {
mergedList.add(node1);
}
}
return mergeKLists(mergedList.toArray(new ListNode[0]));
}
Map
HashMap经常用来提高程序的效率。写入（put）、查找（contains）和取值（get）都为O(1)。这里有一些简单写法：
// 计数：记录相同词语出现的次数
Map<String, Integer> map = new HashMap<>();
for (String s : list) {
map.merge(s, 1, Integer::sum); // 如果没有，值设为1；否则，在原来的基础上加1
}
// map的值为一个列表。如果不存在，创建列表。
// key为字符串，value为储存字符串索引位置的列表
Map<String, List<Integer>> map = new HashMap<>();
for (int i = 0; i < list.size(); ++i) {
map.computeIfAbsent(list.get(i), k -> new ArrayList<>()).add(i);
}
Bitwise & Bit Shift Operations
// Unary bitwise complement (~)
int n = ~5; // ~0101 --> 1010
// Bitwise AND (&)
int m = 0b0001;
int result = n & m; // 1010 -> 0000
// Bitwise inclusive OR (|)
result = n | m; // 1011
// Bitwise exclusive OR (XOR) (^)
result = n ^ 0b1111; // 1010 --> 0101
// Signed left shift (<<): shift once results integer x 2
result = 8 << 1; // 16
result = -8 << 1; // -16
// Signed right shift (>>): shift to right and fill 0 on left, but keep leftmost bit.
// shift once results integer / 2
result = 8 >> 1; // 4
result = -8 >> 1; // -4
// Unsigned right shift (>>>): shift to right and fill 0 on left.
result = 8 >>> 1; // 4
result = -8 >>> 1; // 2147483644
一些常用的用法：
// 乘或除2的n次方
int result = 3 << 4; // 3 * (2 ^ 4)
result = 32 >> 3; // 32 / (2 ^ 3)
// 判断奇偶
boolean isEven = (123 & 1) == 0; // 注意由于优先级的原因，应使用括号
// 判断某位是否为1（比如每个位表示一种flag）
int mask = 0b0010;
boolean isSecondBitFromRightSet = (7 & mask) == mask; // 7 = 0b0111, 7 & mask = 0b0010
// XOR:
// a XOR a = 0
// a XOR 0 = a
// a XOR b XOR c = a XOR (b XOR c)
// a XOR b XOR b = a
Trie
Trie又名“前缀树”，用于根据前缀查找词汇。典型的应用包括：自动完成、拼写检查、IP路由、解字谜等等。哈希表虽说查找的时间复杂度为O(1)，但在查找相同前缀的词汇时就缺乏效率了。而且如果输入了大量的词汇的话，还有因哈希冲突而导致的效率下降。
如果输入的词汇数量为n，查找的前缀长度为m，那么查找的时间复杂度为O(m)。
这里是一个简单的实现：
public class Trie {
public static class Node {
private String word;
private final Map<Character, Node> childrenMap = new HashMap<>();
public Node() {
// empty
}
public boolean hasChild(char c) {
return childrenMap.containsKey(c);
}
public Node getChild(char c) {
return childrenMap.get(c);
}
public Node addChild(char c) {
return childrenMap.computeIfAbsent(c, k -> new Node());
}
public void setWord(String str) {
this.word = str;
}
public String getWord() {
return word;
}
}
private final Node root = new Node();
public Trie() {
// empty
}
// 输入一个词汇
public void insert(String word) {
Node node = root;
for (char c : word.toCharArray()) {
node = node.addChild(c);
}
node.setWord(word);
}
// 查看是否有该词汇
public boolean search(String word) {
Node node = root;
for (char c : word.toCharArray()) {
node = node.getChild(c);
if (node == null) {
return false;
}
}
return node.getWord() != null;
}
// 查看是否有以该前缀开始的词汇
public boolean startsWith(String prefix) {
Node node = root;
for (char c : prefix.toCharArray()) {
node = node.getChild(c);
if (node == null) {
return false;
}
}
return true;
}
}
如果词汇的组成字符是有限的（比如小写英文单词由26个字母组成），另一种实现方法是用一个数组代替Trie.Node中的HashMap。我个人不太喜欢这种方法。但是用Java语言的时候，讽刺的是这种方法往往能快一点点。
public static class Node {
private static final int N = 26; // 字符总数
private Node[] links = new Node[N]; // 查找时用索引 int i = c - 'a';
// 用flag代替上面的字符串能节省点空间。
// 用字符串的目的是在需要得到词汇时不用从头遍历到目前结点，而是能直接拿到
private boolean end = false;
// ...
private int getIndex(char c) {
return c - 'a';
}
public boolean contains(char c) {
return get(c) != null;
}
public Node get(char c) {
return links[getIndex(c)];
}
// ...
}
