Aha,几个有趣的小问题

Aha,几个有趣的问题
(1) 位图+二分查找，排序的预处理

(2) 旋转一个向量
Input: 具有n个元素的向量x,(向左)旋转i个位置
Output:旋转后的向量
Eg: abcdefgh向左旋转三个位置变成defghabc
思路1:另开辟一块大小为i的临时空间d，将x[0]...x[i-1]放入d[0]...d[i-1],而x[i]...x[n-1]左移i位，最后把临时空间中的d[0]...d[i-1]放到x的末尾。
//麻烦在于这个要的额外的空间不小...
思路2:搞个向左旋转一位的函数，调用i次
//麻烦在于这个方法太费时间了。
思路3:在资源有限的情况下,可以弄一个临时变量t，t=x[0]，然后x[0]=x[i],x[i]=x[2i]...，具体描述如下：
for i=[0,gcd(i,n))
{
   t=x[i];
   j=i;
   while(1)
   {
       k=j+d;
       if(k>=n) k-=n;
       if(k==i) break;
       x[j]=x[k];
       j=k;
   }
   x[j]=t;
}
思路4: 把这个问题看作ab->ba,a,b分别为一个数组。
旋转a:ab->a'b
旋转b:a'b->a'b'
整体旋转:a'b'->ba

于是，问题解答如下：
reverse(0,i-1)
reverse(i,n-1)
reverse(0,n-1)

联想：以前曾经有道题，让把一句话反转，单词顺序反转，但单词内部字母顺序不变，比如：I am a student->student a am I.其实这个问题的思路是与这个类似的，我们可以先把整个句子反转，再将每个单词反转。


(3)求变位词问题
Input: 一个词典
Output:列出其中所有的变位词(即组成单词的字母相同的词，比如 tops与pots,stop。)
不可行想法：拿到一个词，搞出字母的所有置换，看词典中有没有...//不打算累死自己也打算累死机器地说...
另外一个想法：比较所有的单词，长度相等，字母是否相同...//这好像也很麻烦啊...
Aha~，签名->排序->Merge~~~~
签名：每个单词按字母顺序排列生成签名,例如：pans的签名为anps,snap的签名亦为anps,签名相同的单词，为变位词。
排序：把签名相同的单词放在一起。
然后就是输出答案了 :)