算法題列表

• 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;i<sizeof(a)/sizeof(a[0]);i++){cout<<a[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->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、倒序打印一個單鏈表;

遞歸實現，先遞歸在打印就變成倒序打印了，如果先打印在調用自己就是順序打印了。

//倒序打印一個單鏈表 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); }

4、給定一個單鏈表的頭指針和一個指定節點的指針，在O(1)時間刪除該節點;

刪除節點的核心還是將這個節點的下一個節點，代替當前節點。

//給定一個單鏈表的頭指針和一個指定節點的指針，在O(1)時間刪除該節點 void DeleteNode(NodeL* head,NodeL* delNode) {if (!head || !delNode){return;}if (delNode->next!=NULL)//刪除中間節點{NodeL* next=delNode->next;delNode->next=next->next;delNode->value=next->value;delete next;next=NULL;}else if (head==delNode)//刪除頭結點{delete delNode;delNode=NULL;*head=NULL;}else//刪除尾節點，考慮到delNode不在head所在的鏈表上的情況{NodeL* tmpNode=head;while (tmpNode && tmpNode->next!=delNode){tmpNode=tmpNode->next;}if (tmpNode!=NULL){delete delNode;delNode=NULL;tmpNode->next=NULL;}} }void DeleteNodeTest() {int nodeCount=10;for (int K=0;K<nodeCount;K++){NodeL* head=NULL;NodeL* cur=NULL;NodeL* delNode=NULL;for (int i=0;i<nodeCount;i++){NodeL* tmpNode=new NodeL(i);if (i==0){cur=head=tmpNode;}else{cur->next=tmpNode;cur=tmpNode; }if (i==K){delNode=tmpNode;} }DeleteNode(head,delNode) ;} }

5、找到鏈表倒數第K個節點;

通過兩個指針，兩個指針都指向鏈表的開始，一個指針先向前走K個節點，然后再以前向前走，當先走的那個節點到達末尾時，另一個節點就剛好與末尾節點相差K個節點。

//找到鏈表倒數第K個節點 NodeL* FindKthToTail(NodeL* head,unsigned int k) {if(head==NULL || k==0)return NULL;NodeL* tmpNode=head;for (int i=0;i<k;i++){if (tmpNode!=NULL){tmpNode=tmpNode->next;}else{return NULL;} }NodeL* kNode=head;while (tmpNode!=NULL){kNode=kNode->next;tmpNode=tmpNode->next;}return kNode; }void FindKthToTailTest() {int nodeCount=10;for (int K=0;K<nodeCount;K++){NodeL* head=NULL;NodeL* cur=NULL; for (int i=0;i<nodeCount;i++){NodeL* tmpNode=new NodeL(i);if (i==0){cur=head=tmpNode;}else{cur->next=tmpNode;cur=tmpNode; }}NodeL* kNode=FindKthToTail(head,K+3) ;if (kNode){cout<<"倒數第 "<<K+3<<" 個節點是："<<kNode->value<<endl;}else{cout<<"倒數第 "<<K+3<<" 個節點不在鏈表中" <<endl;}} }

6、反轉單鏈表;

按順序一個個的翻轉就是了。

//反轉單鏈表 NodeL* ReverseList(NodeL* head) {if (head==NULL){return NULL;}NodeL* reverseHead=NULL;NodeL* curNode=head;NodeL* preNode=NULL;while (curNode!=NULL){NodeL* nextNode=curNode->next;if (nextNode==NULL)reverseHead=curNode; curNode->next=preNode;preNode=curNode;curNode=nextNode;}return reverseHead; }void ReverseListTest() {for (int K=0;K<=10;K++){NodeL* head=NULL;NodeL* cur=NULL; for (int i=0;i<K;i++){NodeL* tmpNode=new NodeL(i);if (i==0){cur=head=tmpNode;}else{cur->next=tmpNode;cur=tmpNode; }}cur=ReverseList( head);while (cur){cout<<cur->value<<" ";cur=cur->next;}cout<<endl;}cout<<endl; }

7、通過兩個棧實現一個隊列;

直接上代碼

//通過兩個棧實現一個隊列 template<typename T> class CQueue { public:void push(const T& val){while (s2.size()>0){s1.push(s2.top());s2.pop();}s1.push(val);}void pop(){ while (s1.size()>0){s2.push(s1.top());s1.pop();}s2.pop();}T& front(){ while (s1.size()>0){s2.push(s1.top());s1.pop();}return s2.top();}int size(){return s1.size()+s2.size();} private:stack<T> s1;stack<T> s2; };void CQueueTest() {CQueue<int> q;for (int i=0;i<10;i++){q.push(i);}while (q.size()>0){cout<<q.front()<<" ";q.pop();} }

8、二分查找;

二分查找記住幾個要點就行了，代碼也就那幾行，反正我現在是可以背出來了，start=0，end=數組長度-1，while(start<=end)，注意溢出。

//二分查找 int binarySearch(int a[],int len,int val) {int start=0;int end=len-1;int index=-1;while (start<=end){index=start+(end-start)/2;if (a[index]==val){return index;}else if (a[index]<val){start=index+1;}else{end=index-1;}}return -1; }

9、快速排序;

來自百度百科，說不清楚

//快速排序 //之前有個面試叫我寫快排，想都沒想寫了個冒泡,思路早忘了，這段代碼來自百度百科 void Qsort(int a[],int low,int high) {if(low>=high){return;}int first=low;int last=high;int key=a[first];//用字表的第一個記錄作為樞軸while(first<last){while(first<last && a[last]>=key )--last;a[first]=a[last];//將比第一個小的移到低端while(first<last && a[first]<=key )++first;a[last]=a[first];//將比第一個大的移到高端}a[first]=key;//樞軸記錄到位Qsort(a,low,first-1);Qsort(a,last+1,high); }void QsortTest() {int a[]={1,3,5,7,9,2,4,6,8,0};int len=sizeof(a)/sizeof(a[0])-1;Qsort(a,0,len); for(int i=0;i<=len;i++){cout<<a[i]<<" ";} cout<<endl; }

10、獲得一個int型的數中二進制中的個數;

核心實現就是while (num= num & (num-1))，通過這個數和比它小1的數的二進制進行&運算，將二進制中1慢慢的從后往前去掉，直到沒有。

//獲得一個int型的數中二進制中1的個數 int Find1Count(int num) {if (num==0){return 0;}int count=1;while (num= num & (num-1)){count++;}return count; }

11、輸入一個數組，實現一個函數，讓所有奇數都在偶數前面;

兩個指針，一個從前往后，一個從后往前，前面的指針遇到奇數就往后走，后面的指針遇到偶數就往前走，只要兩個指針沒有相遇，就奇偶交換。

//輸入一個數組，實現一個函數，讓所有奇數都在偶數前面 void RecordOddEven(int A[],int len) {int i=0,j=len-1;while (i<j){while (i<len && A[i]%2==1) i++; while (j>=0 && A[j]%2==0) j--; if (i<j){A[i]^=A[j]^=A[i]^=A[j]; }} }void RecordOddEvenTest() {int A[]={1,2,3,4,5,6,7,8,9,0,11};int len=sizeof(A)/sizeof(A[0]);RecordOddEven( A , len);for (int i=0;i<len;i++){cout<<A[i]<<" ";}cout<<endl;for (int i=0;i<len;i++){A[i]=2;}RecordOddEven( A , len);for (int i=0;i<len;i++){cout<<A[i]<<" ";}cout<<endl;for (int i=0;i<len;i++){A[i]=1;}RecordOddEven( A , len);for (int i=0;i<len;i++){cout<<A[i]<<" ";} }

12、判斷一個字符串是否是另一個字符串的子串;

我這里就是暴力的對比

//判斷一個字符串是否是另一個字符串的子串 int substr(const char* source,const char* sub) {if (source==NULL || sub==NULL){return -1;}int souLen=strlen(source);int subLen=strlen(sub);if (souLen<subLen){return -1;}int cmpCount=souLen-subLen;for (int i=0;i<=cmpCount;i++){int j=0;for (;j<subLen;j++){if (source[i+j]!=sub[j]){break;}}if (j==subLen){return i ;}}return -1; }

13、把一個int型數組中的數字拼成一個串，這個串代表的數字最小;

先將數字轉換成字符串存在數組中，在通過qsort排序，在排序用到的比較函數中，將要比較的兩個字符串進行組合，如要比較的兩個字符串分別是A,B，那么組合成，A+B，和B+A，在比較A+B和B+A，返回strcmp(A+B, B+A)，經過qsort這么一排序,數組就變成從小到大的順序了，組成的數自然是最小的。

//把一個int型數組中的數字拼成一個串，是這個串代表的數組最小 #define MaxLen 10 int Compare(const void* str1,const void* str2) {char cmp1[MaxLen*2+1];char cmp2[MaxLen*2+1];strcpy(cmp1,*(char**)str1);strcat(cmp1,*(char**)str2);strcpy(cmp2,*(char**)str2);strcat(cmp2,*(char**)str1);return strcmp(cmp1,cmp2); } void GetLinkMin(int a[],int len) {char** str=(char**)new int[len];for (int i=0;i<len;i++){str[i]=new char[MaxLen+1];sprintf(str[i],"%d",a[i]); }qsort(str,len,sizeof(char*),Compare);for (int i=0;i<len;i++){cout<<str[i]<<" ";delete[] str[i] ;}delete[] str; } void GetLinkMinTest() {int arr[]={123,132,213,231,321,312};GetLinkMin(arr,sizeof(arr)/sizeof(int)); }

14、輸入一顆二叉樹，輸出它的鏡像（每個節點的左右子節點交換位置）;

遞歸實現，只要某個節點的兩個子節點都不為空，就左右交換，讓左子樹交換，讓右子樹交換。

struct NodeT {int value;NodeT* left;NodeT* right;NodeT(int value_=0,NodeT* left_=NULL,NodeT* right_=NULL):value(value_),left(left_),right(right_){} };//輸入一顆二叉樹，輸出它的鏡像（每個節點的左右子節點交換位置） void TreeClass(NodeT* root) {if( root==NULL || (root->left==NULL && root->right==NULL) ) return; NodeT* tmpNode=root->left;root->left=root->right;root->right=tmpNode;TreeClass(root->left);TreeClass(root->right); }void PrintTree(NodeT* root) {if(root){cout<<root->value<<" ";PrintTree(root->left);PrintTree(root->right);} }void TreeClassTest() {NodeT* root=new NodeT(8);NodeT* n1=new NodeT(6);NodeT* n2=new NodeT(10);NodeT* n3=new NodeT(5);NodeT* n4=new NodeT(7);NodeT* n5=new NodeT(9);NodeT* n6=new NodeT(11);root->left=n1;root->right=n2;n1->left=n3;n1->right=n4;n2->left=n5;n2->right=n6;PrintTree(root);cout<<endl;TreeClass( root );PrintTree(root);cout<<endl; }

15、輸入兩個鏈表，找到它們第一個公共節點;

如果兩個鏈表有公共的節點，那么第一個公共的節點及往后的節點都是公共的。從后往前數N個節點（N=短鏈表的長度節點個數）,長鏈表先往前走K個節點（K=長鏈表的節點個數-N），這時兩個鏈表都距離末尾N個節點，現在可以一一比較了，最多比較N次，如果有兩個節點相同就是第一個公共節點，否則就沒有公共節點。

//輸入兩個鏈表，找到它們第一個公共節點 int GetLinkLength(NodeL* head) { int count=0;while (head){head=head->next;count++;}return count; }NodeL* FindFirstEqualNode(NodeL* head1,NodeL* head2) {if (head1==NULL || head2==NULL)return NULL;int len1=GetLinkLength(head1);int len2=GetLinkLength(head2);NodeL* longNode;NodeL* shortNode;int leftNodeCount;if (len1>len2){longNode=head1;shortNode=head2;leftNodeCount=len1-len2;}else{longNode=head2;shortNode=head1;leftNodeCount=len2-len1;}for (int i=0;i<leftNodeCount;i++){longNode=longNode->next;}while (longNode && shortNode && longNode!=shortNode){longNode=longNode->next;shortNode=shortNode->next;}if (longNode)//如果有公共節點，必不為NULL{return longNode;}return NULL; }void FindFirstEqualNodeTest() {NodeL* head1=new NodeL(0);NodeL* head2=new NodeL(0);NodeL* node1=new NodeL(1);NodeL* node2=new NodeL(2);NodeL* node3=new NodeL(3);NodeL* node4=new NodeL(4);NodeL* node5=new NodeL(5);NodeL* node6=new NodeL(6);NodeL* node7=new NodeL(7);head1->next=node1;node1->next=node2;node2->next=node3;node3->next=node6;//兩個鏈表相交于節點node6head2->next=node4;node4->next=node5;node5->next=node6;//兩個鏈表相交于節點node6node6->next=node7;NodeL* node= FindFirstEqualNode(head1,head2);if (node){cout<<node->value<<endl;}else{cout<<"沒有共同節點"<<endl;} }

總結

以上是生活随笔為你收集整理的15道使用频率极高的基础算法题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。