64,649
社区成员
发帖
与我相关
我的任务
分享求教两道迅雷笔试题
一． 有n个文件的长度记载在一个无符号64 位整数数组中unsigned __int64 file_length[n]，把这n 个文件从逻辑上按序首尾拼接在一起形成一个逻辑上的大文件，然后以每块长度为unsigned block_length把这个逻辑上的大文件划分成大小相等的数据块（当然，最后一块有可能比block_length小），请定义和实现一个函数，把边界块的序号集合返回给函数的调用者（第一个数据块序号为0）。
注：边界块指的是跨多个文件的数据块。
这个题目比较简单，要求文件总长度，然后除以n。关键是如果文件总长度越界怎么办？
二、如果两个英文单词，组成它们的字符集合相同，而且相同字符出现的次数也相同，则称这两个词匹配：比如说：同”abbc”与词 ”babc”是匹配的。请写出两个字符串的匹配函数bool is_matching( const char* word1, const char* word2);
注：边界块指的是跨多个文件的数据块。
这个题目比较简单，要求文件总长度，然后除以n。关键是如果文件总长度越界怎么办？
二、如果两个英文单词，组成它们的字符集合相同，而且相同字符出现的次数也相同，则称这两个词匹配：比如说：同”abbc”与词 ”babc”是匹配的。请写出两个字符串的匹配函数bool is_matching( const char* word1, const char* word2);
...全文
请发表友善的回复…
发表回复
shiqicai 2009-10-22
- 打赏
- 举报
这道题有很强的现实背景,这就是bt协议描述一个种子中多个文件的方式.
liate1 2009-09-11
- 打赏
- 举报
[Quote=引用 13 楼 hairetz 的回复:]
C/C++ codebool is_matching(constchar* word1,constchar* word2)
{int bit_map[26]={0};//只针对小写字母，所以是26个，包括大写的话，52个元素即可int i;if(strlen(word1)!=strlen(word2) )returnfalse;for(i=0; i<strlen(word1);++i)
{
bit_map[(word1[i]-'a')]++;
bit_map[(word2[i]-'a')]--;
}for(i=0; i<26;++i)if(bit_map[i]!=0)returnfalse;returntrue;
}int _tmain(int argc, _TCHAR* argv[])
{char a[]="aabbc";char b[]="abcab";if(is_matching( a, b))
cout<<"match"<<endl;else
cout<<"false"<<endl;
system("pause");return0;
}
[/Quote]
===========
要是加上指针空值判断的话，应该会更好点
C/C++ codebool is_matching(constchar* word1,constchar* word2)
{int bit_map[26]={0};//只针对小写字母，所以是26个，包括大写的话，52个元素即可int i;if(strlen(word1)!=strlen(word2) )returnfalse;for(i=0; i<strlen(word1);++i)
{
bit_map[(word1[i]-'a')]++;
bit_map[(word2[i]-'a')]--;
}for(i=0; i<26;++i)if(bit_map[i]!=0)returnfalse;returntrue;
}int _tmain(int argc, _TCHAR* argv[])
{char a[]="aabbc";char b[]="abcab";if(is_matching( a, b))
cout<<"match"<<endl;else
cout<<"false"<<endl;
system("pause");return0;
}
[/Quote]
===========
要是加上指针空值判断的话，应该会更好点
frank529 2009-09-11
- 打赏
- 举报
感谢各位的热心帮助
papaofdoudou 2009-09-10
- 打赏
- 举报
mark
猫已经找不回了 2009-09-10
- 打赏
- 举报
[Quote=引用 19 楼 haierpro 的回复:]
引用 16 楼 hairetz 的回复:
引用 14 楼 haierpro 的回复:
10楼的算法看不明白，
m_block=(file_length[i]-m_last) % block_length;
不知道上句中的 file_length[i]-m_last 有没有可能为负数，负数求余是什么结果呢？
11楼的算法好像有问题，好像结果反了，把非边界块存在ans[]中了。
第一题我只写了思路，可能边界块是前一个块。
第2个题目比较简单，顺便写的，结果正常，没有优化及检查，体会思路即可。
第一题看错了，不是结果反了，但是如果没有边界块时，结果肯定是不对的。还有在循环中做乘法，效率有点低。
[/Quote]
这个容易，在等于逻辑上加一个continue就可以了，说了只是写思路，当然具体实现要改的
引用 16 楼 hairetz 的回复:
引用 14 楼 haierpro 的回复:
10楼的算法看不明白，
m_block=(file_length[i]-m_last) % block_length;
不知道上句中的 file_length[i]-m_last 有没有可能为负数，负数求余是什么结果呢？
11楼的算法好像有问题，好像结果反了，把非边界块存在ans[]中了。
第一题我只写了思路，可能边界块是前一个块。
第2个题目比较简单，顺便写的，结果正常，没有优化及检查，体会思路即可。
第一题看错了，不是结果反了，但是如果没有边界块时，结果肯定是不对的。还有在循环中做乘法，效率有点低。
[/Quote]
这个容易，在等于逻辑上加一个continue就可以了，说了只是写思路，当然具体实现要改的
big_cucumber 2009-09-10
- 打赏
- 举报
讯雷是每周6个工作日哦
jiao22220509 2009-09-10
- 打赏
- 举报
[Quote=引用 14 楼 haierpro 的回复:]
10楼的算法看不明白，
m_block=(file_length[i]-m_last) % block_length;
不知道上句中的 file_length[i]-m_last 有没有可能为负数，负数求余是什么结果呢？
11楼的算法好像有问题，好像结果反了，把非边界块存在ans[]中了。
[/Quote]
不知道上句中的 file_length[i]-m_last 有没有可能为负数，负数求余是什么结果呢？
---解释:我的确没有考虑到当下一个小于剩余块的问题,,我检讨,,顺便补充一下,如果小于的话,其实边界块的编号还是那个,,只不过那个m_last 会变小,继续下一个块的检查.
我当时蛮急这思路的,,就写了伪代码,没有经过调试,,而且算法应该还有的优化
10楼的算法看不明白，
m_block=(file_length[i]-m_last) % block_length;
不知道上句中的 file_length[i]-m_last 有没有可能为负数，负数求余是什么结果呢？
11楼的算法好像有问题，好像结果反了，把非边界块存在ans[]中了。
[/Quote]
不知道上句中的 file_length[i]-m_last 有没有可能为负数，负数求余是什么结果呢？
---解释:我的确没有考虑到当下一个小于剩余块的问题,,我检讨,,顺便补充一下,如果小于的话,其实边界块的编号还是那个,,只不过那个m_last 会变小,继续下一个块的检查.
我当时蛮急这思路的,,就写了伪代码,没有经过调试,,而且算法应该还有的优化
devilbelief 2009-09-10
- 打赏
- 举报
#include <map>
#include <iostream>
#include <string.h>
using namespace std;
bool is_matching( const char* word1, const char* word2);
int main(int argc, char **argv)
{
if( is_matching("abab","bbaa") )
{
cout << "==\n";
}
else
{
cout << "!=\n";
}
return 0;
}
bool is_matching(const char* word1, const char* word2)
{
int len;
if( NULL == word1 || NULL == word2 || (len = strlen(word1)) != strlen(word2) )
{
return false;
}
map<char, int> m1,m2;
for( int i=0; i<len; i++)
{
m1[word1[i]]++;
m2[word2[i]]++;
}
return m1 == m2;
}
jean7155 2009-09-10
- 打赏
- 举报
mark
knop1027 2009-09-10
- 打赏
- 举报
第二题,
把两个字符串作个排序,然后比较一下,这样可行吗?
把两个字符串作个排序,然后比较一下,这样可行吗?
knop1027 2009-09-10
- 打赏
- 举报
第二题,
把两个字符串作个排序,然后比较一下,这样可行吗?
把两个字符串作个排序,然后比较一下,这样可行吗?
haierpro 2009-09-10
- 打赏
- 举报
[Quote=引用 16 楼 hairetz 的回复:]
引用 14 楼 haierpro 的回复:
10楼的算法看不明白，
m_block=(file_length[i]-m_last) % block_length;
不知道上句中的 file_length[i]-m_last 有没有可能为负数，负数求余是什么结果呢？
11楼的算法好像有问题，好像结果反了，把非边界块存在ans[]中了。
第一题我只写了思路，可能边界块是前一个块。
第2个题目比较简单，顺便写的，结果正常，没有优化及检查，体会思路即可。
[/Quote]
第一题看错了，不是结果反了，但是如果没有边界块时，结果肯定是不对的。还有在循环中做乘法，效率有点低。
引用 14 楼 haierpro 的回复:
10楼的算法看不明白，
m_block=(file_length[i]-m_last) % block_length;
不知道上句中的 file_length[i]-m_last 有没有可能为负数，负数求余是什么结果呢？
11楼的算法好像有问题，好像结果反了，把非边界块存在ans[]中了。
第一题我只写了思路，可能边界块是前一个块。
第2个题目比较简单，顺便写的，结果正常，没有优化及检查，体会思路即可。
[/Quote]
第一题看错了，不是结果反了，但是如果没有边界块时，结果肯定是不对的。还有在循环中做乘法，效率有点低。
hoomey 2009-09-10
- 打赏
- 举报
mark
猫已经找不回了 2009-09-10
- 打赏
- 举报
呵呵，15楼思路跟我一样，还是位图，而已有点添足了吧，比较的算法不需要2个位图。
猫已经找不回了 2009-09-10
- 打赏
- 举报
[Quote=引用 14 楼 haierpro 的回复:]
10楼的算法看不明白，
m_block=(file_length[i]-m_last) % block_length;
不知道上句中的 file_length[i]-m_last 有没有可能为负数，负数求余是什么结果呢？
11楼的算法好像有问题，好像结果反了，把非边界块存在ans[]中了。
[/Quote]
第一题我只写了思路，可能边界块是前一个块。
第2个题目比较简单，顺便写的，结果正常，没有优化及检查，体会思路即可。
10楼的算法看不明白，
m_block=(file_length[i]-m_last) % block_length;
不知道上句中的 file_length[i]-m_last 有没有可能为负数，负数求余是什么结果呢？
11楼的算法好像有问题，好像结果反了，把非边界块存在ans[]中了。
[/Quote]
第一题我只写了思路，可能边界块是前一个块。
第2个题目比较简单，顺便写的，结果正常，没有优化及检查，体会思路即可。
luotuo512 2009-09-10
- 打赏
- 举报
#include <iostream>
#include <map>
#include <string>
using namespace std;
bool is_matching( const char* word1, const char* word2)
{
int a[26]={0},b[26]={0};
if(strlen(word1)!=strlen(word2))
return false;
for(int i=0;i<strlen(word1);i++)
{
a[*(word1+i)-'a']++;
b[*(word2+i)-'a']++;
}
for(int i=0;i<26;i++)
{
if(a[i]!=b[i])
return false;
}
return true;
}
int main()
{
char *w1="hell",*w2="llohe";
if(is_matching(w1,w2))
cout<<w1<<" matches "<<w2;
else
cout<<w1<<" does not match "<<w2;
return 0;
}
haierpro 2009-09-10
- 打赏
- 举报
10楼的算法看不明白，
m_block=(file_length[i]-m_last) % block_length;
不知道上句中的 file_length[i]-m_last 有没有可能为负数，负数求余是什么结果呢？
11楼的算法好像有问题，好像结果反了，把非边界块存在ans[]中了。
m_block=(file_length[i]-m_last) % block_length;
不知道上句中的 file_length[i]-m_last 有没有可能为负数，负数求余是什么结果呢？
11楼的算法好像有问题，好像结果反了，把非边界块存在ans[]中了。
猫已经找不回了 2009-09-10
- 打赏
- 举报
bool is_matching( const char* word1, const char* word2)
{
int bit_map[26]={0}; //只针对小写字母，所以是26个，包括大写的话，52个元素即可
int i;
if(strlen(word1)!=strlen(word2) )
return false;
for(i=0; i<strlen(word1); ++i)
{
bit_map[(word1[i]-'a')]++;
bit_map[(word2[i]-'a')]--;
}
for(i=0; i<26; ++i)
if(bit_map[i]!=0)
return false;
return true;
}
int _tmain(int argc, _TCHAR* argv[])
{
char a[]="aabbc";
char b[]="abcab";
if(is_matching( a, b))
cout<<"match"<<endl;
else
cout<<"false"<<endl;
system("pause");
return 0;
}
猫已经找不回了 2009-09-10
- 打赏
- 举报
二、如果两个英文单词，组成它们的字符集合相同，而且相同字符出现的次数也相同，则称这两个词匹配：比如说：同”abbc”与词 ”babc”是匹配的。请写出两个字符串的匹配函数bool is_matching( const char* word1, const char* word2);
检测英文单词，用位图是最好办法，现在就写给你。
这个题目简直就是针对位图出的。
检测英文单词，用位图是最好办法，现在就写给你。
这个题目简直就是针对位图出的。
猫已经找不回了 2009-09-10
- 打赏
- 举报
一． 有n个文件的长度记载在一个无符号64 位整数数组中unsigned __int64 file_length[n]，把这n 个文件从逻辑上按序首尾拼接在一起形成一个逻辑上的大文件，然后以每块长度为unsigned block_length把这个逻辑上的大文件划分成大小相等的数据块（当然，最后一块有可能比block_length小），请定义和实现一个函数，把边界块的序号集合返回给函数的调用者（第一个数据块序号为0）。
注：边界块指的是跨多个文件的数据块。
这个题目比较简单，要求文件总长度，然后除以n。关键是如果文件总长度越界怎么办？
这个其实在2重循环里统计出每个跨界的块号，存起来就好了。不知道你说的文件总长度越界是什么意思。
int i,j=0,len = 0;
int block_num = 0;
int ans[MAX];
for(i=0; i<n; ++i)
{
len += file_length[i];
while(block_num*block_length<len)
block_num++;
ans[j++] = block_num;
}
大体思路，这样ans就存了所有的边界块的序号了啊。
注：边界块指的是跨多个文件的数据块。
这个题目比较简单，要求文件总长度，然后除以n。关键是如果文件总长度越界怎么办？
这个其实在2重循环里统计出每个跨界的块号，存起来就好了。不知道你说的文件总长度越界是什么意思。
int i,j=0,len = 0;
int block_num = 0;
int ans[MAX];
for(i=0; i<n; ++i)
{
len += file_length[i];
while(block_num*block_length<len)
block_num++;
ans[j++] = block_num;
}
大体思路，这样ans就存了所有的边界块的序号了啊。
加载更多回复（23）
