15道简单算法题(附源代码第四部分)

H9enRy · 发表于 2014-8-1 00:28:15

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

　　12:判断一个字符串是否是另一个字符串的子串;

　　我这里就是暴力的对比

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

//判断一个字符串是否是另一个字符串的子串
int substr(const char* source,const char* sub)
{
if (source==NULL || sub==NULL)
{
      return -1;
}
int souLen=strlen(source);
int subLen=strlen(sub);
if (souLen<subLen)
{
      return -1;
}

int cmpCount=souLen-subLen;
for (int i=0;i<=cmpCount;i++)
{
      int j=0;
      for (;j<subLen;j++)
      {
         if (source[i+j]!=sub[j])
         {
            break;
         }
      }
      if (j==subLen)
      {
         return i ;
      }
}
return -1;
}

　　13:把一个int型数组中的数字拼成一个串，这个串代表的数字最小;

　　先将数字转换成字符串存在数组中，在通过qsort排序，在排序用到的比较函数中，将要比较的两个字符串进行组合，如要比较的两个字符串分别是A,B，那么组合成，A+B，和B+A，在比较A+B和B+A，返回strcmp(A+B, B+A)，经过qsort这么一排序,数组就变成从小到大的顺序了，组成的数自然是最小的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

//把一个int型数组中的数字拼成一个串，是这个串代表的数组最小
#define MaxLen 10
int Compare(const void* str1,const void* str2)
{
char cmp1[MaxLen*2+1];
char cmp2[MaxLen*2+1];
strcpy(cmp1,*(char**)str1);
strcat(cmp1,*(char**)str2);

strcpy(cmp2,*(char**)str2);
strcat(cmp2,*(char**)str1);
return strcmp(cmp1,cmp2);
}
void GetLinkMin(int a[],int len)
{
char** str=(char**)new int[len];
for (int i=0;i<len;i++)
{
      str[i]=new char[MaxLen+1];
      sprintf(str[i],"%d",a[i]);
}

qsort(str,len,sizeof(char*),Compare);
for (int i=0;i<len;i++)
{
      cout<<str[i]<<" ";
      delete[] str[i] ;
}
delete[] str;
}
void GetLinkMinTest()
{
int arr[]={123,132,213,231,321,312};
GetLinkMin(arr,sizeof(arr)/sizeof(int));
}

　　14:输入一颗二叉树，输出它的镜像（每个节点的左右子节点交换位置）;

　　递归实现，只要某个节点的两个子节点都不为空，就左右交换，让左子树交换，让右子树交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

struct NodeT
{
int value;
NodeT* left;
NodeT* right;
NodeT(int value_=0,NodeT* left_=NULL,NodeT* right_=NULL):value(value_),left(left_),right(right_){}
};

//输入一颗二叉树，输出它的镜像（每个节点的左右子节点交换位置）
void TreeClass(NodeT* root)
{
if( root==NULL || (root->left==NULL && root->right==NULL) )
      return;
NodeT* tmpNode=root->left;
root->left=root->right;
root->right=tmpNode;
TreeClass(root->left);
TreeClass(root->right);
}

void PrintTree(NodeT* root)
{
if(root)
{
      cout<<root->value<<" ";
      PrintTree(root->left);
      PrintTree(root->right);
}
}

void TreeClassTest()
{
NodeT* root=new NodeT(8);
NodeT* n1=new NodeT(6);
NodeT* n2=new NodeT(10);
NodeT* n3=new NodeT(5);
NodeT* n4=new NodeT(7);
NodeT* n5=new NodeT(9);
NodeT* n6=new NodeT(11);
root->left=n1;
root->right=n2;
n1->left=n3;
n1->right=n4;
n2->left=n5;
n2->right=n6;
PrintTree(root);
cout<<endl;
TreeClass( root );
PrintTree(root);
cout<<endl;
}

　　15:输入两个链表，找到它们第一个公共节点;

　　如果两个链表有公共的节点，那么第一个公共的节点及往后的节点都是公共的。从后往前数N个节点（N=短链表的长度节点个数）,长链表先往前走K个节点（K=长链表的节点个数-N），这时两个链表都距离末尾N个节点，现在可以一一比较了，最多比较N次，如果有两个节点相同就是第一个公共节点，否则就没有公共节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

//输入两个链表，找到它们第一个公共节点
int GetLinkLength(NodeL* head)
{
int count=0;
while (head)
{
      head=head->next;
      count++;
}
return count;
}

NodeL* FindFirstEqualNode(NodeL* head1,NodeL* head2)
{
if (head1==NULL || head2==NULL)
      return NULL;
int len1=GetLinkLength(head1);
int len2=GetLinkLength(head2);
NodeL* longNode;
NodeL* shortNode;
int leftNodeCount;
if (len1>len2)
{
      longNode=head1;
      shortNode=head2;
      leftNodeCount=len1-len2;
}else{
      longNode=head2;
      shortNode=head1;
      leftNodeCount=len2-len1;
}
for (int i=0;i<leftNodeCount;i++)
{
      longNode=longNode->next;
}
while (longNode && shortNode && longNode!=shortNode)
{
      longNode=longNode->next;
      shortNode=shortNode->next;
}
if (longNode)//如果有公共节点，必不为NULL
{
      return longNode;
}
return NULL;
}

void FindFirstEqualNodeTest()
{
NodeL* head1=new NodeL(0);
NodeL* head2=new NodeL(0);
NodeL* node1=new NodeL(1);
NodeL* node2=new NodeL(2);
NodeL* node3=new NodeL(3);
NodeL* node4=new NodeL(4);
NodeL* node5=new NodeL(5);
NodeL* node6=new NodeL(6);
NodeL* node7=new NodeL(7);

head1->next=node1;
node1->next=node2;
node2->next=node3;
node3->next=node6;//两个链表相交于节点node6

head2->next=node4;
node4->next=node5;
node5->next=node6;//两个链表相交于节点node6
node6->next=node7;

NodeL* node= FindFirstEqualNode(head1,head2);
if (node)
{
      cout<<node->value<<endl;
}else{
      cout<<"没有共同节点"<<endl;
}
}

cable5881 · 发表于 2014-8-5 12:38:50

SequenceInputStream

cable5881 · 发表于 2014-8-6 21:09:59

hjhjhjhjhjhjhjhjhj

账号		自动登录	找回密码
密码			立即注册

[技术交流] 15道简单算法题(附源代码第四部分)

马上注册，结交更多好友，享用更多功能^_^