15个简单算法题
1:合并排序，將兩個已經排序的數組合并成一個數組，其中一個數組能容下兩個數組的所有元素;
2:合并兩個單鏈表;
3:倒序打印一個單鏈表;
4:給定一個單鏈表的頭指針和一個指定節點的指針，在O(1)時間刪除該節點;
5:找到鏈表倒數第K個節點;
6:反轉單鏈表;
7:通過兩個棧實現一個隊列;
8:二分查找;
9:快速排序;
10:獲得一個int型的數中二進制中的個數;
11:輸入一個數組，實現一個函數，讓所有奇數都在偶數前面;
12:判斷一個字符串是否是另一個字符串的子串;
13:把一個int型數組中的數字拼成一個串，這個串代表的數字最小;
14:輸入一顆二叉樹，輸出它的鏡像（每個節點的左右子節點交換位置）;
15:輸入兩個鏈表，找到它們第一個公共節點;
下面簡單說說思路和代碼實現。
C| 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中，但這里是已經有一個數組能存下兩個數組的全部元素，就不用在創建數組了，但只能從后往前面存，從前往后存，要移動元素很麻煩。
?
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:合并兩個單鏈表;
合并鏈表和合并數組，我用了大致相同的代碼，就不多少了，那本書用的是遞歸實現。
?
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 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; ????} } |
?
3:倒序打印一個單鏈表;
遞歸實現，先遞歸在打印就變成倒序打印了，如果先打印在調用自己就是順序打印了。
?
C++| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | //倒序打印一個單鏈表 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)時間刪除該節點;
刪除節點的核心還是將這個節點的下一個節點，代替當前節點。
?
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 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 | //給定一個單鏈表的頭指針和一個指定節點的指針，在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個節點。
?
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | //找到鏈表倒數第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:反轉單鏈表;
按順序一個個的翻轉就是了。
?
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | //反轉單鏈表 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:通過兩個棧實現一個隊列;
直接上代碼
?
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | //通過兩個棧實現一個隊列 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)，注意溢出
?
C++| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | //二分查找 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:快速排序;
來自百度百科，說不清楚
?
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 | //快速排序 //之前有個面試叫我寫快排，想都沒想寫了個冒泡,思路早忘了，這段代碼來自百度百科 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慢慢的從后往前去掉，直到沒有。
?
C++| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | //獲得一個int型的數中二進制中1的個數 int Find1Count(int num) { ????if (num==0) ????{ ????????return 0; ????} ????int count=1; ????while (num= num & (num-1)) ????{ ????????count++; ????} ????return count; } |
?
11:輸入一個數組，實現一個函數，讓所有奇數都在偶數前面;
兩個指針，一個從前往后，一個從后往前，前面的指針遇到奇數就往后走，后面的指針遇到偶數就往前走，只要兩個指針沒有相遇，就奇偶交換。
?
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 37 38 39 40 41 42 43 44 45 46 47 48 49 | //輸入一個數組，實現一個函數，讓所有奇數都在偶數前面 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:判斷一個字符串是否是另一個字符串的子串;
我這里就是暴力的對比
?
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 | //判斷一個字符串是否是另一個字符串的子串 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這么一排序,數組就變成從小到大的順序了，組成的數自然是最小的。
?
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 | //把一個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:輸入一顆二叉樹，輸出它的鏡像（每個節點的左右子節點交換位置）;
遞歸實現，只要某個節點的兩個子節點都不為空，就左右交換，讓左子樹交換，讓右子樹交換。
?
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | 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次，如果有兩個節點相同就是第一個公共節點，否則就沒有公共節點。
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 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 75 76 77 | //輸入兩個鏈表，找到它們第一個公共節點 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;//兩個鏈表相交于節點node6 ????head2->next=node4; ????node4->next=node5; ????node5->next=node6;//兩個鏈表相交于節點node6 ????node6->next=node7; ????NodeL* node= FindFirstEqualNode(head1,head2); ????if (node) ????{ ????????cout<<node->value<<endl; ????}else{ ????????cout<<"沒有共同節點"<<endl; ????} } |
轉載于:https://www.cnblogs.com/wangcp-2014/p/5484386.html
總結
- 上一篇： 【转载】#pragma once与#if
- 下一篇： aardio学习笔记-变量与常量