< 一 > 前缀树 / 字典树 (trie tree/prefix tree)
类似于状态机的树结构, 初始化为空根节点, 输入字符串进行分支分裂
? - 输入 "abc" - ?-ao-bo-co - 输入 "abd" - ?-ao-bo-co(-do) , 即在 o(b) 节点处分支一个 o(c) 节点 (o 表示节点,"a" 表示类似状态机的边)
节点中可以存储需要的信息 (比如输入了多少次相同串); 查找前缀匹配信息利用前缀树
相比哈希表查询而言, 前缀树查询可扩展性更强, 可以适用于其他条件更苛刻的查询匹配操作
算法实现 (Java)
- public static class TrieNode {
- public int path; // 边经过次数
- public int end;
- public TrieNode[] map; // 表示边
- public TrieNode() {
- path = 0;
- end = 0;
- map = new TrieNode[26]; // 假设只会出现小写字母; 若是中文则可以用 hashmap 来实现 next 指针
- }
- }
- public static class Trie {
- private TrieNode root;
- public Trie() {
- root = new TrieNode();
- }
- public void insert(String Word) {
- if (Word == null) {
- return;
- }
- char[] chs = Word.toCharArray();
- TrieNode node = root;
- int index = 0;
- for (int i = 0; i <chs.length; i++) {
- index = chs[i] - 'a';
- if (node.map[index] == null) {
- node.map[index] = new TrieNode();
- }
- node = node.map[index];
- node.path++;
- }
- node.end++;
- }
- public void delete(String Word) { // 共享节点不删, 计数器 --
- if (search(Word)) {
- char[] chs = Word.toCharArray();
- TrieNode node = root;
- int index = 0;
- for (int i = 0; i < chs.length; i++) {
- index = chs[i] - 'a';
- if (node.map[index].path-- == 1) {
- node.map[index] = null;
- return;
- }
- node = node.map[index];
- }
- node.end--;
- }
- }
- public boolean search(String Word) {
- if (Word == null) {
- return false;
- }
- char[] chs = Word.toCharArray();
- TrieNode node = root;
- int index = 0;
- for (int i = 0; i < chs.length; i++) {
- index = chs[i] - 'a';
- if (node.map[index] == null) {
- return false;
- }
- node = node.map[index];
- }
- return node.end != 0;
- }
- public int prefixNumber(String pre) {
- if (pre == null) {
- return 0;
- }
- char[] chs = pre.toCharArray();
- TrieNode node = root;
- int index = 0;
- for (int i = 0; i < chs.length; i++) {
- index = chs[i] - 'a';
- if (node.map[index] == null) {
- return 0;
- }
- node = node.map[index];
- }
- return node.path;
- }
- }
例子: 字符串数组 arr1,arr2, 求 arr2 中有哪些字符串是在 arr1 中出现的?
先用 arr1 构造前缀树, 然后逐一 search 数组中字符串即可, 看 end
例子: arr2 中有哪些字符, 是作为 arr1 中某个字符串前缀出现的?
先用 arr1 构造前缀树, 然后逐一 search 数组中字符串即可, 看 path
< 二 > 图的存储方式
1) 邻接表 2) 邻接矩阵
邻接表: 每个点都有一条链表, 链表节点表示有该点指向节点表示点的边. - 带权表即把链表节点加上权重参数即可
邻接矩阵: 二维矩阵, 行起点列终点, 权重参数值, 无权即 +-1∞
笔试中最常见的方式是用二维列表存储, 其中一维列表:[边权, 起点, 终点]
类图 - 由二维列表生成类图
Node 点结构: value, 入度 in, 出度 out, 邻接节点 Arraylist(出度节点), 邻接边 Arraylist(出度边).
Edge 边结构: 权重, from,to.
Graph 图结构: 点 Arraylist, 边 Arraylist
转化成类图后方便图相关问题的解决 - 点集边集等, 所有关于图的算法都可以用类图结构方便
算法实现 (Java)
- // 点
- 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<>();
- }
- }
- // 边
- 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;
- }
- }
- // 图
- public class Graph {
- public HashMap<Integer,Node> nodes;
- public HashSet<Edge> edges;
- public Graph() {
- nodes = new HashMap<>();
- edges = new HashSet<>();
- }
- }
- // 二维列表构造类图
- public static Graph createGraph(Integer[][] matrix) {
- Graph graph = new Graph();
- for (int i = 0; i <matrix.length; i++) {
- Integer from = matrix[i][0];
- Integer to = matrix[i][1];
- Integer weight = matrix[i][2];
- if (!graph.nodes.containsKey(from)) {
- graph.nodes.put(from, new Node(from));
- }
- if (!graph.nodes.containsKey(to)) {
- graph.nodes.put(to, new Node(to));
- }
- Node fromNode = graph.nodes.get(from);
- Node toNode = graph.nodes.get(to);
- Edge newEdge = new Edge(weight, fromNode, toNode);
- fromNode.nexts.add(toNode);
- fromNode.out++;
- toNode.in++;
- fromNode.edges.add(newEdge);
- graph.edges.add(newEdge);
- }
- return graph;
- }
< 三 > 图的遍历
广度优先遍历 (宽度优先遍历) - BFS
利用队列实现 - 同时准备一个 set 防止已经遍历过的节点再进队列 (如果只有栈的话, 就将栈转为队列再实现)
根节点判断 set, 入队列和 set,(弹队列打印, 出度节点判断入栈 set). 直至队列变空
算法实现 (Java)
- public static void bfs(Node node) {
- if (node == null) {
- return;
- }
- Queue<Node> queue = new LinkedList<>();
- HashSet<Node> map = new HashSet<>();
- queue.add(node);
- map.add(node);
- while (!queue.isEmpty()) {
- Node cur = queue.poll();
- System.out.println(cur.value);
- for (Node next : cur.nexts) {
- if (!map.contains(next)) {
- map.add(next);
- queue.add(next);
- }
- }
- }
- }
深度优先遍历: DFS
来源: http://www.bubuko.com/infodetail-3386699.html