每日微軟面試題

每日微軟面試題——day 1

<以下微軟面試題全來自網絡>

<以下答案與分析純屬個人觀點，不足之處，還望不吝指出^_^>

題：.編寫反轉字符串的程序，要求優化速度、優化空間。

分析：構建兩個迭代器p 和 q ，在一次遍歷中，p的位置從字串開頭向中間前進，q從字串末尾向中間后退，反轉字串只要每次遍歷都交換p和q所指向的內容即可，直到p和q在中間相遇，這時循環次數剛好等于字串的長度/2。

實現代碼：

[cpp] view plaincopy

/**?
author:?花心龜?
blog：http://blog.csdn.net/zhanxinhang?
**/??
??
#include?<stdio.h>??
void?reverse(char?*_str,int?_l)?//反轉函數,_l指要反轉字串的長度??
{??
?char?*p=_str,*q=_str+_l-1,temp;??
??
?while(q>p)??
???{???
?????temp=*p;??
?????*p=*q;??
?????*q=temp;??
???
?????p++;??
?????q--;??
???}??
}??
???
int?main()??
{??
??charstr0[11]=?"0123456789";???????
?reverse(str0,sizeof(str0)-1);??
?printf("str0?=?%s\n",str0);??
???
??char?str1[6]="01234";??
?reverse(str1,sizeof(str1)-1);??
?printf("str1?=?%s",str1);??
??return?0;??
}??

題：.在鏈表里如何發現循環鏈接？

分析：可以構建兩個迭代器p和pp，p一次向移動一個節點，pp一次移動兩個節點，如果p和pp在某個時刻指向了同一個節點，那么該鏈表就有循環鏈接。

實現代碼：

[cpp] view plaincopy

/**?
Author:花心龜?
Blog：http://blog.csdn.net/zhanxinhang?
**/??
#include?<stdio.h>??
#include?<malloc.h>??
??
#define?TEST??
??
struct?list_node??
{??
??int?data;??
??list_node?*?next;??
};??
list_node?*head;?//指向頭結點??
??
void?list_create()??
{??
??int?i;??
??list_node?*p=NULL;??
??head?=?(list_node*)malloc(sizeof(list_node));??
??head->data=0;?????//頭結點數據設為??
??head->next?=?NULL;??
??
??p=head;??
??for(i=1;?i<6;?i++)?//創建個結點??
????{??
??????p->next?=?(list_node*)malloc(sizeof(list_node));??
??????p->next->data?=?i;??
??????p->next->next?=?NULL;??
??????p=p->next;??
????}??
??p->next?=?head;??//使尾結點的下一個結點指針指向頭結點，構成循環鏈表??
??
#ifdef?TEST??
??p=head;??
??for(i=0;?i<12&&p!=NULL;?i++)??
????{??
??????printf("%d?",p->data);??
??????p=p->next;??
????}??
??printf("\n");??
#endif??
}??
??
void?cycleList_test()??
{??
??if(head==NULL?||?head->next?==?NULL)??
??????return;??
??list_node?*p=NULL,*pp=NULL;??
??p=head;??
??pp=head->next->next;??
??while(p!=pp?)??
????{??
??????p=p->next;??
??????pp=pp->next->next;??
??
??????if(p==NULL?||?pp==NULL)??
????{??
??????printf("不是循環鏈表");??
??????return?;??
????}??
????}??
??printf("是循環鏈表");??
}??
??
void?list_destroy()??
{??
??list_node?*pmove=NULL,*pdel=NULL;??
??pmove=head->next;??
??
?while(pmove!=head)??
???{??
?????pdel=pmove;??
?????pmove=pmove->next;??
?????free(pdel);?????
???}??
??
??free(head);??
}??
int?main()??
{??
??list_create();???//構建循環鏈表??
??cycleList_test();//測試是否是循環鏈表??
??list_destroy();??//銷毀鏈表??
??return?0;??
}?

題：.給出洗牌的一個算法，并將洗好的牌存儲在一個整形數組里。

分析：首先54張牌分別用0到53 的數值表示并存儲在一個整形數組里，數組下標代表紙牌所在的位置。接下來，遍歷整個數組，在遍歷過程中隨機產生一個隨機數，并以該隨機數為下標的數組元素與當前遍歷到的數組元素進行對換。時間復雜度為O(n) (注：所得到的每一種結果的概率的分母越大越好)

實現代碼：

[cpp] view plaincopy

