最近在公司里基本处于打酱油的状态，工作正在交接中。没事又做起了算法题目。好久没怎么写算法题了，感觉手气还不错，经常能一次就写对（编译通过，得到想要的结果，没怎么测试），可能是因为这些题目之前看过或是写过，或许就是自己进步了一点。这15道大部分来自《剑指Offer》，作者的博客之前看过几次，感觉写得很好，但看这本书时却没有那个感觉了，可能是因为看过博客的原因吧，没有了之前的那种惊喜。自己就试着实现里面的一些算法题目，基本上是简单的思考一下，如果没什么思路，就看看作者是怎么想的，大概看一下他的思路或是代码，就开始自己实现。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[alen]>b[blen])
{
a[len--]=a[alen--];
}else{
a[len--]=b[blen--];
}
}
while (alen>=0)
{
a[len--]=a[alen--];
}
while (blen>=0)
{
a[len--]=b[blen--];
}
}
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[0]);i++)
{
cout<<a[i]<<" ";
}
}
|
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;
}
}
|
| 
