1、合并排序,將兩個已經(jīng)排序的數(shù)組合并成一個數(shù)組,其中一個數(shù)組能容下兩個數(shù)組的所有元素; 代碼實現(xiàn): //鏈表節(jié)點struct NodeL { int value; NodeL* next; NodeL(int value_=0,NodeL* next_=NULL):value(value_),next(next_){}}; //二叉樹節(jié)點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、合并排序,將兩個已經(jīng)排序的數(shù)組合并成一個數(shù)組,其中一個數(shù)組能容下兩個數(shù)組的所有元素; 合并排序一般的思路都是創(chuàng)建一個更大數(shù)組C,剛好容納兩個數(shù)組的元素,先是一個while循環(huán)比較,將其中一個數(shù)組A比較完成,將另一個數(shù)組B中所有的小于前一個數(shù)組A的數(shù)及A中所有的數(shù)按順序存入C中,再將A中剩下的數(shù)存入C中,但這里是已經(jīng)有一個數(shù)組能存下兩個數(shù)組的全部元素,就不用在創(chuàng)建數(shù)組了,但只能從后往前面存,從前往后存,要移動元素很麻煩。 //合并排序,將兩個已經(jīng)排序的數(shù)組合并成一個數(shù)組,其中一個數(shù)組能容下兩個數(shù)組的所有元素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<><' ';=""> 2、合并兩個單鏈表; 合并鏈表和合并數(shù)組,我用了大致相同的代碼,就不多少了,那本書用的是遞歸實現(xiàn)。 //鏈表節(jié)點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 3、倒序打印一個單鏈表; 遞歸實現(xiàn),先遞歸在打印就變成倒序打印了,如果先打印在調(diào)用自己就是順序打印了。 //倒序打印一個單鏈表void ReversePrintNode(NodeL* head){ if (head) { ReversePrintNode(head->next); cout 4、給定一個單鏈表的頭指針和一個指定節(jié)點的指針,在O(1)時間刪除該節(jié)點; 刪除節(jié)點的核心還是將這個節(jié)點的下一個節(jié)點,代替當前節(jié)點。 //給定一個單鏈表的頭指針和一個指定節(jié)點的指針,在O(1)時間刪除該節(jié)點void DeleteNode(NodeL* head,NodeL* delNode){ if (!head || !delNode) { return; } if (delNode->next!=NULL)//刪除中間節(jié)點 { NodeL* next=delNode->next; delNode->next=next->next; delNode->value=next->value; delete next; next=NULL; }else if (head==delNode)//刪除頭結(jié)點 { delete delNode; delNode=NULL; *head=NULL; }else//刪除尾節(jié)點,考慮到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 5、找到鏈表倒數(shù)第K個節(jié)點; 通過兩個指針,兩個指針都指向鏈表的開始,一個指針先向前走K個節(jié)點,然后再以前向前走,當先走的那個節(jié)點到達末尾時,另一個節(jié)點就剛好與末尾節(jié)點相差K個節(jié)點。 //找到鏈表倒數(shù)第K個節(jié)點NodeL* FindKthToTail(NodeL* head,unsigned int k){ if(head==NULL || k==0) return NULL; NodeL* tmpNode=head; for (int i=0;i 6、反轉(zhuǎn)單鏈表; 按順序一個個的翻轉(zhuǎn)就是了。 //反轉(zhuǎn)單鏈表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=""> 7、通過兩個棧實現(xiàn)一個隊列; 直接上代碼 //通過兩個棧實現(xiàn)一個隊列template 8、二分查找; 二分查找記住幾個要點就行了,代碼也就那幾行,反正我現(xiàn)在是可以背出來了,start=0,end=數(shù)組長度-1,while(start<> //二分查找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=""> 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 10、獲得一個int型的數(shù)中二進制中的個數(shù); 核心實現(xiàn)就是while (num= num & (num-1)),通過這個數(shù)和比它小1的數(shù)的二進制進行&運算,將二進制中1慢慢的從后往前去掉,直到?jīng)]有。 //獲得一個int型的數(shù)中二進制中1的個數(shù)int Find1Count(int num){ if (num==0) { return 0; } int count=1; while (num= num & (num-1)) { count++; } return count;} 11、輸入一個數(shù)組,實現(xiàn)一個函數(shù),讓所有奇數(shù)都在偶數(shù)前面; 兩個指針,一個從前往后,一個從后往前,前面的指針遇到奇數(shù)就往后走,后面的指針遇到偶數(shù)就往前走,只要兩個指針沒有相遇,就奇偶交換。 //輸入一個數(shù)組,實現(xiàn)一個函數(shù),讓所有奇數(shù)都在偶數(shù)前面void RecordOddEven(int A[],int len){ int i=0,j=len-1; while (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<=cmpcount;i++) {="" int="" j="0;" for=""> 13、把一個int型數(shù)組中的數(shù)字拼成一個串,這個串代表的數(shù)字最小; 先將數(shù)字轉(zhuǎn)換成字符串存在數(shù)組中,在通過qsort排序,在排序用到的比較函數(shù)中,將要比較的兩個字符串進行組合,如要比較的兩個字符串分別是A,B,那么組合成,A+B,和B+A,在比較A+B和B+A,返回strcmp(A+B, B+A),經(jīng)過qsort這么一排序,數(shù)組就變成從小到大的順序了,組成的數(shù)自然是最小的。 //把一個int型數(shù)組中的數(shù)字拼成一個串,是這個串代表的數(shù)組最小#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<><' ';="" delete[]="" str[i]="" ;="" }="" delete[]="" str;}="" void="" getlinkmintest(){="" int="" arr[]="{123,132,213,231,321,312};"> 14、輸入一顆二叉樹,輸出它的鏡像(每個節(jié)點的左右子節(jié)點交換位置); 遞歸實現(xiàn),只要某個節(jié)點的兩個子節(jié)點都不為空,就左右交換,讓左子樹交換,讓右子樹交換。 struct NodeT{ int value; NodeT* left; NodeT* right; NodeT(int value_=0,NodeT* left_=NULL,NodeT* right_=NULL):value(value_),left(left_),right(right_){}};//輸入一顆二叉樹,輸出它的鏡像(每個節(jié)點的左右子節(jié)點交換位置)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 15、輸入兩個鏈表,找到它們第一個公共節(jié)點; 如果兩個鏈表有公共的節(jié)點,那么第一個公共的節(jié)點及往后的節(jié)點都是公共的。從后往前數(shù)N個節(jié)點(N=短鏈表的長度節(jié)點個數(shù)),長鏈表先往前走K個節(jié)點(K=長鏈表的節(jié)點個數(shù)-N),這時兩個鏈表都距離末尾N個節(jié)點,現(xiàn)在可以一一比較了,最多比較N次,如果有兩個節(jié)點相同就是第一個公共節(jié)點,否則就沒有公共節(jié)點。 //輸入兩個鏈表,找到它們第一個公共節(jié)點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
|
|
來自: 新華書店好書榜 > 《「OFFICE」》