[转载] 七道面试题目 - C++

lala

电梯直达

1^#

发表于 2009-11-3 01:08:07 | 只看该作者回帖奖励

|倒序浏览 |阅读模式

大家一起来求解

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

收藏0

使用道具举报

孤独者

2^#

发表于 2009-11-3 01:08:09 | 只看该作者

小弟先抛砖引玉，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;
}

回复支持反对

使用道具举报

寂寞男孩

3^#

发表于 2009-11-3 01:08:12 | 只看该作者

第一题:
#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;
}

回复支持反对

使用道具举报

夜来香

4^#

发表于 2009-11-3 01:08:13 | 只看该作者

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

回复支持反对

使用道具举报

寂寞

5^#

发表于 2009-11-3 01:08:19 | 只看该作者

/*---------------------------------------------------------------------------
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鈊痛

6^#

发表于 2009-11-3 01:08:22 | 只看该作者

第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;
}
}

回复支持反对

使用道具举报

陈君

7^#

发表于 2009-11-3 01:08:24 | 只看该作者

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

#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;
}

复制代码

回复支持反对

使用道具举报

aiq無奈tx

8^#

发表于 2009-11-3 01:08:25 | 只看该作者

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

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

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

回复支持反对

使用道具举报

√金刚石猛男

9^#

发表于 2009-11-3 01:08:28 | 只看该作者

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

回复支持反对

使用道具举报

人偶娃娃

10^#

发表于 2009-11-3 01:08:31 | 只看该作者

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

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

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

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

回复支持反对

使用道具举报

		自动登录	找回密码
密码			注册