本文共 1825 字，大约阅读时间需要 6 分钟。

    第二章主要围绕三个问题

1、给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数

2、给定一个n元一维向量，循环左移i个位置，如n=8，i=3时，abcdefgh变为defghabc

3、如pots、stop和stops互为变位词，每个单词都可以通过其他单词改变字母顺序得到，找出字典中所有变位词

     对于1、主要考虑2分搜索

      对于3，百度笔试题刚考过，伤感，当时给略过去了，现在还是得看啊

      如果考虑暴力解法，含有n个字母的单词有n!种排列，还是很大的数量级的，书上是利用标志单词，标志则为对单词的字母进行排序后的结果，对字典遍历并对每个单词进行标记，还是很简单的事情，然后集中相同标志的单词，具有相同标志的单词，就是互为变位词了。

      配套代码的实现如下：

sign.c ,对每个单词进行标记，通过调用stdlib.h的qsort对单词进行快速排序

/* Copyright (C) 1999 Lucent Technologies *//* From 'Programming Pearls' by Jon Bentley *//* sign.c -- sign each line of a file for finding anagrams    The input line "stop" gives the output line "opst stop" */#include 
   
    #include 
    
     #include 
     
      #define WORDMAX 100int charcomp(char *x, char *y){   return *x - *y;}int main(){   char word[WORDMAX], sig[WORDMAX];    while (scanf("%s%s", sig, word) != EOF) {        strcpy(sig, word);        qsort(sig, strlen(sig), sizeof(char), charcomp);        printf("%s %s\n", sig, word);    }    return 0;}
     
    
   

输出squah.c，不同标记就输出一个换行，相同标记则输出单词，使具有相同标记的单词都在同一行

/* Copyright (C) 1999 Lucent Technologies *//* From 'Programming Pearls' by Jon Bentley *//* squash.c -- print anagram classes on a single line    The input lines "opst pots" and "opst stop" go to "pots stop" */#include 
   
    #include 
    
     #include 
     
      #define WORDMAX 100int main(){   char word[WORDMAX], sig[WORDMAX], oldsig[WORDMAX];    int linenum = 0;    strcpy(oldsig, "");    while (scanf("%s %s", sig, word) != EOF) {        if (strcmp(oldsig, sig) != 0 && linenum > 0)            printf("\n");        strcpy(oldsig, sig);        linenum++;        printf("%s ", word);    }    printf("\n");    return 0;}
     
    
   

不得不说，linux的管道是个好东东，最终运行命令如下：

xia@Ubuntu:~/perl$ ./sign < DICT.TXT | sort | ./squah > list

     就这样吧

转载地址：http://vmcqb.baihongyu.com/