二叉樹面試題
圖(Graph)：是一種復雜的非線性表結構。
頂點：圖中的元素我們叫做頂點(vertex)。
邊：圖中的一個頂點可以與任意其他頂點建立連接關系。我們把這種建立的關系叫做邊(edge)。
度：跟頂點相連接的邊的條數叫做度(degree)。
出度：指向別人的數量。
入度: 指向自己的數量。
有向圖：邊有方向的圖，比如A點到B點的直線距離，微信的添加好友是雙向的
無向圖：邊無方向的圖，當然無向圖可以理解成特殊的有向圖。
帶權圖:在帶權圖中，每條邊都有一個權重(weight)，我們可以通過這個權重 來表示 一些可度量的值。
鄰接矩陣的本質是二維數組，∞表示沒有連線，1 表示有連線。
1. 通過二維數組，我們可以很快的找到一個頂點和哪些頂點有連線。（比如 A頂點,只需要 遍歷第一行即可）
2. 另外，A - A，B - B（也就是頂點到自己的連線），通常使用∞表示。
1)如果是一個無向圖，鄰接矩陣展示出來的二維數組，其實是一個對稱圖。也就是 A -> D 是 1 的時候，對稱的位置 D -> 1 一定也是 1。那么這種情況下會造成空間的浪費。
2)鄰接矩陣還有一個比較嚴重的問題就是如果圖是一個稀疏圖，如果矩陣中將存在大量的∞，這意味著我們浪費了計算機存儲空間來表示根本不存在的邊。而且即使只有一個邊，我們也必須遍歷一行來找出這個邊，也浪費很多時間。
鄰接表由圖中每個頂點以及和頂點相鄰的頂點列表組成。這個列表有很多中方式來存儲：數組/鏈表/字典(哈希表)都可以。比如我們要表示和 A 頂點有關聯的頂點（邊），A 和 B/C/D 有邊，那么我們可以通過 A 找到 對應的數組/鏈表/字典，再取出其中的內容就可以了。
鄰接表計算“出度”是比較簡單的（出度：指向別人的數量, 入度: 指向自己的數量），計算有向圖的“入度”，那么是一件非常麻煩的事情。
封裝圖中的節點類，屬性包括節點對應的值value，收斂進來的節點個數in，發散出去的節點個數out,從該節點發散出去并直接相連的節點nexts，該節點包含的邊數edges;
圖算法面試題
排序面試題
線性表面試題
高頻算法面試題
public class Node {
public int value;
public int in;
public int out;
public ArrayList<Node> nexts;
public ArrayList<Edge> edges;
public Node(int value) {
this.value = value;
in = 0;
out = 0;
nexts = new ArrayList<>();
edges = new ArrayList<>();
}
}
封裝圖中的邊類，屬性包括權重weight，邊的起始節點from，邊的末尾節點to
public class Edge {
public int weight;
public Node from;
public Node to;
public Edge(int weight, Node from, Node to) {
this.weight = weight;
this.from = from;
this.to = to;
}
}
封裝圖類，屬性包括所有的節點nodes和所有的邊edges
public class Graph {
public HashMap<Integer, Node> nodes;
public HashSet<Edge> edges;
public Graph() {
nodes = new HashMap<>();
edges = new HashSet<>();
}
}
寬度優先搜索又叫廣度優先。該算法會從指定的第一個頂點開始遍歷圖，先訪問其所有的相鄰點，就像一次訪問圖的一層。換句話說，就是先寬后深的訪問頂點。
思路：
1. 首先準備一個隊列queue和一個輔助set集合
2. 將指定的第一個頂點入隊queue,并添加到set集合里面
3. 隊列里面的一個頂點出隊并輸出該頂點的值
4. 遍歷該頂點的相鄰頂點，如果set集合里面不包含相鄰頂點cur，則將cur入隊并加入到set集合里面
5. 【3,4】步驟周而復始一次迭代。
//從node出發，進行寬度優先遍歷
public static void bfs(Node node) {
if (node == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
HashSet<Node> set = new HashSet<>();
queue.add(node);
set.add(node);
while (!queue.isEmpty()) {
Node cur = queue.poll();
System.out.println(cur.value);
for (Node next : cur.nexts) {
if (!set.contains(next)) {
set.add(next);
queue.add(next);
}
}
}
}
深度優先搜索算法將會從第一個指定的頂點依次沿著路徑訪問。直到這條路徑最后被訪問了則原路回退并探索下一條路徑。
思路：
1. 首先準備一個棧stack和一個輔助set集合
2. 將指定的第一個頂點入棧stack,并添加到set集合里面，然后輸出該頂點的值
3. 棧里面的一個頂點出棧，保存出棧的頂點cur,
4. 遍歷該頂點cur的相鄰頂點nexts，如果set集合里面不包含相鄰頂點cur，則將cur和相鄰節點next都入棧并將next節點加入到set集合里面，輸出相鄰頂點的值，跳出循環。
5. 【3,4】步驟周而復始一次迭代。
public static void dfs(Node node) {
if (node == null) {
return;
}
Stack<Node> stack = new Stack<>();
HashSet<Node> set = new HashSet<>();
stack.add(node);
set.add(node);
System.out.println(node.value);
while (!stack.isEmpty()) {
Node cur = stack.pop();
for (Node next : cur.nexts) {
if (!set.contains(next)) {
stack.push(cur);
stack.push(next);
set.add(next);
System.out.println(next.value);
break;
}
}
}
}
舉一個例子，比如打游戲時你一定要先打第一關，因為只有打通了第一關，才能解鎖下一關或下幾關，而不能上來就打第二關。
如下圖1 號端點就相當于第一關，而 6 號端點就相當于是最后一關。所以我們就知道了：
1.找一個入度為零（不需其他關卡通關就能解鎖的）的端點，如果有多個，則從編號小的開始找；
2.將該端點的編號輸出；
3.將該端點刪除，同時將所有由該點出發的有向邊刪除；
4.循環進行 2 和 3 ，直到圖中的圖中所有點的入度都為零；
5.拓撲排序結束；
那么我現在就以上圖為例，詳細分析一下過程；
第一步：輸出 “ 1 ”，并刪除由該點出發的有向邊
第二步：輸出 “ 2 ”，并刪除由該點出發的有向邊
第三步：輸出 “ 3 ”，并刪除由該點出發的有向邊
第四步：輸出 “ 4 ”，并刪除由該點出發的有向邊
第五步：輸出 “ 5 ”，并刪除由該點出發的有向邊
第六步：輸出 “ 6 ”，排序結束。所以，最終拓撲排序的結果是1 2 3 4 5 6
思路
1. 首先準備一個inMap,其中key為節點node,value為該節點剩余的入度數。然后準備一個隊列zeroInQueue
2. 遍歷圖graph，將圖graph中node和以及節點對應的入度數in存儲到inMap里面,如果該節點的入度數in為0則將該節點入隊zeroInQueue
3. 將隊列zeroInQueue的節點出隊，保存該節點為cur,把cur存儲到集合result里面，遍歷當前節點cur的相鄰節點，將相鄰節點的入度數減1，如果相鄰節點的入度數為0則將該節點入隊zeroInQueue
4. 【3】步驟周而復始一次迭代。
// directed graph and no loop
public static List<Node> sortedTopology(Graph graph) {
// key：某一個node
// value：剩余的入度
HashMap<Node, Integer> inMap = new HashMap<>();
// 入度為0的點，才能進這個隊列
Queue<Node> zeroInQueue = new LinkedList<>();
for (Node node : graph.nodes.values()) {
inMap.put(node, node.in);
if (node.in == 0) {
zeroInQueue.add(node);
}
}
// 拓撲排序的結果，依次加入result
List<Node> result = new ArrayList<>();
while (!zeroInQueue.isEmpty()) {
Node cur = zeroInQueue.poll();
result.add(cur);
for (Node next : cur.nexts) {
inMap.put(next, inMap.get(next) - 1);
if (inMap.get(next) == 0) {
zeroInQueue.add(next);
}
}
}
return result;
}
所謂生成樹，就是n個點之間連成n-1條邊的圖形。最小生成樹，就是權值（兩點間直線的值）之和的最小值。由此可以總結構造最小生成樹的要求有：（1）必須只使用該圖中的邊來構造最小生成樹；（2）必須使用且僅使用（n-1）條邊來連接圖中的n個頂點；（3）不能使用產生回路的邊；（4）要求樹的（n-1）條邊的權值之和是最小的。
Kruskal（克魯斯卡爾算法）算法是一種用來查找最小生成樹的算法。Kruskal算法是基于貪心的思想得到的。首先我們把所有的邊按照權值先從小到大排列，接著按照順序選取每條邊，如果這條邊的兩個端點不屬于同一集合，那么就將它們合并，直到所有的點都屬于同一個集合為止。換而言之，Kruskal算法就是基于并查集的貪心算法。
public static class MySets {
public HashMap<Node, List<Node>> setMap;
public MySets(List<Node> nodes) {
for (Node cur : nodes) {
List<Node> set = new ArrayList<Node>();
set.add(cur);
setMap.put(cur, set);
}
}
public boolean isSameSet(Node from, Node to) {
List<Node> fromSet = setMap.get(from);
List<Node> toSet = setMap.get(to);
return fromSet == toSet;
}
public void union(Node from, Node to) {
List<Node> fromSet = setMap.get(from);
List<Node> toSet = setMap.get(to);
for (Node toNode : toSet) {
fromSet.add(toNode);
setMap.put(toNode, fromSet);
}
}
}
prim算法 (普里姆算法)我們先初始定義一個頂點u，然后在相鄰的所有邊中找到最小權值的邊 e1，將頂點u鏈接到初始點c之外的頂點v,之后將頂點v放到c中，并且一直重復知道完成。
思路
1. 準備一個邊的小根堆隊列priorityQueue、頂點的集合set和要挑選的邊的集合result
2. 遍歷圖的頂點nodes，將隨機的一個頂點node放到集合set里面，將頂點node所相連所相連的邊入隊到小根堆隊列priorityQueue。
3. 彈出隊列里面最小權重的邊，判斷這個邊的to節點的是不是在set集合里面，如果不在，則將to節點放到set里面，并把這條邊存到result里面。再將to頂點所相連所相連的邊入隊到priorityQueue。周而復始依次迭代。
4. 3步驟之后break，跳出循環。
public static Set<Edge> primMST(Graph graph) {
// 解鎖的邊進入小根堆
PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
HashSet<Node> set = new HashSet<>();
Set<Edge> result = new HashSet<>(); // 依次挑選的的邊在result里
for (Node node : graph.nodes.values()) { // 隨便挑了一個點
// node 是開始點
if (!set.contains(node)) {
set.add(node);
for (Edge edge : node.edges) { // 由一個點，解鎖所有相連的邊
priorityQueue.add(edge);
}
while (!priorityQueue.isEmpty()) {
Edge edge = priorityQueue.poll(); // 彈出解鎖的邊中，最小的邊
Node toNode = edge.to; // 可能的一個新的點
if (!set.contains(toNode)) { // 不含有的時候，就是新的點
set.add(toNode);
result.add(edge);
for (Edge nextEdge : toNode.edges) {
priorityQueue.add(nextEdge);
}
}
}
}
break;
}
return result;
}
官方微信
官方抖音
京公網安備 11030102010736號