前缀树 前缀树是一种可以完成前缀相关查询的树状结构。其构建过程如下: 单个字符串中,字符从前到后的加到一棵多叉树上; 字符放在路上,节点上有专属的数据项(常见的是 pass 和 end 值); 所有样本都这样添加,如果没有路就新建,如有路就复用; 沿途节点的 pass 值增加 1,每个字符串结束时来到的节点 end 值增加 1。 代码实现不是很复杂,主要注意删除一个字符串时,需要先判断是否存在。当最后一个字符删除后,其 pass 值为 0,要依次删除(释放)后续的子节点(路径已经没用了)。 class Node {…

2021-03-04 0条评论 91点热度 0人点赞 SilverLining 阅读全文

堆结构 堆与二叉树 堆结构是用数组实现的完全二叉树结构。 完全二叉树,通俗的解释就是,一颗二叉树要么每一层都是满的,要么不满的那一层也是正在从左向右填满的。 大根堆:完全二叉树中每棵子树的最大值都在顶部; 小根堆:完全二叉树中每棵子树的最小值都在顶部。 将数组表示为完全二叉树,其下标与二叉树节点有如下关系: 0 / \ 1 2 / \ / \ 3 4 5 6 节点左子节点:2 * i + 1 节点右子节点:2 * i + 2 父节点:(i - 1) / 2 有些实现会屏蔽掉数组的第 0 个下标,从下标 1 开始使用…

2021-02-25 0条评论 140点热度 0人点赞 SilverLining 阅读全文

桶排序 桶排序的思想如下: 桶排序思想下的排序都是不基于比较的排序; 时间复杂度为 O(N),额外空间复杂度为 O(M); 应用范围有限,需要样本的数据状况满足桶的划分。 这里的桶可以由数组、队列、栈等等来实现,这是一种基于统计的排序算法。 常见的桶排序算法有计数排序和基数排序。 计数排序 计数排序的适用场景要求数据范围不大,且有规律。例如对员工按年龄排序。 通常可以假设员工的年龄是正整数,分布在 [0 ... 100],我们就建立 100 个桶(Bucket)来统计这些数据。那么在一次 O(N)的遍历中,我们就可…

2021-02-21 0条评论 139点热度 0人点赞 SilverLining 阅读全文

归并排序 传统的数组排序算法时间复杂度是 O(N^2),因为每一次扫描数组,只能将 1 个数字移动到目标位置。每一个数的排序过程之间是互不关联的,也就浪费了一些有用的信息。 递归实现 我们用递归的思想来考虑排序问题,如果一个数组分为左右两部分,且两部分别都是有序的,那么我们只需要做一次 O(N)的操作,就可以将整个数组排序。这个操作就是归并排序核心的算法。 然后,为了合并整个大数组,我们先要将这个数组一分为二个部分,然后再继续分为两部分,直到达到最小子问题:当数组中只有一个元素时,他天然就是有序的。 public …

2021-02-15 0条评论 135点热度 0人点赞 SilverLining 阅读全文

递归 通俗地讲,递归就是自己调用自己。递归函数的意义,是将一个大问题,分解为若干个同等算法,但规模更小的子问题。通过解决一系列小范围的子问题,总而在大范围上解决整个问题。 求数组的最大值 举个例子,求一个数组中的最大值。常规的做法是扫描整个数据,用一个变量记录下最大值,时间复杂度为 O(N)。 而递归的思想是,要求一个数组中的最大值,假设有 10 个数,那么我只要找出左边 5 个数的最大值,和右边 5 个数的最大值,一比较,就可以得到整个数组的最大值。 因此这个问题被分解为了,求两个长度为 5 的数组中的最大值,这…

2021-02-14 0条评论 178点热度 0人点赞 SilverLining 阅读全文

链表 链表是一种非连续的数据结构,常见的实现有单链表和双向链表。 class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } class DoubleNode { public int value; public DoubleNode last; …

2021-02-13 0条评论 228点热度 0人点赞 SilverLining 阅读全文

LifeCycle 接口 上一篇文章中提到,Tomcat 中主要有这些重要的组件: Server:Server 容器代表了一个 tomcat 实例(Catalina 实例),可以包含一个或多个 Service 容器; Service:Service 是提供具体的对外服务的,一个 Service 容器中可以有多个 Connector 组件(监听不同的端口请求并处理)和一个 Servlet 容器(做具体的业务处理逻辑); Engine 和 Host:Engine 组件是 Servlet 容器的核心,它支持定义多个虚拟主…

2021-02-11 0条评论 148点热度 0人点赞 SilverLining 阅读全文

概述 Tomcat 主要有两部分核心功能: HTTP 服务器:实现 Socket 通信(TCP/IP),解析 HTTP 报文 Servlet 容器:提供一些默认 Servlet 的实现,管理自定义的 Servlet Servlet 容器是如何工作的 Servlet 容器是一个复杂的系统,但是,它有 3 个基本任务,对每个请求,servlet 容器会为其完成以下 3 个操作:: 创建一个 request 对象,用可能会在调用的 Servlet 中使用到的信息填充该 request 对象,如参数、头 cookie、查询…

2021-02-05 0条评论 165点热度 0人点赞 SilverLining 阅读全文

美颜焦虑症 人有着一种可以理解的癖好,总要给任何奇迹提供证据。 ——《铁皮鼓》 他那奇特而甜美的声音弥散进我的灵魂,通过音乐我的灵魂开始飞翔。 ——《歌剧魅影》 出身不明和相貌奇丑这两重灾难,早就使他同世界隔离。圣母院对于他就是蛋壳,是窝,是家,是故乡,是宇宙。 ——《巴黎圣母院》 美貌是一层面纱,它常常用来遮掩许多缺点。(巴尔扎克)——《深红累之渊》 除了用口红,也用昂扬的生命让自己亮丽。 ——《深红累之渊》 无限剁手症 一张海报抵得过千言万语,却有一半是假,它们说:请随我言,随我形,随我所登的形象那样。 ——《…

2021-01-13 0条评论 361点热度 0人点赞 SilverLining 阅读全文

了解一个国家,最好是从文化入手。而理解一个国家文化的捷径,就是电影。简单来讲,就是你只要花两个小时的时间,就能看到一个国家或者一种文化的侧面了;而不像是你要去读一本书,或者亲自去旅游,或者去结交一个外国朋友。 日本是亚洲最早输入电影的国家,也是最早向亚洲其他各地输出电影生产模式和电影美学的国家。 电影是最不受 “文化折扣” 影响的文化艺术门类,电影语言和人们天然亲近,可以跨越种族和文化的障碍,人们不需要专门学习就能看懂电影。电影从诞生的那一天起就是商业化的,现在越来越国际化的电影市场,使电影跨越了时间和地域的障碍。…

2020-07-22 0条评论 629点热度 0人点赞 SilverLining 阅读全文