存档

文章标签 ‘百度面试’

兄弟单词 — 两种算法实现

2013年2月28日 2 条评论

---

兄弟单词这个题目最初见于《编程珠玑》,但是里面给出的方法是最笨的,一般不提倡采用吧;这个题目在之前的百度面试中也遇到过,本文实现两种方法的代码,方法如下:

方案一:使用数据结构 map<key,list>。兄弟单词共用一个签名key,key为单词内部排序后的词条,list存储同一key的单词集合;相对于编程珠玑中的方法,该方法在空间上节省了每个单词一个key的空间;在时间上,不再需要二分查找,O(1)的查找;但是这种方法还可以优化,见方案二

方案二:使用trie树。trie树又称字典树,在面试题中关于“字符串”与“数字串”类型的问题中高频出现,非常实用。对于兄弟单词,兄弟单词公用一个key自不必说,只是trie的节点结构应该多出一个域list,用来存储key对应的兄弟单词;具体节点结构应该为


bool isStr, Node* next[26], vector<const char*> brothers

该方案查询的复杂度为O(L),L为key的平均长度;空间上则有很大的优化,例如单词的key有“abc”、“abcd”、“abcde”之类的形式,则这些key也能达到空间公用,不过数据量大还好,数据量小,trie树开辟的空间还是有些浪费的,不多言,上代码:

【测试用例】


input:

cba acb bc cb b

output:

cba acb

bc cb

b

【方案一:使用哈希map实现兄弟单词】

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

#define MAXLEN 100  /* 单词最大长度 */

/* qsort比较函数 */
int charcmp(const void *p, const void *q)
{
	return *(char *)p - *(char *)q;
}

/* 打印输出 & 释放内存 */
void output(map<string,vector<char*>> dic)
{
	for(map<string,vector<char*>>::iterator it = dic.begin(); it != dic.end(); ++it)
	{
		for(vector<char *>::iterator itv = it->second.begin(); itv != it->second.end(); ++itv)
		{
			printf("%s ",*itv);
			free(*itv);
		}
		printf("\n");
	}
}

void main()
{
	map<string,vector<char*>> dic;  /* 存储<key,兄弟单词集> */
	char word[MAXLEN];
	int len = 0;

	while(scanf("%s",word) != EOF) /* ctrl+z结束输入 */
	{
		len = strlen(word);
		if(len > 0)
		{
			char * ptr = (char *) malloc(len+1);
			strcpy(ptr,word);
			qsort(word,len,sizeof(char),charcmp);
			string key(word);
			dic[key].push_back(ptr);
		}
	}
	output(dic);
}

【方案二:使用trie树实现兄弟单词】

阅读全文...

定长线段最多覆盖点的个数

2013年1月5日 2 条评论

---

来自之前百度一面的题目:给定一系列x轴的点坐标,例如 1,3,7,8,9,11这些坐标升序放在数组中,现在给一根绳子,长度为4,问绳子最多能覆盖的点数有多少,例如绳子放前面只能覆盖两个点,1,3,如果放后面能覆盖4个点。

题目不难,但也不是太容易想出来,两个指针前后跑的思路:两个指针往前走,前面的负责加,后面的负责减,前面的每次都移动,如果点间隔长度大于绳子长度,后面指针移动。

阅读全文...