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

2015-07-19 16:14 
7015 
9

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;//枢轴记录到位
  20. Qsort(a,low,first-1);
  21. Qsort(a,last+1,high);
  22. }
  23. void QsortTest()
  24. {
  25. int a[]={1,3,5,7,9,2,4,6,8,0};
  26. int len=sizeof(a)/sizeof(a[0])-1;
  27. Qsort(a,0,len);
  28. for(int i=0;i<=len;i++)
  29. {
  30. cout<<a[i]<<" ";
  31. }
  32. cout<<endl;
  33. }

10、获得一个int型的数中二进制中的个数;

核心实现就是while (num= num & (num-1)),通过这个数和比它小1的数的二进制进行&运算,将二进制中1慢慢的从后往前去掉,直到没有。

  1. //获得一个int型的数中二进制中1的个数
  2. int Find1Count(int num)
  3. {
  4. if (num==0)
  5. {
  6. return 0;
  7. }
  8. int count=1;
  9. while (num= num & (num-1))
  10. {
  11. count++;
  12. }
  13. return count;
  14. }

11、输入一个数组,实现一个函数,让所有奇数都在偶数前面;

两个指针,一个从前往后,一个从后往前,前面的指针遇到奇数就往后走,后面的指针遇到偶数就往前走,只要两个指针没有相遇,就奇偶交换。

  1. //输入一个数组,实现一个函数,让所有奇数都在偶数前面
  2. void RecordOddEven(int A[],int len)
  3. {
  4. int i=0,j=len-1;
  5. while (i<j)
  6. {
  7. while (i<len && A[i]%2==1)
  8. i++;
  9. while (j>=0 && A[j]%2==0)
  10. j--;
  11. if (i<j)
  12. {
  13. A[i]^=A[j]^=A[i]^=A[j];
  14. }
  15. }
  16. }
  17. void RecordOddEvenTest()
  18. {
  19. int A[]={1,2,3,4,5,6,7,8,9,0,11};
  20. int len=sizeof(A)/sizeof(A[0]);
  21. RecordOddEven( A , len);
  22. for (int i=0;i<len;i++)
  23. {
  24. cout<<A[i]<<" ";
  25. }
  26. cout<<endl;
  27. for (int i=0;i<len;i++)
  28. {
  29. A[i]=2;
  30. }
  31. RecordOddEven( A , len);
  32. for (int i=0;i<len;i++)
  33. {
  34. cout<<A[i]<<" ";
  35. }
  36. cout<<endl;
  37. for (int i=0;i<len;i++)
  38. {
  39. A[i]=1;
  40. }
  41. RecordOddEven( A , len);
  42. for (int i=0;i<len;i++)
  43. {
  44. cout<<A[i]<<" ";
  45. }
  46. }

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

我这里就是暴力的对比

  1. //判断一个字符串是否是另一个字符串的子串
  2. int substr(const char* source,const char* sub)
  3. {
  4. if (source==NULL || sub==NULL)
  5. {
  6. return -1;
  7. }
  8. int souLen=strlen(source);
  9. int subLen=strlen(sub);
  10. if (souLen<subLen)
  11. {
  12. return -1;
  13. }
  14. int cmpCount=souLen-subLen;
  15. for (int i=0;i<=cmpCount;i++)
  16. {
  17. int j=0;
  18. for (;j<subLen;j++)
  19. {
  20. if (source[i+j]!=sub[j])
  21. {
  22. break;
  23. }
  24. }
  25. if (j==subLen)
  26. {
  27. return i ;
  28. }
  29. }
  30. return -1;
  31. }

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

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

  1. //把一个int型数组中的数字拼成一个串,是这个串代表的数组最小
  2. #define MaxLen 10
  3. int Compare(const void* str1,const void* str2)
  4. {
  5. char cmp1[MaxLen*2+1];
  6. char cmp2[MaxLen*2+1];
  7. strcpy(cmp1,*(char**)str1);
  8. strcat(cmp1,*(char**)str2);
  9. strcpy(cmp2,*(char**)str2);
  10. strcat(cmp2,*(char**)str1);
  11. return strcmp(cmp1,cmp2);
  12. }
  13. void GetLinkMin(int a[],int len)
  14. {
  15. char** str=(char**)new int[len];
  16. for (int i=0;i<len;i++)
  17. {
  18. str[i]=new char[MaxLen+1];
  19. sprintf(str[i],"%d",a[i]);
  20. }
  21. qsort(str,len,sizeof(char*),Compare);
  22. for (int i=0;i<len;i++)
  23. {
  24. cout<<str[i]<<" ";
  25. delete[] str[i] ;
  26. }
  27. delete[] str;
  28. }
  29. void GetLinkMinTest()
  30. {
  31. int arr[]={123,132,213,231,321,312};
  32. GetLinkMin(arr,sizeof(arr)/sizeof(int));
  33. }