/**?
Author:花心龜?
Blog：http://blog.csdn.net/zhanxinhang?
**/??
??
#include?<stdio.h>??
#include?<time.h>??
#include?<stdlib.h>??
??
void?shuffle(int?boke[])??//洗牌??
{??
??int?i,r,t;??
??srand((unsigned)time(NULL));?//隨機數種子??
??for(i=0;?i<54;?i++)??
????{??
??????r=(rand()%107)/2;??
??
??????//交換??
??????t=boke[i];??
??????boke[i]=boke[r];??
??????boke[r]=t;??
????}??
}??
??
int?main()??
{??
??int?boke[54],i;??
??for(i=0;i<54;i++)?//初始化紙牌??
????boke[i]=i;??
??
??printf("before?shuffle:\n");??
??for(i=0;?i<54;?i++)????//打印??
??????printf("%d?",boke[i]);??
??
??
??shuffle(boke);?????//洗牌??
??
??
??printf("\nafter?shuffle:\n");??
??for(i=0;?i<54;?i++)???//打印??
??????printf("%d?",boke[i]);??
??
??return?0;??
}??

題：寫一個函數，檢查字符串是否是整數，如果是，返回其整數值。

（或者：怎樣只用4行代碼編寫出一個從字符串到長整形的函數？）

分析：略

實現代碼：

[cpp] view plaincopy

/**?
Author:花心龜?
Blog：http://blog.csdn.net/zhanxinhang?
**/??
??
#include?<stdio.h>??
??
long?convert(const?char?*str)?//?4行代碼？下面我用了四句語句，不知當不當否，權當娛樂^^??
{??
??long?value=0,f=1;?????//f將決定value是否為負數??
??
??if(*str?==?'-')?str++,f=-1;??
??
??for(;*str!='\0'?&&?*str>='0'?&&?*str<='9';?str++)??
????value=value*10+(*str-'0');????
??
??return?*str=='\0'?value*f:0;??//如果不為整數返回??
}??
??
int?main()??
{??
??
??char?str0[]?=?"1234567";??
??printf("%d\n",convert(str0));??
??
??char?str1[]?=?"4.56";??
??printf("%d\n",convert(str1));??
??
??char?str2[]?=?"-1234567";??
??printf("%d\n",convert(str2));??
??
??char?str3[]?=?"-4.56";??
??printf("%d\n",convert(str3));??
????
??return?0;??
}?

題：怎樣從頂部開始逐層打印二叉樹結點數據？請編程。

分析：不用遞歸，定義兩個棧(或數組)，也能方便漂亮地搞定。首先棧1存儲第一層中的節點也就是根節點，然后每次循環，打印棧1中的元素，再將棧1中的節點更新為下一層中的節點。總共循環logn+1次。

實現代碼（以下遺漏了對二叉樹的銷毀操作）：

[cpp] view plaincopy

/**?
Author:花心龜?
Blog：http://blog.csdn.net/zhanxinhang?
**/??
#include?<stdio.h>??
#include?<malloc.h>??
??
typedef?struct?bt_node??
{??
??int?data;??
??struct?bt_node?*rchild;??
??struct?bt_node?*lchild;??
}BinTree,node_t;??
??
BinTree?*myTree;??
??
node_t*?bt_new_node(int?data)??
{??
??node_t*?node?=?(node_t*)malloc(sizeof(node_t));??
??node->rchild?=?NULL;??
??node->lchild?=?NULL;??
??node->data?=?data;??
??
??return?node;??
}??
void?bt_create()??
{??
??//第一層根節點，數字11表示第一層的第一個位置，以下類似??
??myTree?=?bt_new_node(11);??
??
??//創建第二層節點???
??myTree->lchild?=?bt_new_node(21);??
??myTree->rchild?=?bt_new_node(22);???
??
??
??//創建第三層節點??
??myTree->lchild->lchild?=?bt_new_node(31);??
??myTree->lchild->rchild?=?bt_new_node(32);??
??myTree->rchild->lchild?=?bt_new_node(33);??
??myTree->rchild->rchild?=?bt_new_node(34);??
??
??//創建第四層節點??
??myTree->rchild->rchild->rchild?=?bt_new_node(48);??
}??
??
void?print_layer_by_layer()??//逐層打印二叉樹非遞歸算法(主題)??
{??
??node_t*?stack1[100]={0};//棧??
??node_t*?stack2[100]={0};//棧??
??int?T1=0,T2=0;???????????//棧頂下標??
??
??
??stack1[T1++]=myTree;???//根節點入棧??
??while(T1)?//若棧為空則停止循環??
????{??
??????while(T1)??
????{??
??????T1--;??
??????printf("%d?",stack1[T1]->data);?//打印棧頂元素??
??????stack2[T2++]=stack1[T1];????????//將棧元素轉存到棧2中??
????}??
??????printf("\n");??
??
??????//此時棧已存儲了當前行的各元素??
??????//通過棧得到下一行中的節點并更新到棧中??
??????while(T2)????
????{??
??????T2--;??
??????if(stack2[T2]->rchild?!=?NULL)??
????????stack1[T1++]=stack2[T2]->rchild;??
??
??????if(stack2[T2]->lchild?!=?NULL)??
????????stack1[T1++]=stack2[T2]->lchild;??
????}??
????}??
}??
int?main()??
{??
??bt_create();????????????//創建二叉樹??
??print_layer_by_layer();?//逐層打印??
??return?0;??
}??

