1、提供单词和词典，找到该单词的所有变位词，可以事先花时间和空间处理下该词典。
因为要查找变位词，事先遍历词典，得到每个单词签名，并建立签名列表，签名列表的每个项包含了该签名的所有单词。有了这个列表，直接得到提供单词的签名去遍历签名列表就能找到所有变位词。
2、给定一个4300000000个32位整数的顺序文件，请问你如何可以找到一个至少出现两次的整数
因为2^32>4300000000所以肯定存在至少出现两次的整数
而且是顺序文件，更提醒我们要用二分查找法
1、把所有整数（N个）看成二进制表示法，将第一位bit为1的数目和第一位bit为0的比较，必有一个数目大于等于另一个。
2、在数目大的那堆数字中继续比较第二bit位，按照1的方法比较，以此类推最后能得到重复出现的数字。
同样的道理，假设我们有N个顺序数字他们都在[1,2^n]范围，且N<2^n,如何找到至少一个没有出现的数字，思路和刚刚的一样
1、把所有整数（N个）看成二进制表示法，将第一位bit为1的数目和第一位bit为0的比较，必有一个数目小于等于另一个。
2、在数目小的那堆数字中继续比较第二bit位，按照1的方法比较，以此类推最后能得到没有出现的数字。
#include <stdio.h>
#include <stdlib.h>
int getRepeat(unsigned char *a, int length, int bitlen)
{
unsigned char result = 0;
int start = 0;
for(int i = 1; i <= bitlen; i++)
{
int bit0 = 0;
int bit1 = 0;
int mod = 1 << (bitlen - i);
int len = length/(1<<(i-1));
for(int j = start; j < start + len; j++)
{
if((a[j] & mod) == 0)
{
bit0++;
}
else
{
bit1++;
}
}
if(bit0 > bit1)
{
result |= 0<<(bitlen - i);
}
else
{
result |= 1<<(bitlen - i);
start+=len/2;
}
}
return result;
}
int getLost(unsigned char *a, int length, int bitlen)
{
unsigned char result = 0;
int start = 0;
for(int i = 1; i <= bitlen; i++)
{
int bit0 = 0;
int bit1 = 0;
int mod = 1 << (bitlen - i);
int len = length/(1<<(i-1));
for(int j = start; j < start + len; j++)
{
if((a[j] & mod) == 0)
{
bit0++;
}
else
{
bit1++;
}
}
if(bit0 < bit1)
{
result |= 0<<(bitlen - i);
}
else
{
result |= 1<<(bitlen - i);
start+=len/2;
}
}
return result;
}
int main()
{
unsigned char a[] = {1,1,1,4,4,5,5,6,7,8,9,10,11,12,13,14,15};
printf("%d\n",getRepeat(a,17,4));
unsigned char b[] = {1,3,4,5,5,6,7,8,9,10,11,12,13,14,15};
printf("%d\n",getLost(b,15,4));
return 1;
}
3、两个向量的转置算法，i,n的最大公约数怎么出现在程序中。
i,n的最大公约数其实就是从头开始进行a[i]=a[2i] a[2i]=a[3i]的次数
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
void reverse1(char c[], int i, int n)
{
int p = 0;
int count = 0;
if(i > 0 && n>=i)
{
while(count!=n)
{
int t = c[p];
int q = p + i;
while((q%n)!=p)
{
c[(q-i)%n] = c[q%n];
count++;
q+=i;
}
c[(q-i)%n] = t;
count++;
p++;
}
}
//p为i,n最大公约数，即从第一个数开始进行c[i]=c[2i] c[2i]=c[3i]循环的次数
printf("%d",p);
}
int main()
{
int i = 0;
char c[] ={'a','b','c','d','e','f','g','h'};
DWORD start, stop;
start = GetTickCount();
reverse1(c,3,8);
stop = GetTickCount();
printf("time: %lld ms\n", stop - start);
for(i = 0; i < 8;i++)
{
printf("%c",c[i]);
}
printf("%c",'\n');
return 1;
}
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
void reverse1(char c[], int i, int n)
{
int p = 0;
int count = 0;
if(i > 0 && n>=i)
{
while(count!=n)
{
int t = c[p];
int q = p + i;
while((q%n)!=p)
{
c[(q-i)%n] = c[q%n];
count++;
q+=i;
}
c[(q-i)%n] = t;
count++;
p++;
}
}
//p为i,n最大公约数，即从第一个数开始进行c[i]=c[2i] c[2i]=c[3i]循环的次数
printf("%d",p);
}
void reverse2(char c[], int i, int j)
{
char p;
while(i<j)
{
p = c[i];
c[i] = c[j];
c[j] = p;
i++;
j--;
}
}
int main()
{
int i = 0;
char c[] ={'a','b','c','d','e','f','g','h'};
DWORD start, stop;
start = GetTickCount();
reverse1(c,3,8);
stop = GetTickCount();
printf("time: %lld ms\n", stop - start);
for(i = 0; i < 8;i++)
{
printf("%c",c[i]);
}
printf("%c",'\n');
char d[] ={'a','b','c','d','e','f','g','h'};
start = GetTickCount();
reverse2(d,0,2);
reverse2(d,3,7);
reverse2(d,0,7);
stop = GetTickCount();
printf("time: %lld ms\n", stop - start);
for(i = 0; i < 8;i++)
{
printf("%c",d[i]);
}
printf("%c",'\n');
return 1;
}
5、将向量abc转为cba
我想到的是在两向量转置的基础上abc->bac->cba
网上百度的方法是对abc取ar br cr 再取（arbrcr）r r表示对向量的转置。
6、给定某一个名字的按钮编码，返回匹配集合
这个题目跟查找变位词差不多，给每个名字编码，将编码一样的放在一起，并顺序排列，查找的时候二分查找就可以了。
7、题意都理解得不是很来。。。。。。。
8、n个元素的实数集，确认是否有k个元素的子集可以让总和至多为t
将n个元素排序，计算头k个数和与尾k个数和，如果t介于二者之间就有。