15道使用频率极高的基础算法题【转】

2015-07-19 16:14 
11369 
10

15道使用频率极高的基础算法题:

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

代码实现:

  1. //链表节点
  2. struct NodeL
  3. {
  4. int value;
  5. NodeL* next;
  6. NodeL(int value_=0,NodeL* next_=NULL):value(value_),next(next_){}
  7. };
  8. //二叉树节点
  9. struct NodeT
  10. {
  11. int value;
  12. NodeT* left;
  13. NodeT* right;
  14. NodeT(int value_=0,NodeT* left_=NULL,NodeT* right_=NULL):value(value_),left(left_),right(right_){}
  15. };

1、合并排序,将两个已经排序的数组合并成一个数组,其中一个数组能容下两个数组的所有元素;

合并排序一般的思路都是创建一个更大数组C,刚好容纳两个数组的元素,先是一个while循环比较,将其中一个数组A比较完成,将另一个数组B中所 有的小于前一个数组A的数及A中所有的数按顺序存入C中,再将A中剩下的数存入C中,但这里是已经有一个数组能存下两个数组的全部元素,就不用在创建数组 了,但只能从后往前面存,从前往后存,要移动元素很麻烦。

  1. //合并排序,将两个已经排序的数组合并成一个数组,其中一个数组能容下两个数组的所有元素
  2. void MergeArray(int a[],int alen,int b[],int blen)
  3. {
  4. int len=alen+blen-1;
  5. alen--;
  6. blen--;
  7. while (alen>=0 && blen>=0)
  8. {
  9. if (a[alen]>b[blen])
  10. {
  11. a[len--]=a[alen--];
  12. }else{
  13. a[len--]=b[blen--];
  14. }
  15. }
  16. while (alen>=0)
  17. {
  18. a[len--]=a[alen--];
  19. }
  20. while (blen>=0)
  21. {
  22. a[len--]=b[blen--];
  23. }
  24. }
  25. void MergeArrayTest()
  26. {
  27. int a[]={2,4,6,8,10,0,0,0,0,0};
  28. int b[]={1,3,5,7,9};
  29. MergeArray(a,5,b,5);
  30. for (int i=0;i<sizeof(a)/sizeof(a[0]);i++)
  31. {
  32. cout<<a[i]<<" ";
  33. }
  34. }

2、合并两个单链表;

合并链表和合并数组,我用了大致相同的代码,就不多少了,那本书用的是递归实现。

  1. //链表节点
  2. struct NodeL
  3. {
  4. int value;
  5. NodeL* next;
  6. NodeL(int value_=0,NodeL* next_=NULL):value(value_),next(next_){}
  7. };
  8. //合并两个单链表
  9. NodeL* MergeList(NodeL* head1,NodeL* head2)
  10. {
  11. if (head1==NULL)
  12. return head2;
  13. if (head2==NULL)
  14. return head1;
  15. NodeL* head=NULL;
  16. if (head1->value<head2->value)
  17. {
  18. head=head1;
  19. head1=head1->next;
  20. }else{
  21. head=head2;
  22. head2=head2->next;
  23. }
  24. NodeL* tmpNode=head;
  25. while (head1 && head2)
  26. {
  27. if (head1->value<head2->value)
  28. {
  29. head->next=head1;
  30. head1=head1->next;
  31. }else{
  32. head->next=head2;
  33. head2=head2->next;
  34. }
  35. head=head->next;
  36. }
  37. if (head1)
  38. {
  39. head->next=head1;
  40. }
  41. if (head2)
  42. {
  43. head->next=head2;
  44. }
  45. return tmpNode;
  46. }
  47. void MergeListTest()
  48. {
  49. NodeL* head1=new NodeL(1);
  50. NodeL* cur=head1;
  51. for (int i=3;i<10;i+=2)
  52. {
  53. NodeL* tmpNode=new NodeL(i);
  54. cur->next=tmpNode;
  55. cur=tmpNode;
  56. }
  57. NodeL* head2=new NodeL(2);
  58. cur=head2;
  59. for (int i=4;i<10;i+=2)
  60. {
  61. NodeL* tmpNode=new NodeL(i);
  62. cur->next=tmpNode;
  63. cur=tmpNode;
  64. }
  65. NodeL* head=MergeList(head1,head2);
  66. while (head)
  67. {
  68. cout<<head->value<<" ";
  69. head=head->next;
  70. }
  71. }