另：關于此題的其它想法請看3樓我的回復，回復上的編碼步驟為廣度優先遍歷二叉樹算法，不過本人不才哈，不知題目中的意思是一層一層的打印呢，還是按照層的順序從左到右一個一個打印呢（好像也是逐層打印），且不管它，通過對兩種算法比較，上面使用棧的算法功能更強，至少打完一層可以再打一個回行。而使用隊列的廣度優先遍歷二叉樹算法有效率優勢，且代碼簡潔易懂，就是不能打完一層后回行。^_^ 純屬個人觀點，望不吝指教。

題：怎樣把一個鏈表掉個順序（也就是反序，注意鏈表的邊界條件并考慮空鏈表）？

分析：這題比較有意思，我想了個高效的實現。首先定義兩個迭代器 p 和 q，q從第一個節點開始遍歷，p從第二個節點開始遍歷，每次遍歷將頭指針的next指向p的next，然后將p的next 反指向q(此時q是p的前一個節點)，也就是說將每個節點的鏈接方向掉過來，最后尾節點變成了頭節點，頭節點變成了尾節點，時間復雜度為高效的O(n)

圖示：(最后一個N指空節點)

以下便是是我簡潔的實現代碼：

[cpp] view plaincopy

/**?
Author:花心龜?
Blog：http://blog.csdn.net/zhanxinhang?
**/??
???
#include?<stdio.h>??
#include?<malloc.h>??
???
#define?TEST??
???
typedef?struct?list_node??
{??
??int?data;??
??structlist_node?*?next;??
}list_node;??
???
list_node?*head;?//頭結點??
???
void?list_create()??
{??
??int?i;??
??list_node?*p;??
??head?=?(list_node*)malloc(sizeof(list_node));??
??head->data=0;?????//頭結點數據設為??
??head->next?=?NULL;??
???
??p=head;??
??for(i=1;i<6;?i++)?//創建5個結點??
????{??
??????p->next?=?(list_node*)malloc(sizeof(list_node));??
??????p->next->data?=?i;??
??????p->next->next?=?NULL;??
??????p=p->next;??
????}??
???
#ifdef?TEST??
??p=head;??
??while(p!=NULL)???//打印該鏈表??
????{??
??????printf("%d",p->data);??
??????p=p->next;??
????}??
??printf("\n");??
#endif??
}??
???
void?list_reverse()??//使鏈表反序?（主題）??
{??
??printf("^^after?reversing:\n");??
??if(head?==?NULL?||?head->next==NULL)?return?;//如果head為空，則返回??
??list_node?*p,*q;??
??q=head;??
??p=head->next;??
???
??while(p!=NULL)??
????{??
????head->next=p->next;?//將頭指針的next指向p的下一個節點??
????p->next=q;??????????//將p的next值反指向它的前一個節點q??
????q=p;????????????????//q移向p的位置??
????p=head->next;???????//p移向它的下一個位置??
????}??
?????
????head?=?q;??
???
#ifdef?TEST??
??p=head;??
??while(p!=NULL)????????//打印該鏈表??
????{??
??????printf("%d",p->data);??
??????p=p->next;??
????}??
??printf("\n");??
#endif??
???
}??
???
void?list_destroy()??//銷毀函數??
{??
??list_node?*pmove=NULL,*pdel=NULL;??
??pmove=head;??
???
?while(pmove!=head)??
???{??
?????pdel=pmove;??
?????free(pdel);????
?????pmove=pmove->next;??
???}??
}??
int?main()??
{??
??list_create();???//構建單鏈表??
??list_reverse();??//反轉鏈表??
??list_destroy();??//銷毀鏈表??
??return?0;??
}?

題：求隨機數構成的數組中找到長度大于=3的最長的等差數列

輸出等差數列由小到大:?

如果沒有符合條件的就輸出[0,0]

格式：

輸入[1,3,0,5,-1,6]

輸出[-1,1,3,5]

要求時間復雜度，空間復雜度盡量小

分析：基本算法思路（采用動態規劃思想）：首先，只要得到數列的公差和一個首項就可以確定一個等差數列，因此我們要尋找最長等差數列的公差以及首項。其次，為了方便查找公差和首項，我們應該將原數組進行由小到大排序，這樣各兩數之間的公差也是成遞增形勢的，這樣我們就可以避免回溯查找首項。

因此，在搜尋公差及首項的過程中，我們可以分兩三個決策階段：

1、如果公差為0，應該做何處理。

2、如果公差不為0，應該做何處理。

3、如果找到的數列長度是當前最長的做相應的處理

