数据结构与算法（十一）Trie字典树

Trie字典树的基本概念
Trie字典树的基本操作
1. 插入
2. 查找
3. 前缀查询
4. 删除
基于链表的Trie字典树
基于Trie的Set性能对比
LeetCode相关线段树的问题
1. LeetCode第208号问题
2. LeetCode第211号问题
3. LeetCode第677号问题

Trie字典树的基本概念

上一篇我们介绍了线段树(Segment Tree)，本文主要介绍Trie字典树。

通过前面的介绍我们知道一个线性表的顺序查找的时间复杂度为O(n)；二分搜索树的查找为O(log n)，它们都和数据结构中的元素个数相关。关于线性表和二分搜索树的时间复杂度分析有需要的可以查看 Set集合和BinarySearchTree的时间复杂度分析

本文介绍的Trie字典树(主要用于存储字符串)查找速度主要和它的元素(字符串)的长度相关[O(w)]。

Trie字典树主要用于存储字符串，Trie 的每个 Node 保存一个字符。用链表来描述的话，就是一个字符串就是一个链表。每个Node都保存了它的所有子节点。

例如我们往字典树中插入see、pain、paint三个单词，Trie字典树如下所示：

这里写图片描述

也就是说如果只考虑小写的26个字母，那么Trie字典树的每个节点都可能有26个子节点。

Trie字典树的基本操作

插入

本文是使用链表来实现Trie字典树，字符串的每个字符作为一个Node节点，Node主要有两部分组成：

是否是单词 (boolean isWord)
节点所有的子节点，用map来保存 (Map next)

例如插入一个paint单词，如果用户查询pain，尽管 paint 包含了 pain，但是Trie中仍然不包含 pain 这个单词，所以如果往Trie中插入一个单词，需要把该单词的最后一个字符的节点的 isWord 设置为 true。所以为什么Node需要存储 是否是单词 这个属性。

节点的所有子节点，通过一个Map来存储，key是当前子节点对应的字符，value是子节点。

实现的伪代码如下：

