- while循环如果确定只执行一次，那其实和if一样，while可以换成if。e.g.239
- Arrays.asList()里面的参数不能是基本类型数组
- System.out.println(Arrays.asList(res)); 输出的是res数组的地址 System.out.println(Arrays.toString(res)); 输出的res数组的内容
图的三种表示方式：Edgelists, Adjacency matrices, Adjacency lists(省空间)
https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs存一个图：adjacent list。如果时间足够，用自定义节点类DirectedGraphNode or UndirectedGraphNode。
~~建议用ArrayList，而不是HashMap，因为有时候会TLE ~~ （只针对LeetCode情况，不要被误导）。但是如果图的节点不是0到N-1，或者1到N，只能用HashMap存了，key是父亲节点，用Integer，value是子节点，用ArrayList，比如582. Kill Process。
面试中，存图，建议直接用HashMap，这样更General。
二叉树中进行 BFS 和图中进行 BFS 最大的区别就是二叉树中无需使用HashSet/visited数组（C++: unordered_map, Python: dict) 来存储访问过的节点（丢进过 queue 里的节点）因为二叉树这种数据结构，上下层关系分明，没有环（circle），所以不可能出现一个节点的儿子的儿子是自己的情况。但是在图中，一个节点的邻居的邻居就可能是自己了图的BFS用到的数据结构：ArrayList + visited数组/HashSet + Queue
visited数组的优点：可以有多个状态，比汝0 1 2。e.g. 261.Graph Valid Tree方向数组的几种写法：上下左右
int[][] dirs = ; 推荐这种，可以用for-each遍历
int[] dx = {-1, 1, 0, 0}; int[] dy = {0, 0, -1, 1};表示矩阵中点的方法：
用长度为2的一维数组int[]；推荐这种，省时间
自定义Point class；给二维数组某一整行赋值：// res[i][0] = r0; // res[i][1] = c0;
res[i] = new int[]{r0, c0};在Java中只有一维数组。二维数组本质上也是一维数组,只是数组中的每一个元素都指向了另一个一维数组而已。因此每行的个数可以不一样。
(double) (target - cars[i][0]) / cars[i][1] 只需最前面的(double)，cars[i][1]前面不用加(double)
diff1.equals("" + diff2.charAt(1) + diff2.charAt(0)) 如果不加“”，diff2.charAt(1) + diff2.charAt(0)返回的是int
O(n^3)的时间复杂度有时可以降到O(n^2)，通过增加O(n^2)的空间复杂度 e.g. _778SwimInRisingWater
list转为array：list.toArray(new T[list.size()]); // list.size()可以写成0 T不能是基本数据类型
set转为array：set.toArray(new T[set.size()]); // list.size()可以写成0 T不能是基本数据类型
array转为list: Arrays.asList(array);
array转为set: new HashSet<>(Arrays.asList(array));
List<Integer> list = Arrays.asList(3, 5, 5, 6);// Collections.sort(list, (a, b) -> b.getValue() - a.getValue());
list.sort((a, b) -> b.getValue() - a.getValue()); 这种短，如果排序list
输出数组，Arrays.toString(arr)，
list直接放进就行。System.out.println(list); List<List<Integer>> 也可以直接输出
List<int[]>不能直接输出，只能for循环，所以面试中如果要输出，还是改成List<List<Integer>>好
添加时这么写：res.add(new ArrayList<>(Arrays.asList(1, 2, 3)));if (i % 3 == 0 && i % 5 == 0) { // can be simplified to i % 15 == 0
List和Array组合
List<List<Integer>> 一般用这个构建图
List<int[]> array in list
List<Integer>[] list in array 这种写法用于构建图也是不错的，但是可能面试官看不懂
int[][]
用HashMap对一个数组nums计数
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
简化else if，即else中如果只有一个if块，可以写成else if
if (s.charAt(i) != '#') {
temp.append(s.charAt(i));
} else {
if (temp.length() != 0) { //这种形式的else if可以简化写成下面的形式。
temp.deleteCharAt(temp.length() - 1);
}
}
if (s.charAt(i) != '#') {
temp.append(s.charAt(i));
} else if (temp.length() != 0) {
temp.deleteCharAt(temp.length() - 1);
}
简化
if (e2a.containsKey(e)) {
uf.connect(e2a.get(e), i);
e2a.put(e, uf.find(i));
} else {
e2a.put(e, uf.find(i));
}
if (e2a.containsKey(e)) {
uf.connect(e2a.get(e), i);
}
e2a.put(e, uf.find(i));
DirectedGraphNode & UndirectedGraphNode
class DirectedGraphNode {
int label;
List<DirectedGraphNode> neighbors;
...
}
class UndirectedGraphNode { //无向图的表示方法，要会
int label;
List<UndirectedGraphNode> neighbors;
UndirectedGraphNode(int x) {
label = x;
neighbors = new ArrayList<>();
}
}
Union Find
class UnionFind {
private int[] father;
private int count; // 当需要检查集合数量时，加上这个变量，很常用
// an extra variable to record the number of reduced subsets
// can't be initialized in the constructor since the total number of initial subsets depends on '1'
// so use another variable in main function to record the total number
public UnionFind(int n) {
father = new int[n];
count = n; // 有的时候，count会在主函数里面用一个total变量赋值，以节省代码
for (int i = 0; i < n; i++) {
father[i] = i;
}
}
public int find(int x) {
if (father[x] == x) {
return x;
}
return father[x] = find(father[x]); // path compression. return find(father[x]);
}
public void connect(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA != rootB) {
father[rootA] = rootB; // unite 2 subsets, the count of subsets decreases by one
count--; // 用--比较好，保持统一
}
}
}