? ? ? 針對以上情況，我們應該選擇一種合適的數據結構——平衡排序樹，stl中的set，map，mutiset，multimap是以紅黑樹結構為形勢的容器，無疑是非常合適的，根據題目情況，可能存在具有相同元素的數組，因此我們選擇multiset，這樣無論我們對數據進行插入排序，查找都是比較高效的，因此總體上是可以滿意的。

? ? ? 最后有幾項時間上的優化不在這里說明，詳情可看代碼。若有不足之處，望能不吝指出！^_^

我的實現代碼：

[cpp] view plaincopy

/**?
Author:花心龜?
Blog：http://blog.csdn.net/zhanxinhang?
**/??
#include?<iostream>??
#include?<ctime>??
#include?<set>??
using?namespace?std;??
??
void?show_longest_seq(const?multiset<int>&?myset)??
{??
????int?maxLength?=?0,?curr_pos?=?0,?curr_d?=?0,?counter=0,i=0;?//一些輔助變量??
????int?d_result,?a1_result;?//存儲最長等差數列的公差以及首項??
????multiset<int>::const_iterator?set_it1,set_it2;??
??
??????
????/*?
?????????(主題)尋找長度最長的等差數列,最壞情況下時間復雜度為O(n^3)?
????*/??
????for(set_it1?=?myset.begin();?set_it1?!=?myset.end();)??
????{??
????????for(set_it2=set_it1,set_it2++;?set_it2?!=?myset.end();)//第二層循環從set_it1所指的下一個元素開始遍歷??
????????{??
????????????curr_d?=?*set_it2?-?*set_it1;?//算得當前公差，注意由于set為自排序容器，從小到大排列，所以curr_d恒為正??
??
????????????if(curr_d?==?0)?//?如果公差為0??
????????????{??
????????????????counter?=?myset.count(*set_it1);??
????????????????set_it2?=?myset.upper_bound(*set_it1);//(優化項)跳過與set_it1相等的元素??
????????????}??
????????????else??
????????????{??
????????????????counter?=?2;?//（優化項）最小長度要求要不小于所以直接從開始累加??
????????????????while(myset.find(*set_it1?+?counter*curr_d)?!=?myset.end())?//計算數列項個數??
????????????????????++counter;??
??
????????????????set_it2?=?myset.upper_bound(*set_it2);//?（優化項）跳過與*set_it2相等的元素??
????????????}??
??
??????????????
????????????if(counter?>?maxLength)??//如果新數列長度大于maxLength??
????????????{??
????????????????d_result?=?curr_d;??
????????????????a1_result?=?*set_it1;??
????????????????????????maxLength?=?counter;??
????????????}??
????????}??
??
????????curr_pos?+=?myset.count(*set_it1);?????//計算第一層循環遍歷到的當前位置??
????????if(myset.size()-curr_pos?<?maxLength)??//?(優化項)如果集合中剩下的元素小于最大數列長度，就退出循環??
????????????break;??
??
????????set_it1?=?myset.upper_bound(*set_it1);?//下一次set_it1?的位置，并跳過相同元素??
????}??
??
??
??
??
????/*?
???????打印最長等差數列?
????*/??
????if(maxLength?<=?2)??
????{??
????????cout<<"longest_seq：[0,0]"<<endl;??
????}??
????else??
????{??
????????cout<<"longest_seq：";??
??????????
????????for(i?=?0;?i<maxLength;??i++)??
????????????cout<<*(myset.find(a1_result?+?i*d_result))<<'?';??
??
????????cout<<endl;??
????}??
}??
//Blog：http://blog.csdn.net/zhanxinhang??
?test?in?main??
int?main()??
{??
????int?a[]={1,3,0,5,-1,6};??
????multiset<int>?myset;??
????myset.insert(a,a+6);??
????show_longest_seq(myset);??
????cout<<endl;??
??
????int?l;??
????srand((unsigned)time(NULL));??
????for(int?j?=?0;?j?<?5;?j++)??
????{??
????????myset.clear();??
????????cout<<"input:[?";??
????????l=rand()%10;??
????????for(int?i?=?0;?i?<?l;?++i)??
????????{??
????????????int?element?=?rand()%10;??
????????????myset.insert(element);??
????????????cout<<element<<'?';??
????????}??
????????cout<<']'<<endl;??
????????show_longest_seq(myset);??
????????cout<<endl;??
????}??
??
??
????return?0;??
}??

附一張測試結果圖：

題：兩個鏈表，一升一降。合并為一個升序鏈表。

分析：（假設升序的鏈表為鏈表1，降序的鏈表為鏈表2，p1，p2分別作為它們的迭代器，還有一個合并鏈表用于存放合并后的數據）

