- 浏览: 585724 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
字典树 又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。
它有3个基本特性:
1)根节点不包含字符,除根节点外每一个节点都只包含一个字符。
2)从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
3)每个节点的所有子节点包含的字符都不相同。
如用 ak ab ab ai oricon orish 所构造出来的字典树为:
例: POJ2001,题目大意:
给你很多个字符串,让你找每个字符串的最短前缀,但这么多字符串前缀不能有相同的,要能唯一标识一个字符串,而且前缀长度尽量小。
样例:
Sample Input
carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate
Sample Output
carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona
AC 代码:
后记:
题目虽然在北大PKU上AC了(说明解答没有错),但在自己电脑上DOS下运行时不能输出答案,问题在下面这段代码:(不然跳出循环)
网上也没有找到答案,到底如何处理本题的输入,请各位提出,谢谢!
它有3个基本特性:
1)根节点不包含字符,除根节点外每一个节点都只包含一个字符。
2)从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
3)每个节点的所有子节点包含的字符都不相同。
如用 ak ab ab ai oricon orish 所构造出来的字典树为:
例: POJ2001,题目大意:
给你很多个字符串,让你找每个字符串的最短前缀,但这么多字符串前缀不能有相同的,要能唯一标识一个字符串,而且前缀长度尽量小。
样例:
Sample Input
carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate
Sample Output
carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona
AC 代码:
import java.util.Scanner; import java.util.List; import java.util.ArrayList; public class Main{ private int SIZE = 26; private TrieNode root; //字典树的根 private List<String> l=new ArrayList<String>(); public Main() { //初始化字典树 root = new TrieNode(); } private class TrieNode { //字典树节点 private int num;//有多少字符通过这个节点. private TrieNode[] son;// 所有的儿子节点 private boolean isEnd;//是不是最后一个节点 private char val;// 节点的值 TrieNode() { num = 1; son = new TrieNode[SIZE]; isEnd = false; } } public void insert(String str) { //在字典树中插入一个单词 if (str == null || str.length() == 0) { return; } TrieNode node = root; char[] letters=str.toCharArray(); for (int i = 0, len = str.length(); i < len; i++) { int pos = letters[i] - 'a'; if (node.son[pos] == null) { node.son[pos] = new TrieNode(); node.son[pos].val = letters[i]; } else { node.son[pos].num++; } node = node.son[pos]; } node.isEnd = true; } // 在字典树中查找. public void search(String str) { if (str == null || str.length() == 0) { return ; } TrieNode node = root; char[] letters=str.toCharArray(); for (int i = 0, len = str.length(); i < len; i++) { int pos = letters[i] - 'a'; System.out.printf("%c",letters[i]); node=node.son[pos]; if( node.num==1) break;; } } private void go() { Scanner in = new Scanner(System.in); String s=null; int num=0; while(in.hasNext()){ s=in.next(); l.add(s); insert(s); num ++; } for(int i = 0; i < num; i++){ System.out.printf("%s ",l.get(i)); search(l.get(i)); System.out.println(); } } public static void main(String[] args) { Main ma=new Main(); ma.go(); } }
后记:
题目虽然在北大PKU上AC了(说明解答没有错),但在自己电脑上DOS下运行时不能输出答案,问题在下面这段代码:(不然跳出循环)
Scanner in = new Scanner(System.in); String s=null; int num=0; while(in.hasNext()){ s=in.next(); l.add(s); insert(s); num ++; }
网上也没有找到答案,到底如何处理本题的输入,请各位提出,谢谢!
评论
2 楼
quanminy
2012-12-23
int pos = letters[i] - 'a'; 这样得到的指针位置不保险,输入数字或大写字符或其他字符程序直接挂调。
1 楼
quanminy
2012-12-23
Java代码
Scanner in = new Scanner(System.in);
String s=null;
int num=0;
while(in.hasNext()){
s=in.next();
l.add(s);
insert(s);
num ++;
}
这个 部分是因为Scanner 不断的等待前台输入数据,所以会不断的循环。可以设置一些特殊的字符作为命令入口,结束循环。
Scanner in = new Scanner(System.in);
String s=null;
int num=0;
while(in.hasNext()){
s=in.next();
l.add(s);
insert(s);
num ++;
}
这个 部分是因为Scanner 不断的等待前台输入数据,所以会不断的循环。可以设置一些特殊的字符作为命令入口,结束循环。
发表评论
-
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2332北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1954import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1837POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1359接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2425当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1776关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1682关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1758关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1708一、树状数组是干什么的? 平常我们会遇到一些对数组进 ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2032POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2491设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(三)懒操作(兼解POJ1823) JAVA
2012-12-02 15:37 2040继续上文"线段树入门学习(二)" ht ... -
线段树入门学习(二)(兼解POJ3468) JAVA
2012-11-30 16:55 2502继续上文http://128kj.iteye. ... -
线段树入门学习(兼解HDU1754)
2012-11-30 11:24 2611先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是 ... -
AVL树及JAVA实现
2012-11-26 16:34 2225一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 2018形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2793例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18586堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3990一、什么是并查集 ... -
根据二叉树前序遍历和中序遍历的结果输出后序遍历(java)
2012-10-07 19:58 3277前序遍历的第一个元素为根节点,在中序遍历中找到这个根节点 ...
相关推荐
可变长数组和字典树Java代码实现。比较容易复制和学习。
这是个人搜集的LeetCode上一些经典面试问题的Java语言实现,涉及数组、链表、堆栈、队列、二叉树、并查集、字典树等15个维度,供各位学习参考使用!
全套微服务架构,视频学习java微服务架构,包括如下 第1章 微服务简介 001构建单体应用 002微服务解决复杂问题 003微服务的优点 004微服务的缺点 第2章 Linux使用 005Linux 简介 006Linux 与 Windows ...
- 使用最新技术栈,社区资源丰富,基于Java 21(Core Module Support 17-21)、Spring Boot 3.2。 (Support Virtual Threads/fibre/loom) - 基于注解的动态查询(Specification),可根据需要扩充查询注解。 - 支持...
学习数据结构的一些代码,包括数组,链表,二分搜索树,集合,映射,优先队列,并查集,线段树,字典树(前缀树),AVL树,红黑树,哈希表,如有错误,多多指教。 我们在调用set,map等标准库里的东西,大多使用平衡...
操作可行性分析,系统的主要业务和业务流程分析,还包括数据字典的设计,管理信息系统的设计,IPO图和决策树设计,管理信息系统的实施和运行,还有部分源代码,该希望大家多多支持,欢迎大家哦评论,积极交流学习!
字典、关联数组 栈 Stack 是线程安全的。 内部使用数组保存数据,不够时翻倍。 树 二叉树 每个节点最多有两个叶子节点。 完全二叉树 叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干...
字典树 并查集(基于数组索引) 并查集(基于树) 并查集(使用节点size优化) 并查集(使用rank优化) 平衡二叉树 leetcode按题目类型分类 leetcode按难易分类 写在最后 我的数据结构是从的开始学起的,算是我数据...
字典、关联数组 栈 树 二叉树 完全二叉树 平衡二叉树 二叉查找树(BST) 红黑树 B,B+,B*树 LSM 树 BitSet 常用算法 计数排序 桶排序 基数排序 二分查找 Java 中的排序工具 布隆过滤器 字符串比较 KMP 算法 深度...
java开发oa系统源码下载 平台简介 ...字典管理:对系统中经常使用的一些较为固定的数据进行维护。 参数管理:对系统动态配置常用参数。 通知公告:系统通知公告信息发布维护。 操作日志:系统正常操作日志
字典管理:对系统中经常使用的一些较为固定的数据进行维护。 参数管理:对系统动态配置常用参数。 通知公告:系统通知公告信息发布维护。 操作日志:系统正常操作日志记录和查询;系统异常信息日志记录和查询。 登录...
leetcode计算机刷墙 主要包括以下内容 LeetCode刷题笔记 专题学习笔记 另一个目的也是怕笔记丢了,毕竟typora虽然强大,但不能云端存储。...14、字典树 15、堆 16、前缀和 17、背包问题 ...... 陆续更新中
现已完成所有探索中的数据结构类卡片,后又添加了动态规划,字典树,滑动窗口,树状数组,回溯专题。 LeetcodeDB.md对应Leetcode中的题目。 每日一题.md从2020年7月1日开始。 剑指offer.md对应leetcode中的题目(已...
数据字典管理:支持中、英文信息,支持无限级别分类配置,动态控制是否可用等。 部门信息管理:支持中、英文无限级别部门信息增加,删除,修改操作,部门列表、树心查询等。 日志管理:系统日志列表查询、在线...
java lru leetcode 开始 DaLiu Start... 数据结构 (data structure) 是相互之间存在一种或多种特定关系的数据元素的...字典树 Trie, etc 特殊 位运算Bitwise, 布隆过滤器BloomFilter LRU Cache 算法 If-else, switch -
5 数据字典内容和使用 目标 5-2 数据字典 5-3 数据字典内容 5-5 如何使用数据字典 5-6 数据字典视图种类 5-7 动态性能表 5-8 查询数据字典和动态性能视图 5-9 数据字典例子 5-10 小结 5-10 6 维护控制文件 目标 6-2...
- 字典管理:对系统中经常使用的一些较为固定的数据进行维护。 - 参数管理:对系统动态配置常用参数。 - 通知公告:系统通知公告信息发布维护。 - 操作日志:系统正常操作日志记录和查询;系统异常信息日志记录和...
字符串:字典树、后缀树 动力 之前有一个爬虫机会,Airbnb。这可以算是一个超好的公司了,待遇福利都很好,但是我在他们的一面上就挂了,就是算法。给我做的题目是leetcode简单级别的,如果现场面是medium到hard级别...
java开发oa系统源码下载 平台简介 一直想做一款后台管理系统,看了很多优秀的开源项目但是发现没有合适的。于是利用空闲休息时间开始自己写了一套后台系统。如此有了若依。她可以用于所有的Web应用程序,如网站管理...