public void add(String word) {Node current = root;char[] cs = word.toCharArray();for (char c : cs) {Node next = current.next.get(c);if (next == null) {//一个字符对应一个Node节点current.next.put(c, new Node());}current = current.next.get(c);}//current就是word的最后一个字符的Node
//如果当前的node已经是一个word，则不需要添加
if (!current.isWord) {size++;current.isWord = true;
}

}

查找

Trie查找操作就比较简单了，遍历带查找的字符串的字符，如果每个节点都存在，并且待查找字符串的最后一个字符对应的Node的 isWord 属性为 true ，则表示该单词存在，伪代码如下：

public boolean contains(String word) {Node current = root;for (int i = 0; i < word.length(); i++) {char c = word.charAt(i);Node node = current.next.get(c);if (node == null) {return false;}current = node;}//current就是word的最后一个字符的Nodereturn current.isWord;
}

前缀查询

前缀查询和上面的查询操作基本类似，就是不需要判断 isWord 了

public boolean containsPrefix(String prefix) {Node current = root;for (int i = 0; i < prefix.length(); i++) {char c = prefix.charAt(i);Node node = current.next.get(c);if (node == null) {return false;}current = node;}return true;
}

删除

Trie的删除操作就稍微复杂一些，主要分为以下3种情况：

如果单词是另一个单词的前缀

如果待删除的单词是另一个单词的前缀，只需要把该单词的最后一个节点的 isWord 的改成false

比如Trie中存在 panda 和 pan 这两个单词，删除 pan ，只需要把字符 n 对应的节点的 isWord 改成 false 即可

如下图所示

这里写图片描述

如果单词的所有字母的都没有多个分支，删除整个单词

如果单词的所有字母的都没有多个分支（也就是说该单词所有的字符对应的Node都只有一个子节点），则删除整个单词

例如要删除如下图的see单词，如下图所示：

这里写图片描述

如果单词的除了最后一个字母，其他的字母有多个分支

这里写图片描述

基于链表的Trie字典树

public class Trie {
private Node root;private int size;private static class Node {public boolean isWord;public Map&lt;Character, Node&gt; next;public Node() {next = new TreeMap&lt;&gt;();}public Node(boolean isWord) {this();this.isWord = isWord;}}public Trie() {root = new Node();
}public int size() {return size;
}public boolean isEmpty() {return size == 0;
}/*** 插入操作** @param word 单词*/
public void add(String word) {Node current = root;char[] cs = word.toCharArray();for (char c : cs) {Node next = current.next.get(c);if (next == null) {current.next.put(c, new Node());}current = current.next.get(c);}//如果当前的node已经是一个word，则不需要添加if (!current.isWord) {size++;current.isWord = true;}
}/*** 是否包含某个单词** @param word 单词* @return 存在返回true，反之false*/
public boolean contains(String word) {Node current = root;for (int i = 0; i &lt; word.length(); i++) {char c = word.charAt(i);Node node = current.next.get(c);if (node == null) {return false;}current = node;}//如果只存在 panda这个词，查询 pan，虽然有这3个字母，但是并不存在该单词return current.isWord;
}/*** Trie是否包含某个前缀** @param prefix 前缀* @return*/
public boolean containsPrefix(String prefix) {Node current = root;for (int i = 0; i &lt; prefix.length(); i++) {char c = prefix.charAt(i);Node node = current.next.get(c);if (node == null) {return false;}current = node;}return true;
}/** 1，如果单词是另一个单词的前缀，只需要把该word的最后一个节点的isWord的改成false* 2，如果单词的所有字母的都没有多个分支，删除整个单词* 3，如果单词的除了最后一个字母，其他的字母有多个分支，*//*** 删除操作** @param word* @return*/
public boolean remove(String word) {Node multiChildNode = null;int multiChildNodeIndex = -1;Node current = root;for (int i = 0; i &lt; word.length(); i++) {Node child = current.next.get(word.charAt(i));//如果Trie中没有这个单词if (child == null) {return false;}//当前节点的子节点大于1个if (child.next.size() &gt; 1) {multiChildNodeIndex = i;multiChildNode = child;}current = child;}//如果单词后面还有子节点if (current.next.size() &gt; 0) {if (current.isWord) {current.isWord = false;size--;return true;}//不存在该单词，该单词只是前缀return false;}//如果单词的所有字母的都没有多个分支，删除整个单词if (multiChildNodeIndex == -1) {root.next.remove(word.charAt(0));size--;return true;}//如果单词的除了最后一个字母，其他的字母有分支if (multiChildNodeIndex != word.length() - 1) {multiChildNode.next.remove(word.charAt(multiChildNodeIndex + 1));size--;return true;}return false;
}

}

基于Trie的Set性能对比

在前面的Set集合和BinarySearchTree的时间复杂度分析中我们分别使用了基于链表和基于二分搜索树实现的Set，对两本英文原著进行简单的词频统计。

现在使用Trie实现下Set集合，然后三者性能做一个比较，还是以傲慢与偏见、双城记、战争与和平三本原著作为数据源。

傲慢与偏见(Pride and Prejudice)的性能对比

Pride and PrejudiceTotal words: 125901Total different words: 6530

TrieSet Time: 0.099788784
BSTSet Time: 0.339963625
LinkedListSet Time: 3.554973381

从中可以看出傲慢与偏见不同的单词只有6000左右，阅读难度不是很大。

双城记(A Tale of Two Cities)的性能对比

A Tale of Two CitiesTotal words: 141489Total different words: 9944

TrieSet Time: 0.119505174
BSTSet Time: 0.331334495
LinkedListSet Time: 5.26063235

战争与和平(War and peace)的性能对比

War and PeaceTotal words: 602359Total different words: 16725

TrieSet Time: 0.09750872
BSTSet Time: 0.233328074

以上关于原著词汇的统计只是简单的对比单词是否一致，并没有考虑一个单词的过去式、进行时等时态，只要字符串不一致都把它当作不同的单词。

LeetCode相关线段树的问题

LeetCode第208号问题

问题描述：

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例：

Trie trie = new Trie();

trie.insert(“apple”);
trie.search(“apple”); // 返回 true
trie.search(“app”); // 返回 false
trie.startsWith(“app”); // 返回 true
trie.insert(“app”);
trie.search(“app”); // 返回 true

问题说明：

你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

这个问题在我们实现的 Trie字典树 中已经实现了这个功能了，add()就是对应的insert()，contains()就是对应的search()，starcontainsPrefix()就是对应的startsWith()，这里就不贴代码了。

LeetCode第211号问题

问题描述：

设计一个支持以下两种操作的数据结构：

void addWord(word)
bool search(word)
search(word) 
1
2
3

可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。

示例:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
1
2
3
4
5
6
7

问题说明：

你可以假设所有单词都是由小写字母 a-z 组成的。

这个问题就是上一个问题的基础上加上 . 的处理，稍微复杂点。

如果下一个字符是 . ，那么需要遍历该节点的所有子节点，对所有子节点的处理就是一个递归程序：

public boolean searchByWildCard(String express) {return search(root, express, 0);
}

private boolean search(Node node, String express, int index) {
//如果已经到了待查询字符串的尾端了
if (index == express.length()) {
return node.isWord;
}
char c = express.charAt(index);
if (c != ‘.’) {
Node nextChar = node.next.get©;
if (nextChar == null) {
return false;
}
return search(nextChar, express, index + 1);
} else {//如果是通配符
Map<Character, Node> nextNodes = node.next;
//遍历所有的子节点
for (Map.Entry<Character, Node> entry : nextNodes.entrySet()) {
if (search(entry.getValue(), express, index + 1)) {
return true;
}
}
return false;
}
}

LeetCode第677号问题

问题描述：

实现一个 MapSum 类里的两个方法，insert 和 sum。

对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。

对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。

示例 1:

输入: insert("apple", 3), 输出: Null
输入: sum("ap"), 输出: 3
输入: insert("app", 2), 输出: Null
输入: sum("ap"), 输出: 5
1
2
3
4

总结一句话就是，求出所有符合该前缀的字符串的键值的总和。

节点需要保存一个键值，用于求和。节点Node不需要维护 isWord 这个属性了，因为不关注是不是一个单词。

class Node {public int value;public Map<Character, Node> next;
}

public int sum(String prefix) {
Node cur = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
Node node = cur.next.get©;
if (node == null) {
return 0;
}
cur = node;
}

//cur指向prefix的最后一个字符的Node//对每个以prefix为前缀的node进行累加
return countValue(cur);

}

private int countValue(Node node) {
int result = node.value;
for (char c : node.next.keySet()) {
result += countValue(node.next.get©);
}
return result;
}

上面三个LeetCode的问题答案，都可以在我的github上查看

Reference

本文主要内容和大纲是学习了慕课网 liuyubobobo 老师的视频《算法大神带你玩转数据结构从入门到精通》
有需要的同学可以看看, 真心不错. 墙裂推荐… 最好能加上自己的思考和理解.

下面是我的公众号，干货文章不错过，有需要的可以关注下，有任何问题可以联系我：

公众号: chiclaim

文本相关源代码github

                                </div><link href="https://csdnimg.cn/release/phoenix/mdeditor/markdown_views-60ecaf1f42.css" rel="stylesheet"></div>
</article>

        <div class="hide-article-box hide-article-pos text-center"><a class="btn-readmore" id="btn-readmore-zk" data-report-view="{&quot;mod&quot;:&quot;popu_376&quot;,&quot;dest&quot;:&quot;https://blog.csdn.net/johnny901114/article/details/80711441&quot;,&quot;strategy&quot;:&quot;readmore&quot;,&quot;ab&quot;:&quot;new&quot;}" data-report-click="{&quot;mod&quot;:&quot;popu_376&quot;,&quot;dest&quot;:&quot;https://blog.csdn.net/johnny901114/article/details/80711441&quot;,&quot;strategy&quot;:&quot;readmore&quot;,&quot;ab&quot;:&quot;new&quot;}">展开阅读全文<svg class="icon chevrondown" aria-hidden="true"><use xlink:href="#csdnc-chevrondown"></use></svg></a></div>

点赞25
评论
分享
x
海报分享
扫一扫，分享海报
收藏 61
手机看
分享到微信朋友圈
x
扫一扫，手机阅读

                        </li><li class="tool-item"><a class="tool-attend tool-bt-button tool-bt-attend" href="javascript:;">关注</a></li></ul><div style="display:flex"><a class="tool-mover-open" id="btn-readmore" style="display: none;" data-type="0" data-report-click="{&quot;mod&quot;:&quot;popu_376&quot;,&quot;dest&quot;:&quot;https://blog.csdn.net/johnny901114/article/details/80711441&quot;,&quot;strategy&quot;:&quot;packupbar&quot;,&quot;ab&quot;:&quot;new&quot;}" height="3"><span>收起全文</span><img id="btn-close-img" style="display: block;" src="https://csdnimg.cn/release/phoenix/template/new_img/CommentArrow.png" alt=""></a></div>
</div>

        </div><a id="commentBox" name="commentBox"></a>

还能输入1000个字符

<div class="comment-list-container"><a id="comments"></a><div class="comment-list-box"></div><div id="commentPage" class="pagination-box d-none"></div><div class="opt-box text-center"><div class="btn btn-sm btn-link-blue" id="btnMoreComment"></div></div>
</div>

初级玩转Linux+Ubuntu(嵌入式开发基础课程)

06-26

课程主要面向嵌入式Linux初学者、工程师、学生

主要从一下几方面进行讲解：1.linux学习路线、基本命令、高级命令2.shell、vi及vim入门讲解3.软件安装下载、NFS、Samba、FTP等服务器配置及使用

                <!-- <div class="recommend-item-box type_hot_word"><div class="content clearfix"><div class="float-left"><span><a href="https://java.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://java.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://java.csdn.net/","index":"#"}'  target="_blank">Java</a></span><span><a href="https://c1.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://c1.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://c1.csdn.net/","index":"#"}'  target="_blank">C语言</a></span><span><a href="https://python.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://python.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://python.csdn.net/","index":"#"}'  target="_blank">Python</a></span><span><a href="https://cplus.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://cplus.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://cplus.csdn.net/","index":"#"}'  target="_blank">C++</a></span><span><a href="https://csharp.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://csharp.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://csharp.csdn.net/","index":"#"}'  target="_blank">C#</a></span><span><a href="https://vbn.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://vbn.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://vbn.csdn.net/","index":"#"}'  target="_blank">Visual Basic .NET</a></span><span><a href="https://js.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://js.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://js.csdn.net/","index":"#"}'  target="_blank">JavaScript</a></span><span><a href="https://php.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://php.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://php.csdn.net/","index":"#"}'  target="_blank">PHP</a></span><span><a href="https://sql.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://sql.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://sql.csdn.net/","index":"#"}'  target="_blank">SQL</a></span><span><a href="https://go.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://go.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://go.csdn.net/","index":"#"}'  target="_blank">Go语言</a></span><span><a href="https://r.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://r.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://r.csdn.net/","index":"#"}'  target="_blank">R语言</a></span><span><a href="https://assembly.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://assembly.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://assembly.csdn.net/","index":"#"}'  target="_blank">Assembly language</a></span><span><a href="https://swift.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://swift.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://swift.csdn.net/","index":"#"}'  target="_blank">Swift</a></span><span><a href="https://ruby.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://ruby.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://ruby.csdn.net/","index":"#"}'  target="_blank">Ruby</a></span><span><a href="https://matlab.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://matlab.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://matlab.csdn.net/","index":"#"}'  target="_blank">MATLAB</a></span><span><a href="https://plsql.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://plsql.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://plsql.csdn.net/","index":"#"}'  target="_blank">PL/SQL</a></span><span><a href="https://perl.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://perl.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://perl.csdn.net/","index":"#"}'  target="_blank">Perl</a></span><span><a href="https://vb.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://vb.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://vb.csdn.net/","index":"#"}'  target="_blank">Visual Basic</a></span><span><a href="https://obj.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://obj.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://obj.csdn.net/","index":"#"}'  target="_blank">Objective-C</a></span><span><a href="https://delphi.csdn.net/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://delphi.csdn.net/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://delphi.csdn.net/","index":"#"}'  target="_blank">Delphi/Object Pascal</a></span><span><a href="https://www.csdn.net/unity/" data-report-click='{"mod":"1586412712_001","ab":"new","dest":"https://www.csdn.net/unity/","index":"索引#"}' data-report-view='{"mod":"1586412712_001","ab":"new","dest":"https://www.csdn.net/unity/","index":"#"}'  target="_blank">Unity3D</a></span><span><a href="https://www.csdn.net/gather_13/NtTakgxsLWRvd25sb2Fk.html" target="_blank">c#怎么获得线程名</a></span><span><a href="https://www.csdn.net/gather_1d/NtTakgysLWRvd25sb2Fk.html" target="_blank">c# usb 采集器</a></span><span><a href="https://www.csdn.net/gather_10/NtTakg0sLWRvd25sb2Fk.html" target="_blank">c# sort()</a></span><span><a href="https://www.csdn.net/gather_1c/NtjaAgysLWRvd25sb2Fk.html" target="_blank">c#面对对象的三大特性</a></span><span><a href="https://www.csdn.net/gather_1d/NtjaAgzsLWRvd25sb2Fk.html" target="_blank">c# 打印 等比缩放</a></span><span><a href="https://www.csdn.net/gather_19/NtjaAg0sLWRvd25sb2Fk.html" target="_blank">c#弹出右键菜单</a></span><span><a href="https://www.csdn.net/gather_14/NtjaAg2sLWRvd25sb2Fk.html" target="_blank">c# 系统托盘图标</a></span><span><a href="https://www.csdn.net/gather_1d/NtjaAg3sLWRvd25sb2Fk.html" target="_blank">c# 键值对 键可以重复</a></span><span><a href="https://www.csdn.net/gather_1d/NtjaAg5sLWRvd25sb2Fk.html" target="_blank">c# 鼠标移上去提示</a></span><span><a href="https://www.csdn.net/gather_10/NtjaEgwsLWRvd25sb2Fk.html" target="_blank">c#结构体定义</a></span></div></div></div> --><div class="recommend-loading-box"><img src="https://csdnimg.cn/release/phoenix/images/feedLoading.gif"></div><!-- <div class="recommend-end-box"><p class="text-center">没有更多推荐了，<a href="https://blog.csdn.net/" class="c-blue c-blue-hover c-blue-focus">返回首页</a></p></div> --></div><div class="template-box"><span>©️2020 CSDN</span><span>皮肤主题: 数字20</span><span> 设计师:CSDN官方博客                                    </span><span><a href="https://blog.csdn.net/" class="back-home c-blue c-blue-hover c-blue-focus">返回首页</a></span></div><script src="https://csdnimg.cn/pubfooter/js/publib_footer-1.0.4.js" data-isfootertrack="false" type="text/javascript"></script><div><div class="bottom-pub-footer footer-box pub_fo"><div class="pub-footer-new">    <div id="pub-footerall">        <div class="contact-info">          <a class="right-dotte spec_a" href="//www.csdn.net/company/index.html#about" target="_blank">关于我们</a>          <a href="//www.csdn.net/company/index.html#recruit" target="_blank" class="right-dotte spec_a">招聘</a>          <a href="//www.csdn.net/company/index.html#advertisement" target="_blank" class="right-dotte spec_a">广告服务</a>          <a href="https://www.csdn.net/gather/A" target="_blank" class="footer_baidu right-dotte spec_a">网站地图</a>          <em>          <svg width="16" height="16" xmlns="http://www.w3.org/2000/svg"><path d="M2.167 2h11.666C14.478 2 15 2.576 15 3.286v9.428c0 .71-.522 1.286-1.167 1.286H2.167C1.522 14 1 13.424 1 12.714V3.286C1 2.576 1.522 2 2.167 2zm-.164 3v1L8 10l6-4V5L8 9 2.003 5z" fill="#999AAA" fill-rule="evenodd"></path></svg>          <a href="mailto:webmaster@csdn.net" target="_blank"><span class="txt right-dotte">kefu@csdn.net</span></a><svg t="1538012951761" width="17" height="17" style="" viewBox="0 0 1024 1024" version="1.1" xmlns="http://www.w3.org/2000/svg" p-id="23083" xmlns:xlink="http://www.w3.org/1999/xlink"><defs><style type="text/css"></style></defs><path d="M466.4934485 880.02006511C264.6019863 859.18313878 107.13744214 688.54706608 107.13744214 481.14947309 107.13744214 259.68965394 286.68049114 80.14660493 508.14031029 80.14660493s401.00286817 179.54304901 401.00286814 401.00286816v1.67343191C908.30646249 737.58941724 715.26799489 943.85339507 477.28978337 943.85339507c-31.71423369 0-62.61874229-3.67075386-92.38963569-10.60739903 30.09478346-11.01226158 56.84270313-29.63593923 81.5933008-53.22593095z m-205.13036267-398.87059202a246.77722444 246.77722444 0 0 0 493.5544489 0 30.85052691 30.85052691 0 0 0-61.70105383 0 185.07617062 185.07617062 0 0 1-370.15234125 0 30.85052691 30.85052691 0 0 0-61.70105382 0z" p-id="23084" fill="#999AAA"></path></svg>          <a href="http://bbs.csdn.net/forums/Service" target="_blank"><span class="right-dotte">客服论坛</span></a><svg t="1538013874294" width="17" height="17" style="" viewBox="0 0 1194 1024" version="1.1" xmlns="http://www.w3.org/2000/svg" p-id="23784" xmlns:xlink="http://www.w3.org/1999/xlink"><defs><style type="text/css"></style></defs><path d="M1031.29689505 943.85339507h-863.70679012A71.98456279 71.98456279 0 0 1 95.60554212 871.86883228v-150.85178906c0-28.58329658 16.92325492-54.46750945 43.13135785-65.93861527l227.99160176-99.75813425c10.55341735-4.61543317 18.24580594-14.0082445 20.72896295-25.23643277l23.21211998-105.53417343a71.95757195 71.95757195 0 0 1 70.28414006-56.51881307h236.95255971c33.79252817 0 63.02360485 23.5090192 70.28414004 56.51881307l23.21211997 105.53417343c2.48315701 11.25517912 10.17554562 20.62099961 20.72896296 25.23643277l227.99160177 99.75813425a71.98456279 71.98456279 0 0 1 43.13135783 65.93861527v150.85178906A71.98456279 71.98456279 0 0 1 1031.26990421 943.85339507z m-431.85339506-143.94213475c143.94213474 0 143.94213474-48.34058941 143.94213474-107.96334876s-64.45411922-107.96334877-143.94213474-107.96334877c-79.51500637 0-143.94213474 48.34058941-143.94213475 107.96334877s0 107.96334877 143.94213475 107.96334876zM1103.254467 296.07330247v148.9894213a35.97878598 35.97878598 0 0 1-44.15700966 35.03410667l-143.94213473-33.57660146a36.0057768 36.0057768 0 0 1-27.80056231-35.03410668V296.1002933c-35.97878598-47.98970852-131.95820302-71.98456279-287.91126031-71.98456279S347.53801649 248.11058478 311.53223967 296.1002933v115.385829c0 16.73431906-11.52508749 31.25538946-27.80056233 35.03410668l-143.94213473 33.57660146A35.97878598 35.97878598 0 0 1 95.63253297 445.06272377V296.07330247C162.81272673 152.13116772 330.77670658 80.14660493 599.47049084 80.14660493s436.63077325 71.98456279 503.81096699 215.92669754z" p-id="23785" fill="#999AAA"></path></svg>          <span class="txt right-dotte">400-660-0108</span>          <svg t="1538013544186" width="17" height="17" style="" viewBox="0 0 1024 1024" version="1.1" xmlns="http://www.w3.org/2000/svg" p-id="23556" xmlns:xlink="http://www.w3.org/1999/xlink"><defs><style type="text/css"></style></defs><path d="M902.60033922 650.96445566c-18.0718526-100.84369837-94.08399771-166.87723736-94.08399771-166.87723737 10.87530062-91.53186599-28.94715402-107.78733693-28.94715401-107.78733691C771.20003413 93.08221664 517.34798062 98.02553561 511.98620441 98.16348824 506.65661791 98.02553561 252.75857992 93.08221664 244.43541101 376.29988138c0 0-39.79946279 16.25547094-28.947154 107.78733691 0 0-75.98915247 66.03353901-94.0839977 166.87723737 0 0-9.63372291 170.35365477 86.84146124 20.85850523 0 0 21.70461757 56.79068296 61.50407954 107.78733692 0 0-71.1607951 23.19910867-65.11385185 83.46161052 0 0-2.43717093 67.16015592 151.93232126 62.56172014 0 0 108.5460788-8.0932473 141.10300432-52.14626271H526.33792324c32.57991817 44.05301539 141.10300431 52.1462627 141.10300431 52.14626271 154.3235077 4.59843579 151.95071457-62.56172013 151.95071457-62.56172014 6.00095876-60.26250183-65.11385185-83.46161053-65.11385185-83.46161052 39.77647014-50.99665395 61.4810877-107.78733693 61.4810877-107.78733692 96.45219231 149.49514952 86.84146124-20.85850523 86.84146125-20.85850523" p-id="23557" fill="#999AAA"></path></svg><a href="https://url.cn/5epoHIm?_type=wpa&amp;qidian=true" class="qqcustomer_s" target="_blank"><span class="txt">QQ客服（8:30-22:00）</span></a>          </em>        </div>        <div class="allow-info">          <a href="http://www.beian.gov.cn/portal/registerSystemInfo?recordcode=11010502030143" rel="noreferrer" target="_blank">公安备案号 11010502030143</a>          <a href="http://beian.miit.gov.cn/publish/query/indexFirst.action" rel="noreferrer" target="_blank">京ICP备19004658号</a>          <a href="https://csdnimg.cn/release/live_fe/culture_license.png" rel="noreferrer" target="_blank">京网文〔2020〕1039-165号</a>          <a href="https://www.csdn.net/company/index.html#statement" target="_blank">版权与免责声明</a>          <a href="https://blog.csdn.net/blogdevteam/article/details/90369522" target="_blank">版权申诉</a>          <a href="http://www.cyberpolice.cn/" target="_blank">网络110报警服务</a>        </div>        <div class="allow-info">          <a href="http://www.12377.cn/" target="_blank">中国互联网举报中心</a>          <a href="https://download.csdn.net/index.php/tutelage/" target="_blank">家长监护</a>          <a href="https://blog.csdn.net/blogdevteam/article/details/90369522" target="_blank">版权申诉</a>          <a href="http://www.bjjubao.org/" target="_blank">北京互联网违法和不良信息举报中心</a>          <a>©1999-2020 北京创新乐知网络技术有限公司</a>        </div>        <div class="bg-gray" style="display:none;">            <div class="feed_copyright">            <p class="fz12_baidu"><img style="display:none;vertical-align: middle;height:20px;margin-right:5px" src="https://csdnimg.cn/pubfooter/images/gongan.png"><a style="margin-right:16px;" href="http://www.beian.gov.cn/portal/registerSystemInfo?recordcode=11010502030143" rel="noreferrer" target="_blank" class="ml14">公安备案号 11010502030143</a> <a href="http://beian.miit.gov.cn/publish/query/indexFirst.action" rel="noreferrer" target="_blank" class="ml14" style="margin-right:16px;">京ICP备19004658号</a><a href="https://csdnimg.cn/release/live_fe/culture_license.png" rel="noreferrer" target="_blank" class="ml14" style="margin-right:16px;">京网文〔2020〕1039-165号</a><a style="margin-right:16px;" href="https://csdnimg.cn/cdn/content-toolbar/csdn-ICP.png" target="_blank">   经营性网站备案信息</a><span class="fz12_baidu">©1999-2020 北京创新乐知网络技术有限公司 </span></p>            </div>        </div>        <div class="allow-info-box" style="display:none;">        <a href="https://www.csdn.net/company/index.html#statement" target="_blank"><span>版权与免责声明</span></a>        <a href="https://blog.csdn.net/blogdevteam/article/details/90369522" target="_blank"><span>版权申诉</span></a>        <a href="https://download.csdn.net/index.php/tutelage/" target="_blank"><span>家长监护</span></a>        <a href="http://www.cyberpolice.cn/" target="_blank"><span>网络110报警服务</span></a>        <a href="http://www.12377.cn/" target="_blank"><span>中国互联网举报中心</span></a>        <a href="http://www.bjjubao.org/" target="_blank"><span>北京互联网违法和不良信息举报中心</span></a>        </div>    </div></div></div></div></main>