法一、最容易想到的且容易實現的就是使兩個表都變成升序，然后就是經典的合并排序算法的步驟了，步驟是構建p1，p2兩個迭代器，分別用于迭代兩個鏈表，每次遍歷，若p1所指的節點數據大于p2所指的節點數據則將p1所指的節點數據插入到要合并鏈表中去且使p1指向下一個節點，否則將p2將所指的節點數據插入到合并鏈表中去且使p2指向下一個節點，直到p1和p2任意一個指向了NULL為止。最后可能兩個鏈表中尚有剩余的節點，將其逐個插入到合并鏈表中去即可。

法二、使用遞歸方法后序遍歷降序鏈表2，遍歷順序就相當于升序的順序了。在遞歸遍歷鏈表2的過程中，需要處理有以下三件事：(注意順序)

(1) 如果p2的數據小于p1的就插入到合并鏈表中

(2) 如果p2的數據大于p1，那么就對鏈表1循環遍歷，每次將p1中的數據插到合并鏈表中，直到p2不大于p1，且p1不為空

(3) 如果p1為空，就直接將p2插入到合并鏈表中

(這個方法你想到了沒！)

完整實現代碼：

[cpp] view plaincopy

/**?
Author:花心龜?
Blog：http://blog.csdn.net/zhanxinhang?
**/??
???
#include?<stdio.h>??
#include?<malloc.h>??
#include?<stdlib.h>???
??
typedef?struct?list_node??
{??
??int?data;??
??struct?list_node?*?next;??
}list_node;??
???
list_node?*list1=NULL;?//鏈表頭結點??
list_node?*list2=NULL;?//鏈表頭結點??
??
void?list_print(const?list_node?*p)//打印該鏈表函數??
{??
??if(p==NULL)return;??
??while(p!=NULL)?????
????{??
??????printf("%d?",p->data);??
??????p=p->next;??
????}??
??printf("\n");??
}??
??
void?list_create(list_node*?&head,?int?data[],?int?N)??
{??
??if(data?==?NULL)?return;??
??
??int?i;??
??list_node?*p;??
??p?=?(list_node*)malloc(sizeof(list_node));??
??p->data?=?data[0];??
??p->next?=?NULL;??
??head?=?p;???
??for(i=1;i<N;?i++)???
????{??
??????p->next?=?(list_node*)malloc(sizeof(list_node));??
??????p->next->data?=?data[i];??
??????p->next->next?=?NULL;??
??????p=p->next;??
????}??
}??
??
void?list_reverse(list_node*?&head)??//使鏈表反序??
{??
??if(head?==?NULL)?return?;//如果head1為空，則返回??
??list_node?*p,*q;??
??q=head;??
??p=head->next;??
???
??while(p!=NULL)??
????{??
????head->next=p->next;?//將頭指針的next指向p的下一個節點??
????p->next=q;??????????//將p的next值反指向它的前一個節點q??
????q=p;????????????????//q移向p的位置??
????p=head->next;???????//p移向它的下一個位置??
????}??
??
????head?=?q;??
}??
??
void?list_destroy(list_node?*head)??//銷毀函數??
{??
??list_node?*pmove=NULL,*pdel=NULL;??
??pmove=head;??
???
?while(pmove!=head)??
???{??
?????pdel=pmove;??
?????free(pdel);????
?????pmove=pmove->next;??
???}??
}??
??
list_node*?merge_two_list()?//合并鏈表1和鏈表2（法一）??
{??
????list_reverse(list2);????//反轉鏈表使之與鏈表一樣升序排列??
????list_node?*list_merged;??//和并后的鏈表??
????list_node?*p1,*p2,*p0;????????
????list_merged?=?(list_node*)malloc(sizeof(list_node));??
????list_merged->data?=?0;??
????list_merged->next?=?NULL;??
????p0?=?list_merged;??
??
????p1=list1;??
????p2=list2;??
????while(p1!=NULL?&&?p2!=NULL)??
????{??
????????if(p1->data?<?p2->data)??
????????{??
????????????p0->next=(list_node*)malloc(sizeof(list_node));??
????????????p0->next->data=p1->data;??
????????????p0->next->next=NULL;??
????????????p0=p0->next;??
????????????p1=p1->next;??
????????}??
????????else??
????????{??
????????????p0->next=(list_node*)malloc(sizeof(list_node));??
????????????p0->next->data=p2->data;??
????????????p0->next->next=NULL;??
????????????p0=p0->next;??
????????????p2=p2->next;??
????????}??
????}??
????while(p1!=NULL)??
????{??
????????????p0->next=(list_node*)malloc(sizeof(list_node));??
????????????p0->next->data=p1->data;??
????????????p0->next->next=NULL;??
????????????p0=p0->next;??
????????????p1=p1->next;??
????}??
????while(p2!=NULL)??
????{??
????????????p0->next=(list_node*)malloc(sizeof(list_node));??
????????????p0->next->data=p2->data;??
????????????p0->next->next=NULL;??
????????????p0=p0->next;??
????????????p2=p2->next;??
????}??
????return?list_merged;??
}??
??
??
??
list_node*?p0=(list_node*)malloc(sizeof(list_node));??
list_node*?phead=p0;??
list_node*?&p1=list1;?//p1與list1綁定??
list_node*?foreach(list_node*?p2)?//遞歸合并（法二）??
{??
????if(p2==NULL)?return?phead;??
??
????foreach(p2->next);???
??
????if(p1->data?>?p2->data)??
????{??
????????p0->next?=?(list_node*)malloc(sizeof(list_node));??
????????p0->next->data?=?p2->data;??
????????p0->next->next?=?NULL;???
????????p0=p0->next;??
????????return?phead;??
????}??
????while(p1!=NULL?&&?p1->data<=p2->data)??
????{??
????????p0->next?=?(list_node*)malloc(sizeof(list_node));??
????????p0->next->data?=?p1->data;??
????????p0->next->next?=?NULL;???
????????p0=p0->next;??
????????p1?=?p1->next;??
????}??
????if(p1==NULL)??
????{??
????????p0->next?=?(list_node*)malloc(sizeof(list_node));??
????????p0->next->data?=?p2->data;??
????????p0->next->next?=?NULL;???
????????p0=p0->next;??
????}??
??
????return?phead;??
}??
//Blog：http://blog.csdn.net/zhanxinhang??
int?main()??
{??
????int?list1_data[]?=?{1,4,6,8,10};????//鏈表數據升序?可在這里該數據進行測試??
????int?list2_data[]?=?{14,9,3,2};??????//鏈表數據降序??
??
????list_create(list1,list1_data,5);???//構建單鏈表??
????list_create(list2,list2_data,4);???//構建單鏈表??
????list_print(list1);??
????list_print(list2);??
??
????//list_node?*list_merged=merge_two_list();?//合并兩個鏈表??
????//list_print(list_merged->next);??????//打印合并后的鏈表??
??
????list_node?*list_merged2=foreach(list2);????//使用遞歸合并兩個鏈表??
????list_print(list_merged2->next);??
??
????list_destroy(list1);????????????????//銷毀鏈表??
????list_destroy(list2);????????????????//銷毀鏈表??
//??list_destroy(list_merged);??????????//銷毀合并后的鏈表??
????list_destroy(list_merged2);?????????//銷毀合并后的鏈表??
????system("pause");??
????return?0;??
}??

