[转载] 七道面试题目

lala

大家一起来求解

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

孤独者

小弟先抛砖引玉，bug之处请多多指教！！
第二题：
将一个链表（linked list）逆序


node* reverse(node* head)
{
node *p1,*p2,*tmp;
p1=head;
p2=p1->next;
while(p2!=NULL)
{
tmp=p2->next;
p2->next=p1;
p1=p2;
p2=tmp;
}
head->next=NULL;
head=p1;
return head;
}

寂寞男孩

第一题:
#include"iostream"
#include"string"
using namespace std;
void main()
{
string str;
int i;
cout<<"请输入字符串："<<endl;
getline(cin,str);
cout<<"所输入的字符串的逆序是：";
for(i=str.length()-1;i>=0;i--)
cout<<str[i];
cout<<endl;
}

夜来香

很基础。。。。第5题是经典最长平台，第三题有一个玩弄位运算的玩法
用来当练习做做还是不错的

寂寞

/*---------------------------------------------------------------------------
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:
===========================================================================
http://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;
}

①個亼de鈊痛

第1题我做过啊呵呵
#include<iostream.h>
void invert(char*,int);
void main()
{
char *s,a[30];
int n;
cout<<"请输入字符个数n:";
cin>>n;
cout<<"请输入n个数:"<<endl;
for(int i=0;i<n;i++)
cin>>a[i];
cout<<endl;
s=&a[0];//s=a
invert(s,n);
cout<<"逆序串为 :"<<endl;
for( i=0;i<n;i++)
cout<<*(s+i)<<" ";//a[i]==s[i]==*(a+i)==*(s+i)
cout<<endl;
}
void invert(char*s,int j)
{
char k,*s1,*s2;
int i;
for(i=0;i<j/2;i++)
{
s1=s+i;
s2=s+(j-i-1);
k=*s1;
*s1=*s2;
*s2=k;
}
}

陈君

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

1. #include <iostream>
   
2. using namespace std;
   
3. int main()
   
4. {
   
5. unsigned char c; // 1 byte
   
6. int s = 0;
   
7. cin >> c;
   
8. cout << endl;
   
9. 
   
10. for (int i=0; i<8; i++) // 8 bit
    
11. {
    
12. if ( ((c & (1<<i))>>i) == 1) // shift
    
13. ++s;
    
14. }
    
15. cout << "被置1的位有：" << s << "个。" << endl;
    
16. }

复制代码

aiq無奈tx

楼上的参考一下5楼的解法吧



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

请大家不要用TC来学习C语言，点击此处查看原因
C++编写的Windows界面游戏
C/C++算法习题(OnlineJudge)： http://yzfy.org/

√金刚石猛男

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

人偶娃娃

以下是引用远去的列车在2007-9-15 11:20:34的发言：

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



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

请大家不要用TC来学习C语言，点击此处查看原因
C++编写的Windows界面游戏
C/C++算法习题(OnlineJudge)： http://yzfy.org/