第六十一題：找出整型數組中兩個只出現了一次的數(其余都出現了兩遍)

思路：凡是涉及到出現了兩次，出現了一次的都用XOR。把所有的數都XOR一遍得到一個數tmp，這個數就是要得到的兩個數的XOR。tmp肯定不為0，因為這要得的兩個數一定不相等。則使用tmp為1的位可以把原數組分為兩組。因為這兩個數的這一位一定不同（1^0=1），所以這兩個數一定各自落在一個組里，而出現了兩次的同一個數也會在同一組里。重新對各個組XOR一編即可找到這個組中唯一出現一次的數了。整個過程遍歷了兩次數組，復雜度O(2n)=O(n) void twoSingleNum(const int *a,int cnt){int tmp=0;for(int i=0;i<cnt;++i) tmp^=a[i];//比較短的時候放后面int mark=1;while( (tmp&mark)==0)mark<<=1;// mark<<1 has no effect on markint num1=0,num2=0;for(int i=0;i<cnt;++i)(a[i]&mark)==0 ? num1^=a[i] : num2^=a[i];//must have (), &'s priority is very low.cout<<num1<<" "<<num2<<endl; }

第六十三題：刪除字符串中的特定字符

思路：定義兩個指針slow和fast，如果fast不是要刪的字符則*slow=*fast,++fast,++slow;否則只++fast跳過要刪的字符。相當于把字符串復制一遍，只不過跳過了要刪的字符。復雜度O(n) void delChars(char s[],const char *chars){int hash[256];memset(hash,0,sizeof(int)*256);while(*chars!='\0'){hash[int(*chars)]=1;chars++;}char *pFast=s,*pSlow=s;while(*pFast!='\0'){if(hash[int(*pFast)]==0){*pSlow=*pFast;pSlow++;}pFast++;//相當于把不刪的復制到前面的slow，刪的就跳過 }*pSlow='\0'; }

第六十四題：尋找丑數(從小到大打印1500個丑數)

丑數是因式全由 2 3 5組成的數。如果逐個因式分解效率爆低。使用動態規劃的思想，后一個丑數肯定是前面丑數的min(2倍 3倍 5倍)且剛好大于前面一個丑數。可以把已經算好的丑數記錄在數組中。然后找到前面某個丑數的2倍剛好大于最后一個丑數的，再找3倍、5倍。這三個數的最小者就是下一個丑數。可用三個指針來從前往后尋找。 void generateUglyNum(int n){int buf[n+10];buf[0]=1;buf[1]=2;buf[2]=3;buf[3]=4;buf[4]=5;int *p2=buf,*p3=buf,*p5=buf;for(int i=5;i<n;++i){while(*p2*2<=buf[i-1])p2++;unsigned int c1=*p2*2;while(*p3*3<=buf[i-1])*p3++;unsigned int c2=*p3*3;while(*p5*5<=buf[i-1])*p5++;unsigned int c3=*p5*5;if(c1<=c2 && c1<=c3)buf[i]=c1;if(c2<=c1 && c2<=c3)buf[i]=c2;if(c3<=c1 && c3<=c2)buf[i]=c3;cout<<i+1<<":"<<buf[i]<<endl;}

第六十五題：輸出1到最大的N位數

void helper(int n){int tmp=0;for(int i=0;i<n;++i){tmp+=9;if(i!=n-1)tmp*=10;}for(int i=1;i<=tmp;++i){cout<<i<<" ";}cout<<endl; }

第六十六題：利用遞歸翻轉一個棧

利用遞歸可以把棧元素一個一個拿出來，進行某種操作后一個一個放回去。利用這種規律可以先把棧元素拿出來，放回去的時候每個元素都沉到最底。如何沉到最底也是利用遞歸。 template <class T> void reverse_stack_recursive(stack<T> &s){if(!s.empty()){T tmp=s.top();s.pop();reverse_stack_recursive(s);//從頂到底一個一個拿開putToButtom(s,tmp);//從棧最低的元素一個一個放回，但是每次都返回棧底 } }template <class T>//這是一種棧的常用操作，先拿出來，再放回去 void putToButtom(stack<T> &s,T &tmp){if(s.empty()){s.push(tmp);//拿到沒有了，就放這個目標元素到棧底return;}T o=s.top();//將棧里的元素一個一個拿開 s.pop();putToButtom(s,tmp);//直到棧為空，放進目標元素s.push(o);//再一個一個放回去 }

第六十七題：撲克牌順序

一開始用了一個麻煩的方法，就是想挑出所有不合法的情況(盡量避免這種思路，因為不合法的情況會隨著思考的深入變得越來越多)，最后就是合法的了。但不合法情況的組合比較多，容易漏。 好的方法是用量值來統籌所有情況，把王當做一種可以填充gap的東西，一個王填一個gap。如果可以用的王用完了，或者有兩張牌一樣的情況就是不合法了。 int has_gap(int a[],int l,int allowGaps){for(int i=1;i<5-l;++i){//不同王數for的長度不一，這里用一個參數來傳遞for的長度就可以實現代碼重用，不用寫3個for了。if(a[i]-a[i-1]==0)return 0;allowGaps-=a[i]-a[i-1]-1;}if(allowGaps<0)return 0;return 1; }int is_sequence_good(int a[]){//14 is the kingsort(a,a+5);if(a[3]==14 && a[4]==14)return has_gap(a,2,2);//double kingselse if(a[4]==14)return has_gap(a,1,1);else return has_gap(a,0,0); }

第六十七題：打印出n粒骰子的點數和的出現概率

思路：每種搭配出現的概率都是1/6^n，因此問題轉移到每種和存在多少種搭配？如3+3=2+4=1+5，兩粒骰子的時候和6時就5種情況(2,4 1,5可調轉) 使用動態規劃非常簡單，關鍵是公式:f(s,n)=f(s-1,n-1)+f(s-2,n-1)+f(s-3,n-1)+f(s-4,n-1)+f(s-5,n-1)+f(s-6,n-1)，s為n粒骰子的和。 解釋：n粒骰子和為s出現的次數，等于n-1粒時，s分別減少1到6時的次數之和。就是概率上的全概率的意思。 void showDicePro(int n){#define DICE_NUM 6 //為以后擴展做準備，注意擴展性可以給面試官好印象int p[n][DICE_NUM*n+1];memset(p,0,sizeof(int)*(DICE_NUM*n+1)*n);for(int j=1;j<=DICE_NUM;++j) p[0][j]=1;//初始化1顆骰子的情況for(int i=1;i<n;++i)for(int j=1;j<=DICE_NUM*n;++j)for(int k=j-DICE_NUM;k<j;++k)if(k>=0) p[i][j]+=p[i-1][k];//n粒的情況DP n-1的for(int i=1;i<=DICE_NUM*n;++i) cout<<p[n-1][i]<<" ";cout<<endl; }

第六十八題：把數組組成最小的數

思路1：建立一個比較函數判斷兩個數應該放前放后。從最高位開始比較，如果某一位比較小則放前。如果長度不等，多出來的位與前面的位依次對比，詳細看代碼。 思路2：此法簡單。借用字符串比較兩個數的前后順序。如"ab">"ba"的話，則a放b前，即a<b。由于ab拼接的兩個字符串長度一定相等，直接使用string的<即可判斷。 PS：1、sort的比較函數的意思就是第一個參數放第二個參數前面的話就true。2、sprintf的用法：可以先用char[]來格式化字符串，然后直接用string的構造函數string(char*)來轉化(string沒有format函數)。 bool fronter(int a,int b){//思路1vector<int> va,vb,tmp;while(a!=0){tmp.push_back(a%10);a/=10;}while(!tmp.empty()){va.push_back(tmp.back());tmp.pop_back();}while(b!=0){tmp.push_back(b%10);b/=10;}while(!tmp.empty()){vb.push_back(tmp.back());tmp.pop_back();}//比較長度int lena=va.size();int lenb=vb.size();int i=0,j=0;while(i<lena || j<lenb){if(va[i]<vb[j] && i<lena && j<lenb)return true;if(va[i]>vb[j] && i<lena && j<lenb)return false;if(i==lena && j==lenb)return false;if(i==lena && j!=lenb){//前面的放前面就是trueif(vb[j]>vb[j-lena])return true;//短在前else if(vb[j]<vb[j-lena]) return false;}//多出來的位與第一位比if(i!=lena && j==lenb){if(va[i]>va[i-lenb])return false;//短在前else if(va[i]<va[i-lenb])return true;}if(i<lena)++i;if(j<lenb)++j;}return true; }bool helper(int a,int b){//思路2char sa[50],sb[50];sprintf(sa,"%d",a);sprintf(sb,"%d",b);string stra(sa),strb(sb);return stra+strb<strb+stra; }void final(int *num,int n){vector<int> a;for(int i=0;i<n;++i)a.push_back(num[i]);sort(a.begin(),a.end(),helper);for(unsigned int i=0;i<a.size();++i){cout<<a[i];}cout<<endl; }

第六十九題：旋轉數組中的最小數

思路1：直接從左往右掃，碰到右比左小的就是最小數。沒有的話第一個就是最小數。 思路2：參照二分查找。如果有旋轉，最小數一定在旋轉那。 void helper(int *a,int n){if(n==2){if(a[0]>a[1])cout<<a[1]<<endl;else cout<<a[0]<<endl;return;}int mid=n/2;if(a[0]>a[mid])helper(a,mid+1);//有旋轉else if(a[mid]>a[n-1])helper(a+mid,n-mid);//有旋轉else if(a[0]<a[mid])helper(a,mid+1);//沒旋轉else helper(a+mid,n-mid);//沒旋轉 }

?

轉載于:https://www.cnblogs.com/iyjhabc/archive/2013/03/28/2986020.html

總結

以上是生活随笔為你收集整理的[微软面试100题]61-70的全部內容，希望文章能夠幫你解決所遇到的問題。

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