題：如何刪除鏈表的倒數第m的元素？

分析：構建p0,p1兩個迭代器，初始使p0和p1指向頭結點，接著使p1移動到第m+1項，然后指向頭得p0與p1同時前進，當p1指向空節點的時候結束，這時p0所指的位置就是倒數第m個，時間復雜度為O（n）

實現代碼：（為了學習的需要，現在C++朋友采用c++實現，不能滿足c朋友要采用c實現的愿望，此實為c++朋友的遺憾，不過一切重在思想。^_^）

[cpp] view plaincopy

/**?
Author:花心龜?
Blog：http://blog.csdn.net/zhanxinhang?
**/??
#include?<iostream>??
#include?<list>??
using?namespace?std;??
??
class?App??
{??
????list<int>?*plist;???
??
????void?delete_node_at_last(int?m)?//today`s?topic??
????{??
????????list<int>::iterator?p0,?p1;??
????????p0=p1=p2=plist->begin();??
??
????????//使p1移到第m+1項??
????????for(int?i=1;?i<=m;?i++)??
????????????p1++;??
??
????????//p0和p1同時前進，當p1到達終點時p0所指向的就是倒數第m個節點??
????????while(p1!=plist->end())??
????????????p0++,p1++;??
??
????????//刪除節點??
????????plist->erase(p0);??
????}??
??
????void?create_list()??
????{??
????????int?list_data[]={1,2,3,4,5,6,7,8,9};?//鏈表數據??
????????plist?=?new?list<int>(list_data,?list_data+sizeof(list_data)/sizeof(int));??
????}??
??
????void?print_list()??
????{??
????????list<int>::iterator?it;??
????????for(it=plist->begin();?it!=plist->end();?it++)??
????????????cout<<*it<<'?';??
????}??
??
public:??
????//test?in?run?funtion??
????void?run()??
????{??
????????create_list();??
????????delete_node_at_last(3);?//刪除倒數第三個節點??
????????print_list();??
????}??
??
????~App()??
????{??
????????delete?plist;??
????}??
};??
//Blog：http://blog.csdn.net/zhanxinhang??
int?main()??
{??
App?myapp;??
myapp.run();??
system("pause");??
return?0;??
}?

題：1、如何判斷一個字符串是對稱的？如a，aa，aba。? ?

? ? ? ? ?2、如何利用2函數找出一個字符串中的所有對稱子串？

分析：

? ? ? ??且看第一個問題判斷字符串對稱，有以下兩種方法。

