1. 在用户输入英文单词时,经常发生错误,我们需要对其进行纠错。假设已经有一个包含了正确英文单词的词典,请你设计一个拼写纠错的程序。(1)请描述你解决这个问题的思路;(2)请给出主要的处理流程,算法,以及算法的复杂度;(3)请描述可能的改进(改进的方向如效果,性能等等,这是一个开放问题)。
2. 请设计一个字典。以字符串为索引,存储用户定义的定长结构。要求有增、删、查、改的功能。已经给定一个函数,可以由字符串映射到一个签名,每个签名由两个unsigned int类型组成。假设每一个字符串能够对应唯一的一个签名,完全没有重复(或者重复的概率可以忽略),并且签名分布足够均匀。
请描述你的数据结构?内存如何申请?增、删、查、改的功能如何实现?如果操作很频繁,该如何优化?
需要把整个数组都进行排序的。
3. 一个单词字典库,单词个数约为10万,每个单词长度不超过16,单词都是由小写字母组成,同时给出16个小写字母,
请设计一种高效算法来找到用这些给出字母拼出一个字典中最大长度的单词。给出的16个字母每个字母最多使用一次,也可以不使用。
存在多解的时候给出任意一个最优答案就行。
例如:给出adeenrstuvxyzuki可以拼出adventures
请详细描述你的算法思路(如需要,可给出代码\伪代码来辅助描述),并分析其时间复杂度。最后请分析下你的算法以及数据结构的优缺点,存在哪些可改进的地方。
参考:http://hi.baidu.com/lbxthinker/blog/item/aaa0450914a0be9c0b7b8236.html
分享到:
相关推荐
算法面试通关40讲完整课件 37-39 字典树 算法面试通关40讲完整课件 37-39 字典树 算法面试通关40讲完整课件 37-39 字典树 算法面试通关40讲完整课件 37-39 字典树 算法面试通关40讲完整课件 37-39 字典树 算法面试...
16-字典树.pdf
用C语言实现的字典树算法,用C语言实现的字典树算法。
acm字典树模板!acm字典树模板!acm字典树模板!acm字典树模板!
字典树算法,可以很方便的实现多叉树,而且查找复杂度教低,是ACM算法设计常用数据结构
字典树:又称为Trie,是一种用于快速检索的多叉树结构。Trie把要查找的关键词看作一个字符序列,并根据构成关键词字符的先后顺序构造用于检索的树结构;一棵m度的Trie树或者为空,或者由m棵m度的Trie树构成。
这是本人在ACM路上总结的比较有代表性的字典树的问题,希望能给ACMER带来帮助
字典树
java是实现的快速单词检错程序,内部算法使用字典树匹配。 开发环境netbeans
文件包括以下子文件,每个文件里面包括了一定数量的ppt,doc,c++模板代码,希望对算法的入门的学习者有用。...10-字典树 11-二分图 12-网络流 13-高精度 14-几何 15-自动机 16-DP_01背包 16-DP_树状dp 16-贪心 17-数论
功能: 通过字典树等算法模拟了一个输入法频率提示工具。 原理: 没记错的话是用的字典树频率的统计方式做的。
NULL 博文链接:https://auauau.iteye.com/blog/675645
树状数组 后缀数组 字典树 多串匹配算法及启示
实现字典树的c++代码,数据结构跟思路都很清晰
* 字典树 * 遍历-层次遍历 * 遍历-中序遍历-非递归 * 遍历-前序遍历-非递归 * 遍历-后序遍历-非递归 * 二叉查找树-两数之和 * 二叉查找树-中第K小的元素 * 二叉查找树-从有序数组中构造二叉查找树 * 二叉查找树-从...
数据结构与算法 课程设计说明书 拼写检查器 trie树 字典树.doc
python 数据结构 算法 LeetCode 牛客 面试 编程之美 动态规划 字典树 快速排序 树 字符串 数组 链表 全排列 堆排序 位运算 大数相加
字典树:又称为Trie,是一种用于快速检索的多叉树结构。
六、树和树的算法 6-01 树的概念 6-02 二叉树的概念 6-03 二叉树的广度优先遍历 6-04 二叉树的实现 6-05 二叉树的先序、中序、后序遍历 6-06 二叉树由遍历确定一棵树 ———————————————— 版权...
- 集合、字典、散列集 - 常见算法 - 递归 - 排序 - 枚举 - 算法复杂度分析 - 算法思维 - 分治 - 贪心 - 动态规划 - 高级数据结构 - 树、图 - 深度优先和广度优先搜索 本小节会带领大家快速过一遍数据结构...