careercup-高等难度 18.5
2024-10-13 22:06:40
18.5 有个内含单词的超大文本文件,给定任意两个单词,找出在这个文件中这两个单词的最短距离(也即相隔几个单词)。有办法在O(1)时间里完成搜索操作吗?解法的空间复杂度如何?
解法1:我们假设单词word1和word2谁在前谁在后无关紧要。要解决此题,我们需要遍历一次这个文件。在遍历期间,我们会记下最后看见word1和word2的地方,并把它们的位置存入lastPosWord1和lastPosWord2中。碰到word1时,就拿他跟lastPosWord2比较,如有必要则更新min,然后更新lastPosWord1.每碰到word2时,我们也执行同样的操作。遍历结束后,就可以得到最短距离。
实现算法:
int ShortestDist(string text[], int n, string word1, string word2){
int min = kMaxInt / ;
int pos1 = -min;
int pos2 = -min; for(int pos=; pos<n; ++pos){
if(text[pos] == word1){
pos1 = pos;
int dist = pos1 - pos2;
if(dist < min)
min = dist;
}
else if(text[pos] == word2){
pos2 = pos;
int dist = pos2 - pos1;
if(dist < min)
min = dist;
}
} return min;
}
如果上述代码要重复调用(查询其他单词对的最短距离),可以构造一个散列表,记录每个单词及其出现的位置。然后,我们只需找到listA和listB中(算术)差值最小的那两个值。
hash_map<string,vector<int> > listA;
hash_map<string,vector<int> > listB;
listA:{1,2,9,15,25}
listB:{4,10,19}
最新文章
- chattr的常用参数详解
- ubuntu下安装JDK并搭建activeMQ
- spring mvc 重定向问题
- 获取Token不完整问题
- raspbian 静态IP
- Two Sigma OA
- jquery插件——日历控件
- 中兴电信光纤猫F612管理员密码获取方法
- 菜鸟学习 - Unity中的热更新 - LuaInterface用户指南
- Android 开发转型前端准备知识
- POJ 3279(Fliptile)题解
- 【工作笔记四】去掉a标签超链接的虚线框的方法
- 日期、时间选择器(DatePicker和TimePicker)的功能与用法
- JSON的服务器开发之路
- ES6学习重难点总结(持续更新)
- hdu2196 树形dp经典|树的直径
- Exploring the world of Android :: Part 1
- 证明 U and V={0}时 dim(U+V)=dim(U)+dim(V)
- 【三分钟视频教程】iOS开发中 Xcode 报 apple-o linker 错误的#解决方案#
- Oracle 11gR2 RAC 新特性说明
热门文章
- 【转】What&#39;s the difference between simulation and emulation
- TopFreeTheme精选免费模板【20130617】
- Yii 1.1 URL两个笔记 同时支持PATH于GET路由和隐藏index.php
- samba服务设置,Linux系统和Windows文件共享
- Hadoop HDFS概念学习系列之分布式文件管理系统(二十五)
- Hadoop MapReduce概念学习系列之map并发任务数和reduce并发任务数的原理和代码实现(十八)
- sql的join用法
- LC并联谐振回路
- POJ1469COURSES(二分图匹配)
- C#POP3协议实现SSL验证登陆GMAIL