? ? ? ? 方法一、使迭代器p1指向頭，p2指向尾。使p1，p2相對而行(—> | <—)，每次比較p1，p2是否相等，直到它們相遇。

? ? ? ??方法二、使p1、p2指向中間的一個元素（如果字符串長度為偶數的話就指向中間兩個相鄰的元素），使它們相向而行(<— |—>)，每次比較p1，p2是否相等。直到它們一個指向頭一個指向尾便結束。??

（可以看出方法1明顯好于方法2）

? ? ? ??現在看第二個問題打印所有的對稱子串，判斷對稱子串的問題我們似乎已經解決，且有以上兩種方法，針對現在的情況是否兩種都合適呢，確切的說不是。如果是方法一，請想象一下，如果要p1，p2一個指向子串的頭一個指向子串的尾，那么至少要兩層循環一層控制p1一層控制p2，還有一層循環用于判斷子串是否對稱，也就是說總共需要三層嵌套循環，時間復雜度指數為3。而如果選擇方法二呢？兩層循環就能實現，不過要適應現在這種情況需要做些修改，就是針對偶數長度的子串進行一次遍歷，再針對奇數長度的子串進行一次遍歷，也就是兩層嵌套循環中內層有兩次循環，時間復雜度指數為2。詳情且看代碼。

實現加測試代碼：

[cpp] view plaincopy

/**?
Author:花心龜?
Blog：http://blog.csdn.net/zhanxinhang?
**/??
??
#include?<iostream>??
#include?<cstdlib>??
#include?<ctime>??
using?namespace?std;??
class?App??
{??
????typedef?string::iterator?Iter_t;??
??
????string?m_str;??
????void?print(Iter_t?p1,?Iter_t?p2)?//打印從p1開始到p2結束的字符??
????{??
????????while(p1<=p2)??
????????{??
????????????cout<<*p1;??
????????????p1++;??
????????}??
????????cout<<"?|?";??
????}??
????bool?isHuiwen1(Iter_t?start,Iter_t?end)?//法1判斷是否為對稱子串??
????{??
????????Iter_t?p1?=?start;??
????????Iter_t?p2?=?end;??
????????int?times?=?(distance(p1,p2)+1)?/?2;?//比較次數??
????????while(times)??
????????{??
????????????if(*p1?!=?*p2)??
????????????????return?false;??
??
????????????p1++;???
????????????p2--;???
????????????times--;??
????????}??
????????return?true;??
????}??
??
????bool?isHuiwen2(Iter_t?mid_it)?//法2判斷是否為對稱子串??
????{??
????????Iter_t?p1,p2;??
????????p1?=?p2?=?mid_it;??
??
????????while(p1>=m_str.begin()?&&?p2?<?m_str.end())???
????????{?????????????
????????????if(*p1?!=?*p2)???
????????????????break;????
????????????print(p1,p2);//打印從p1到p2的字符??
????????????p1--,p2++;??
????????}??
??
????????p1?=?p2?=?mid_it;??
????????p2++;?//使p2向前移動一個位置，此時p1，p2分別指向中間兩個相鄰位置??
????????while(p1>=m_str.begin()?&&?p2?<?m_str.end())????
????????{??
????????????if(*p1?!=?*p2)??
????????????????return?false;??
????????????print(p1,p2);//打印從p1到p2的字符??
????????????p1--,p2++;??
????????}??
????????return?true;??
????}??
??
????void?show_all_substr_of_huiwen1()?//法一打印所有對稱子串??
????{??
????????Iter_t?p2=m_str.end()-1;??
????????Iter_t?p1?=?m_str.begin();??
????????for(;p1!=m_str.end();p1++)??
????????????for(p2=p1;p2!=m_str.end();p2++)??
????????????{??
????????????????if(isHuiwen1(p1,p2))??
????????????????????print(p1,p2);??
????????????}??
????}??
??
????void?show_all_substr_of_huiwen2()??//法二打印所有對稱子串??
????{??
????????Iter_t?it?=?m_str.begin();??
??
????????for(;it!=m_str.end();it++)??
????????{??
????????????isHuiwen2(it);??
????????}??
????}??
??
public:??
??
????void?run()??
????{??
????????m_str="abaaba";??
????????cout<<"測試數據為:abaaba"<<endl;??
????????show_all_substr_of_huiwen1();??
????????cout<<endl;??
????????show_all_substr_of_huiwen2();??
????????cout<<endl;??
??
????????m_str="asdfie";??
????????cout<<"測試數據為:asdfie"<<endl;??
????????show_all_substr_of_huiwen1();??
????????cout<<endl;??
????????show_all_substr_of_huiwen2();??
????????cout<<endl;??
??
????????m_str="aabaa";??
????????cout<<"測試數據為:aabaa"<<endl;??
????????show_all_substr_of_huiwen1();??
????????cout<<endl;??
????????show_all_substr_of_huiwen2();??
????????cout<<endl;??
??
????????//時間比較//??
????????m_str="this?is?a?string?for?testing.?aabaa?alskjdfkljasdjflasdflkajsldkjfsjlakjsdlfjwoekjlakjlsdkjflsajlkdjfowieuoriuq?aaddbb?sldjfalkjsdlfkjasldjflajsldfjalskdjflakjsdlfkjaslkdjflajsdlfkjaslkdjflkajsdlkjflkasjdlfjaklsjdkfljaklsdjfklsajdflkjslkdjflaskjdlfkjalsdjlfkajsldfkjlaksjdfljasldjflaskjdfkasjdflaksjdkfljaskldfjlaksjdfljasldjflaksjdkljfkalsjdlkfjasldjflasjdlfjasldjfklsajdfljaskldfjlsakjdflkasjdfkl?this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.make?-k?make?-k?make?-k?make?-k?make?-k?make?-k?is?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.make?-k?make?-k?make?-k?make?-k?make?-k?make?-k?is?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.make?-k?make?-k?make?-k?make?-k?make?-k?make?-k?is?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.make?-k?make?-k?make?-k?make?-k?make?-k?make?-k?is?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.make?-k?make?-k?make?-k?make?-k?make?-k?make?-k?is?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.make?-k?make?-k?make?-k?make?-k?make?-k?make?-k?is?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.make?-k?make?-k?make?-k?make?-k?make?-k?make?-k?is?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.make?-k?make?-k?make?-k?make?-k?make?-k?make?-k?is?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.make?-k?make?-k?make?-k?make?-k?make?-k?make?-k?is?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.make?-k?make?-k?make?-k?make?-k?make?-k?make?-k?is?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.make?-k?make?-k?make?-k?make?-k?make?-k?make?-k?is?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.this?is?a?string?for?testing.make?-k?make?-k?make?-k?make?-k?make?-k?make?-k?end";??
??
??
????????time_t?start,record1;??
??
??
????????cout<<"show?all?substr?of?huiwen?1:";??
????????system("pause");??
????????start?=?time(NULL);??????
????????show_all_substr_of_huiwen1();??
????????record1?=?time(NULL);??
??
????????cout<<endl;??
????????cout<<"time:"<<record1-start;??
????????cout<<endl;??
??
??
????????cout<<"show?all?substr?of?huiwen?2:";??
????????system("pause");??
????????start?=?time(NULL);??
????????show_all_substr_of_huiwen2();??
????????record1?=?time(NULL);??
??
????????cout<<endl;??
????????cout<<"time:"<<record1-start;??
????????cout<<endl;??
??
????????cout<<"(可以看到打印速度明顯快于上一次)";??
????}??
};??
??
int?main()??
{??
????App?myapp;??
????myapp.run();??
??
????system("pause");??
????return?0;??
}??