查看全文
如若内容造成侵权/违法违规/事实不符，请联系编程学习网邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！

01_线性回归：正规方程推导及梯度下降封装
正规方程推导|梯度下降封装线性回归简单介绍最小二乘法简单介绍线性回归求解方式：正规方程正规方程简单介绍正规方程推导过程线性回归的使用1.波士顿房价预测使用正规方程进行计算2.[天猫双十一销量预测](https://blog.csdn.net/CSDN16YD/article/details/107234109)线性回归求…...
2024/4/30 11:42:04
配置阿里云镜像加速器
配置镜像加速器使用加速器可以提升获取Docker官方镜像的速度docker配置文件目录/etc/docker 如果无配置文件,创建配置文件daemon.json{#地址为阿里云加速器地址"registry-mirrors": ["https://yg4swn7f.mirror.aliyuncs.com"] }重启配置,重启docker生效sys…...
2024/5/7 18:21:08
Selenium元素定位学习笔记
Selenium元素定位元素定位方法汇总使用ID定位我们以百度网站为例：我们进行百度一下搜索测试。@Testpublic void idTest() {//使用ID定位，定位输入框，并输入百度一下。driver.findElement(By.id("kw")).sendKeys("百度一下");//使用ID定位，并点击driv…...
2024/4/16 3:47:56
访问控制模型简介
自主访问控制模型(DAC)用户有权对自身创建的访问对象进行访问,并可将这些对象的访问权授予其他用户或从其他用户那里收回访问权限ACL(访问控制列表)特点缺陷+ 授权实施主体自主赋予和回收其他主体对资源的访问权限+ 系统管理员通过维护ACL来控制用户访问有关数据 +主体权限太大…...
2024/4/16 3:47:41
小说分销运营赚不赚钱就在这3个问题了！
关于创业，总有人在想，以后能不能做起来还是个未知数，就一直在观望，然而最后往往是连末班车都赶不上。下面跟大家分享一下小说分销运营要注意的三个问题。一、清晰的产品定位小说项目是以优质作品为竞争力，当年的起点就是凭借质量黏结了一批忠实的粉丝。他们认为平台只要…...
2024/5/7 14:45:41
3个月吃透阿里P8推荐的528页高可用可伸缩微服务架构，成功入蚂蚁
前言本文通过 Dubbo、Spring Cloud、Service Mesh 等技术构建微服务体系，并深入浅出的介绍了微服务架构发展历程、领域驱动设计、稳定性保证的常用手段、分布式事务的一致性方案，以及通过大量的案例探讨微服务落地方案，例如双活体系建设，分布式监控，微服务编排，百亿流量微…...
2024/4/27 12:52:26
警惕MD5带来的信息安全问题
1引言很多同学常用MD5，但并不明白其优缺点，有时用来存密码、有时存证件号、手机号的，其实这样做是有点风险的。具体看下面分析： 2MD5是什么?MD5(Message-Digest Algorithm)相当于一种hash算法，可以快速的计算出字符串(比如手机号、ID号(SFZ)、卡号、密码等)、文件的唯一摘…...
2024/4/19 16:43:48
利用HTML和css来制作网易新闻列表
网页新闻列表重点：如何使用行内块元素 ```css <!DOCTYPE html> <html lang="en"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><title&g…...
2024/4/16 3:47:46
图像数据读取的通道顺序
如果使用skimage读取图像，得到的结果顺序是（宽高通道数） from skimage import io image = io.imread(r"F:\vGG\niu.png") 输出为：(227, 227, 4)如果使用opencv读取图像，输出结果的顺序也是（宽高通道数） import cv2 image=cv2.imread(r"F:\vGG\niu.png&qu…...
2024/5/7 17:16:43
20200709学习笔记（远程scp+执行）
97的日志写不进去，最后发现是hostname字段超了，这货不叫h97叫localhost，爷佛了修改主机名称 hostnamectl set-hostname h97 写出来个自动往所有节点分发并读日志的脚本，下一步优化是让它自己找能读的去写，然后就是咋读即时的然后写成daemon了丑，但是好用！ autoscp.py …...
2024/4/22 16:01:00
网络安全学习篇17_物理层、数据链路层
上一篇博客：OSI与TCP/IP协议簇初步目录物理层网线数据链路层数据链路层交换机工作原理帧结构开始一、物理层（1层 Physical Layer ） 1.网线二、数据链路层 1. 数据链路层（2层 Data Link Layer）1.属于2层 2.传输单元：帧 3.帧结构:请参见图片帧头：6+6+2=14字节 MTU值：15…...
2024/4/16 3:48:27
Git添加用户名、密码、修改用户名密码
Git global setup git config --global user.name undefined git config --global user.email huoxinyue5@jd.comGit修改用户名密码 git config --global --replace-all user.name "要修改的用户名" git config --global --replace-all user.email"要修改的邮箱…...
2024/5/7 13:04:42
JAVA子类与继承
这个学期返校了，一直在学校忙别的东西(打游戏)，没什么时间写博客，现在放假，又开始闲起来了，把 java的东西整理整理 ==============================================================================在类的声明中，通过使用关键字extends来定义一个类的子类。当我们准备编…...
2024/4/20 15:04:43
React：Route ——Styling the Active Route
Styling the Active Route 用NavLink替代Link import {Route, NavLink} from react-router-dom;可以设置activeClassName=string；可以设置activeStyle={{}} class默认为active，故也可以在css文件中对active进行设置；注意点需要对to的地址进行exact操作，不然会作为前缀，…...
2024/4/24 15:57:10
R语言处理/读取带有JSON数据字段的csv文件/JSON文件
读取JSON文件(后缀为.json) 这个相对比较简单，R或者Java都可以轻松处理，下两个json相关的包就可以了 install.packages("rjson") install.packages("jsonlite") library(rjson) library(jsonlite)data = jsonlite::stream_in(file("jsondatafile1.j…...
2024/4/27 12:29:35
数据结构与算法——背包、队列、栈简介
背包（Bag）简介背包(Bag)是一种不支持从中删除元素的一种数据结构——这种数据结构的主要用处就是收集元素，并且提供遍历所有集合中的元素的方法。他的迭代顺序是随机的，并不确定。 APIBagpublic class Bag<Item> implements Iterable<Item> {Bag(); //创…...
2024/4/16 3:48:32
python学习-3
for循环： for 目标 in 表达式：循环体range( [start,] stop [, step=1] ) 生成一个从start参数值开始，到step参数值结束的数字序列break，continue与C语言一致列表普通列表，混合列表，空列表 aapend() 向列表添加元素（只能加一个） extend() 一个列表添加到另一个列表…...
2024/4/1 2:51:11
EsgynDB 简单步骤测试JDBC能否连通数据库
有时候我们会发现某个应用通过JDBC接口无法连通数据库，但从其他环境中是可以正常连接目标数据库的，为了排除是应用本身的问题，我们可以构建一个简单的JDBC测试程序来验证机器到数据库的连通性。主要步骤为：编写简单的Java测试程序TestConnEsg.java，内容如下import java.sq…...
2024/4/16 3:47:51
面向对象思想概述
概述 Java语言是一种面向对象的程序设计语言，而面向对象思想是一种程序设计思想，我们在面向对象思想的指引下，使用Java语言去设计、开发计算机程序。这里的对象泛指现实中一切事物，每种事物都具备自己的属性和行为。面向对象思想就是在计算机程序设计过程中，参照现实中事…...
2024/5/4 20:57:41
IDEA-Maven的环境配置及使用
IDEA-Maven的环境配置及使用一、Maven的下载IDEA的往期下载地址：https://www.jetbrains.com/1.点击进入1.往期的下载地址：http://www.apache.org/操作步骤：我们点击进入Projects---->如图（1）、（2）、（3）、（4）、（5）、解压后我们可以看到这个目录（6）、解压文件…...
2024/4/16 3:48:42

数据结构与算法（十一）Trie字典树

数据结构与算法（十一）Trie字典树

Trie字典树的基本概念

Trie字典树的基本操作

插入

查找

前缀查询

删除

如果单词是另一个单词的前缀

如果单词的所有字母的都没有多个分支，删除整个单词

如果单词的除了最后一个字母，其他的字母有多个分支

基于链表的Trie字典树

基于Trie的Set性能对比

更多关于Trie的话题

LeetCode相关线段树的问题

LeetCode第208号问题

LeetCode第211号问题

LeetCode第677号问题

Reference

相关文章

最新文章