1.把二元查找樹轉(zhuǎn)變成排序的雙向鏈表
題目：
輸入一棵二元查找樹曹洽，將該二元查找樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。
要求不能創(chuàng)建任何新的結(jié)點(diǎn)双泪，只調(diào)整指針的指向坞古。
10
/ \
6 14
/ \ / \
4 8 12 16
轉(zhuǎn)換成雙向鏈表
4=6=8=10=12=14=16。
首先我們定義的二元查找樹 節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
2.設(shè)計(jì)包含min函數(shù)的棧酱鸭。
定義棧的數(shù)據(jù)結(jié)構(gòu)吗垮，要求添加一個(gè)min函數(shù)，能夠得到棧的最小元素凹髓。
要求函數(shù)min烁登、push以及pop的時(shí)間復(fù)雜度都是O(1)。
3.求子數(shù)組的最大和
題目：
輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)饵沧。
數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組锨络，每個(gè)子數(shù)組都有一個(gè)和。
求所有子數(shù)組的和的最大值狼牺。要求時(shí)間復(fù)雜度為O(n)羡儿。
例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數(shù)組為3, 10, -4, 7, 2是钥，
因此輸出為該子數(shù)組的和18掠归。
4.在二元樹中找出和為某一值的所有路徑
題目：輸入一個(gè)整數(shù)和一棵二元樹。
從樹的根結(jié)點(diǎn)開始往下訪問(wèn)一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的所有結(jié)點(diǎn)形成一條路徑悄泥。
打印出和與輸入整數(shù)相等的所有路徑虏冻。
例如 輸入整數(shù)22和如下二元樹
10
/ \
5 12
/ \
4 7
則打印出兩條路徑：10, 12和10, 5, 7。
二元樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義為：
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
5.查找最小的k個(gè)元素(采用小根堆 和 大根堆 來(lái)解決)
題目：輸入n個(gè)整數(shù)弹囚，輸出其中最小的k個(gè)厨相。
例如輸入1，2鸥鹉，3领铐，4，5宋舷，6绪撵，7和8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字為1祝蝠，2音诈，3和4。
public static void FindKMin(int[] sort, int k)
{
int[] heap = sort;
int rootIndex = k / 2 - 1;
while (rootIndex >= 0)
{
reheap(heap, rootIndex, k - 1);
rootIndex--;
}
for (int i = k, len=heap.Length; i < len; i++)
{
if (heap[i]<heap[0])
{
heap[0] = heap[i];
reheap(heap, 0, k - 1);
}
}
Console.WriteLine("The {0} min element =",k);
for (int i = 0; i < k; i++)
{
Console.Write(heap[i] + " ");
}
}
private static void reheap(int[] heap, int rootIndex, int lastInddex)
{
int orphan = heap[rootIndex];
bool done = false;
int leftIndex = rootIndex * 2 + 1;
while (!done && leftIndex <= lastInddex)
{
int largerIndex = leftIndex;
if (leftIndex+1 <= lastInddex)
{
int rightIndex = leftIndex + 1;
if (heap[rightIndex] > heap[leftIndex])
{
largerIndex = rightIndex;
}
}
if (orphan < heap[largerIndex])
{
heap[rootIndex] = heap[largerIndex];
rootIndex = largerIndex;
leftIndex = rootIndex * 2 + 1;
}
else
{
done = true;
}
}
heap[rootIndex] = orphan;
}
第6題
騰訊面試題：
給你10分鐘時(shí)間绎狭，根據(jù)上排給出十個(gè)數(shù)细溅，在其下排填出對(duì)應(yīng)的十個(gè)數(shù)
要求下排每個(gè)數(shù)都是先前上排那十個(gè)數(shù)在下排出現(xiàn)的次數(shù)。
上排的十個(gè)數(shù)如下：
【0儡嘶，1喇聊，2，3蹦狂，4誓篱，5，6凯楔，7窜骄，8，9】
舉一個(gè)例子摆屯，
數(shù)值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0在下排出現(xiàn)了6次邻遏，1在下排出現(xiàn)了2次，
2在下排出現(xiàn)了1次，3在下排出現(xiàn)了0次....
以此類推..
完整代碼如下:
include<iostream>
using namespace std;
const int Len = 4;
bool isLegal(int* A,int n)
{
for(int i=0;i<n;++i)
{
int count=0;
for(int j=0;j<n;++j)
{
if(i==A[j])
++count;
}
if(A[i] != count)
return false;
}
return true;
}
void ArrayF(int* A,int n,int Sum)
{
if(!A || n < 1 || Sum < 1)//處理異常,A==NULL,n <=0,Sum<1
return ;
if( n==1 )
{
A[0]=Sum;
if(isLegal(A,Len))
{
for(int i=0;i<Len;++i)
cout<<A[i]<<' ';
cout<<endl;
}
}
else
{
for(int i=0;i<=Sum;++i)
{
A[n-1]=i;
ArrayF(A,n-1,Sum-i);
}
}
}
void main()
{
int A[20]={0};
ArrayF(A,Len,Len);
}
第7題
微軟亞院之編程判斷倆個(gè)鏈表是否相交
給出倆個(gè)單向鏈表的頭指針准验，比如h1赎线，h2，判斷這倆個(gè)鏈表是否相交糊饱。
為了簡(jiǎn)化問(wèn)題垂寥，我們假設(shè)倆個(gè)鏈表均不帶環(huán)。
問(wèn)題擴(kuò)展：
1.如果鏈表可能有環(huán)列?
2.如果需要求出倆個(gè)鏈表相交的第一個(gè)節(jié)點(diǎn)列?
第8題
1.有兩個(gè)房間济似，一間房里有三盞燈，另一間房有控制著三盞燈的三個(gè)開關(guān)盏缤，
這兩個(gè)房間是 分割開的砰蠢，從一間里不能看到另一間的情況。
現(xiàn)在要求受訓(xùn)者分別進(jìn)這兩房間一次唉铜，然后判斷出這三盞燈分別是由哪個(gè)開關(guān)控制的台舱。
有什么辦法呢？
（先亮A燈一段時(shí)間,再關(guān)閉A燈亮B燈,進(jìn)入有燈的房間,得出結(jié)論:亮著的是B燈,暗著的兩盞燈中,熱的燈是A燈,剩下的是C燈）
2.你讓一些人為你工作了七天潭流，你要用一根金條作為報(bào)酬竞惋。金條被分成七小塊，每天給出一塊灰嫉。
如果你只能將金條切割兩次拆宛，你怎樣分給這些工人?
3. ★用一種算法來(lái)顛倒一個(gè)鏈接表的順序。現(xiàn)在在不用遞歸式的情況下做一遍讼撒。
a1 -> a2 ->a3
第一對(duì)：(NULL,a1) ——開始
第二對(duì)：(a1,a2)
第三對(duì)：(a2,a3)
第四對(duì)：(a3,NULL) ——完畢
//非遞歸方式翻轉(zhuǎn)
void Reverse_non_recursive(){
Node *pair1 = NULL;
Node *pair2 = head;
while (pair2 != NULL){
Node *temp = pair2->next;
pair2->next = pair1;
pair1 = pair2;
pair2 = temp;
}
head = pair1;
}
★用一種算法在一個(gè)循環(huán)的鏈接表里插入一個(gè)節(jié)點(diǎn)浑厚，但不得穿越鏈接表。
★用一種算法整理一個(gè)數(shù)組根盒。你為什么選擇這種方法?
★用一種算法使通用字符串相匹配钳幅。
★顛倒一個(gè)字符串。優(yōu)化速度炎滞。優(yōu)化空間敢艰。
★顛倒一個(gè)句子中的詞的順序，比如將“我叫克麗絲”轉(zhuǎn)換為“克麗絲叫我”册赛，
實(shí)現(xiàn)速度最快钠导，移動(dòng)最少。
★找到一個(gè)子字符串森瘪。優(yōu)化速度辈双。優(yōu)化空間。
★比較兩個(gè)字符串柜砾，用O(n)時(shí)間和恒量空間湃望。
★假設(shè)你有一個(gè)用1001個(gè)整數(shù)組成的數(shù)組，這些整數(shù)是任意排列的，但是你知道所有的整數(shù)都在1到1000(包括1000)之間证芭。此外瞳浦，除一個(gè)數(shù)字出現(xiàn) 兩次外，其他所有數(shù)字只出現(xiàn)一次废士。假設(shè)你只能對(duì)這個(gè)數(shù)組做一次處理叫潦，用一種算法找出重復(fù)的那個(gè)數(shù)字。如果你在運(yùn)算中使用了輔助的存儲(chǔ)方式官硝，那么你能找到不 用這種方式的算法嗎?
★不用乘法或加法增加8倍〈Ｈ铮現(xiàn)在用同樣的方法增加7倍。
第9題
判斷整數(shù)序列是不是二元查找樹的后序遍歷結(jié)果
(思路是序列最后一個(gè)必是根節(jié)點(diǎn)氢架，從前往后遍歷傻咖，比根節(jié)點(diǎn)小的都是其左子樹，并且位于序列的左半部分岖研，比其大的為其右子樹卿操，應(yīng)該位于其右半部分。)
include <iostream>
using namespace std;
void test(const int data[],int start,int node,bool &flag){
if(flag&&start<node){ // 判斷條件孙援，注意start<node
int left=start;
while(data[node]>data[left]){ //取得其左子樹
left++;
}
for(int j=left;j<node;j++){ //判斷是否為其右子樹
if(data[j]<data[node]) {flag=false; return;} //若
}
test(data,0,left-1,flag); //遞歸
test(data,left,node-1,flag);
}
}
int main(void){
bool flag=true;
int a[]={5,7,6,9,11,10,8};
test(a,0,6,flag);
if(flag) cout<<"yes"<<endl;
else cout<<"no"<<endl;
int b[]={7,4,6,5};
test(b,0,3,flag);
if(flag) cout<<"yes"<<endl;
else cout<<"no"<<endl;
system("pause");
return 0;
}
第10題
翻轉(zhuǎn)句子中單詞的順序害淤。
題目：輸入一個(gè)英文句子，翻轉(zhuǎn)句子中單詞的順序拓售，但單詞內(nèi)字符的順序不變窥摄。
句子中單詞以空格符隔開。為簡(jiǎn)單起見础淤，標(biāo)點(diǎn)符號(hào)和普通字母一樣處理溪王。
例如輸入“I am a student.”，則輸出“student. a am I”值骇。
第11題
求二叉樹中節(jié)點(diǎn)的最大距離...
如果我們把二叉樹看成一個(gè)圖莹菱，父子節(jié)點(diǎn)之間的連線看成是雙向的，
我們姑且定義"距離"為兩節(jié)點(diǎn)之間邊的個(gè)數(shù)吱瘩。
寫一個(gè)程序道伟，
求一棵二叉樹中相距最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)之間的距離。
第12題
題目：求1+2+…+n使碾，
要求不能使用乘除法蜜徽、for、while票摇、if拘鞋、else、switch矢门、case等關(guān)鍵字以及條件判斷語(yǔ)句（A?B:C）盆色。
第13題：
題目：輸入一個(gè)單向鏈表灰蛙，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。鏈表的倒數(shù)第0個(gè)結(jié)點(diǎn)為鏈表的尾指針隔躲。
鏈表結(jié)點(diǎn)定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
第14題：
題目：輸入一個(gè)已經(jīng)按升序排序過(guò)的數(shù)組和一個(gè)數(shù)字摩梧，
在數(shù)組中查找兩個(gè)數(shù)，使得它們的和正好是輸入的那個(gè)數(shù)字宣旱。
要求時(shí)間復(fù)雜度是O(n)仅父。如果有多對(duì)數(shù)字的和等于輸入的數(shù)字，輸出任意一對(duì)即可浑吟。
例如輸入數(shù)組1笙纤、2、4组力、7省容、11、15和數(shù)字15忿项。由于4+11=15蓉冈，因此輸出4和11城舞。
第15題：
題目：輸入一顆二元查找樹轩触，將該樹轉(zhuǎn)換為它的鏡像，
即在轉(zhuǎn)換后的二元查找樹中家夺，左子樹的結(jié)點(diǎn)都大于右子樹的結(jié)點(diǎn)脱柱。
用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。
例如輸入：
8
/ \
6 10
/\ /\
5 7 9 11
輸出：
8
/ \
10 6
/\ /\
11 9 7 5
定義二元查找樹的結(jié)點(diǎn)為：
struct BSTreeNode // a node in the binary search tree (BST)
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
第16題：
題目（微軟）：
輸入一顆二元樹拉馋，從上往下按層打印樹的每個(gè)結(jié)點(diǎn)榨为，同一層中按照從左往右的順序打印。
例如輸入
8
/ \
6 10
/ \ / \
5 7 9 11
輸出8 6 10 5 7 9 11煌茴。
第17題：
題目：在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符随闺。如輸入abaccdeff，則輸出b蔓腐。
分析：這道題是2006年google的一道筆試題矩乐。
第18題：
題目：n個(gè)數(shù)字（0,1,…,n-1）形成一個(gè)圓圈，從數(shù)字0開始回论，
每次從這個(gè)圓圈中刪除第m個(gè)數(shù)字（第一個(gè)為當(dāng)前數(shù)字本身散罕，第二個(gè)為當(dāng)前數(shù)字的下一個(gè)數(shù)字）。
當(dāng)一個(gè)數(shù)字刪除后傀蓉，從被刪除數(shù)字的下一個(gè)繼續(xù)刪除第m個(gè)數(shù)字欧漱。
求出在這個(gè)圓圈中剩下的最后一個(gè)數(shù)字。
July：我想葬燎，這個(gè)題目误甚，不少人已經(jīng) 見識(shí)過(guò)了缚甩。
第19題：
題目：定義Fibonacci數(shù)列如下：
/ 0 n=0
f(n)= 1 n=1
\ f(n-1)+f(n-2) n=2
輸入n，用最快的方法求該數(shù)列的第n項(xiàng)靶草。
分析：在很多C語(yǔ)言教科書中講到遞歸函數(shù)的時(shí)候蹄胰，都會(huì)用Fibonacci作為例子。
因此很多程序員對(duì)這道題的遞歸解法非常熟悉奕翔，但....呵呵裕寨，你知道的。派继。
第20題：
題目：輸入一個(gè)表示整數(shù)的字符串宾袜，把該字符串轉(zhuǎn)換成整數(shù)并輸出。
例如輸入字符串"345"驾窟，則輸出整數(shù)345庆猫。
第21題
2010年中興面試題
編程求解：
輸入兩個(gè)整數(shù) n 和 m，從數(shù)列1绅络，2月培，3.......n 中 隨意取幾個(gè)數(shù),
使其和等于 m ,要求將其中所有的可能組合列出來(lái).
第22題：
有4張紅色的牌和4張藍(lán)色的牌，主持人先拿任意兩張恩急，再分別在A杉畜、B、C三人額頭上貼任意兩張牌衷恭，
A此叠、B、C三人都可以看見其余兩人額頭上的牌随珠，看完后讓他們猜自己額頭上是什么顏色的牌灭袁，
A說(shuō)不知道，B說(shuō)不知道窗看，C說(shuō)不知道茸歧，然后A說(shuō)知道了。
請(qǐng)教如何推理显沈，A是怎么知道的软瞎。
如果用程序，又怎么實(shí)現(xiàn)呢构罗？
第23題：
用最簡(jiǎn)單铜涉，最快速的方法計(jì)算出下面這個(gè)圓形是否和正方形相交。"
3D坐標(biāo)系 原點(diǎn)(0.0,0.0,0.0)
圓形:
半徑r = 3.0
圓心o = (., 0.0, .)
正方形:
4個(gè)角坐標(biāo);
1:(., 0.0, .)
2:(., 0.0, .)
3:(., 0.0, .)
4:(., 0.0, .)
第24題：
鏈表操作遂唧，
（1）.單鏈表就地逆置芙代，
（2）合并鏈表
第25題：
寫一個(gè)函數(shù),它的原形是int continumax(char *outputstr,char *intputstr)
功能：
在字符串中找出連續(xù)最長(zhǎng)的數(shù)字串，并把這個(gè)串的長(zhǎng)度返回盖彭，
并把這個(gè)最長(zhǎng)數(shù)字串付給其中一個(gè)函數(shù)參數(shù)outputstr所指內(nèi)存纹烹。
例如："abcd12345ed125ss123456789"的首地址傳給intputstr后页滚，函數(shù)將返回9，
outputstr所指的值為123456789
26.左旋轉(zhuǎn)字符串
題目：
定義字符串的左旋轉(zhuǎn)操作：把字符串前面的若干個(gè)字符移動(dòng)到字符串的尾部铺呵。
如把字符串a(chǎn)bcdef左旋轉(zhuǎn)2位得到字符串cdefab裹驰。請(qǐng)實(shí)現(xiàn)字符串左旋轉(zhuǎn)的函數(shù)。
要求時(shí)間對(duì)長(zhǎng)度為n的字符串操作的復(fù)雜度為O(n)片挂，輔助內(nèi)存為O(1)幻林。
27.跳臺(tái)階問(wèn)題(其實(shí)這是斐波拉茨公式)
題目：一個(gè)臺(tái)階總共有n級(jí)，如果一次可以跳1級(jí)音念，也可以跳2級(jí)沪饺。
求總共有多少總跳法，并分析算法的時(shí)間復(fù)雜度闷愤。
/----------------------------
Copyright by yuucyf. 2011.08.16
-----------------------------/
include "stdafx.h"
include <iostream>
using namespace std;
int JumpStep(int n)
{
if (n <= 0) return 0;
if (n == 1 || n == 2) return n;
return (JumpStep(n-1) + JumpStep(n-2));
}
int _tmain(int argc, _TCHAR* argv[])
{
int nStep = 0;
cout << "請(qǐng)輸入臺(tái)階數(shù)：";
cin >> nStep;
cout << "臺(tái)階數(shù)為" << nStep << ",那么總共有" << JumpStep(nStep) << "種跳法." << endl;
return 0;
}
這道題最近經(jīng)常出現(xiàn)整葡，包括MicroStrategy等比較重視算法的公司
都曾先后選用過(guò)個(gè)這道題作為面試題或者筆試題。
28.整數(shù)的二進(jìn)制表示中1的個(gè)數(shù)
題目：輸入一個(gè)整數(shù)讥脐，求該整數(shù)的二進(jìn)制表達(dá)中有多少個(gè)1遭居。
例如輸入10，由于其二進(jìn)制表示為1010旬渠，有兩個(gè)1俱萍，因此輸出2。
hamming_weight
int calculate_one(int n)
{
n = (n&0x55555555) + ((n>>1)&0x55555555);
n = (n&0x33333333) + ((n>>2)&0x33333333);
n = (n&0x0f0f0f0f) + ((n>>4)&0x0f0f0f0f);
n = (n&0x00ff00ff) + ((n>>8)&0x00ff00ff);
n = (n&0x0000ffff) + ((n>>16)&0x0000ffff);
return n;
}
方法二
int calculate_one(int n)
{
int count=0;
while(n != 0){
n &= n-1;
count ++;
}
return count;
}
29.棧的push坟漱、pop序列
題目：輸入兩個(gè)整數(shù)序列鼠次。其中一個(gè)序列表示棧的push順序更哄，
判斷另一個(gè)序列有沒有可能是對(duì)應(yīng)的pop順序芋齿。
為了簡(jiǎn)單起見，我們假設(shè)push序列的任意兩個(gè)整數(shù)都是不相等的成翩。
比如輸入的push序列是1觅捆、2、3麻敌、4栅炒、5，那么4术羔、5赢赊、3、2级历、1就有可能是一個(gè)pop系列释移。
因?yàn)榭梢杂腥缦碌膒ush和pop序列：
push 1，push 2寥殖，push 3玩讳，push 4涩蜘，pop，push 5熏纯，pop同诫，pop，pop樟澜，pop误窖，
這樣得到的pop序列就是4、5秩贰、3贩猎、2、1萍膛。
但序列4吭服、3、5蝗罗、1艇棕、2就不可能是push序列1、2串塑、3沼琉、4、5的pop序列桩匪。
思路是：讓輸入的push序列與pop序列的第一位相比較打瘪，如不同，則進(jìn)棧傻昙，若相同闺骚，則跳過(guò)，同時(shí)pop序列的元素也向后移動(dòng)一位妆档。
include <iostream>
include <stack>
using namespace std;
bool isPopSerial(int push[], int pop[], int n)//我自己寫的一種方法僻爽，注意函數(shù)名
{
int i=0,j=0;
stack<int> mystack;
while(i < n)//只要沒有全部將push數(shù)組push到棧中
{
mystack.push(push[i]);
i++;
while(!mystack.empty() && mystack.top() == pop[j])
{
mystack.pop();
j++;
}
}
if( mystack.empty() && j==n)//最后是pop序列的唯一條件：棧變空了，且pop序列游標(biāo)到了最后
return true;
return false;//除此之外都不是pop序列
}
30.在從1到n的正數(shù)中1出現(xiàn)的次數(shù)
題目：輸入一個(gè)整數(shù)n贾惦，求從1到n這n個(gè)整數(shù)的十進(jìn)制表示中1出現(xiàn)的次數(shù)胸梆。
include<iostream>
2 #include<string>
3 using namespace std;
4
5 int NumbersOf1sFrom1ToN(unsigned int n)
6 {
7 int currentN = n;
8
9 //計(jì)數(shù)器
10 int cnt = 0;
11
12 //商，計(jì)算該數(shù)字包含多少個(gè)10须板，100碰镜，1000等
13 int quotient = 0;
14
15 //余數(shù)，計(jì)算除去“整”的包含习瑰，剩下的數(shù)字包含的1的個(gè)數(shù)
16 int remainder = 0;
17
18 //每一輪循環(huán)中的權(quán)重绪颖，分別記錄10，100杰刽，1000中包含多少個(gè)位1菠发，十位1王滤，百位1；
19 int mult = 1;
20
21 while(currentN)
22 {
23 quotient = currentN / 10;
24 remainder = currentN % 10;
25
26 //包含多少個(gè)10滓鸠，100雁乡，1000，乘以對(duì)應(yīng)的數(shù)量的個(gè)位1糜俗，十位1踱稍，百位1
27 cnt += quotient * mult;
28
29 //余數(shù)大于1，多加一個(gè)該輪下的權(quán)重
30 if(remainder > 1)
31 {
32 cnt += mult;
33 }
34 //余數(shù)等于1
35 else if(remainder == 1)
36 {
37 cnt += n - currentN * mult + 1;
38 }
39
40
41 currentN = currentN / 10;
42 mult *= 10;
43 }
44
45 return cnt;
46 }
47
48 int main()
49 {
50 cout<<"please enter the number N:"<<endl;
51 unsigned int number = 0;
52 cin>>number;
53
54 cout<<"the number of 1s From 1 to N is:"<<endl;
55 cout<<NumbersOf1sFrom1ToN(number)<<endl;
56 return 0;
}
31.一類似于蜂窩的結(jié)構(gòu)的圖悠抹，進(jìn)行搜索最短路徑（要求5分鐘）
迪杰斯特拉算法
include <iostream>
include <iomanip>
include <string>
using namespace std;
define INFINITY 65535//無(wú)邊時(shí)的權(quán)值
define MAX_VERTEX_NUM 10//最大頂點(diǎn)數(shù)
typedef struct MGraph{
string vexs[10];//頂點(diǎn)信息
int arcs[10][10];//鄰接矩陣
int vexnum, arcnum;//頂點(diǎn)數(shù)和邊數(shù)
}MGraph;
int LocateVex(MGraph G, string u)//返回頂點(diǎn)u在圖中的位置
{
for(int i=0; i<G.vexnum; i++)
if(G.vexs[i]==u)
return i;
return -1;
}
void CreateDN(MGraph &G)//構(gòu)造有向網(wǎng)
{
string v1, v2;
int w;
int i, j, k;
cout<<"請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：";
cin>>G.vexnum>>G.arcnum;
cout<<"請(qǐng)輸入頂點(diǎn)：";
for(i=0; i<G.vexnum; i++)
cin>>G.vexs[i];
for(i=0; i<G.vexnum; i++)
for(j=0; j<G.vexnum; j++)
G.arcs[i][j]=INFINITY;
cout<<"請(qǐng)輸入邊和權(quán)值："<<endl;
for(k=0; k<G.arcnum; k++)
{
cin>>v1>>v2>>w;
i=LocateVex(G, v1);
j=LocateVex(G, v2);
G.arcs[i][j]=w;
}
}
//迪杰斯特拉算法求有向網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑p[v]及帶權(quán)長(zhǎng)度D[v]
//p[][]=-1表示沒有路徑珠月，p[v][i]存的是從v0到v當(dāng)前求得的最短路徑經(jīng)過(guò)的第i+1個(gè)頂點(diǎn)(這是打印最短路徑的關(guān)鍵)，則v0到v的最短路徑即為p[v][0]到p[v][j]直到p[v][j]=-1,路徑打印完畢楔敌。
//final[v]為true當(dāng)且僅當(dāng)v∈S,即已經(jīng)求得從v0到v的最短路徑啤挎。
void ShortestPath_DIJ(MGraph G, int v0, int p[][MAX_VERTEX_NUM], int D[])
{
int v, w, i, j, min;
bool final[10];
for(v=0; v<G.vexnum; v++)
{
final[v]=false;//設(shè)初值
D[v]=G.arcs[v0][v];//D[]存放v0到v得最短距離，初值為v0到v的直接距離
for(w=0; w<G.vexnum; w++)
p[v][w]=-1;//設(shè)p[][]初值為-1卵凑，即沒有路徑
if(D[v]<INFINITY)//v0到v有直接路徑
{
p[v][0]=v0;//v0到v最短路徑經(jīng)過(guò)的第一個(gè)頂點(diǎn)
p[v][1]=v;//v0到v最短路徑經(jīng)過(guò)的第二個(gè)頂點(diǎn)
}
}
D[v0]=0;//v0到v0距離為0
final[v0]=true;//v0頂點(diǎn)并入S集
for(i=1; i<G.vexnum; i++)//其余G.vexnum-1個(gè)頂點(diǎn)
{//開始主循環(huán)庆聘，每次求得v0到某個(gè)頂點(diǎn)v的最短路徑，并將v并入S集勺卢，然后更新p和D
min=INFINITY;
for(w=0; w<G.vexnum; w++)//對(duì)所有頂點(diǎn)檢查
if(!final[w] && D[w]<min)//在S集之外(即final[]=false)的頂點(diǎn)中找離v0最近的頂點(diǎn)伙判，將其賦給v,距離賦給min
{
v=w;
min=D[w];
}
final[v]=true;//v并入S集
for(w=0; w<G.vexnum; w++)//根據(jù)新并入的頂點(diǎn)，更新不在S集的頂點(diǎn)到v0的距離和路徑數(shù)組
{
if(!final[w] && min<INFINITY && G.arcs[v][w]<INFINITY && (min+G.arcs[v][w]<D[w]))
{//w不屬于S集且v0->v->w的距離<目前v0->w的距離
D[w]=min+G.arcs[v][w];//更新D[w]
for(j=0; j<G.vexnum; j++)//修改p[w]黑忱，v0到w經(jīng)過(guò)的頂點(diǎn)包括v0到v經(jīng)過(guò)的所有頂點(diǎn)再加上頂點(diǎn)w
{
p[w][j]=p[v][j];
if(p[w][j]==-1)//在p[w][]第一個(gè)等于-1的地方加上頂點(diǎn)w
{
p[w][j]=w;
break;
}
}
}
}
}
}
void main()
{
int i, j;
MGraph g;
CreateDN(g);
int p[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//最短路徑數(shù)組p
int D[MAX_VERTEX_NUM];//最短距離數(shù)組D
ShortestPath_DIJ(g, 0, p, D);
cout<<"最短路徑數(shù)組p[i][j]如下："<<endl;
for(i=0; i<g.vexnum; i++)
{
for(j=0; j<g.vexnum; j++)
cout<<setw(3)<<p[i][j]<<" ";
cout<<endl;
}
cout<<g.vexs[0]<<"到各頂點(diǎn)的最短路徑及長(zhǎng)度為："<<endl;
for(i=0; i<g.vexnum; i++)
{
if(i!=0 && D[i]!=INFINITY)
{
cout<<g.vexs[0]<<"-"<<g.vexs[i]<<"的最短路徑長(zhǎng)度為:"<<D[i];
cout<<" 最短路徑為：";
for(j=0; j<g.vexnum; j++)
{
if(p[i][j]>-1)
cout<<g.vexs[p[i][j]]<<" ";
}
cout<<endl;
}
else if(D[i]==INFINITY)
cout<<g.vexs[0]<<"-"<<g.vexs[i]<<":"<<"不可達(dá)"<<endl;
}
}
有兩個(gè)序列a,b宴抚，大小都為n,序列元素的值任意整數(shù)，無(wú)序甫煞；
要求：通過(guò)交換a,b中的元素菇曲，使[序列a元素的和]與[序列b元素的和]之間的差最小。
例如:
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];
include "stdio.h"
include "stdlib.h"
void balanceArray(int a[],int b[],int n);
int sumArray(int a[],int n);
int main(void)
{
int i;
int a[5]={0,1,2,3,4},b[5]={5,6,7,8,9};
balanceArray(a,b,5);
for(i=0;i<5;i++)
printf("%3d",a[i]);
printf("\n");
for(i=0;i<5;i++)
printf("%3d",b[i]);
printf("\n");
return 0;
}
void balanceArray(int a[],int b[],int n)
{
int p,q;
int i,j,itemDValue,sumDValue,tmp,flag=1;
if(sumArray(a,n) < sumArray(b,n))
{
p = b;
q = a;
}
while(flag)
{
flag=!flag;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
itemDValue = p[i]-q[j];
sumDValue = sumArray(p,n) - sumArray(q,n);
if((itemDValue < sumDValue)&&(itemDValue > 0))
{
flag=!flag;
tmp = p[i];
p[i] = q[j];
q[j] = tmp;
}
}
}
}
}
int sumArray(int a[],int n)
{
int i,count=0;
for(i=0;i<n;i++)
count += a[i];
return count;
}
實(shí)現(xiàn)一個(gè)挺高級(jí)的字符匹配算法：
給一串很長(zhǎng)字符串危虱，要求找到符合要求的字符串羊娃，例如目的串：123
1******3***2 ,12*****3這些都要找出來(lái)
其實(shí)就是類似一些和諧系統(tǒng)唐全。埃跷。。邮利。弥雹。
實(shí)現(xiàn)一個(gè)隊(duì)列。
隊(duì)列的應(yīng)用場(chǎng)景為：
一個(gè)生產(chǎn)者線程將int類型的數(shù)入列延届，一個(gè)消費(fèi)者線程將int類型的數(shù)出列
求一個(gè)矩陣中最大的二維矩陣(元素和最大).如:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是:
4 5
5 3
要求:(1)寫出算法;(2)分析時(shí)間復(fù)雜度;(3)用C寫出關(guān)鍵代碼
//非最優(yōu)解
include<iostream>
using namespace std;
int max_matrix(int (*array)[5], int maxx, int maxy, int& posi, int& posj)
{
int max = 0;
int i = 0, j = 0;
while(i < maxx - 1)
{
j = 0;
while( j < maxy - 1)
{
int t = array[i][j] + array[i+1][j] + array[i][j+1] + array[i+1][j+1];
if( max < t)
{
max = t;
posi = i;
posj = j;
}
j ++;
}
i ++;
}
return max;
}
int main()
{
int a[3][5] = {{1,2,0,3,4}, {2,3,4,5,1}, {1,1,5,3,0}};
int i = 0, j = 0;
int max = max_matrix(a, 3, 5, i, j);
cout << "max num: " << max <<endl;
cout << "matrix: " << endl;
cout << a[i][j] << " " << a[i][j+1] << endl;
cout << a[i+1][j] << " " << a[i+1][j+1] << endl;
}
第36題-40題（有些題目搜集于CSDN上的網(wǎng)友剪勿，已標(biāo)明）：
36.引用自網(wǎng)友：longzuo
谷歌筆試：
n支隊(duì)伍比賽，分別編號(hào)為0方庭，1厕吉，2酱固。。头朱。运悲。n-1，已知它們之間的實(shí)力對(duì)比關(guān)系项钮，
存儲(chǔ)在一個(gè)二維數(shù)組w[n][n]中班眯，w[i][j] 的值代表編號(hào)為i，j的隊(duì)伍中更強(qiáng)的一支烁巫。
所以w[i][j]=i 或者j署隘，現(xiàn)在給出它們的出場(chǎng)順序，并存儲(chǔ)在數(shù)組order[n]中亚隙，
比如order[n] = {4,3,5,8,1......}磁餐，那么第一輪比賽就是 4對(duì)3， 5對(duì)8阿弃。.......
勝者晉級(jí)崖媚，敗者淘汰，同一輪淘汰的所有隊(duì)伍排名不再細(xì)分恤浪，即可以隨便排畅哑，
下一輪由上一輪的勝者按照順序，再依次兩兩比水由，比如可能是4對(duì)5,直至出現(xiàn)第一名
編程實(shí)現(xiàn)荠呐，給出二維數(shù)組w，一維數(shù)組order 和 用于輸出比賽名次的數(shù)組result[n]砂客，
求出result泥张。
有n個(gè)長(zhǎng)為m+1的字符串，
如果某個(gè)字符串的最后m個(gè)字符與某個(gè)字符串的前m個(gè)字符匹配鞠值，則兩個(gè)字符串可以聯(lián)接媚创，
問(wèn)這n個(gè)字符串最多可以連成一個(gè)多長(zhǎng)的字符串，如果出現(xiàn)循環(huán)彤恶，則返回錯(cuò)誤钞钙。
百度面試：
1.用天平（只能比較，不能稱重）從一堆小球中找出其中唯一一個(gè)較輕的声离，使用x次天平芒炼，
最多可以從y個(gè)小球中找出較輕的那個(gè)，求y與x的關(guān)系式术徊。
answer:二分法
2.有一個(gè)很大很大的輸入流本刽，大到?jīng)]有存儲(chǔ)器可以將其存儲(chǔ)下來(lái)，
而且只輸入一次，如何從這個(gè)輸入流中隨機(jī)取得m個(gè)記錄子寓。
3.大量的URL字符串暗挑，如何從中去除重復(fù)的，優(yōu)化時(shí)間空間復(fù)雜度
網(wǎng)易有道筆試：
(1).
求一個(gè)二叉樹中任意兩個(gè)節(jié)點(diǎn)間的最大距離斜友，
兩個(gè)節(jié)點(diǎn)的距離的定義是 這兩個(gè)節(jié)點(diǎn)間邊的個(gè)數(shù)窿祥，
比如某個(gè)孩子節(jié)點(diǎn)和父節(jié)點(diǎn)間的距離是1，和相鄰兄弟節(jié)點(diǎn)間的距離是2蝙寨，優(yōu)化時(shí)間空間復(fù)雜度晒衩。
(2).
求一個(gè)有向連通圖的割點(diǎn)，割點(diǎn)的定義是墙歪，如果除去此節(jié)點(diǎn)和與其相關(guān)的邊听系，
有向圖不再連通，描述算法虹菲。
40.百度研發(fā)筆試題
引用自：zp155334877
1)設(shè)計(jì)一個(gè)棧結(jié)構(gòu)靠胜，滿足一下條件：min，push毕源，pop操作的時(shí)間復(fù)雜度為O(1)浪漠。
2)一串首尾相連的珠子(m個(gè))，有N種顏色(N<=10)霎褐，
設(shè)計(jì)一個(gè)算法址愿，取出其中一段，要求包含所有N中顏色冻璃，并使長(zhǎng)度最短响谓。
并分析時(shí)間復(fù)雜度與空間復(fù)雜度。
3)設(shè)計(jì)一個(gè)系統(tǒng)處理詞語(yǔ)搭配問(wèn)題省艳，比如說(shuō) 中國(guó) 和人民可以搭配娘纷，
則中國(guó)人民 人民中國(guó)都有效或舞。要求：
*系統(tǒng)每秒的查詢數(shù)量可能上千次蟹瘾；
*詞語(yǔ)的數(shù)量級(jí)為10W纳像；
*每個(gè)詞至多可以與1W個(gè)詞搭配
當(dāng)用戶輸入中國(guó)人民的時(shí)候盐须，要求返回與這個(gè)搭配詞組相關(guān)的信息。
41.求固晶機(jī)的晶元查找程序
晶元盤由數(shù)目不詳?shù)拇笮∫粯拥木гM成虎囚，晶元并不一定全布滿晶元盤缸榄，
照相機(jī)每次這能匹配一個(gè)晶元饼酿，如匹配過(guò)棉圈，則拾取該晶元涩堤，
若匹配不過(guò)，照相機(jī)則按測(cè)好的晶元間距移到下一個(gè)位置分瘾。
求遍歷晶元盤的算法 求思路。
42.請(qǐng)修改append函數(shù)，利用這個(gè)函數(shù)實(shí)現(xiàn)：
兩個(gè)非降序鏈表的并集德召，1->2->3 和 2->3->5 并為 1->2->3->5
另外只能輸出結(jié)果白魂，不能修改兩個(gè)鏈表的數(shù)據(jù)。
43.遞歸和非遞歸倆種方法實(shí)現(xiàn)二叉樹的前序遍歷上岗。
44.騰訊面試題：
1.設(shè)計(jì)一個(gè)魔方（六面）的程序福荸。
2.有一千萬(wàn)條短信，有重復(fù)肴掷，以文本文件的形式保存敬锐，一行一條，有重復(fù)呆瞻。
請(qǐng)用5分鐘時(shí)間台夺，找出重復(fù)出現(xiàn)最多的前10條。
3.收藏了1萬(wàn)條url痴脾，現(xiàn)在給你一條url颤介，如何找出相似的url。（面試官不解釋何為相似）
45.雅虎：
1.對(duì)于一個(gè)整數(shù)矩陣赞赖，存在一種運(yùn)算滚朵，對(duì)矩陣中任意元素加一時(shí)，需要其相鄰（上下左右）
某一個(gè)元素也加一前域，現(xiàn)給出一正數(shù)矩陣辕近，判斷其是否能夠由一個(gè)全零矩陣經(jīng)過(guò)上述運(yùn)算得到。
2.一個(gè)整數(shù)數(shù)組匿垄，長(zhǎng)度為n亏推，將其分為m份，使各份的和相等年堆，求m的最大值
比如{3吞杭，2，4变丧，3芽狗，6} 可以分成{3，2痒蓬，4童擎，3，6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m的最大值為3
46.搜狐：
四對(duì)括號(hào)可以有多少種匹配排列方式攻晒？比如兩對(duì)括號(hào)可以有兩種：（）（）和（（））
47.創(chuàng)新工場(chǎng)：
求一個(gè)數(shù)組的最長(zhǎng)遞減子序列 比如{9顾复，4，3鲁捏，2芯砸，5，4，3假丧，2}的最長(zhǎng)遞減子序列為{9双揪，5，4包帚，3渔期，2}
48.微軟：
一個(gè)數(shù)組是由一個(gè)遞減數(shù)列左移若干位形成的，比如{4渴邦，3疯趟，2，1谋梭，6信峻，5}
是由{6，5章蚣，4站欺，3，2纤垂，1}左移兩位形成的矾策，在這種數(shù)組中查找某一個(gè)數(shù)。
49.一道看上去很嚇人的算法面試題：
如何對(duì)n個(gè)數(shù)進(jìn)行排序峭沦，要求時(shí)間復(fù)雜度O(n)贾虽，空間復(fù)雜度O(1)
50.網(wǎng)易有道筆試：
1.求一個(gè)二叉樹中任意兩個(gè)節(jié)點(diǎn)間的最大距離，兩個(gè)節(jié)點(diǎn)的距離的定義是 這兩個(gè)節(jié)點(diǎn)間邊的個(gè)數(shù)吼鱼，
比如某個(gè)孩子節(jié)點(diǎn)和父節(jié)點(diǎn)間的距離是1蓬豁，和相鄰兄弟節(jié)點(diǎn)間的距離是2，優(yōu)化時(shí)間空間復(fù)雜度菇肃。
2.求一個(gè)有向連通圖的割點(diǎn)地粪，割點(diǎn)的定義是，
如果除去此節(jié)點(diǎn)和與其相關(guān)的邊琐谤，有向圖不再連通蟆技，描述算法。
51.和為n連續(xù)正數(shù)序列斗忌。
題目：輸入一個(gè)正數(shù)n质礼，輸出所有和為n連續(xù)正數(shù)序列。
例如輸入15织阳，由于1+2+3+4+5=4+5+6=7+8=15眶蕉，所以輸出3個(gè)連續(xù)序列1-5、4-6和7-8唧躲。
分析：這是網(wǎng)易的一道面試題造挽。
52.二元樹的深度碱璃。
題目：輸入一棵二元樹的根結(jié)點(diǎn)，求該樹的深度刽宪。
從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過(guò)的結(jié)點(diǎn)（含根厘贼、葉結(jié)點(diǎn)）形成樹的一條路徑界酒，最長(zhǎng)路徑的長(zhǎng)度為樹的深度圣拄。
例如：輸入二元樹：
10
/ \
6 14
/ / \
4 12 16
輸出該樹的深度3。
二元樹的結(jié)點(diǎn)定義如下：
struct SBinaryTreeNode // a node of the binary tree
{
int m_nValue; // value of node
SBinaryTreeNode *m_pLeft; // left child of node
SBinaryTreeNode *m_pRight; // right child of node
};
分析：這道題本質(zhì)上還是考查二元樹的遍歷毁欣。
53.字符串的排列庇谆。
題目：輸入一個(gè)字符串，打印出該字符串中字符的所有排列凭疮。
例如輸入字符串a(chǎn)bc饭耳，則輸出由字符a、b执解、c所能排列出來(lái)的所有字符串
abc寞肖、acb、bac衰腌、bca新蟆、cab和cba。
分析：這是一道很好的考查對(duì)遞歸理解的編程題右蕊，
因此在過(guò)去一年中頻繁出現(xiàn)在各大公司的面試琼稻、筆試題中。
54.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面饶囚。
題目：輸入一個(gè)整數(shù)數(shù)組帕翻，調(diào)整數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分萝风，
所有偶數(shù)位于數(shù)組的后半部分嘀掸。要求時(shí)間復(fù)雜度為O(n)。
題目：類CMyString的聲明如下：
class CMyString
{
public:
CMyString(char* pData = NULL);
CMyString(const CMyString& str);
~CMyString(void);
CMyString& operator = (const CMyString& str);
private:
char* m_pData;
};
請(qǐng)實(shí)現(xiàn)其賦值運(yùn)算符的重載函數(shù)规惰，要求異常安全睬塌，即當(dāng)對(duì)一個(gè)對(duì)象進(jìn)行賦值時(shí)發(fā)生異常，對(duì)象的狀態(tài)不能改變卿拴。
56.最長(zhǎng)公共字串衫仑。
題目：如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個(gè)字符串二中，
則字符串一稱之為字符串二的子串堕花。
注意文狱，并不要求子串（字符串一）的字符必須連續(xù)出現(xiàn)在字符串二中。
請(qǐng)編寫一個(gè)函數(shù)缘挽，輸入兩個(gè)字符串瞄崇，求它們的最長(zhǎng)公共子串呻粹，并打印出最長(zhǎng)公共子串。
例如：輸入兩個(gè)字符串BDCABA和ABCBDAB苏研，字符串BCBA和BDAB都是是它們的最長(zhǎng)公共子串等浊，
則輸出它們的長(zhǎng)度4，并打印任意一個(gè)子串摹蘑。
分析：求最長(zhǎng)公共子串（Longest Common Subsequence, LCS）是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃題筹燕，
因此一些重視算法的公司像MicroStrategy都把它當(dāng)作面試題。
57.用倆個(gè)棧實(shí)現(xiàn)隊(duì)列衅鹿。
題目：某隊(duì)列的聲明如下：
template<typename T> class CQueue
{
public:
CQueue() {}
~CQueue() {}
void appendTail(const T& node); // append a element to tail
void deleteHead(); // remove a element from head
private:
T> m_stack1;
T> m_stack2;
};
分析：從上面的類的聲明中撒踪，我們發(fā)現(xiàn)在隊(duì)列中有兩個(gè)棧。
因此這道題實(shí)質(zhì)上是要求我們用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列大渤。
相信大家對(duì)棧和隊(duì)列的基本性質(zhì)都非常了解了：棧是一種后入先出的數(shù)據(jù)容器制妄，
因此對(duì)隊(duì)列進(jìn)行的插入和刪除操作都是在棧頂上進(jìn)行；隊(duì)列是一種先入先出的數(shù)據(jù)容器泵三，
我們總是把新元素插入到隊(duì)列的尾部耕捞，而從隊(duì)列的頭部刪除元素。
58.從尾到頭輸出鏈表烫幕。
題目：輸入一個(gè)鏈表的頭結(jié)點(diǎn)俺抽，從尾到頭反過(guò)來(lái)輸出每個(gè)結(jié)點(diǎn)的值。鏈表結(jié)點(diǎn)定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析：這是一道很有意思的面試題纬霞。
該題以及它的變體經(jīng)常出現(xiàn)在各大公司的面試凌埂、筆試題中。
59.不能被繼承的類诗芜。
題目：用C++設(shè)計(jì)一個(gè)不能被繼承的類瞳抓。
分析：這是Adobe公司2007年校園招聘的最新筆試題。
這道題除了考察應(yīng)聘者的C++基本功底外伏恐，還能考察反應(yīng)能力孩哑，是一道很好的題目。
60.在O（1）時(shí)間內(nèi)刪除鏈表結(jié)點(diǎn)翠桦。
題目：給定鏈表的頭指針和一個(gè)結(jié)點(diǎn)指針横蜒，在O(1)時(shí)間刪除該結(jié)點(diǎn)。鏈表結(jié)點(diǎn)的定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
函數(shù)的聲明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
分析：這是一道廣為流傳的Google面試題销凑，能有效考察我們的編程基本功丛晌，還能考察我們的反應(yīng)速度，
更重要的是斗幼，還能考察我們對(duì)時(shí)間復(fù)雜度的理解澎蛛。
61.找出數(shù)組中兩個(gè)只出現(xiàn)一次的數(shù)字
題目：一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次蜕窿。
請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字谋逻。要求時(shí)間復(fù)雜度是O(n)呆馁，空間復(fù)雜度是O(1)。
分析：這是一道很新穎的關(guān)于位運(yùn)算的面試題毁兆。
62.找出鏈表的第一個(gè)公共結(jié)點(diǎn)浙滤。
題目：兩個(gè)單向鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)气堕。
鏈表的結(jié)點(diǎn)定義為：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析：這是一道微軟的面試題纺腊。微軟非常喜歡與鏈表相關(guān)的題目，
因此在微軟的面試題中送巡，鏈表出現(xiàn)的概率相當(dāng)高摹菠。
63.在字符串中刪除特定的字符盒卸。
題目：輸入兩個(gè)字符串骗爆，從第一字符串中刪除第二個(gè)字符串中所有的字符。例如蔽介，輸入”They are students.”和”aeiou”摘投，
則刪除之后的第一個(gè)字符串變成”Thy r stdnts.”。
分析：這是一道微軟面試題虹蓄。在微軟的常見面試題中犀呼，與字符串相關(guān)的題目占了很大的一部分，
因?yàn)閷懗绦虿僮髯址芎芎玫姆从澄覀兊木幊袒竟Α?/p>
- 尋找丑數(shù)薇组。
題目：我們把只包含因子2外臂、3和5的數(shù)稱作丑數(shù)（Ugly Number）。例如6律胀、8都是丑數(shù)宋光，
但14不是，因?yàn)樗蜃?炭菌。習(xí)慣上我們把1當(dāng)做是第一個(gè)丑數(shù)罪佳。
求按從小到大的順序的第1500個(gè)丑數(shù)。
分析：這是一道在網(wǎng)絡(luò)上廣為流傳的面試題黑低，據(jù)說(shuō)google曾經(jīng)采用過(guò)這道題赘艳。
65.輸出1到最大的N位數(shù)
題目：輸入數(shù)字n，按順序輸出從1最大的n位10進(jìn)制數(shù)克握。比如輸入3蕾管，
則輸出1、2菩暗、3一直到最大的3位數(shù)即999掰曾。
分析：這是一道很有意思的題目⊙校看起來(lái)很簡(jiǎn)單婴梧，其實(shí)里面卻有不少的玄機(jī)下梢。
66.顛倒棧。
題目：用遞歸顛倒一個(gè)棧塞蹭。例如輸入棧{1, 2, 3, 4, 5}孽江，1在棧頂。
顛倒之后的棧為{5, 4, 3, 2, 1}番电，5處在棧頂岗屏。
67.倆個(gè)閑玩娛樂(lè)。
1.撲克牌的順子
從撲克牌中隨機(jī)抽5張牌漱办，判斷是不是一個(gè)順子这刷，即這5張牌是不是連續(xù)的。
2-10為數(shù)字本身娩井，A為1暇屋，J為11，Q為12洞辣，K為13咐刨，而大小王可以看成任意數(shù)字。
2.n個(gè)骰子的點(diǎn)數(shù)扬霜。
把n個(gè)骰子扔在地上定鸟，所有骰子朝上一面的點(diǎn)數(shù)之和為S。輸入n著瓶，
打印出S的所有可能的值出現(xiàn)的概率联予。
68.把數(shù)組排成最小的數(shù)。
題目：輸入一個(gè)正整數(shù)數(shù)組材原，將它們連接起來(lái)排成一個(gè)數(shù)沸久，輸出能排出的所有數(shù)字中最小的一個(gè)。
例如輸入數(shù)組{32, 321}华糖，則輸出這兩個(gè)能排成的最小數(shù)字32132麦向。
請(qǐng)給出解決問(wèn)題的算法，并證明該算法客叉。
分析：這是09年6月份百度的一道面試題诵竭，
從這道題我們可以看出百度對(duì)應(yīng)聘者在算法方面有很高的要求。
69.旋轉(zhuǎn)數(shù)組中的最小元素兼搏。
題目：把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾卵慰，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)排好序的數(shù)組的一個(gè)旋轉(zhuǎn)佛呻，
輸出旋轉(zhuǎn)數(shù)組的最小元素裳朋。例如數(shù)組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1吓著。
分析：這道題最直觀的解法并不難鲤嫡。從頭到尾遍歷數(shù)組一次送挑，就能找出最小的元素，
時(shí)間復(fù)雜度顯然是O(N)暖眼。但這個(gè)思路沒有利用輸入數(shù)組的特性惕耕，我們應(yīng)該能找到更好的解法。
70.給出一個(gè)函數(shù)來(lái)輸出一個(gè)字符串的所有排列诫肠。
ANSWER 簡(jiǎn)單的回溯就可以實(shí)現(xiàn)了司澎。當(dāng)然排列的產(chǎn)生也有很多種算法，去看看組合數(shù)學(xué)栋豫，
還有逆序生成排列和一些不需要遞歸生成排列的方法挤安。
印象中Knuth的<TAOCP>第一卷里面深入講了排列的生成。這些算法的理解需要一定的數(shù)學(xué)功底丧鸯，
也需要一定的靈感蛤铜，有興趣最好看看。
71.數(shù)值的整數(shù)次方骡送。
題目：實(shí)現(xiàn)函數(shù)double Power(double base, int exponent)昂羡，求base的exponent次方。
不需要考慮溢出摔踱。
分析：這是一道看起來(lái)很簡(jiǎn)單的問(wèn)題≡狗撸可能有不少的人在看到題目后30秒寫出如下的代碼：
double Power(double base, int exponent)
{
double result = 1.0;
for(int i = 1; i <= exponent; ++i)
result *= base;
return result;
}
題目：設(shè)計(jì)一個(gè)類派敷，我們只能生成該類的一個(gè)實(shí)例。
分析：只能生成一個(gè)實(shí)例的類是實(shí)現(xiàn)了Singleton模式的類型撰洗。
73.對(duì)策字符串的最大長(zhǎng)度篮愉。
題目：輸入一個(gè)字符串，輸出該字符串中對(duì)稱的子字符串的最大長(zhǎng)度差导。
比如輸入字符串“google”试躏，由于該字符串里最長(zhǎng)的對(duì)稱子字符串是“goog”，因此輸出4设褐。
分析：可能很多人都寫過(guò)判斷一個(gè)字符串是不是對(duì)稱的函數(shù)颠蕴，這個(gè)題目可以看成是該函數(shù)的加強(qiáng)版。
74.數(shù)組中超過(guò)出現(xiàn)次數(shù)超過(guò)一半的數(shù)字
題目：數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)了數(shù)組長(zhǎng)度的一半助析，找出這個(gè)數(shù)字犀被。
分析：這是一道廣為流傳的面試題，包括百度外冀、微軟和Google在內(nèi)的多家公司都
曾經(jīng)采用過(guò)這個(gè)題目寡键。要幾十分鐘的時(shí)間里很好地解答這道題，
除了較好的編程能力之外雪隧，還需要較快的反應(yīng)和較強(qiáng)的邏輯思維能力西轩。
75.二叉樹兩個(gè)結(jié)點(diǎn)的最低共同父結(jié)點(diǎn)
題目：二叉樹的結(jié)點(diǎn)定義如下：
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
輸入二叉樹中的兩個(gè)結(jié)點(diǎn)员舵，輸出這兩個(gè)結(jié)點(diǎn)在數(shù)中最低的共同父結(jié)點(diǎn)。
分析：求數(shù)中兩個(gè)結(jié)點(diǎn)的最低共同結(jié)點(diǎn)是面試中經(jīng)常出現(xiàn)的一個(gè)問(wèn)題藕畔。這個(gè)問(wèn)題至少有兩個(gè)變種固灵。
76.復(fù)雜鏈表的復(fù)制
題目：有一個(gè)復(fù)雜鏈表，其結(jié)點(diǎn)除了有一個(gè)m_pNext指針指向下一個(gè)結(jié)點(diǎn)外劫流，
還有一個(gè)m_pSibling指向鏈表中的任一結(jié)點(diǎn)或者NULL巫玻。其結(jié)點(diǎn)的C++定義如下：
struct ComplexNode
{
int m_nValue;
ComplexNode* m_pNext;
ComplexNode* m_pSibling;
};
下圖是一個(gè)含有5個(gè)結(jié)點(diǎn)的該類型復(fù)雜鏈表。
圖中實(shí)線箭頭表示m_pNext指針祠汇，虛線箭頭表示m_pSibling指針仍秤。為簡(jiǎn)單起見，
指向NULL的指針沒有畫出可很。
請(qǐng)完成函數(shù)ComplexNode* Clone(ComplexNode* pHead)诗力，以復(fù)制一個(gè)復(fù)雜鏈表。
分析：在常見的數(shù)據(jù)結(jié)構(gòu)上稍加變化我抠，這是一種很新穎的面試題苇本。
要在不到一個(gè)小時(shí)的時(shí)間里解決這種類型的題目，我們需要較快的反應(yīng)能力菜拓，
對(duì)數(shù)據(jù)結(jié)構(gòu)透徹的理解以及扎實(shí)的編程功底瓣窄。
77.關(guān)于鏈表問(wèn)題的面試題目如下：
1.給定單鏈表，檢測(cè)是否有環(huán)纳鼎。
使用兩個(gè)指針p1,p2從鏈表頭開始遍歷俺夕，p1每次前進(jìn)一步，p2每次前進(jìn)兩步贱鄙。如果p2到達(dá)鏈表尾部劝贸，
說(shuō)明無(wú)環(huán)，否則p1逗宁、p2必然會(huì)在某個(gè)時(shí)刻相遇(p1==p2)映九，從而檢測(cè)到鏈表中有環(huán)。
2.給定兩個(gè)單鏈表(head1, head2)瞎颗，檢測(cè)兩個(gè)鏈表是否有交點(diǎn)件甥，如果有返回第一個(gè)交點(diǎn)。
如果head1==head2言缤，那么顯然相交嚼蚀，直接返回head1。
否則管挟，分別從head1,head2開始遍歷兩個(gè)鏈表獲得其長(zhǎng)度len1與len2轿曙，假設(shè)len1>=len2，
那么指針p1由head1開始向后移動(dòng)len1-len2步，指針p2=head2导帝，
下面p1守谓、p2每次向后前進(jìn)一步并比較p1p2是否相等，如果相等即返回該結(jié)點(diǎn)您单，
否則說(shuō)明兩個(gè)鏈表沒有交點(diǎn)斋荞。
3.給定單鏈表(head)，如果有環(huán)的話請(qǐng)返回從頭結(jié)點(diǎn)進(jìn)入環(huán)的第一個(gè)節(jié)點(diǎn)虐秦。
運(yùn)用題一平酿，我們可以檢查鏈表中是否有環(huán)。
如果有環(huán)悦陋，那么p1p2重合點(diǎn)p必然在環(huán)中蜈彼。從p點(diǎn)斷開環(huán)，
方法為：p1=p, p2=p->next, p->next=NULL俺驶。此時(shí)幸逆，原單鏈表可以看作兩條單鏈表，
一條從head開始暮现，另一條從p2開始还绘，于是運(yùn)用題二的方法，我們找到它們的第一個(gè)交點(diǎn)即為所求栖袋。
4.只給定單鏈表中某個(gè)結(jié)點(diǎn)p(并非最后一個(gè)結(jié)點(diǎn)拍顷，即p->next!=NULL)指針，刪除該結(jié)點(diǎn)栋荸。
辦法很簡(jiǎn)單菇怀，首先是放p中數(shù)據(jù),然后將p->next的數(shù)據(jù)copy入p中，接下來(lái)刪除p->next即可晌块。
5.只給定單鏈表中某個(gè)結(jié)點(diǎn)p(非空結(jié)點(diǎn))，在p前面插入一個(gè)結(jié)點(diǎn)帅霜。
辦法與前者類似匆背，首先分配一個(gè)結(jié)點(diǎn)q，將q插入在p后身冀，接下來(lái)將p中的數(shù)據(jù)copy入q中钝尸，
然后再將要插入的數(shù)據(jù)記錄在p中。
78.鏈表和數(shù)組的區(qū)別在哪里搂根？
分析：主要在基本概念上的理解珍促。
但是最好能考慮的全面一點(diǎn)，現(xiàn)在公司招人的競(jìng)爭(zhēng)可能就在細(xì)節(jié)上產(chǎn)生剩愧，
誰(shuí)比較仔細(xì)猪叙，誰(shuí)獲勝的機(jī)會(huì)就大。
1.編寫實(shí)現(xiàn)鏈表排序的一種算法。說(shuō)明為什么你會(huì)選擇用這樣的方法穴翩？
2.編寫實(shí)現(xiàn)數(shù)組排序的一種算法犬第。說(shuō)明為什么你會(huì)選擇用這樣的方法？
3.請(qǐng)編寫能直接實(shí)現(xiàn)strstr()函數(shù)功能的代碼芒帕。
80.阿里巴巴一道筆試題
問(wèn)題描述:
12個(gè)高矮不同的人,排成兩排,每排必須是從矮到高排列,而且第二排比對(duì)應(yīng)的第一排的人高,問(wèn)排列方式有多少種?
這個(gè)筆試題,很YD,因?yàn)榘涯硞€(gè)遞歸關(guān)系隱藏得很深歉嗓。