14、输入一颗二叉树,输出它的镜像(每个节点的左右子节点交换位置);

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

  1. struct NodeT
  2. {
  3. int value;
  4. NodeT* left;
  5. NodeT* right;
  6. NodeT(int value_=0,NodeT* left_=NULL,NodeT* right_=NULL):value(value_),left(left_),right(right_){}
  7. };
  8. //输入一颗二叉树,输出它的镜像(每个节点的左右子节点交换位置)
  9. void TreeClass(NodeT* root)
  10. {
  11. if( root==NULL || (root->left==NULL && root->right==NULL) )
  12. return;
  13. NodeT* tmpNode=root->left;
  14. root->left=root->right;
  15. root->right=tmpNode;
  16. TreeClass(root->left);
  17. TreeClass(root->right);
  18. }
  19. void PrintTree(NodeT* root)
  20. {
  21. if(root)
  22. {
  23. cout<<root->value<<" ";
  24. PrintTree(root->left);
  25. PrintTree(root->right);
  26. }
  27. }
  28. void TreeClassTest()
  29. {
  30. NodeT* root=new NodeT(8);
  31. NodeT* n1=new NodeT(6);
  32. NodeT* n2=new NodeT(10);
  33. NodeT* n3=new NodeT(5);
  34. NodeT* n4=new NodeT(7);
  35. NodeT* n5=new NodeT(9);
  36. NodeT* n6=new NodeT(11);
  37. root->left=n1;
  38. root->right=n2;
  39. n1->left=n3;
  40. n1->right=n4;
  41. n2->left=n5;
  42. n2->right=n6;
  43. PrintTree(root);
  44. cout<<endl;
  45. TreeClass( root );
  46. PrintTree(root);
  47. cout<<endl;
  48. }

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

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

  1. //输入两个链表,找到它们第一个公共节点
  2. int GetLinkLength(NodeL* head)
  3. {
  4. int count=0;
  5. while (head)
  6. {
  7. head=head->next;
  8. count++;
  9. }
  10. return count;
  11. }
  12. NodeL* FindFirstEqualNode(NodeL* head1,NodeL* head2)
  13. {
  14. if (head1==NULL || head2==NULL)
  15. return NULL;
  16. int len1=GetLinkLength(head1);
  17. int len2=GetLinkLength(head2);
  18. NodeL* longNode;
  19. NodeL* shortNode;
  20. int leftNodeCount;
  21. if (len1>len2)
  22. {
  23. longNode=head1;
  24. shortNode=head2;
  25. leftNodeCount=len1-len2;
  26. }else{
  27. longNode=head2;
  28. shortNode=head1;
  29. leftNodeCount=len2-len1;
  30. }
  31. for (int i=0;i<leftNodeCount;i++)
  32. {
  33. longNode=longNode->next;
  34. }
  35. while (longNode && shortNode && longNode!=shortNode)
  36. {
  37. longNode=longNode->next;
  38. shortNode=shortNode->next;
  39. }
  40. if (longNode)//如果有公共节点,必不为NULL
  41. {
  42. return longNode;
  43. }
  44. return NULL;
  45. }
  46. void FindFirstEqualNodeTest()
  47. {
  48. NodeL* head1=new NodeL(0);
  49. NodeL* head2=new NodeL(0);
  50. NodeL* node1=new NodeL(1);
  51. NodeL* node2=new NodeL(2);
  52. NodeL* node3=new NodeL(3);
  53. NodeL* node4=new NodeL(4);
  54. NodeL* node5=new NodeL(5);
  55. NodeL* node6=new NodeL(6);
  56. NodeL* node7=new NodeL(7);
  57. head1->next=node1;
  58. node1->next=node2;
  59. node2->next=node3;
  60. node3->next=node6;//两个链表相交于节点node6
  61. head2->next=node4;
  62. node4->next=node5;
  63. node5->next=node6;//两个链表相交于节点node6
  64. node6->next=node7;
  65. NodeL* node= FindFirstEqualNode(head1,head2);
  66. if (node)
  67. {
  68. cout<<node->value<<endl;
  69. }else{
  70. cout<<"没有共同节点"<<endl;
  71. }
  72. }
上一篇: NoSQL【转】

评论列表

暂无评论

添加评论

* (邮箱不会公开,只会做回复通知用)

* (好的站点我会把它添加到友情链接

* (需要您帮忙,确定您是真实的访客)

*

提交评论