数据结构 1 线性数据结构 1.1 数组 1.2 链表 1.3 栈 1.4 队列 2 图 2.1 基本概念 2.2 图的存储 2.3 图的搜索 2.3.1 DFS public int[] findOrder(int numCourses, int[][] prerequisites) { // adjacency list Set<Integer>[] graph = new Set[numCourses]; for (int[] e : prerequisites) { // e[0] depends on e[1] // e[1] --> e[0] if (graph[e[1]] == null) { graph[e[1]] = new HashSet<>(); } graph[e[1]].add(e[0]); } List<Integer> list = new ArrayList<>(numCourses); boolean[] globalVisited = new boolean[numCourses]; boolean[] localVisited = new boolean[numCourses]; // to check cycle for (int i = 0; i < numCourses; ++i) { if (!dfs(graph, i, globalVisited, localVisited, list)) { return new int[0]; } } // copy and reverse int[] result = new int[numCourses]; for (int i = 0; i < numCourses; ++i) { result[i] = list.get(numCourses - i - 1); } return result; } // return: can finish public boolean dfs(Set<Integer>[] graph, int node, boolean[] globalVisited, boolean[] localVisited, List<Integer> list) { if (localVisited[node]) return false; if (globalVisited[node]) return true; localVisited[node] = true; globalVisited[node] = true; Set<Integer> next = graph[node]; if (next != null) { for (Integer n : next) { if (!dfs(graph, n, globalVisited, localVisited, list)) { // return false and exit, no need to reset localVisited return false; } } } localVisited[node] = false; // reset list.add(node); return true; } 2.4 图的路径 2.4.1 弗洛伊德 class Solution { public int networkDelayTime(int[][] times, int N, int K) { // w[i][j]: time from [i] to [j], Integer.MAX_VALUE: inf int[][] w = new int[N+1][N+1]; for (int i = 1; i <= N; ++i) { Arrays.fill(w[i], Integer.MAX_VALUE); w[i][i] = 0; } for (int[] e : times) { int u = e[0], v = e[1], t = e[2]; w[u][v] = t; } for (int k = 1; k <= N; ++k) { for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { int sum; if (w[i][k] == Integer.MAX_VALUE w[k][j] == Integer.MAX_VALUE) { sum = Integer.MAX_VALUE; } else { sum = w[i][k] + w[k][j]; } w[i][j] = Math.min(w[i][j], sum); } } } int max = -1; for (int j = 1; j <= N; ++j) { if (w[K][j] == Integer.MAX_VALUE) return -1; max = Math.max(max, w[K][j]); } return max; } } 2.4.2 Dijkstra class Solution { public int networkDelayTime(int[][] times, int N, int K) { // graph[i]: List<int[]>, [to node, w] List<int[]>[] graph = new List[N+1]; for (int i = 1; i <= N; ++i) { graph[i] = new LinkedList<>(); } for (int[] e : times) { int from = e[0], to = e[1], w = e[2]; graph[from].add(new int[]{to, w}); } // [distance, node] PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]); // node --> min distance HashMap<Integer, Integer> dist = new HashMap<>(); heap.offer(new int[]{0, K}); while (heap.size() > 0) { int[] n = heap.poll(); int distance = n[0]; int node = n[1]; if (dist.containsKey(node)) continue; // already determined dist.put(node, distance); // node determined for (int[] g : graph[node]) { int nextNode = g[0]; int w = g[1]; // K --> ... --> node --> nextNode if (dist.containsKey(nextNode)) continue; // alreay determined heap.offer(new int[]{distance + w, nextNode}); } } if (dist.size() != N) return -1; int max = -1; for (int d : dist.values()) { max = Math.max(max, d); } return max; } } 2.5 图的出入度问题 class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { Map<Integer, List<Integer>> graph = new HashMap<>(); int[] indegree = new int[numCourses]; for (int[] e : prerequisites) { // e[0] depends on e[1] // e[1] --> e[0] int pre = e[1], cur = e[0]; List<Integer> list = graph.get(pre); if (list == null) { list = new LinkedList<>(); graph.put(pre, list); } list.add(cur); indegree[cur]++; } Queue<Integer> queue = new LinkedList<>(); for (int i = 0; i < numCourses; ++i) { if (indegree[i] == 0) { queue.add(i); } } int[] result = new int[numCourses]; int size = 0; while (queue.size() > 0) { int node = queue.poll(); result[size++] = node; List<Integer> next = graph.get(node); if (next != null) { for (int n : next) { indegree[n]--; if (indegree[n] == 0) { queue.offer(n); } } } } if (size != numCourses) return new int[0]; return result; } } 2.6 最小生成树 2.6.1 Kruskal class Solution { public int minimumCost(int N, int[][] connections) { // sort connections by cost from small to large Arrays.sort(connections, (a,b) -> a[2]-b[2]); int[] parent = new int[N+1]; for (int i = 1; i <= N; ++i) { parent[i] = i; } int cost = 0; for (int[] edge : connections) { if (union(edge[0], edge[1], parent)) { cost += edge[2]; } } // check if all the roots are the same int p = -1; for (int i = 1; i <= N; ++i) { int root = findRoot(i, parent); if (p == -1) { p = root; } else if (p != root) { return -1; } } return cost; } public int findRoot(int x, int[] parent) { while (x != parent[x]) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; } public boolean union(int a, int b, int[] parent) { a = findRoot(a, parent); b = findRoot(b, parent); if (a == b) return false; parent[a] = b; return true; } } 2.6.2 Prim class Solution { public int minimumCost(int N, int[][] connections) { int INF = Integer.MAX_VALUE; // graph[i][j]: // INF: not reachable // x: distance int[][] graph = new int[N+1][N+1]; for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { if (i == j) graph[i][j] = 0; else graph[i][j] = INF; } } for (int[] edge : connections) { int u = edge[0], v = edge[1], w = edge[2]; graph[u][v] = graph[v][u] = w; } // dist[i] // d: current min distance from one of added nodes // INF: distance is inf, not reachable int[] dist = new int[N+1]; Arrays.fill(dist, INF); // added nodes boolean[] added = new boolean[N+1]; // set node [1] as candidates dist[1] = 0; int cost = 0; for (int k = 0; k < N; ++k) { // N nodes to add // find node with min distance int min = INF; int node = -1; for (int i = 1; i <= N; ++i) { if (!added[i] && dist[i] < min) { min = dist[i]; node = i; } } // no reachable node found if (node == -1) { return -1; } // add [node] cost += dist[node]; added[node] = true; // update dist[i] with distance from [node] to [i] for (int i = 1; i <= N; ++i) { if (added[i]) continue; if (graph[node][i] == INF) continue; dist[i] = Math.min(dist[i], graph[node][i]); } } return cost; } } 3 堆 3.1 概念 3.2 分类 3.3 存储 3.4 操作 3.5 排序 4 树 4.1 分类 4.2 存储 4.3 遍历 5 红黑树 5.1 概念与特点 红黑树是一种自平衡二叉查找树。JDK中，TreeMap、TreeSet以及HashMap都使用了红黑树。
...