首页 > 代码库 > 《Cracking the Coding Interview》——第18章:难题——题目5
《Cracking the Coding Interview》——第18章:难题——题目5
2014-04-29 01:51
题目:你有一个文本文件,每行一个单词。给定两个单词,请找出这两个单词在文件中出现的其中一对位置,使得这两个位置的距离最短。
解法:我的思路是建立倒排索引,计算出所有单词出现的所有位置。下面代码只给出了两个索引的处理方法。倒排索引一般以链表的形式出现,通过顺序扫描两个链表,类似归并排序算法中的merge过程,就能够找出最短距离。请看代码。
代码:
1 // 18.5 Given a text file containing words, find the shortest distance between two words. 2 #include <algorithm> 3 #include <climits> 4 using namespace std; 5 6 struct ListNode { 7 int val; 8 ListNode *next; 9 ListNode(int _val = 0): val(_val), next(nullptr) {}; 10 }; 11 12 class Solution { 13 public: 14 int minDist(ListNode *head1, ListNode *head2) 15 { 16 // the two list records the forward indices of two word, i.e. their occurrence position. 17 // For example, 1->4->5->nullptr means the word appears at 1st, 4th and 5th line. 18 19 int min_dist = INT_MAX; 20 ListNode *p1, *p2; 21 22 p1 = head1; 23 p2 = head2; 24 while (p1 != nullptr && p2 != nullptr) { 25 if (p1->val < p2->val) { 26 min_dist = min(min_dist, p2->val - p1->val); 27 p1 = p1->next; 28 } else { 29 min_dist = min(min_dist, p1->val - p2->val); 30 p2 = p2->next; 31 } 32 } 33 34 return min_dist; 35 } 36 };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。