3、倒序打印一个单链表;

递归实现,先递归在打印就变成倒序打印了,如果先打印在调用自己就是顺序打印了。

  1. //倒序打印一个单链表
  2. void ReversePrintNode(NodeL* head)
  3. {
  4. if (head)
  5. {
  6. ReversePrintNode(head->next);
  7. cout<<head->value<<endl;
  8. }
  9. }
  10. void ReversePrintNodeTest()
  11. {
  12. NodeL* head=new NodeL();
  13. NodeL* cur=head;
  14. for (int i=1;i<10;i++)
  15. {
  16. NodeL* tmpNode=new NodeL(i);
  17. cur->next=tmpNode;
  18. cur=tmpNode;
  19. }
  20. ReversePrintNode(head);
  21. }

4、给定一个单链表的头指针和一个指定节点的指针,在O(1)时间删除该节点;

删除节点的核心还是将这个节点的下一个节点,代替当前节点。

  1. //给定一个单链表的头指针和一个指定节点的指针,在O(1)时间删除该节点
  2. void DeleteNode(NodeL* head,NodeL* delNode)
  3. {
  4. if (!head || !delNode)
  5. {
  6. return;
  7. }
  8. if (delNode->next!=NULL)//删除中间节点
  9. {
  10. NodeL* next=delNode->next;
  11. delNode->next=next->next;
  12. delNode->value=next->value;
  13. delete next;
  14. next=NULL;
  15. }else if (head==delNode)//删除头结点
  16. {
  17. delete delNode;
  18. delNode=NULL;
  19. *head=NULL;
  20. }else//删除尾节点,考虑到delNode不在head所在的链表上的情况
  21. {
  22. NodeL* tmpNode=head;
  23. while (tmpNode && tmpNode->next!=delNode)
  24. {
  25. tmpNode=tmpNode->next;
  26. }
  27. if (tmpNode!=NULL)
  28. {
  29. delete delNode;
  30. delNode=NULL;
  31. tmpNode->next=NULL;
  32. }
  33. }
  34. }
  35. void DeleteNodeTest()
  36. {
  37. int nodeCount=10;
  38. for (int K=0;K<nodeCount;K++)
  39. {
  40. NodeL* head=NULL;
  41. NodeL* cur=NULL;
  42. NodeL* delNode=NULL;
  43. for (int i=0;i<nodeCount;i++)
  44. {
  45. NodeL* tmpNode=new NodeL(i);
  46. if (i==0)
  47. {
  48. cur=head=tmpNode;
  49. }else{
  50. cur->next=tmpNode;
  51. cur=tmpNode;
  52. }
  53. if (i==K)
  54. {
  55. delNode=tmpNode;
  56. }
  57. }
  58. DeleteNode(head,delNode) ;
  59. }
  60. }

5、找到链表倒数第K个节点;

通过两个指针,两个指针都指向链表的开始,一个指针先向前走K个节点,然后再以前向前走,当先走的那个节点到达末尾时,另一个节点就刚好与末尾节点相差K个节点。

  1. //找到链表倒数第K个节点
  2. NodeL* FindKthToTail(NodeL* head,unsigned int k)
  3. {
  4. if(head==NULL || k==0)
  5. return NULL;
  6. NodeL* tmpNode=head;
  7. for (int i=0;i<k;i++)
  8. {
  9. if (tmpNode!=NULL)
  10. {
  11. tmpNode=tmpNode->next;
  12. }else{
  13. return NULL;
  14. }
  15. }
  16. NodeL* kNode=head;
  17. while (tmpNode!=NULL)
  18. {
  19. kNode=kNode->next;
  20. tmpNode=tmpNode->next;
  21. }
  22. return kNode;
  23. }
  24. void FindKthToTailTest()
  25. {
  26. int nodeCount=10;
  27. for (int K=0;K<nodeCount;K++)
  28. {
  29. NodeL* head=NULL;
  30. NodeL* cur=NULL;
  31. for (int i=0;i<nodeCount;i++)
  32. {
  33. NodeL* tmpNode=new NodeL(i);
  34. if (i==0)
  35. {
  36. cur=head=tmpNode;
  37. }else{
  38. cur->next=tmpNode;
  39. cur=tmpNode;
  40. }
  41. }
  42. NodeL* kNode=FindKthToTail(head,K+3) ;
  43. if (kNode)
  44. {
  45. cout<<"倒数第 "<<K+3<<" 个节点是:"<<kNode->value<<endl;
  46. }else{
  47. cout<<"倒数第 "<<K+3<<" 个节点不在链表中" <<endl;
  48. }
  49. }
  50. }