測試結果：

各測試數據下的一二行為打印出來的所有對稱字串。

按下任意鍵后：

以上是使用方法1打印出來的結果。

按下任意鍵后：

以上便是用方法2打印出來的結果。

題：假設你有一個用1001個整數組成的數組，這些整數是任意排列的，但是你知道所有的整數都在1到1000(包括1000)之間。此外，除一個數字出現兩次外，其他所有數字只出現一次。假設你只能對這個數組做一次處理，用一種算法找出重復的那個數字。如果你在運算中使用了輔助的存儲方式，那么你能找到不用這種方式的算法嗎?

分析：

方法一、若使用輔助的存儲方式，該選擇何種存儲方式呢？可使用hash的存儲方式，以1到1000作為hash表的索引，遍歷原數組，統計各數字出現的個數并存儲到以該數字為索引值的hash表中，若某個hash[x]的值為2則退出循環，x就是重復出現兩次的數字。時間復雜度最壞是O(n)。優點：高效率，缺點：消耗的內存空間過大。代碼如下：

[cpp] view plaincopy

int?fun1(const?int?a[])??
{??
??int?hash[1002]={0};??
??int?x=0;??
??for(int?i?=?0;?i<1001;?i++)??
????{??
??????if((++hash[a[i]])?==?2)??
????????{??
??????????x?=?a[i];??
??????????break;??
????????}??
????}??
??return?x;??
}??

方法二、若不使用輔助的存儲方式呢？已知1001個整數組成的數組只有一個數字出現了兩次，且整數都在1到1000之間，所以可推得數組里面包含了1到1000之間的所有數字為[1,2,3……1000]和一個出現兩次的x為1到1000中的任一個數字。這樣就可以計算原數組里的所有數字之和S1和等差數列[1,2,3……1000]的和S2，再計算S1與S2之差，該差就是原數組中出現兩次的數字x。時間復雜度是固定的O(n)。優缺點：內存空間消耗幾乎沒有，但是效率要輸于使用hash表的存儲方式。代碼如下：

[cpp] view plaincopy