马思纯的脸没长开# TVChinese - 中文电视
J*8
1 楼
The question is not hard. But I missed two key points.
The details below.
==========================================================
/*
example
char *words[] = {"foo", "bar", "baz", NULL};
setup(words);
1) First step:
isMember("foo") -> true
isMember("garply") -> false
2) Second step:
isMember("f.o") -> true
isMember("..") -> false
*/
#include
#include
#include
char *words[] = {"foo", "bar", "baz", "caz","cat",NULL};
int num=0;
void print_words(void)
{
int i=0;
while(words[i]){
printf("%s\n",words[i]);
i++;
}
}
/* arbitrary preprocessing. May be slow */
void setup(char *words[])
{
int i=0,j;
char temp[16];
while(words[i]){
i++;
}
num=i;
printf("num=%d\n",num);
//Brute force sorting
for(i=0;i
strcpy(temp,words[i]);
strcpy(words[i],words[j]);
strcpy(words[j],temp);
}
}
}
//Missed: Can't do qsort() lib call here. !!!!
printf("sorted.\n");
}
//Missed: in this case, it does NOT make sense to compare as strcmp
//only matched or not.
int matchdot(const char *s1, const char *s2)
{
if(!s1||!s2)
return 0;
while(*s1&&*s2&&((*s1==*s2)||(*s2=='.'))){
s1++;
s2++;
}
if(*s1||*s2)
return 0;
return 1;
}
/* returns whether word is a member of words given in setup() as fast as
possible */
int isMember(char *word) {
int low=0,high=num-1;
int mid;
while(high>=low){
mid=low+(high-low)/2;
if(!strcmp(words[mid],word))
return 1;
else if(strcmp(words[mid],word)>0)
high=mid-1;
else
low=mid+1;
}
return 0;
}
int isMemberdot(char *word) {
int i=0;
while(words[i]){
if(matchdot(words[i],word))
return 1;
i++;
}
return 0;
}
int main (int argc, char *argv[])
{
char buf[16];
print_words();
setup(words);
print_words();
//1) test cases
strcpy(buf,"cat");
if(isMember(buf))
printf("isMember(%s)=Yes\n",buf);
else
printf("isMember(%s)=No\n",buf);
strcpy(buf,"cot");
if(isMember(buf))
printf("isMember(%s)=Yes\n",buf);
else
printf("isMember(%s)=No\n",buf);
//2) test cases
strcpy(buf,"cat");
if(isMemberdot(buf))
printf("isMemberdot(%s)=Yes\n",buf);
else
printf("isMemberdot(%s)=No\n",buf);
strcpy(buf,"cot");
if(isMemberdot(buf))
printf("isMemberdot(%s)=Yes\n",buf);
else
printf("isMemberdot(%s)=No\n",buf);
strcpy(buf,"c.t");
if(isMemberdot(buf))
printf("isMemberdot(%s)=Yes\n",buf);
else
printf("isMemberdot(%s)=No\n",buf);
strcpy(buf,"..");
if(isMemberdot(buf))
printf("isMemberdot(%s)=Yes\n",buf);
else
printf("isMemberdot(%s)=No\n",buf);
return 0;
}
===================
running results
The details below.
==========================================================
/*
example
char *words[] = {"foo", "bar", "baz", NULL};
setup(words);
1) First step:
isMember("foo") -> true
isMember("garply") -> false
2) Second step:
isMember("f.o") -> true
isMember("..") -> false
*/
#include
#include
#include
char *words[] = {"foo", "bar", "baz", "caz","cat",NULL};
int num=0;
void print_words(void)
{
int i=0;
while(words[i]){
printf("%s\n",words[i]);
i++;
}
}
/* arbitrary preprocessing. May be slow */
void setup(char *words[])
{
int i=0,j;
char temp[16];
while(words[i]){
i++;
}
num=i;
printf("num=%d\n",num);
//Brute force sorting
for(i=0;i
strcpy(temp,words[i]);
strcpy(words[i],words[j]);
strcpy(words[j],temp);
}
}
}
//Missed: Can't do qsort() lib call here. !!!!
printf("sorted.\n");
}
//Missed: in this case, it does NOT make sense to compare as strcmp
//only matched or not.
int matchdot(const char *s1, const char *s2)
{
if(!s1||!s2)
return 0;
while(*s1&&*s2&&((*s1==*s2)||(*s2=='.'))){
s1++;
s2++;
}
if(*s1||*s2)
return 0;
return 1;
}
/* returns whether word is a member of words given in setup() as fast as
possible */
int isMember(char *word) {
int low=0,high=num-1;
int mid;
while(high>=low){
mid=low+(high-low)/2;
if(!strcmp(words[mid],word))
return 1;
else if(strcmp(words[mid],word)>0)
high=mid-1;
else
low=mid+1;
}
return 0;
}
int isMemberdot(char *word) {
int i=0;
while(words[i]){
if(matchdot(words[i],word))
return 1;
i++;
}
return 0;
}
int main (int argc, char *argv[])
{
char buf[16];
print_words();
setup(words);
print_words();
//1) test cases
strcpy(buf,"cat");
if(isMember(buf))
printf("isMember(%s)=Yes\n",buf);
else
printf("isMember(%s)=No\n",buf);
strcpy(buf,"cot");
if(isMember(buf))
printf("isMember(%s)=Yes\n",buf);
else
printf("isMember(%s)=No\n",buf);
//2) test cases
strcpy(buf,"cat");
if(isMemberdot(buf))
printf("isMemberdot(%s)=Yes\n",buf);
else
printf("isMemberdot(%s)=No\n",buf);
strcpy(buf,"cot");
if(isMemberdot(buf))
printf("isMemberdot(%s)=Yes\n",buf);
else
printf("isMemberdot(%s)=No\n",buf);
strcpy(buf,"c.t");
if(isMemberdot(buf))
printf("isMemberdot(%s)=Yes\n",buf);
else
printf("isMemberdot(%s)=No\n",buf);
strcpy(buf,"..");
if(isMemberdot(buf))
printf("isMemberdot(%s)=Yes\n",buf);
else
printf("isMemberdot(%s)=No\n",buf);
return 0;
}
===================
running results
