做一个网站花多少钱,网站导航营销步骤,网站快照没了,常州网站制作计划trie树的使用场景
我们若需要制作一个通讯录的软件#xff0c;使用常规树结构查询的复杂度为O(logn),但trie树的复杂度确与数据多少无关#xff0c;与单词长度有关#xff0c;这就大大缩减的查询的时间复杂度。
trie树的基本实现
基础结构
package com.study.trieDemo;i…trie树的使用场景
我们若需要制作一个通讯录的软件使用常规树结构查询的复杂度为O(logn),但trie树的复杂度确与数据多少无关与单词长度有关这就大大缩减的查询的时间复杂度。
trie树的基本实现
基础结构
package com.study.trieDemo;import java.util.TreeMap;/*** Created by Zsy on 2020/8/21.*/
public class Trie {private class Node {private boolean isWord;private TreeMapCharacter, Node next;public Node(boolean isWord) {this.isWord isWord;next new TreeMapCharacter, Node();}public Node() {this(false);}}private Node root;private int size;public int getSize() {return size;}}
添加 /*** 向tire中添加一个单词* param word*/public void add(String word) {Node cur root;for (int i 0; i word.length(); i) {char c word.charAt(i);if (cur.next.get(c) null)cur.next.put(c, new Node());cur cur.next.get(c);}if (!cur.isWord) {cur.isWord true;size;}}搜索单词 /*** 查找单词word是否在trie树中* param word* return*/public boolean contains(String word){Node curroot;for (int i 0; i word.length() ; i) {char cword.charAt(i);if (cur.next.get(c)null)return false;curcur.next.get(c);}return cur.isWord;}leetcode中关于trie的题目
208. 实现 Trie (前缀树)
208. 实现 Trie (前缀树)
实现
package com.study.leetcode;import java.util.TreeMap;/*** Created by Zsy on 2020/8/21.*/
public class Trie_208 {private Node root;private class Node {private boolean isWord;private TreeMapCharacter, Node next;public Node(boolean isWord) {this.isWord isWord;next new TreeMapCharacter, Node();}public Node() {this(false);}}/*** Initialize your data structure here.*/public Trie_208() {root new Node();}/*** Inserts a word into the trie.*/public void insert(String word) {Node cur root;for (int i 0; i word.length(); i) {char c word.charAt(i);if (cur.next.get(c) null)cur.next.put(c, new Node());cur cur.next.get(c);}cur.isWord true;}/*** Returns if the word is in the trie.*/public boolean search(String word) {Node cur root;for (int i 0; i word.length(); i) {char c word.charAt(i);if (cur.next.get(c) null)return false;cur cur.next.get(c);}return cur.isWord;}/*** Returns if there is any word in the trie that starts with the given prefix.*/public boolean startsWith(String prefix) {Node cur root;for (int i 0; i prefix.length(); i) {char c prefix.charAt(i);if (cur.next.get(c) null)return false;cur cur.next.get(c);}return true;}
}
211. 添加与搜索单词 - 数据结构设计
题目链接
211. 添加与搜索单词 - 数据结构设计
实现
package com.study.leetcode;import java.util.TreeMap;/*** Created by Zsy on 2020/8/21.*/
public class WordDictionary_211 {private Node root;private class Node {private boolean isWord;private TreeMapCharacter, Node next;public Node(boolean isWord) {this.isWord isWord;next new TreeMapCharacter, Node();}public Node() {this(false);}}/*** Initialize your data structure here.*/public WordDictionary_211() {root new Node();}/*** Adds a word into the data structure.*/public void addWord(String word) {Node cur root;for (int i 0; i word.length(); i) {char c word.charAt(i);if (cur.next.get(c) null)cur.next.put(c, new Node());cur cur.next.get(c);}cur.isWord true;}/*** Returns if the word is in the data structure. A word could contain the dot character . to represent any one letter.*//*** 使用match进行递归查询* param word* return*/public boolean search(String word) {return match(root, word, 0);}private boolean match(Node node, String word, int index) {if (index word.length())return node.isWord;char c word.charAt(index);if (c ! .) {if (node.next.get(c) null)return false;return match(node.next.get(c), word, index 1);} else {for (char nextChar : node.next.keySet())if (match(node.next.get(nextChar), word, index 1))return true;return false;}}}
677. 键值映射
题目链接
677. 键值映射
题解
package com.study.leetcode;import java.util.TreeMap;/*** Created by Zsy on 2020/8/21.*/
public class MapSum_677 {private class Node {public int value;public TreeMapCharacter, Node next;public Node(int value) {this.value value;next new TreeMapCharacter, Node();}public Node() {this(0);}}private Node root;/*** Initialize your data structure here.*/public MapSum_677() {root new Node();}/*** 非递归法插入节点通过查询next中是否存在对应key的节点进行相应插入操作* param key* param val*/public void insert(String key, int val) {Node cur root;for (int i 0; i key.length(); i) {char c key.charAt(i);if (cur.next.get(c) null)cur.next.put(c, new Node());cur cur.next.get(c);}cur.value val;}/*** 找到匹配节点的指针将地址传给sum进行递归计算* param prefix* return*/public int sum(String prefix) {Node cur root;for (int i 0; i prefix.length(); i) {char c prefix.charAt(i);if (cur.next.get(c) null)return 0;cur cur.next.get(c);}return sum(cur);}private int sum(Node node) {//省略了if(nodenull) return 0;int value node.value;for (char c : node.next.keySet()) {valuesum(node.next.get(c));}return value;}
}
