CareerCup 150題C言語版解答1.1

CareerCup 150(Cracking the Coding Interview)は、Googleの元従業員が作成したプログラマー面接の攻略で、多くのIT大手の面接プロセスを網羅しています.この本のテーマは難易度が適当で、難しくないが、一度コードを正しく書くには、もっと練習しなければならない.
この本は有名になって久しいので、あまり紹介しません.本の中で提供されている解答はJavaバージョンで、私自身はCが好きです.だから、ここでC言語バージョンの解答を記録して、みんなともっと交流したいです.
------------------------------- 1.1.c -----------------------
テーマはここで書かないで、ネット上にはあちこちにあります.
2つの方法:1つは直接遍歴し、もう1つは速い列を使って並べ替えながら探すことです.
/* This is one of the solution set to CareerCup 150 problems.

*

* Problem 1.1

*

* Compile command: gcc 1.1.c -std=c99

*/

#include

#include

#include

int straightWay(char *str);//O(n^2) time, O(n) space

void quicksort(char *str, int length);//O(nlogn) time, O(n) space
int main(int argc, char *argv[])

{

if(argc != 3)

   {

       printf("usage: ");

return 1;

   }

switch(atoi(argv[1]))

   {

case 1:

if(straightWay(argv[2]))

               printf("Dup.");

break;

case 2:

           quicksort(argv[2], strlen(argv[2]));

break;

default:

           printf("Wrong choice.");

break;

   }

return 0;

}
int straightWay(char *str)

{

int i=0,j=0;

int len = (int)strlen(str);

while(i < len)

   {

for(j=i+1; j < len; j++)

       {

if(str[i] == str[j])

           {

return 1;

           }

       }

       i++;

   }

return 0;

}
void quicksort(char *str, int length)

{

int low, high;

char pivot, tmp;

if (length < 2)

return;

   pivot = str[0];

   low = 0;

   high = length;

for(;;)

   {

while(str[++low] < pivot && low < length);

if(str[low] == pivot)

       {

           printf("Dup.");

return;

       }

while(str[--high] > pivot);

if(low >= high)

break;

       tmp = str[low];

       str[low] = str[high];

       str[high] = tmp;

   }

   tmp = str[low - 1];

   str[low - 1] = str[0];

   str[0] = tmp;

   quicksort(str, low - 1);

   quicksort(str + low, length - low);

}