6、反转单链表;

按顺序一个个的翻转就是了。

  1. //反转单链表
  2. NodeL* ReverseList(NodeL* head)
  3. {
  4. if (head==NULL)
  5. {
  6. return NULL;
  7. }
  8. NodeL* reverseHead=NULL;
  9. NodeL* curNode=head;
  10. NodeL* preNode=NULL;
  11. while (curNode!=NULL)
  12. {
  13. NodeL* nextNode=curNode->next;
  14. if (nextNode==NULL)
  15. reverseHead=curNode;
  16. curNode->next=preNode;
  17. preNode=curNode;
  18. curNode=nextNode;
  19. }
  20. return reverseHead;
  21. }
  22. void ReverseListTest()
  23. {
  24. for (int K=0;K<=10;K++)
  25. {
  26. NodeL* head=NULL;
  27. NodeL* cur=NULL;
  28. for (int i=0;i<K;i++)
  29. {
  30. NodeL* tmpNode=new NodeL(i);
  31. if (i==0)
  32. {
  33. cur=head=tmpNode;
  34. }else{
  35. cur->next=tmpNode;
  36. cur=tmpNode;
  37. }
  38. }
  39. cur=ReverseList( head);
  40. while (cur)
  41. {
  42. cout<<cur->value<<" ";
  43. cur=cur->next;
  44. }
  45. cout<<endl;
  46. }
  47. cout<<endl;
  48. }

7、通过两个栈实现一个队列;

直接上代码

  1. //通过两个栈实现一个队列
  2. template<typename T>
  3. class CQueue
  4. {
  5. public:
  6. void push(const T& val)
  7. {
  8. while (s2.size()>0)
  9. {
  10. s1.push(s2.top());
  11. s2.pop();
  12. }
  13. s1.push(val);
  14. }
  15. void pop()
  16. {
  17. while (s1.size()>0)
  18. {
  19. s2.push(s1.top());
  20. s1.pop();
  21. }
  22. s2.pop();
  23. }
  24. T& front()
  25. {
  26. while (s1.size()>0)
  27. {
  28. s2.push(s1.top());
  29. s1.pop();
  30. }
  31. return s2.top();
  32. }
  33. int size()
  34. {
  35. return s1.size()+s2.size();
  36. }
  37. private:
  38. stack<T> s1;
  39. stack<T> s2;
  40. };
  41. void CQueueTest()
  42. {
  43. CQueue<int> q;
  44. for (int i=0;i<10;i++)
  45. {
  46. q.push(i);
  47. }
  48. while (q.size()>0)
  49. {
  50. cout<<q.front()<<" ";
  51. q.pop();
  52. }
  53. }

8、二分查找;

二分查找记住几个要点就行了,代码也就那几行,反正我现在是可以背出来了,start=0,end=数组长度-1,while(start<=end),注意溢出。

  1. //二分查找
  2. int binarySearch(int a[],int len,int val)
  3. {
  4. int start=0;
  5. int end=len-1;
  6. int index=-1;
  7. while (start<=end)
  8. {
  9. index=start+(end-start)/2;
  10. if (a[index]==val)
  11. {
  12. return index;
  13. }else if (a[index]<val)
  14. {
  15. start=index+1;
  16. }else
  17. {
  18. end=index-1;
  19. }
  20. }
  21. return -1;
  22. }

9、快速排序;

来自百度百科,说不清楚

  1. //快速排序
  2. //之前有个面试叫我写快排,想都没想写了个冒泡,思路早忘了,这段代码来自百度百科
  3. void Qsort(int a[],int low,int high)
  4. {
  5. if(low>=high)
  6. {
  7. return;
  8. }
  9. int first=low;
  10. int last=high;
  11. int key=a[first];//用字表的第一个记录作为枢轴
  12. while(first<last)
  13. {
  14. while(first<last && a[last]>=key )--last;
  15. a[first]=a[last];//将比第一个小的移到低端
  16. while(first<last && a[first]<=key )++first;
  17. a[last]=a[first];//将比第一个大的移到高端
  18. }
  19. a[first]=key;//枢轴