[转载] 七道面试题目

/*---------------------------------------------------------------------------
File name: 七道面试题目.c
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 9/14/2007 17:42:10
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

https://bbs.bc-cn.net/viewthread.php?tid=170050

大家一起来求解

1、将一个字符串逆序 　　
2、将一个链表（linked list）逆序
3、计算一个字节（byte）里有多少bit被置1 　
4、搜索给定的字节（byte） 　　
5、在一个字符串中找到可能的最长的子字符串，该字符串是由同一字符组成的　　
6、字符串转换成整数 　　
7、整数转换成字符串
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
1、将一个字符串逆序 　　

O(1) space + O(n) time in-place reversion.
*/
char* reverse_string(char *s)
{
char *p, *q, ch;

if(!s) return NULL;

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));

printf("\n\nTest #4\n");
longest=longestSubString(dst, src);
printf("%d %s\n", longest, dst);

printf("\n\nTest #5\n");
printf("%d\n", strToInt(intString));

printf("\n\nTest #5\n");
printf("Please input an integer n: ");
scanf("%d", &n);
intToStr(n, buffer);
printf("The number you just entered is %s\n", buffer);

return 0;
}

3、计算一个字节（byte）里有多少bit被置1

[CODE]#include <iostream>
using namespace std;

int main()
{
unsigned char c; // 1 byte
int s = 0;
cin >> c;
cout << endl;

for (int i=0; i<8; i++) // 8 bit
{
if ( ((c & (1<<i))>>i) == 1) // shift
++s;
}

cout << "被置1的位有：" << s << "个。" << endl;
}[/CODE]

就是不同方法才贴出来啊，我这是平民大众解法，n&(n-1)比较难想到

希望各位版主多多点评！！

这样转换有什么意义不？



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/

Thank you.
I know how to do it now .