部分IT公司算法笔试题面试题(五)

23、求两个串中的第一个最长子串（神州数码以前试题）。如”abractyeyt”,”dgdsaeactyey”的最大子串为”actyet”。
#include “stdafx.h”
char *MaxSubString(char *str1, char *str2) {
int i, j, k, index, max=0;
for(i=0; str1[i]; i++)
for(j=0; str2[j]; j++) {
for(k=0; str1[i+k]==str2[j+k] && (str2[i+k] || str1[i+k]); k++);
if(k>max) { // 出现大于当前子串长度的子串，则替换子串位置和程度
index = j; max = k;
}
}
char *strResult = (char *)calloc(sizeof(char), max+1);
for(i=0; i strResult[i] = str2[index++];
return strResult;
}

int main(int argc, char* argv[]) {
char str1[] = “abractyeyt”, str2[] = “dgdsaeactyey”;
char *strResult = MaxSubString(str1, str2);
printf(“str1=%s\nstr2=%s\nMaxSubString=%s\n”, str1, str2, strResult);
}

24、不开辟用于交换数据的临时空间，如何完成字符串的逆序(在技术一轮面试中，有些面试官会这样问)
#include “stdafx.h”
void change(char *str) {
for(int i=0,j=strlen(str)-1; i str[i] ^= str[j] ^= str[i] ^= str[j];
}
}
int main(int argc, char* argv[]) {
char str[] = “abcdefg”;
printf(“strSource=%s\n”, str);
change(str);
printf(“strResult=%s\n”, str);
return getchar();
}

25、删除串中指定的字符（做此题时，千万不要开辟新空间，否则面试官可能认为你不适合做嵌入式开发）
#include “stdafx.h”
void delChar(char *str, char c) {
int i, j=0;
for(i=0; str[i]; i++)
if(str[i]!=c) str[j++]=str[i];
str[j] = ‘\0′;
}

int main(int argc, char* argv[]) {
char str[] = “abcdefgh”; // 注意，此处不能写成char *str = “abcdefgh”;
printf(“%s\n”, str);
delChar(str, ‘c’);
printf(“%s\n”, str);
}

26、判断单链表中是否存在环（网上说的笔试题）
#include “stdafx.h”
typedef char eleType; // 定义链表中的数据类型
typedef struct listnode { // 定义单链表结构
eleType data;
struct listnode *next;
}node;

node *create(int n) { // 创建单链表，n为节点个数
node *p = (node *)malloc(sizeof(node));
node *head = p; head->data = ‘A’;
for(int i=’B'; i<’A'+n; i++) {
p = (p->next = (node *)malloc(sizeof(node)));
p->data = i;
p->next = NULL;
}
return head;
}

void addCircle(node *head, int n) { // 增加环，将链尾指向链中第n个节点
node *q, *p = head;
for(int i=1; p->next; i++) {
if(i==n) q = p;
p = p->next;
}
p->next = q;
}

int isCircle(node *head) { // 这是笔试时需要写的最主要函数，其他函数可以不写
node *p=head,*q=head;
while( p->next && q->next) {
p = p->next;
if (NULL == (q=q->next->next)) return 0;
if (p == q) return 1;
}
return 0;
}

int main(int argc, char* argv[]) {
node *head = create(12);
addCircle(head, 8); // 注释掉此行，连表就没有环了
printf(“%d\n”, isCircle(head));
}