使用频率高的算法题.doc

15道使用频率极高的基础算法题： 1、合并排序，将两个已经排序的数组合并成一个数组，其中一个数组能容下两个数组的所有元素;2、合并两个已经排序的单链表;3、倒序打印一个单链表;?4、给定一个单链表的头指针和一个指定节点的指针，在O(1)时间删除该节点;5、找到链表倒数第K个节点;6、反转单链表;7、通过两个栈实现一个队列;8、二分查找;9、快速排序;10、获得一个int型的数中二进制中的个数;11、输入一个数组，实现一个函数，让所有奇数都在偶数前面;12、判断一个字符串是否是另一个字符串的子串;13、把一个int型数组中的数字拼成一个串，这个串代表的数字最小;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中，但这里是已经有一个数组能存下两个数组的全部元素，就不用在创建数组了，但只能从后往前面存，从前往后存，要移动元素很麻烦。 //合并排序，将两个已经排序的数组合并成一个数组，其中一个数组能容下两个数组的所有元素 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;isizeof(a)/sizeof(a[0]);i++) { couta[i] ; } } 2、合并两个单链表; 合并链表和合并数组，我用了大致相同的代码，就不多少了，那本书用的是递归实现。 //链表节点 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-valuehead2-value) { head=head1; head1=head1-next; }else{ head=head2; head2=head2-next; }