H9enRy 发表于 2014-8-1 01:06:29

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



　1:合并排序，将两个已经排序的数组合并成一个数组，其中一个数组能容下两个数组的所有元素;　　2:合并两个单链表;　　3:倒序打印一个单链表;　　4:给定一个单链表的头指针和一个指定节点的指针，在O(1)时间删除该节点;　　5:找到链表倒数第K个节点;　　6:反转单链表;　　7:通过两个栈实现一个队列;　　8:二分查找;　　9:快速排序;　　10:获得一个int型的数中二进制中的个数;　　11:输入一个数组，实现一个函数，让所有奇数都在偶数前面;　　12:判断一个字符串是否是另一个字符串的子串;　　13:把一个int型数组中的数字拼成一个串，这个串代表的数字最小;　　14:输入一颗二叉树，输出它的镜像（每个节点的左右子节点交换位置）;　　15:输入两个链表，找到它们第一个公共节点;　　下面简单说说思路和代码实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//链表节点
struct NodeL
{
    int value;
    NodeL* next;
    NodeL(int value_=0,NodeL* next_=NULL):value(value_),next(next_){}
};
//二叉树节点
struct NodeT
{
    int value;
    NodeT* left;
    NodeT* right;
    NodeT(int value_=0,NodeT* left_=NULL,NodeT* right_=NULL):value(value_),left(left_),right(right_){}
};




　　1:合并排序，将两个已经排序的数组合并成一个数组，其中一个数组能容下两个数组的所有元素;　　合并排序一般的思路都是创建一个更大数组C，刚好容纳两个数组的元素，先是一个while循环比较，将其中一个数组A比较完成，将另一个数组B中所有的小于前一个数组A的数及A中所有的数按顺序存入C中，再将A中剩下的数存入C中，但这里是已经有一个数组能存下两个数组的全部元素，就不用在创建数组了，但只能从后往前面存，从前往后存，要移动元素很麻烦。
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
//合并排序，将两个已经排序的数组合并成一个数组，其中一个数组能容下两个数组的所有元素
void MergeArray(int a[],int alen,int b[],int blen)
{
    int len=alen+blen-1;
    alen--;
    blen--;
    while (alen>=0 && blen>=0)
    {
      if (a>b)
      {
            a=a;
      }else{
            a=b;
      }
    }

    while (alen>=0)
    {
      a=a;
    }
    while (blen>=0)
    {
      a=b;
    }
}

void MergeArrayTest()
{
    int a[]={2,4,6,8,10,0,0,0,0,0};
    int b[]={1,3,5,7,9};
    MergeArray(a,5,b,5);
    for (int i=0;i<sizeof(a)/sizeof(a);i++)
    {
      cout<<a<<" ";
    }
}




　　2:合并两个单链表;　　合并链表和合并数组，我用了大致相同的代码，就不多少了，那本书用的是递归实现。
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
//链表节点
struct NodeL
{
    int value;
    NodeL* next;
    NodeL(int value_=0,NodeL* next_=NULL):value(value_),next(next_){}
};

//合并两个单链表
NodeL* MergeList(NodeL* head1,NodeL* head2)
{
    if (head1==NULL)
      return head2;
    if (head2==NULL)
      return head1;

    NodeL* head=NULL;
    if (head1->value<head2->value)
    {
      head=head1;
      head1=head1->next;
    }else{
      head=head2;
      head2=head2->next;
    }
    NodeL* tmpNode=head;
    while (head1 && head2)
    {
      if (head1->value<head2->value)
      {
            head->next=head1;
            head1=head1->next;
      }else{
            head->next=head2;
            head2=head2->next;
      }
      head=head->next;
    }
    if (head1)
    {
      head->next=head1;
    }
    if (head2)
    {
      head->next=head2;
    }
    return tmpNode;
}

void MergeListTest()
{
    NodeL* head1=new NodeL(1);
    NodeL* cur=head1;
    for (int i=3;i<10;i+=2)
    {
      NodeL* tmpNode=new NodeL(i);
      cur->next=tmpNode;
      cur=tmpNode;
    }
    NodeL* head2=new NodeL(2);
    cur=head2;
    for (int i=4;i<10;i+=2)
    {
      NodeL* tmpNode=new NodeL(i);
      cur->next=tmpNode;
      cur=tmpNode;
    }
    NodeL* head=MergeList(head1,head2);
    while (head)
    {
      cout<<head->value<<" ";
      head=head->next;
    }
}




　　3:倒序打印一个单链表;　　递归实现，先递归在打印就变成倒序打印了，如果先打印在调用自己就是顺序打印了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//倒序打印一个单链表
void ReversePrintNode(NodeL* head)
{
    if (head)
    {
      ReversePrintNode(head->next);
      cout<<head->value<<endl;
    }
}
void ReversePrintNodeTest()
{
    NodeL* head=new NodeL();
    NodeL* cur=head;
    for (int i=1;i<10;i++)
    {
      NodeL* tmpNode=new NodeL(i);
      cur->next=tmpNode;
      cur=tmpNode;
    }
    ReversePrintNode(head);
}







cable5881 发表于 2014-8-4 18:01:47

儿飞飞飞飞威风威风

cable5881 发表于 2014-8-11 17:38:38

谢谢楼主分享！！！！！！！！！！

tlwangxd 发表于 2014-11-18 09:30:16

学习

leslie初见 发表于 2014-11-26 20:08:06


必须得顶下

tlwangxd 发表于 2014-12-3 08:51:29

路过

微逻辑 发表于 2014-12-9 00:17:35

好

tlwangxd 发表于 2014-12-10 09:04:16

看看

zjc7836 发表于 2015-1-14 20:40:38

楼主nb

zjc78361 发表于 2015-1-21 20:10:52

代码在哪？
页: [1]
查看完整版本: 15道简单算法题(附源代码第一部分)