p=s;
q=s+strlen(s)-1;
// swap head and tail
while(p<q)
{
ch=*p;
*p++=*q;
*q--=ch;
}
return s;
}
/**
2、将一个链表（linked list）逆序
I am assuming the linked list is a singularly linked list, which
has a next pointer.
*/
typedef struct node
{
int data;
struct node* next;
} node;
node* reverse_linkedlist(node* head)
{
/**
p --- previous
n --- next
c --- current
*/
node* p=NULL, *n, *c=head;
/**
Note the symmetry inside the loop
n-->c->next-->p-->c-->n.
This is very similar to what you do for the swap function:
tmp-->a-->b-->tmp
*/
while(c!=NULL)
{
n = c->next;
c->next = p;
p = c;
c= n;
}
//head = p; // Line#head: uncomment this line does not affect output of test #2
return p;
}
void print_linkedlist(node* head)
{
while(head!=NULL)
{
printf("%d ", head->data);
head=head->next;
}
}
/**
3、计算一个字节（byte）里有多少bit被置1
Consider n&(n-1).
*/
int numOfBits(int n)
{
int count=0;
while(n!=0)
{
++count;
n&=n-1;
}
return count;
}
/**
4、搜索给定的字节（byte）
This problem does not sound familiar to me. Need a
more detailed problem statement.
*/
/**
5、在一个字符串中找到可能的最长的子字符串，该字符串是由同一字符组成的
*/
/**
The caller of this function are responsible for allocating memory
for the two string buffers.
dst --- destination buffer
src --- source buffer
@return returns the length of the longest sub-string
consisting of the same char.
*/
int longestSubString(char* dst, const char* src)
{
const char *p, *q;
char longestChar;
int c=1, longestSofar=1, i;
if(src==NULL)
{
dst=NULL;
return 0;
}
if(strlen(src)==0)
{
*dst='\0';
return 0;
}
if(strlen(src)==1)
{
*dst=*src;
*(++dst)='\0';
return 1;
}
p = src;
q = src+1;
while(*q)
{
if(*p==*q)
{
++c;
if(c>longestSofar)
{
longestSofar=c;
longestChar=*p;
}
}
else
{
c=1;
}
p=q;
++q;
}
for(i=0; i<longestSofar; ++i)
*dst++=longestChar;
*dst='\0';
return longestSofar;
}
/**
6、字符串转换成整数
In C, we can use atoi() or atol(). There are other functions:
atof(), strtol().
In C++, we can use a string stream to parese the input string.
*/
int strToInt(const char* s)
{
int i;
i=atoi(s);
return i;
}
/**
7、整数转换成字符串
In C, we can use itoa(). Note that this function is not standard,
although most compliers have implemented it.
(Taken from cplusplus.com:)
This function is not defined in ANSI-C and is not part of C++, but is
supported by some compilers. A standard-compliant alternative for some
cases may be sprintf:
sprintf(str,"%d",value) converts to decimal base.
sprintf(str,"%x",value) converts to hexadecimal base.
sprintf(str,"%o",value) converts to octal base.
*/
char* intToStr(int n, char* buffer)
{
return itoa(n, buffer, 10);
}
int main()
{
char s[]="12345";
char* pStr;
int i;
node* head, *tmp, *prev;
int n;
// change this string to run test #4
char src[100] = "123aa66789bb23333";
char dst[100];
int longest;
char intString[] = "12345";
char buffer[1000];
// test #1
printf("Test #1\n");
pStr = reverse_string(s);
printf("%s\n%s\n", s, pStr);
/** output is
54321
54321
*/
// test #2
printf("\n\nTest #2\n");
tmp = (node*)malloc(sizeof(node));
tmp->data = 1;
head = tmp;
for(i=2; i<=5; ++i)
{
prev=tmp;
tmp=(node*)malloc(sizeof(node));
tmp->data=i;
tmp->next=NULL;
prev->next=tmp;
}
print_linkedlist(head);
tmp = reverse_linkedlist(head);
printf("\n");
print_linkedlist(head);
printf("\n");
print_linkedlist(tmp);
/** output is
1 2 3 4 5
1
5 4 3 2 1
Think about why second line is "1 ". You can also
uncomment Line#head above to run test #2.
Hint: pass-by-value vs pass-by-reference(or address).
*/
printf("\n\nTest #3\nPlease input an integer n: ");
scanf("%d", &n);
printf("Number of bits equal to 1 is %d\n", numOfBits(n));
