本文轉自：http://blog.csdn.net/v_JULY_v/archive/2011/01/10/6126406.aspx
1.把二進制查找樹轉變成排序的雙向連結清單
題目：
輸入一棵二進制查找樹，将該二進制查找樹轉換成一個排序的雙向連結清單。
要求不能建立任何新的結點，隻調整指針的指向。
10
/ /
6 14
/ / / /
4 8 12 16
轉換成雙向連結清單
4=6=8=10=12=14=16。
首先我們定義的二進制查找樹 節點的資料結構如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
//引用 245 樓 tree_star 的回複
#include <stdio.h>
#include <iostream.h>
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
typedef BSTreeNode DoubleList;
DoubleList * pHead;
DoubleList * pListIndex;
void convertToDoubleList(BSTreeNode * pCurrent);
// 建立二進制查找樹
void addBSTreeNode(BSTreeNode * & pCurrent, int value)
{
if (NULL == pCurrent)
{
BSTreeNode * pBSTree = new BSTreeNode();
pBSTree->m_pLeft = NULL;
pBSTree->m_pRight = NULL;
pBSTree->m_nValue = value;
pCurrent = pBSTree;
}
else
{
if ((pCurrent->m_nValue) > value)
{
addBSTreeNode(pCurrent->m_pLeft, value);
}
else if ((pCurrent->m_nValue) < value)
{
addBSTreeNode(pCurrent->m_pRight, value);
}
else
{
//cout<<"重複加入節點"<<endl;
}
}
}
// 周遊二進制查找樹 中序
void ergodicBSTree(BSTreeNode * pCurrent)
{
if (NULL == pCurrent)
{
return;
}
if (NULL != pCurrent->m_pLeft)
{
ergodicBSTree(pCurrent->m_pLeft);
}
// 節點接到連結清單尾部
convertToDoubleList(pCurrent);
// 右子樹為空
if (NULL != pCurrent->m_pRight)
{
ergodicBSTree(pCurrent->m_pRight);
}
}
// 二叉樹轉換成list
void convertToDoubleList(BSTreeNode * pCurrent)
{
pCurrent->m_pLeft = pListIndex;
if (NULL != pListIndex)
{
pListIndex->m_pRight = pCurrent;
}
else
{
pHead = pCurrent;
}
pListIndex = pCurrent;
cout<<pCurrent->m_nValue<<endl;
}
int main()
{
BSTreeNode * pRoot = NULL;
pListIndex = NULL;
pHead = NULL;
addBSTreeNode(pRoot, 10);
addBSTreeNode(pRoot, 4);
addBSTreeNode(pRoot, 6);
addBSTreeNode(pRoot, 8);
addBSTreeNode(pRoot, 12);
addBSTreeNode(pRoot, 14);
addBSTreeNode(pRoot, 15);
addBSTreeNode(pRoot, 16);
ergodicBSTree(pRoot);
return 0;
}
///
4
6
8
10
12
14
15
16
Press any key to continue
//
2.設計包含min函數的棧。
定義棧的資料結構，要求添加一個min函數，能夠得到棧的最小元素。
要求函數min、push以及pop的時間複雜度都是O(1)。
結合連結清單一起做。
首先我做插入以下數字：10，7，3，3，8，5，2， 6
0: 10 -> NULL (MIN=10, POS=0)
1: 7 -> [0] (MIN=7, POS=1) 用數組表示堆棧，第0個元素表示棧底
2: 3 -> [1] (MIN=3, POS=2)
3: 3 -> [2] (MIN=3, POS=3)
4: 8 -> NULL (MIN=3, POS=3) 技巧在這裡，因為8比目前的MIN大，是以彈出8不會對目前的MIN産生影響
5：5 -> NULL (MIN=3, POS=3)
6: 2 -> [2] (MIN=2, POS=6) 如果2出棧了，那麼3就是MIN
7: 6 -> [6]
出棧的話采用類似方法修正。
是以，此題的第1小題，即是借助輔助棧，儲存最小值，
且随時更新輔助棧中的元素。
如先後，push 2 6 4 1 5
stack A stack B（輔助棧）
4: 5 1 //push 5,min=p->[3]=1 ^
3: 1 1 //push 1,min=p->[3]=1 | //此刻push進A的元素1小于B中棧頂元素2
2: 4 2 //push 4,min=p->[0]=2 |
1: 6 2 //push 6,min=p->[0]=2 |
0: 2 2 //push 2,min=p->[0]=2 |
push第一個元素進A，也把它push進B，
當向Apush的元素比B中的元素小， 則也push進B，即更新B。否則，不動B，儲存原值。
向棧A push元素時，順序由下至上。
輔助棧B中，始終儲存着最小的元素。
然後，pop棧A中元素，5 1 4 6 2
A B ->更新
4: 5 1 1 //pop 5,min=p->[3]=1 |
3: 1 1 2 //pop 1,min=p->[0]=2 |
2: 4 2 2 //pop 4,min=p->[0]=2 |
1: 6 2 2 //pop 6,min=p->[0]=2 |
0: 2 2 NULL //pop 2,min=NULL v
當pop A中的元素小于B中棧頂元素時，則也要pop B中棧頂元素。
3.求子數組的最大和
題目：
輸入一個整形數組，數組裡有正數也有負數。
數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。
求所有子數組的和的最大值。要求時間複雜度為O(n)。
例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數組為3, 10, -4, 7, 2，
是以輸出為該子數組的和18。
//July 2010/10/18
#include <iostream.h>
int maxSum(int* a, int n)
{
int sum=0;
int b=0;
for(int i=0; i<n; i++)
{
if(b<0)
b=a[i];
else
b+=a[i];
if(sum<b)
sum=b;
}
return sum;
}
int main()
{
int a[10]={1,-8,6,3,-1,5,7,-2,0,1};
cout<<maxSum(a,10)<<endl;
return 0;
}
運作結果，如下：
20
Press any key to continue
------------------------------------------------------------
int maxSum(int* a, int n)
{
int sum=0;
int b=0;
for(int i=0; i<n; i++)
{
if(b<=0) //此處修正下，把b<0改為 b<=0
b=a[i];
else
b+=a[i];
if(sum<b)
sum=b;
}
return sum;
}
//
解釋下：
例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，
那麼最大的子數組為3, 10, -4, 7, 2，
是以輸出為該子數組的和18
所有的東西都在以下倆行，
即：
b ： 0 1 -1 3 13 9 16 18 7
sum： 0 1 1 3 13 13 16 18 18
其實算法很簡單，目前面的幾個數，加起來後，b<0後，
把b重新指派，置為下一個元素，b=a[i]。
當b>sum，則更新sum=b;
若b<sum，則sum保持原值，不更新。:)。July、10/31。
///
第4題，
當通路到某一結點時，把該結點添加到路徑上，并累加目前結點的值。
如果目前結點為葉結點并且目前路徑的和剛好等于輸入的整數，則目前的路徑符合要求，我們把它列印出來
。
如果目前結點不是葉結點，則繼續通路它的子結點。目前結點通路結束後，遞歸函數将自動回到父結點。
是以我們在函數退出之前要在路徑上删除目前結點并減去目前結點的值，
以確定傳回父結點時路徑剛好是根結點到父結點的路徑。
我們不難看出儲存路徑的資料結構實際上是一個棧結構，因為路徑要與遞歸調用狀态一緻，
而遞歸調用本質就是一個壓棧和出棧的過程。
void FindPath
(
BinaryTreeNode* pTreeNode, // a node of binary tree
int expectedSum, // the expected sum
std::vector<int>& path, // a path from root to current node
int& currentSum // the sum of path
)
{
if(!pTreeNode)
return;
currentSum += pTreeNode->m_nValue;
path.push_back(pTreeNode->m_nValue);
// if the node is a leaf, and the sum is same as pre-defined,
// the path is what we want. print the path
bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight);
if(currentSum == expectedSum && isLeaf)
{
std::vector<int>::iterator iter = path.begin();
for(; iter != path.end(); ++ iter)
std::cout << *iter << '/t';
std::cout << std::endl;
}
// if the node is not a leaf, goto its children
if(pTreeNode->m_pLeft)
FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum);
if(pTreeNode->m_pRight)
FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum);
// when we finish visiting a node and return to its parent node,
// we should delete this node from the path and
// minus the node's value from the current sum
currentSum -= pTreeNode->m_nValue;
path.pop_back();
}
5.查找最小的k個元素
題目：輸入n個整數，輸出其中最小的k個。
例如輸入1，2，3，4，5，6，7和8這8個數字，
則最小的4個數字為1，2，3和4。
//July 2010/10/18
//引用自116 樓 wocaoqwer 的回複。
#include<iostream>
using namespace std;
class MinK{
public:
MinK(int *arr,int si):array(arr),size(si){}
bool kmin(int k,int*& ret){
if(k>size)
{
ret=NULL;
return false;
}
else
{
ret=new int[k--];
int i;
for(i=0;i<=k;++i)
ret[i]=array[i];
for(int j=(k-1)/2;j>=0;--j)
shiftDown(ret,j,k);
for(;i<size;++i)
if(array[i]<ret[0])
{
ret[0]=array[i];
shiftDown(ret,0,k);
}
return true;
}
}
void remove(int*& ret){
delete[] ret;
ret=NULL;
}
private:
void shiftDown(int *ret,int pos,int length){
int t=ret[pos];
for(int s=2*pos+1;s<=length;s=2*s+1){
if(s<length&&ret[s]<ret[s+1])
++s;
if(t<ret[s])
{
ret[pos]=ret[s];
pos=s;
}
else break;
}
ret[pos]=t;
}
int *array;
int size;
};
int main()
{
int array[]={1,2,3,4,5,6,7,8};
MinK mink(array,sizeof(array)/sizeof(array[0]));
int *ret;
int k=4;
if(mink.kmin(k,ret))
{
for(int i=0;i<k;++i)
cout<<ret[i]<<endl;
mink.remove(ret);
}
return 0;
}
/
運作結果：
4
2
3
1
Press any key to continue
/
---------------------
第5題，也可以：
用類似快排的partition的方法，隻求2邊中的一邊，在O(N)時間得到第k大的元素v；
再掃描一遍( O(N) )，得到所有小于等于v的元素。
其中，快速排序每一趟比較用時O（n），要進行lgn次比較，才最終完成整個排序。
是以快排的複雜度才為O（n*lgn）。
像現在，隻需要，找到第k大的元素，排一趟是O（n），排倆趟是O（2n），
其中第二趟，可以在第一趟後選擇排序哪邊，即隻要排一邊了，
遞歸找到第k大的元素，是O（N）的複雜度，最後周遊那一邊O（k），輸出這k個元素，即可。
是以，總的運作時間複雜度為O（N）。
（如果，要有序輸出的話，則再将那k的元素排序，時間複雜度為O（N+klgk）。）
-------------------------------------------------
第5題，再具體闡述下：
類似快排中的分割算法（如果不清楚快速排序，請參考本BLOG内關于快速排序的倆篇文章）：
每次分割後都能傳回樞紐點在數組中的位置s,然後比較s與k的大小
若大的話，則再次遞歸劃分array[s..n]，
小的話，就遞歸array[left...s-1] //s為中間樞紐點元素。
否則傳回array[s]，就是partition中傳回的值。 //就是要找到這個s。
找到符合要求的s值後，再周遊輸出比s小的那一邊的元素。
代碼實作：
//引自飛羽。
int kth_elem(int a[],int low, int high,int k)
{
int pivot=a[low];
int low_temp = low;
int high_temp = high;
while(low<high)
{
while(low<high&&a[high]>pivot)
--high;
a[low]=a[high];
while(low<high&&a[low]<pivot)
++low;
a[high]=a[low];
}
a[low]=pivot;
//上面為快排的那個分割算法
//以下就是主要思想中所述的内容
if(low==k-1) //找k值
return a[low];
else if(low>k-1)
return kth_elem(a,low_temp,low-1,k);
else
return kth_elem(a,low+1,high_temp,k);
}
----------------------------------------
後序補充：
關于分治思想：
如果第一次 分劃，找到的第s小符合要求m，則停止，
如果找到的第s小，s<m，則到 s的右邊繼續找
如果找到的第s小，s>m，則 到s的左邊繼續找。
舉例說明：
2 1 3 6 4 5
假設第一次劃分之後，3為中間元素：
1、如果要求找第3小的元素，而找到的s=m(要求)，則傳回3
2、如果要求找第1小的元素，而找到的s>m，則在s的左邊找
3、如果要求找第4小的元素，而找到的s<m，則在s的右邊找。
在算法導論上，第九章中，以期望線性時間做選擇，一節中，
我找到了這個 尋找數組中第k小的元素的，平均時間複雜度為O（N）的證明。
中文版是 第110頁，英文版約是第164頁。
不是一趟O（N），而是最終找到那第k個數，然後将其輸出，的複雜度為O（N）。
（或者，O（n+k），最後周遊那k個元素輸出。）。
利用的正是上述類似快排中的分治算法，而與快速排序不同的是：
即快速排序要遞歸處理劃分後的倆邊，而此上述程式，即本題需處理劃分之後的一邊。
是以，快速排序的期望運作時間為O(nlgn),
而上述程式的期望運作時間，最後證明可得O(n)，且假定元素是不同的。
第6題
------------------------------------
騰訊面試題：
給你10分鐘時間，根據上排給出十個數，在其下排填出對應的十個數
要求下排每個數都是先前上排那十個數在下排出現的次數。
上排的十個數如下：
【0，1，2，3，4，5，6，7，8，9】
初看此題，貌似很難，10分鐘過去了，可能有的人，題目都還沒看懂。
舉一個例子，
數值: 0,1,2,3,4,5,6,7,8,9
配置設定: 6,2,1,0,0,0,1,0,0,0
0在下排出現了6次，1在下排出現了2次，
2在下排出現了1次，3在下排出現了0次....
以此類推..
// 引用自July 2010年10月18日。
//數值: 0,1,2,3,4,5,6,7,8,9
//配置設定: 6,2,1,0,0,0,1,0,0,0
#include <iostream.h>
#define len 10
class NumberTB
{
private:
int top[len];
int bottom[len];
bool success;
public:
NumberTB();
int* getBottom();
void setNextBottom();
int getFrequecy(int num);
};
NumberTB::NumberTB()
{
success = false;
//format top
for(int i=0;i<len;i++)
{
top[i] = i;
}
}
int* NumberTB::getBottom()
{
int i = 0;
while(!success)
{
i++;
setNextBottom();
}
return bottom;
}
//set next bottom
void NumberTB::setNextBottom()
{
bool reB = true;
for(int i=0;i<len;i++)
{
int frequecy = getFrequecy(i);
if(bottom[i] != frequecy)
{
bottom[i] = frequecy;
reB = false;
}
}
success = reB;
}
//get frequency in bottom
int NumberTB::getFrequecy(int num) //此處的num即指上排的數 i
{
int count = 0;
for(int i=0;i<len;i++)
{
if(bottom[i] == num)
count++;
}
return count; //cout即對應 frequecy
}
int main()
{
NumberTB nTB;
int* result= nTB.getBottom();
for(int i=0;i<len;i++)
{
cout<<*result++<<endl;
}
return 0;
}
///
運作結果：
6
2
1
1
Press any key to continue
/
第7題
------------------------------------
微軟亞院之程式設計判斷倆個連結清單是否相交
給出倆個單向連結清單的頭指針，比如h1，h2，判斷這倆個連結清單是否相交。
為了簡化問題，我們假設倆個連結清單均不帶環。
問題擴充：
1.如果連結清單可能有環列?
2.如果需要求出倆個連結清單相交的第一個節點列?
//這一題，自己也和不少人讨論過了，
//更詳細的，請看這裡：
//My sina Blog：
//http://blog.sina.com.cn/s/blog_5e3ab00c0100le4s.html
1.首先假定連結清單不帶環
那麼，我們隻要判斷倆個連結清單的尾指針是否相等。
相等，則連結清單相交；否則，連結清單不相交。
2.如果連結清單帶環，
那判斷一連結清單上倆指針相遇的那個節點，在不在另一條連結清單上。
如果在，則相交，如果不在，則不相交。
是以，事實上，這個問題就轉化成了：
1.先判斷帶不帶環
2.如果都不帶環，就判斷尾節點是否相等
3.如果都帶環，判斷一連結清單上倆指針相遇的那個節點，在不在另一條連結清單上。
如果在，則相交，如果不在，則不相交。
//用兩個指針，一個指針步長為1，一個指針步長為2，判斷連結清單是否有環
bool check(const node* head)
{
if(head==NULL)
return false;
node *low=head, *fast=head->next;
while(fast!=NULL && fast->next!=NULL)
{
low=low->next;
fast=fast->next->next;
if(low==fast) return true;
}
return false;
}
//如果連結清單可能有環，則如何判斷兩個連結清單是否相交
//思路：連結清單1 步長為1，連結清單2步長為2 ，如果有環且相交則肯定相遇，否則不相交
list1 head: p1
list2 head: p2
while( p1 != p2 && p1 != NULL && p2 != NULL )
[b]//但當連結清單有環但不相交時，此處是死循環。![/b]
{
p1 = p1->next;
if ( p2->next )
p2 = p2->next->next;
else
p2 = p2->next;
}
if ( p1 == p2 && p1 && p2)
//相交
else
//不相交
是以，判斷帶環的連結清單，相不相交，隻能這樣：
如果都帶環，判斷一連結清單上倆指針相遇的那個節點，在不在另一條連結清單上。
如果在，則相交，如果不在，則不相交。(未寫代碼實作，見諒。:)..
------------------
第9題
-----------------------------------
判斷整數序列是不是二進制查找樹的後序周遊結果
題目：輸入一個整數數組，判斷該數組是不是某二進制查找樹的後序周遊的結果。
如果是傳回true，否則傳回false。
例如輸入5、7、6、9、11、10、8，由于這一整數序列是如下樹的後序周遊結果：
8
/ /
6 10
/ / / /
5 7 9 11
是以傳回true。
如果輸入7、4、6、5，沒有哪棵樹的後序周遊的結果是這個序列，是以傳回false。
//貌似，少有人關注此題。:).2010/10/18
bool verifySquenceOfBST(int squence[], int length)
{
if(squence == NULL || length <= 0)
return false;
// root of a BST is at the end of post order traversal squence
int root = squence[length - 1];
// the nodes in left sub-tree are less than the root
int i = 0;
for(; i < length - 1; ++ i)
{
if(squence[i] > root)
break;
}
// the nodes in the right sub-tree are greater than the root
int j = i;
for(; j < length - 1; ++ j)
{
if(squence[j] < root)
return false;
}
// verify whether the left sub-tree is a BST
bool left = true;
if(i > 0)
left = verifySquenceOfBST(squence, i);
// verify whether the right sub-tree is a BST
bool right = true;
if(i < length - 1)
right = verifySquenceOfBST(squence + i, length - i - 1);
return (left && right);
}
關于第9題：
其實，就是一個後序周遊二叉樹的算法。
關鍵點：
1.
//确定根結點
int root = squence[length - 1];
2.
// the nodes in left sub-tree are less than the root
int i = 0;
for(; i < length - 1; ++ i)
{
if(squence[i] > root)
break;
}
// the nodes in the right sub-tree are greater than the root
int j = i;
for(; j < length - 1; ++ j)
{
if(squence[j] < root)
return false;
}
3.
遞歸周遊，左右子樹。
---------------------------------------
第10題，單詞翻轉。
//單詞翻轉，引用自117 樓 wocaoqwer 的回複。
#include<iostream>
#include<string>
using namespace std;
class ReverseWords{
public:
ReverseWords(string* wo):words(wo){}
void reverse_()
{
int length=words->size();
int begin=-1,end=-1;
for(int i=0;i<length;++i){
if(begin==-1&&words->at(i)==' ')
continue;
if(begin==-1)
{
begin=i;
continue;
}
if(words->at(i)==' ')
end=i-1;
else if(i==length-1)
end=i;
else
continue;
reverse__(begin,end); //1.字母翻轉
begin=-1,end=-1;
}
reverse__(0,length-1); //2.單詞翻轉
}
private:
void reverse__(int begin,int end) //
{
while(begin<end)
{
char t=words->at(begin);
words->at(begin)=words->at(end);
words->at(end)=t;
++begin;
--end;
}
}
string* words;
};
int main(){
string s="I am a student.";
ReverseWords r(&s);
r.reverse_();
cout<<s<<endl;
return 0;
}
運作結果：
student. a am I
Press any key to continue
第11題
------------------------------------
求二叉樹中節點的最大距離...
如果我們把二叉樹看成一個圖，
父子節點之間的連線看成是雙向的，
我們姑且定義"距離"為兩節點之間邊的個數。
寫一個程式，
求一棵二叉樹中相距最遠的兩個節點之間的距離。
//July 2010/10/19
//此題思路，tree_star and i 在257、258樓，講的很明白了。
//定義一個結構體
struct NODE
{
NODE* pLeft;
NODE* pRight;
int MaxLen;
int MaxRgt;
};
NODE* pRoot; //根節點
int MaxLength;
void traversal_MaxLen(NODE* pRoot)
{
if(pRoot == NULL)
{
return 0;
};
if(pRoot->pLeft == NULL)
{
pRoot->MaxLeft = 0;
}
else //若左子樹不為空
{
int TempLen = 0;
if(pRoot->pLeft->MaxLeft > pRoot->pLeft->MaxRight)
//左子樹上的，某一節點，往左邊大，還是往右邊大
{
TempLen+=pRoot->pLeft->MaxLeft;
}
else
{
TempLen+=pRoot->pLeft->MaxRight;
}
pRoot->nMaxLeft = TempLen + 1;
traversal_MaxLen(NODE* pRoot->pLeft);
//此處，加上遞歸
}
if(pRoot->pRigth == NULL)
{
pRoot->MaxRight = 0;
}
else //若右子樹不為空
{
int TempLen = 0;
if(pRoot->pRight->MaxLeft > pRoot->pRight->MaxRight)
//右子樹上的，某一節點，往左邊大，還是往右邊大
{
TempLen+=pRoot->pRight->MaxLeft;
}
else
{
TempLen+=pRoot->pRight->MaxRight;
}
pRoot->MaxRight = TempLen + 1;
traversal_MaxLen(NODE* pRoot->pRight);
//此處，加上遞歸
}
if(pRoot->MaxLeft + pRoot->MaxRight > 0)
{
MaxLength=pRoot->nMaxLeft + pRoot->MaxRight;
}
}
// 資料結構定義
struct NODE
{
NODE* pLeft; // 左子樹
NODE* pRight; // 右子樹
int nMaxLeft; // 左子樹中的最長距離
int nMaxRight; // 右子樹中的最長距離
char chValue; // 該節點的值
};
int nMaxLen = 0;
// 尋找樹中最長的兩段距離
void FindMaxLen(NODE* pRoot)
{
// 周遊到葉子節點，傳回
if(pRoot == NULL)
{
return;
}
// 如果左子樹為空，那麼該節點的左邊最長距離為0
if(pRoot -> pLeft == NULL)
{
pRoot -> nMaxLeft = 0;
}
// 如果右子樹為空，那麼該節點的右邊最長距離為0
if(pRoot -> pRight == NULL)
{
pRoot -> nMaxRight = 0;
}
// 如果左子樹不為空，遞歸尋找左子樹最長距離
if(pRoot -> pLeft != NULL)
{
FindMaxLen(pRoot -> pLeft);
}
// 如果右子樹不為空，遞歸尋找右子樹最長距離
if(pRoot -> pRight != NULL)
{
FindMaxLen(pRoot -> pRight);
}
// 計算左子樹最長節點距離
if(pRoot -> pLeft != NULL)
{
int nTempMax = 0;
if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight)
{
nTempMax = pRoot -> pLeft -> nMaxLeft;
}
else
{
nTempMax = pRoot -> pLeft -> nMaxRight;
}
pRoot -> nMaxLeft = nTempMax + 1;
}
// 計算右子樹最長節點距離
if(pRoot -> pRight != NULL)
{
int nTempMax = 0;
if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight)
{
nTempMax = pRoot -> pRight -> nMaxLeft;
}
else
{
nTempMax = pRoot -> pRight -> nMaxRight;
}
pRoot -> nMaxRight = nTempMax + 1;
}
// 更新最長距離
if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen)
{
nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;
}
}
//很明顯，思路完全一樣，但書上給的這段代碼更規範！:)。
第12題
題目：求1+2+…+n，
要求不能使用乘除法、for、while、if、else、switch、case等關鍵字
以及條件判斷語句（A?B:C）。
//July、2010/10/19
-----------------
循環隻是讓相同的代碼執行n遍而已，我們完全可以不用for和while達到這個效果。
比如定義一個類，我們new一含有n個這種類型元素的數組，
那麼該類的構造函數将确定會被調用n次。我們可以将需要執行的代碼放到構造函數裡。
------------------
#include <iostream.h>
class Temp
{
public:
Temp()
{
++N;
Sum += N;
}
static void Reset() { N = 0; Sum = 0; }
static int GetSum() { return Sum; }
private:
static int N;
static int Sum;
};
int Temp::N = 0;
int Temp::Sum = 0;
int solution1_Sum(int n)
{
Temp::Reset();
Temp *a = new Temp[n]; //就是這個意思，new出n個數組。
delete []a;
a = 0;
return Temp::GetSum();
}
int main()
{
cout<<solution1_Sum(100)<<endl;
return 0;
}
//運作結果：
//5050
//Press any key to continue
//July、2010/10/19
//第二種思路：
----------------
既然不能判斷是不是應該終止遞歸，我們不妨定義兩個函數。
一個函數充當遞歸函數的角色，另一個函數處理終止遞歸的情況，
我們需要做的就是在兩個函數裡二選一。
從二選一我們很自然的想到布爾變量，
比如ture/(1)的時候調用第一個函數，false/(0)的時候調用第二個函數。
那現在的問題是如和把數值變量n轉換成布爾值。
如果對n連續做兩次反運算，即!!n，那麼非零的n轉換為true，0轉換為false。
#include <iostream.h>
class A;
A* Array[2];
class A
{
public:
virtual int Sum (int n) { return 0; }
};
class B: public A
{
public:
virtual int Sum (int n) { return Array[!!n]->Sum(n-1)+n; }
};
int solution2_Sum(int n)
{
A a;
B b;
Array[0] = &a;
Array[1] = &b;
int value = Array[1]->Sum(n);
//利用虛函數的特性，當Array[1]為0時，即Array[0] = &a; 執行A::Sum，
//當Array[1]不為0時， 即Array[1] = &b; 執行B::Sum。
return value;
}
int main()
{
cout<<solution2_Sum(100)<<endl;
return 0;
}
//5050
//Press any key to continue
第13題：
題目：
輸入一個單向連結清單，輸出該連結清單中倒數第k個結點,
連結清單的倒數第0個結點為連結清單的尾指針。
//此題一出，相信，稍微有點 經驗的同志，都會說到：
------------------------
設定兩個指針p1,p2
首先p1和p2都指向head
然後p2向前走n步，這樣p1和p2之間就間隔k個節點
然後p1和p2同……
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
struct ListNode
{
char data;
ListNode* next;
};
ListNode* head,*p,*q;
ListNode *pone,*ptwo;
ListNode* fun(ListNode *head,int k)
{
pone = ptwo = head;
for(int i=0;i<=k-1;i++)
ptwo=ptwo->next;
while(ptwo!=NULL)
{
pone=pone->next;
ptwo=ptwo->next;
}
return pone;
}
int main()
{
char c;
head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL;
p = head;
while(c !='0')
{
q = (ListNode*)malloc(sizeof(ListNode));
q->data = c;
q->next = NULL;
p->next = q;
p = p->next;
c = getchar();
}
cout<<"---------------"<<endl;
cout<<fun(head,2)->data<<endl;
return 0;
}
/
1254863210
---------------
2
Press any key to continue
第14題：
題目：輸入一個已經按升序排序過的數組和一個數字，
在數組中查找兩個數，使得它們的和正好是輸入的那個數字。
要求時間複雜度是O(n)。
如果有多對數字的和等于輸入的數字，輸出任意一對即可。
例如輸入數組1、2、4、7、11、15和數字15。由于4+11=15，是以輸出4和11。
//由于數組已經過升序排列，是以，難度下降了不少。
//July、2010/10/19
#include <iostream.h>
bool FindTwoNumbersWithSum
(
int data[], // 已經排序的 數組
unsigned int length, // 數組長度
int sum, //使用者輸入的 sum
int& num1, // 輸出符合和等于sum的第一個數
int& num2 // 第二個數
)
{
bool found = false;
if(length < 1)
return found;
int begin = 0;
int end = length - 1;
while(end > begin)
{
long curSum = data[begin] + data[end];
if(curSum == sum)
{
num1 = data[begin];
num2 = data[end];
found = true;
break;
}
else if(curSum > sum)
end--;
else
begin++;
}
return found;
}
int main()
{
int x,y;
int a[6]={1,2,4,7,11,15};
if(FindTwoNumbersWithSum(a,6,15,x,y) )
{
cout<<x<<endl<<y<<endl;
}
return 0;
}
4
11
Press any key to continue
擴充：如果輸入的數組是沒有排序的，但知道裡面數字的範圍，其他條件不變，
如何在O(n)時間裡找到這兩個數字？
關于第14題，
1.題目假定是，隻要找出倆個數，的和等于給定的數，
其實是，當給定一排數，
4,5,7,10,12
然後給定一個數，22。
就有倆種可能了。因為22=10+12=10+5+7。
而恰恰與第4題，有關聯了。望大家繼續思考下。:)。
2.第14題，還有一種思路，如下倆個數組：
1、 2、 4、7、11、15 //用15減一下為
14、13、11、8、4、 0 //如果下面出現了和上面一樣的數，稍加判斷，就能找出這倆個數來了。
第一個數組向右掃描，第二個數組向左掃描。
第15題：
題目：輸入一顆二進制查找樹，将該樹轉換為它的鏡像，
即在轉換後的二進制查找樹中，左子樹的結點都大于右子樹的結點。
用遞歸和循環兩種方法完成樹的鏡像轉換。
例如輸入：
8
/ /
6 10
/ / / /
5 7 9 11
輸出：
8
/ /
10 6
/ / / /
11 9 7 5
定義二進制查找樹的結點為：
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
};
//就是遞歸翻轉樹，有子樹則遞歸翻轉子樹。
//July、2010/10/19
void Revertsetree(list *root)
{
if(!root)
return;
list *p;
p=root->leftch;
root->leftch=root->rightch;
root->rightch=p;
if(root->leftch)
Revertsetree(root->leftch);
if(root->rightch)
Revertsetree(root->rightch);
}
由于遞歸的本質是編譯器生成了一個函數調用的棧，
是以用循環來完成同樣任務時最簡單的辦法就是用一個輔助棧來模拟遞歸。
首先我們把樹的頭結點放入棧中。
在循環中，隻要棧不為空，彈出棧的棧頂結點，交換它的左右子樹。
如果它有左子樹，把它的左子樹壓入棧中；
如果它有右子樹，把它的右子樹壓入棧中。
這樣在下次循環中就能交換它兒子結點的左右子樹了。
//再用輔助棧模拟遞歸，改成循環的（有誤之處，望不吝指正）：
void Revertsetree(list *phead)
{
if(!phead)
return;
stack<list*> stacklist;
stacklist.push(phead); //首先把樹的頭結點放入棧中。
while(stacklist.size())
//在循環中，隻要棧不為空，彈出棧的棧頂結點，交換它的左右子樹
{
list* pnode=stacklist.top();
stacklist.pop();
list *ptemp;
ptemp=pnode->leftch;
pnode->leftch=pnode->rightch;
pnode->rightch=ptemp;
if(pnode->leftch)
stacklist.push(pnode->leftch); //若有左子樹，把它的左子樹壓入棧中
if(pnode->rightch)
stacklist.push(pnode->rightch); //若有右子樹，把它的右子樹壓入棧中
}
}
第16題
題目：輸入一顆二進制樹，從上往下按層列印樹的每個結點，同一層中按照從左往右的順序列印。
例如輸入
8
/ /
6 10
// //
5 7 9 11
輸出8 6 10 5 7 9 11。
//題目不是我們所熟悉的，樹的前序，中序，後序。即是樹的層次周遊。
得到的代碼如下：
///
// Get how many 1s in an integer's binary expression
///
int NumberOf1_Solution1(int i)
{
int count = 0;
while(i)
{
if(i & 1)
count ++;
i = i >> 1;
}
return count;
}
可能有讀者會問，整數右移一位在數學上是和除以2是等價的。
那可不可以把上面的代碼中的右移運算符換成除以2呢？答案是最好不要換成除法。
因為除法的效率比移位運算要低的多，
在實際程式設計中如果可以應盡可能地用移位運算符代替乘除法。
這個思路當輸入i是正數時沒有問題，但當輸入的i是一個負數時，
不但不能得到正确的1的個數，還将導緻死循環。
以負數0x80000000為例，右移一位的時候，
并不是簡單地把最高位的1移到第二位變成0x40000000，
而是0xC0000000。這是因為移位前是個負數，仍然要保證移位後是個負數，
是以移位後的最高位會設為1。
如果一直做右移運算，最終這個數字就會變成0xFFFFFFFF而陷入死循環。
為了避免死循環，我們可以不右移輸入的數字i。
首先i和1做與運算，判斷i的最低位是不是為1。
接着把1左移一位得到2，再和i做與運算，就能判斷i的次高位是不是1……
這樣反複左移，每次都能判斷i的其中一位是不是1。基于此，我們得到如下代碼：
///
// Get how many 1s in an integer's binary expression
///
int NumberOf1_Solution2(int i)
{
int count = 0;
unsigned int flag = 1;
while(flag)
{
if(i & flag)
count ++;
flag = flag << 1;
}
return count;
}
29.棧的push、pop序列
題目：輸入兩個整數序列。其中一個序清單示棧的push順序，
判斷另一個序列有沒有可能是對應的pop順序。
如果我們希望pop的數字正好是棧頂數字，直接pop出棧即可；
如果希望pop的數字目前不在棧頂，我們就到
push序列中還沒有被push到棧裡的數字中去搜尋這個數字，
并把在它之前的所有數字都push進棧。
如果所有的數字都被push進棧仍然沒有找到這個數字，表明該序列不可能是一個pop序列。
我們來着重分析下此題：
push序列已經固定，
push pop
--- -- -> /---->
5 4 3 2 1 / 4 5 3 2 1
| 5 |
| 4 |
| 3 |
| 2 |
|___1__|
1.要得到4 5 3 2 1的pop序列，即pop的順序為4->5->3->2->1
首先，要pop4，可讓push5 之前，pop4，然後push5，pop5
然後發現3在棧頂，直接pop 3..2..1
2.再看一序列，
push pop
--- -- -> /---->
5 4 3 2 1 / 4 3 5 1 2
| 5 |
| 4 |
| 3 |
| 2 |
|___1__|
想得到4 3 5 1 2的pop序列，是否可能? 4->3->5->1->2
同樣在push5之前，push 了 4 3 2 1，pop4，pop 3，然後再push 5，pop5
2
再看棧中的從底至上是 1 ，由于1 2已經在棧中，是以隻能先pop2，才能pop1。
是以，很顯然，不可能有 4 3 5 1 2的 pop序列。
是以上述那段注釋的話的意思，即是，
如果，一個元素在棧頂，直接pop即可。如果它不在棧頂，那麼從push序列中找這個元素
找到，那麼push 它，然後再 pop 它。否則，無法在 那個順序中 pop。
//
push序列已經固定，
push pop
--- -- -> /---->
5 4 3 2 1 / 3 5 4 2 1 //可行
| 5 | 1 4 5 3 2 //亦可行，不知各位，是否已明了題意?:)..
| 4 |
| 3 |
| 2 |
|___1__|
///
今早我也來了，呵。
昨晚，後來，自個又想了想，要怎麼才能pop想要的一個數列?
push序列已經固定，
push pop
--- -- -> /---->
5 4 3 2 1 / 5 4 3 2 1
| 5 |
| 4 |
| 3 |
| 2 |
|___1__|
比如，當棧中已有數列 2
1
而現在我随機 要 pop4，一看，4不在棧中，再從push序列中，
正好，4在push隊列中，push4進棧之前，還得把 4前面的數，即3 先push進來，。
好，現在，push 3, push 4，然後便是想要的結果：pop 4。
是以，當我要pop 一個數時，先看這個數 在不在已經push的 棧頂，如果，在，好，直接pop它。
如果，不在，那麼，從 push序列中，去找這個數，找到後，push 它進棧，
如果push隊列中它的前面還有數，那麼 還得把它前面數，先push進棧。
如果鋪設隊列中沒有這個數，那當然 就不是存在這個 pop 結果了。
不知，我說明白了沒?：）.接下來，給一段，參考程式：
//有誤之處，懇請指正。July、2010/11/09。:)。
bool IsPossiblePopOrder(const int* pPush, const int* pPop, int nLength)
{
bool bPossible = false;
if(pPush && pPop && nLength > 0)
{
const int *pNextPush = pPush;
const int *pNextPop = pPop;
// ancillary stack
std::stack<int> stackData;
// check every integers in pPop
while(pNextPop - pPop < nLength)
{
// while the top of the ancillary stack is not the integer
// to be poped, try to push some integers into the stack
while(stackData.empty() || stackData.top() != *pNextPop)
{
// pNextPush == NULL means all integers have been
// pushed into the stack, can't push any longer
if(!pNextPush)
break;
stackData.push(*pNextPush);
// if there are integers left in pPush, move
// pNextPush forward, otherwise set it to be NULL
if(pNextPush - pPush < nLength - 1)
pNextPush ++;
else
pNextPush = NULL;
}
// After pushing, the top of stack is still not same as
// pPextPop, pPextPop is not in a pop sequence
// corresponding to pPush
if(stackData.top() != *pNextPop)
break;
// Check the next integer in pPop
stackData.pop();
pNextPop ++;
}
// if all integers in pPop have been check successfully,
// pPop is a pop sequence corresponding to pPush
if(stackData.empty() && pNextPop - pPop == nLength)
bPossible = true;
}
return bPossible;
}
30.在從1到n的正數中1出現的次數
題目：輸入一個整數n，求從1到n這n個整數的十進制表示中1出現的次數。
例如輸入12，從1到12這些整數中包含1 的數字有1，10，11和12，1一共出現了5次。
分析：這是一道廣為流傳的google面試題。
我們每次判斷整數的個位數字是不是1。如果這個數字大于10，除以10之後再判斷個位數字是不是1。
基于這個思路，不難寫出如下的代碼：*/
int NumberOf1(unsigned int n);
int NumberOf1BeforeBetween1AndN_Solution1(unsigned int n)
{
int number = 0;
// Find the number of 1 in each integer between 1 and n
for(unsigned int i = 1; i <= n; ++ i)
number += NumberOf1(i);
return number;
}
int NumberOf1(unsigned int n)
{
int number = 0;
while(n)
{
if(n % 10 == 1)
number ++;
n = n / 10;
}
return number;
}
這個思路有一個非常明顯的缺點就是每個數字都要計算1在該數字中出現的次數，是以時間複雜度是O(n)。
當輸入的n非常大的時候，需要大量的計算，運算效率很低。
各位，不妨讨論下，更好的解決辦法。:)...
---------------------------
第30題，網友love8909給的思路：
char num[16];
int len, dp[16][16][2];
int dfs(int pos, int ct, int less)
{
if (pos == len)
return ct;
int &ret = dp[pos][ct][less];
if (ret != -1)
return ret;
ret = 0;
for (int d = 0; d <= (less ? 9 : num[pos] - '0'); d++)
ret += dfs(pos + 1, ct + (d == 1), less || d < num[pos] - '0');
return ret;
}
int NumOf1(int n)
{
sprintf(num, "%d", n);
len = strlen(num);
memset(dp, 0xff, sizeof(dp));
return dfs(0, 0, 0);
}
希望，更多的人，提出優化方案。
==========
32.
有兩個序列a,b，大小都為n,序列元素的值任意整數，無序；
要求：通過交換a,b中的元素，使[序列a元素的和]與[序列b元素的和]之間的差最小。
例如:
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];
求解思路：
目前數組a和數組b的和之差為
A = sum(a) - sum(b)
a的第i個元素和b的第j個元素交換後，a和b的和之差為
A' = sum(a) - a[i] + b[j] - （sum(b) - b[j] + a[i])
= sum(a) - sum(b) - 2 (a[i] - b[j])
= A - 2 (a[i] - b[j])
設x = a[i] - b[j]
|A| - |A'| = |A| - |A-2x|
假設A > 0,
當x 在 (0,A)之間時，做這樣的交換才能使得交換後的a和b的和之差變小，
x越接近A/2效果越好,
如果找不到在(0,A)之間的x，則目前的a和b就是答案。
是以算法大概如下：
在a和b中尋找使得x在(0,A)之間并且最接近A/2的i和j，交換相應的i和j元素，
重新計算A後，重複前面的步驟直至找不到(0,A)之間的x為止。
/
算法
1. 将兩序列合并為一個序列，并排序，為序列Source
2. 拿出最大元素Big，次大的元素Small
3. 在餘下的序列S[:-2]進行平分，得到序列max，min
4. 将Small加到max序列，将Big加大min序列，重新計算新序列和，和大的為max，小的為min。
def mean( sorted_list ):
if not sorted_list:
return (([],[]))
big = sorted_list[-1]
small = sorted_list[-2]
big_list, small_list = mean(sorted_list[:-2])
big_list.append(small)
small_list.append(big)
big_list_sum = sum(big_list)
small_list_sum = sum(small_list)
if big_list_sum > small_list_sum:
return ( (big_list, small_list))
else:
return (( small_list, big_list))
tests = [ [1,2,3,4,5,6,700,800],
[10001,10000,100,90,50,1],
range(1, 11),
[12312, 12311, 232, 210, 30, 29, 3, 2, 1, 1]
]
for l in tests:
l.sort()
print "Source List:/t", l
l1,l2 = mean(l)
print "Result List:/t", l1, l2
print "Distance:/t", abs(sum(l1)-sum(l2))
print '-*'*40
輸出結果
Source List: [1, 2, 3, 4, 5, 6, 700, 800]
Result List: [1, 4, 5, 800] [2, 3, 6, 700]
Distance: 99
-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
Source List: [1, 50, 90, 100, 10000, 10001]
Result List: [50, 90, 10000] [1, 100, 10001]
Distance: 38
-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
Source List: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Result List: [2, 3, 6, 7, 10] [1, 4, 5, 8, 9]
Distance: 1
-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
Source List: [1, 1, 2, 3, 29, 30, 210, 232, 12311, 12312]
Result List: [1, 3, 29, 232, 12311] [1, 2, 30, 210, 12312]
Distance: 21
33.
實作一個挺進階的字元比對算法：
給一串很長字元串，要求找到符合要求的字元串，例如目的串：123
1******3***2 ,12*****3這些都要找出來
其實就是類似一些和諧系統。。。。。
分析：
自然比對就是對待比對的每個字元挨個比對
設你的待比對字串長度位n,模式字元串長度位m.
對于待比對字元串中的任意一個字元最壞情況下要比對m次，也就是說這個字元不在模式字元串中。
是以最壞情況下總共是m*n此比對，時間複雜度就是O(m*n)
倘若使用hash表對待字元串進行hash處理O(n)的時間複雜度，那麼對于模式字元串中的任意字元，
僅需一次hash判斷就可以得知是否在待比對字元串中出現。
最壞僅需m次就可以得到結果。時間複雜度為O(m)或者O(n);
與此題相類似：
就是給一個很長的字元串str 還有一個字元集比如{a,b,c} 找出str裡包含{a,b,c}的最短子串。
要求O(n)?
比如，字元集是a,b,c，字元串是abdcaabcx，則最短子串為abc。
用兩個變量 front rear 指向一個的子串區間的頭和尾
用一個int cnt[255]={0}記錄目前這個子串裡 字元集a,b,c 各自的個數，
一個變量sum記錄字元集裡有多少個了
rear 一直加，更新cnt[]和sum的值，直到 sum等于字元集個數
然後front++,直到cnt[]裡某個字元個數為0，這樣就找到一個符合條件的字串了
繼續前面的操作，就可以找到最短的了。
//還有沒有人，對此題了解的比較深的? 望 也多闡述下...:)。
34.實作一個隊列。
隊列的應用場景為：
一個生産者線程将int類型的數入列，一個消費者線程将int類型的數出列
生産者消費者線程示範
一個生産者線程将int類型的數入列，一個消費者線程将int類型的數出列
#include <windows.h>
#include <stdio.h>
#include <process.h>
#include <iostream>
#include <queue>
using namespace std;
HANDLE ghSemaphore; //信号量
const int gMax = 100; //生産(消費)總數
std::queue<int> q; //生産入隊,消費出隊
//生産者線程
unsigned int __stdcall producerThread(void* pParam)
{
int n = 0;
while(++n <= gMax)
{
//生産
q.push(n);
cout<<"produce "<<n<<endl;
ReleaseSemaphore(ghSemaphore, 1, NULL); //增加信号量
Sleep(300);//生産間隔的時間,可以和消費間隔時間一起調節
}
_endthread(); //生産結束
return 0;
}
//消費者線程
unsigned int __stdcall customerThread(void* pParam)
{
int n = gMax;
while(n--)
{
WaitForSingleObject(ghSemaphore, 10000);
//消費
q.pop();
cout<<"custom "<<q.front()<<endl;
Sleep(500);//消費間隔的時間,可以和生産間隔時間一起調節
}
//消費結束
CloseHandle(ghSemaphore);
cout<<"working end."<<endl;
_endthread();
return 0;
}
void threadWorking()
{
ghSemaphore = CreateSemaphore(NULL, 0, gMax, NULL); //信号量來維護線程同步
cout<<"working start."<<endl;
unsigned threadID;
HANDLE handles[2];
handles[0] = (HANDLE)_beginthreadex(
NULL,
0,
producerThread,
nullptr,
0,
&threadID);
handles[1] = (HANDLE)_beginthreadex(
NULL,
0,
customerThread,
nullptr,
0,
&threadID);
WaitForMultipleObjects(2, handles, TRUE, INFINITE);
}
int main()
{
threadWorking();
getchar();
return 0;
}
35.
求一個矩陣中最大的二維矩陣(元素和最大).如:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是:
4 5
5 3
要求:(1)寫出算法;(2)分析時間複雜度;(3)用C寫出關鍵代碼
此第35題與第3題相類似，一個是求最大子數組和，一個是求最大子矩陣和。
3.求子數組的最大和
題目：
輸入一個整形數組，數組裡有正數也有負數。
數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。
求所有子數組的和的最大值。要求時間複雜度為O(n)。
例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數組為3, 10, -4, 7, 2，
int maxSum(int* a, int n)
{
int sum=0;
int b=0;
for(int i=0; i<n; i++)
{
if(b<=0) //此處修正下，把b<0改為 b<=0
b=a[i];
else
b+=a[i];
if(sum<b)
sum=b;
}
return sum;
}
//
解釋下：
例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，
那麼最大的子數組為3, 10, -4, 7, 2，
是以輸出為該子數組的和18
所有的東西都在以下倆行，
即：
b：0 1 -1 3 13 9 16 18 7
sum：0 1 1 3 13 13 16 18 18
其實算法很簡單，目前面的幾個數，加起來後，b<0後，
把b重新指派，置為下一個元素，b=a[i]。
當b>sum，則更新sum=b;
若b<sum，則sum保持原值，不更新。:)。July、10/31。
///
現在回到我們的最初的最大子矩陣的問題,
假設最大子矩陣的結果為從第r行到k行、從第i列到j列的子矩陣，
如下所示(ari表示a[r][i],假設數組下标從1開始)：
| a11 …… a1i ……a1j ……a1n |
| a21 …… a2i ……a2j ……a2n |
.....
| ar1 …… ari ……arj ……arn | 第r行 . . .
.......... |
V
| ak1 …… aki ……akj ……akn | 第k行 . . .
.....
| an1 …… ani ……anj ……ann |
那麼我們将從第r行到第k行的每一行中相同列的加起來，可以得到一個一維數組如下：
(ar1+……+ak1, ar2+……+ak2, ……,arn+……+akn)
由此我們可以看出最後所求的就是此一維數組的最大子斷和問題，
到此我們已經将問題轉化為上面的已經解決了的問題了。
ar1
..
ak1
注，是豎直方向，相加
//有誤之處，肯定指正。:)。
#include <iostream>
2 using namespace std;
3
4 int ** a;
5 int **sum;
6 int max_array(int *a,int n)
7 {
8 int *c = new int [n];
9 int i =0;
10 c[0] = a[0];
11 for(i=1;i<n;i++)
12 {
13 if(c[i-1]<0)
14 c[i] = a[i];
15 else
16 c[i] = c[i-1]+a[i];
17 }
18 int max_sum = -65536;
19 for(i=0;i<n;i++)
20 if(c[i]>max_sum)
21 max_sum = c[i];
22 delete []c;
23 return max_sum;
24
25 }
26 int max_matrix(int n)
27 {
28 int i =0;
29 int j = 0;
30 int max_sum = -65535;
31 int * b = new int [n];
32
33 for(i=0;i<n;i++)
34 {
35 for(j=0;j<n;j++)
36 b[j]= 0;
37 for(j=i;j<n;j++)
//把數組從第i行到第j行相加起來儲存在b中，在加時，自底向上，首先計算行間隔(j-i)等于1的情況，
//然後計算j-i等于 2的情況，一次類推,在小間隔的基礎上一次累加，避免重複計算
38 {
39 for(int k =0;k<=n;k++)
40 b[k] += a[j][k];
41 int sum = max_array(b,n);
42 if(sum > max_sum)
3 max_sum = sum;
44 }
45 }
46 delete []b;
47 return max_sum;
48 }
49 int main()
50 {
51 int n;
52 cin >> n;
53
54 a = new int *[n];
55 sum = new int *[n];
56 int i =0;
57 int j =0;
58 for(i=0;i<n;i++)
59 {
60 sum[i] = new int[n];
61 a[i] = new int[n];
62 for(j=0;j<n;j++)
63 {
64 cin>>a[i][j];
65 sum[i][j] =0 ;
//sum[r][k]表示起始和結尾橫坐标分别為r,k時的最大子矩陣
66 //sum[r][k] = max{sum (a[i][j]):r<=i<=k}:0<=k<=n-1
67 }
68 }
69
73 cout << max_matrix(n);
74 }
我們再來分析下這段，代碼，為了讓你真正弄透它。:)。
求最大子矩陣，我們先按給的代碼的思路來：
1.求最大子矩陣，我們把矩陣中，每一豎直方向的排列，看做一個元素。
是以，矩陣就轉化成了我們熟悉的一維數組。
即以上矩陣，相當于：
a[1->n][1] a[1->n][2] ... a[1->n][i] .. a[1->n][j] .. a[1->n][n]
1->n表示豎直方向，同一列的元素相加。
那麼，假設最大子矩陣，是在第r行->第k行，所有元素的和。
| ar1 …… ari ……arj ……arn |
| . . . . |
| . . . . |
| ak1 …… aki ……akj ……akn |
是以題目就轉化成了類似第3題的思路。
2.先把這第r行->k行的列的元素，分别相加。
即這段代碼：
26 int max_matrix(int n)
27 {
28 int i =0;
29 int j = 0;
30 int max_sum = -65535;
31 int * b = new int [n];
32
33 for(i=0;i<n;i++)
34 {
35 for(j=0;j<n;j++)
36 b[j]= 0;
37 for(j=i;j<n;j++)
//把數組從第i行到第j行相加起來儲存在b中，在加時，自底向上，
//首先計算行間隔(j-i)等于1的情況，然後計算j-i等于 2的情況，
//一次類推,在小間隔的基礎上一次累加，避免重複計算
38 {
39 for(int k =0;k<=n;k++)
40 b[k] += a[j][k];
41 int sum = max_array(b,n);
42 if(sum > max_sum)
3 max_sum = sum;
44 }
45 }
46 delete []b;
47 return max_sum;
48 }
咱們，來稍微分析下，
即，求這段矩陣的和
i行 a[i][1] a[r][2] ... a[r][k] .. a[r][n]
| a[i+1][1]
...
v a[j-1][1]
j行 a[j][1] a[j][2] ... a[j][k] .. a[j][n]
for(i=0;i<n;i++) //第i行
{
for(j=0;j<n;j++) //第j行
b[j]=0; //先把b[j]初始化為 0
for(j=i;j<n;j++) //第i行->第j行 固定行
{
for(int k=0;k<=n;k++) //從上而下，列元素相加
b[k] += a[j][k];
//相加之後，調用上述的求和函數max_array(b,n)即可。
int sum=max_array(b,n);
if(sum>max_sum)
max_sum=sum; //sum->b的結果
}
}
delete []b;
return max_sum;
至于求和max_array(int* a,int n)函數，
6 int max_array(int *a,int n)
7 {
8 int *c = new int [n];
9 int i =0;
10 c[0] = a[0];
11 for(i=1;i<n;i++)
12 {
13 if(c[i-1]<0)
14 c[i] = a[i];
15 else
16 c[i] = c[i-1]+a[i];
17 }
18 int max_sum = -65536;
19 for(i=0;i<n;i++)
20 if(c[i]>max_sum)
21 max_sum = c[i];
22 delete []c;
23 return max_sum;
24
25 }
代碼，則與這個差不多：
int maxSum(int* a, int n)
{
int sum=0;
int b=0;
for(int i=0; i<n; i++)
{
if(b<0) //其實，此處b<0，亦可。無需b<=0.
b=a[i];
else
b+=a[i];
if(sum<b)
sum=b;
}
return sum;
}
例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，
那麼最大的子數組為3, 10, -4, 7, 2，
是以輸出為該子數組的和18
所有的東西都在以下倆行，
即：
b：0 1 -1 3 13 9 16 18 7
sum：0 1 1 3 13 13 16 18 18
最後，矩陣之和，在main函數裡，調用這個函數cout << max_matrix(n);輸出即可。
有誤之處，歡迎指正。
另外，調換倆個for循環的順序，是否更精準?
for(i=0;i<n;i++) //第i行
{
for(j=0;j<n;j++) //第j行
b[j]=0; //先把b[j]初始化為 0
for(int k=0;k<=n;k++) //固定一列，然後0列->k列—>n列，逐級+。
{
for(j=i;j<n;j++) //第i行->第j行->第n行+ +++
//調換倆個for循環的順序，是否更精準?
b[k] += a[j][k];
//相加之後，調用上述的求和函數max_array(b,n)即可。
int sum=max_array(b,n);
if(sum>max_sum)
max_sum=sum; //sum->b的結果
}
}
delete []b;
return max_sum;
完。:)
36.引用自網友：longzuo
谷歌筆試：
n支隊伍比賽，分别編号為0，1，2。。。。n-1，已知它們之間的實力對比關系，
存儲在一個二維數組w[n][n]中，w[i][j] 的值代表編号為i，j的隊伍中更強的一支。
是以w[i][j]=i 或者j，現在給出它們的出場順序，并存儲在數組order[n]中，
比如order[n] = {4,3,5,8,1......}，那麼第一輪比賽就是 4對3， 5對8。.......
勝者晉級，敗者淘汰，同一輪淘汰的所有隊伍排名不再細分，即可以随便排，
下一輪由上一輪的勝者按照順序，再依次兩兩比，比如可能是4對5,直至出現第一名
程式設計實作，給出二維數組w，一維數組order 和 用于輸出比賽名次的數組result[n]，求出result。
#include <stdio.h>
#include <list>
#include <iostream>
void raceResult(int** w, int* order, int* result, int n)
{
std::list<int> winer;
int count = n;
while(n)
{
winer.push_front(order[--n]);
}
int resultNum = count - 1;
int nFirst, nSecond;
int round = 1;
while(winer.size() > 1)
{
//一輪開始
std::cout<<std::endl<<"round "<<round++<<std::endl;
std::list<int>::iterator it = winer.begin();
while (it != winer.end())
{
nFirst = *it;
if (++it == winer.end())
{
//輪空
std::cout<<nFirst<<" rest this round"<<std::endl;
}
else
{
nSecond = *it;
int nWiner = *((int*)w + count * nFirst + nSecond);
if (nWiner == nFirst)
{
it = winer.erase(it);
result[resultNum--] = nSecond;
std::cout<<nFirst<<" kick out "<<nSecond<<std::endl;
}
else
{
it = winer.erase(--it);
result[resultNum--] = nFirst;
++it;
std::cout<<nSecond<<" kick out "<<nFirst<<std::endl;
}
}
}
}
if (winer.size() == 1)
{
result[0] = winer.front();
}
std::cout<<std::endl<<"final result: ";
int nPlace = 0;
while(nPlace < count)
{
std::cout<<std::endl<<result[nPlace++];
}
}
void test()
{
//team 2>team 1>team 3>team 0>team 4>team 5
int w[6][6] = {
0,1,2,3,0,0,
1,1,2,1,1,1,
2,2,2,2,2,2,
3,1,2,3,3,3,
0,1,2,3,4,5
};
int order[6] = {1,3,4,2,0,5};
int result[6] = {-1};
raceResult((int**)w, order, result, 6);
getchar();
}
//自己加上主函數，測試了下，結果竟正确..
int main()
{
test();
return 0;
}
///
round 1
1 kick out 3
2 kick out 4
0 kick out 5
round 2
2 kick out 1
0 rest this round
round 3
2 kick out 0
final result:
2
1
5
4
3
/
37.
有n個長為m+1的字元串，
如果某個字元串的最後m個字元與某個字元串的前m個字元比對，則兩個字元串可以聯接，
問這n個字元串最多可以連成一個多長的字元串，如果出現循環，則傳回錯誤。
恩，好辦法
引用 5 樓 hblac 的回複:
37. 把每個字元串看成一個圖的頂點，兩個字元串比對就連一條有向邊。相當于判斷一個有向圖
是否有環以及求它的直徑
38.
百度面試：
1.用天平（隻能比較，不能稱重）從一堆小球中找出其中唯一一個較輕的，
使用x次天平，最多可以從y個小球中找出較輕的那個，求y與x的關系式
2.有一個很大很大的輸入流，大到沒有存儲器可以将其存儲下來，而且隻輸入一次，如何從這個輸入
流中随機取得m個記錄
3.大量的URL字元串，如何從中去除重複的，優化時間空間複雜度
38,1. y=3^x
38,2. 每次輸入一個記錄時，随機産生一個0到1之間的随機數，
用這些随機數維護一個大小為m的堆，即可。
38,3.大量的URL字元串，如何從中去除重複的，優化時間空間複雜度
這道題見過了，解法是構造一個hash函數，把url适當散列到若幹個，
比如1000個小檔案中，然後在每個小檔案中去除重複的url，再把他們合并。
原理是相同的url，hash之後的散列值仍然是相同的。
38,1
samsho2
我對天平稱重這道題的了解是：
每次将球分成三堆，盡可能讓三堆球一樣多或者讓其中一堆多或者少一個。
球數y和沉重次數x的關系是：
y=1 =》x=0；（顯然）
y=2 =》x=1；（顯然）
y=3 =》x=2；（顯然）
如果y>3，也是将球分為三堆，記為A堆、B堆、C堆
if y=3k（k>1）
稱重一次，就可以判斷瑕疵球在哪堆，進而使得球數降為k個；
if y=3k+1（k>=1） 假設C堆多放1球，A堆和B堆進行稱重
稱重一次，就可以判斷瑕疵球在哪堆，
if A == B ，瑕疵球在C堆，進而使得球數降為k+1個；
else 瑕疵球在輕的堆，進而使得球數降為k個；
if y=3k-1（k>=2） 假設C堆少放1球，A堆和B堆進行稱重
稱重一次，就可以判斷瑕疵球在哪堆，
if A == B ，瑕疵球在C堆，進而使得球數降為k個；
else 瑕疵球在輕的堆，進而使得球數降為k-1個；
利用以上過程反複，可得結果。
最後的次數x = log3（y），可能在y哪裡還需要做點什麼修正。但複雜度就是log y
38，1.
用天平（隻能比較，不能稱重）從一堆小球中找出其中唯一一個較輕的，
使用x次天平 最多可以從y個小球中找出較輕的那個，求y與x的關系式
hengchun11
用天平比較二邊放一樣的球數：有三種可能性
第一種 左邊重 說明較輕的在右邊；
第二種 右邊重 說明較輕的在左邊；
第三種 一樣重 說明較輕的不在這裡面；
以上有三種可能性，在稱x=1的情況下，說明 y=2是可以稱出來的 y=3，也是可以的；y=4就不行
了
是以 我覺得 分成三部分來稱 就可以稱出最多的球
x=1 y=3
x=2 y=9
x=3 y=27
可以得出y=3的x次方
39.
網易有道筆試：
(1).
求一個二叉樹中任意兩個節點間的最大距離，
兩個節點的距離的定義是 這兩個節點間邊的個數，
比如某個孩子節點和父節點間的距離是1，和相鄰兄弟節點間的距離是2，優化時間空間複雜度。
(2).
求一個有向連通圖的割點，割點的定義是，如果除去此節點和與其相關的邊，
有向圖不再連通，描述算法。
先看第39題的第1小問，
求一個二叉樹中任意倆個結點之間的距離。
以前自個，寫的，求二叉樹中節點的最大距離...
void traversal_MaxLen(NODE* pRoot)
{
if(pRoot == NULL)
{
return 0;
};
if(pRoot->pLeft == NULL)
{
pRoot->MaxLeft = 0;
}
else //若左子樹不為空
{
int TempLen = 0;
if(pRoot->pLeft->MaxLeft > pRoot->pLeft->MaxRight)
//左子樹上的，某一節點，往左邊大，還是往右邊大
{
TempLen+=pRoot->pLeft->MaxLeft;
}
else
{
TempLen+=pRoot->pLeft->MaxRight;
}
pRoot->nMaxLeft = TempLen + 1;
traversal_MaxLen(NODE* pRoot->pLeft);
//此處，加上遞歸
}
if(pRoot->pRigth == NULL)
{
pRoot->MaxRight = 0;
}
else //若右子樹不為空
{
int TempLen = 0;
if(pRoot->pRight->MaxLeft > pRoot->pRight->MaxRight)
//右子樹上的，某一節點，往左邊大，還是往右邊大
{
TempLen+=pRoot->pRight->MaxLeft;
}
else
{
TempLen+=pRoot->pRight->MaxRight;
}
pRoot->MaxRight = TempLen + 1;
traversal_MaxLen(NODE* pRoot->pRight);
//此處，加上遞歸
}
if(pRoot->MaxLeft + pRoot->MaxRight > 0)
{
MaxLength=pRoot->nMaxLeft + pRoot->MaxRight;
}
}
// 資料結構定義
struct NODE
{
NODE* pLeft; // 左子樹
NODE* pRight; // 右子樹
int nMaxLeft; // 左子樹中的最長距離
int nMaxRight; // 右子樹中的最長距離
char chValue; // 該節點的值
};
int nMaxLen = 0;
// 尋找樹中最長的兩段距離
void FindMaxLen(NODE* pRoot)
{
// 周遊到葉子節點，傳回
if(pRoot == NULL)
{
return;
}
// 如果左子樹為空，那麼該節點的左邊最長距離為0
if(pRoot -> pLeft == NULL)
{
pRoot -> nMaxLeft = 0;
}
// 如果右子樹為空，那麼該節點的右邊最長距離為0
if(pRoot -> pRight == NULL)
{
pRoot -> nMaxRight = 0;
}
// 如果左子樹不為空，遞歸尋找左子樹最長距離
if(pRoot -> pLeft != NULL)
{
FindMaxLen(pRoot -> pLeft);
}
// 如果右子樹不為空，遞歸尋找右子樹最長距離
if(pRoot -> pRight != NULL)
{
FindMaxLen(pRoot -> pRight);
}
// 計算左子樹最長節點距離
if(pRoot -> pLeft != NULL)
{
int nTempMax = 0;
if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight)
{
nTempMax = pRoot -> pLeft -> nMaxLeft;
}
else
{
nTempMax = pRoot -> pLeft -> nMaxRight;
}
pRoot -> nMaxLeft = nTempMax + 1;
}
// 計算右子樹最長節點距離
if(pRoot -> pRight != NULL)
{
int nTempMax = 0;
if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight)
{
nTempMax = pRoot -> pRight -> nMaxLeft;
}
else
{
nTempMax = pRoot -> pRight -> nMaxRight;
}
pRoot -> nMaxRight = nTempMax + 1;
}
// 更新最長距離
if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen)
{
nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;
}
}
//很明顯，思路完全一樣，但書上 給的這段代碼 更規範！:)。
zhoulei0907
int get_depth(Tree *tree) {
int depth = 0;
if ( tree ) {
int a = get_depth(tree->left);
int b = get_depth(tree->right);
depth = ( a > b ) ? a : b;
depth++;
}
return depth;
}
int get_max_distance(Tree *tree) {
int distance = 0;
if ( tree ) {
// get the max distance connected to the current node
distance = get_depth(tree->left) + get_depth(tree->right);
// compare the value with it's sub trees
int l_distance = get_max_distance(tree->left);
int r_distance = get_max_distance(tree->right);
distance = ( l_distance > distance ) ? l_distance : distance;
distance = ( r_distance > distance ) ? r_distance : distance;
}
return distance;
}
解釋一下，get_depth函數是求二叉樹的深度，用的是遞歸算法：
一棵二叉樹的深度就是它的左子樹的深度和右子樹的深度，兩者的最大值加一。
get_max_distance函數是求二叉樹的最大距離，也是用遞歸算法：
首先算出經過根節點的最大路徑的距離，其實就是左右子樹的深度和；
然後分别算出左子樹和右子樹的最大距離，三者比較，最大值就是目前二叉樹的最大距離了。
這個算法不是效率最高的，因為在計算二叉樹的深度的時候存在重複計算。
但應該是可讀性比較好的，同時也沒有改變原有二叉樹的結構和使用額外的全局變量。
July：
很好。那麼，咱們再來 探讨下這個二叉樹的最大距離問題。
計算一個二叉樹的最大距離有兩個情況:
情況A: 路徑經過左子樹的最深節點，通過根節點，再到右子樹的最深節點。
情況B: 路徑不穿過根節點，而是左子樹或右子樹的最大距離路徑，取其大者。
隻需要計算這兩個情況的路徑距離，并取其大者，就是該二叉樹的最大距離。
簡單的寫下算法。
1.如果根結點，為空，當然 return 0；
2.如果左子樹不為空，
尋找左子樹上最深的那個點（左深度）。
否則，左子樹為空
不尋找。
//即最大距離不通過根結點。
//即最大距離為maxLeft =左深度+1
3.如果右子樹不為空
尋找右子樹上最深的那個點（右深度）。
否則，右子樹為空
不尋找。
//即最大距離不通過根結點。
//即最大距離為maxRight =右深度+1
是以，最大的距離，即為
當有左，無右時，則最大距離maxLen=maxLeft（左深度）+1 //不過根結點
當有右，無左時，則最大距離maxLen=maxRight（右深度）+1 //不過根結點
當有左，也有右時，則最大距離maxLen=maxLeft（左深度）+1 + maxRight（右深度）+1 //過根結點
三者，比較，即得，最終的maxLen。
然後麼最後的問題就隻剩，求左子樹maxLeft或者右子樹maxRight的深度問題。
求一個子樹，如左子樹的maxLeft，即深度問題，
我們可以這麼考慮，
左子樹不為空，左子樹上的，某一節點，往左邊大，還是往右邊大
往左邊大，那麼maxLen加上 往左邊的距離， 即相當于搜尋往深的那一邊 左邊 搜尋
往右邊大，那麼maxLen加上 往右邊的距離。 即相當于搜尋往深的那一邊 左邊 搜尋
好比 鑿井一樣，總要往更深的方向鑿。
鑿到某一個深度後，想下，是往左邊一點鑿，更好列，還是往右邊一點點鑿更好列。
總之，目的就是為了，鑿到更大 的深度。
就是這個道理了。:)。
經過上述，我一番苦口婆心之後，再來看以下這段代碼，是不是更加容易懂了。
:)....
void FindMaxLen(NODE* pRoot)
{
// 周遊到葉子節點，傳回
if(pRoot == NULL)
{
return;
}
// 如果左子樹為空，那麼該節點的左邊最長距離為0
if(pRoot -> pLeft == NULL)
{
pRoot -> nMaxLeft = 0;
}
// 如果右子樹為空，那麼該節點的右邊最長距離為0
if(pRoot -> pRight == NULL)
{
pRoot -> nMaxRight = 0;
}
// 如果左子樹不為空，遞歸尋找左子樹最長距離
if(pRoot -> pLeft != NULL)
{
FindMaxLen(pRoot -> pLeft);
}
// 如果右子樹不為空，遞歸尋找右子樹最長距離
if(pRoot -> pRight != NULL)
{
FindMaxLen(pRoot -> pRight);
}
// 計算左子樹最長節點距離
if(pRoot -> pLeft != NULL)
{
int nTempMax = 0;
if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight)
{
nTempMax = pRoot -> pLeft -> nMaxLeft;
}
else
{
nTempMax = pRoot -> pLeft -> nMaxRight;
}
pRoot -> nMaxLeft = nTempMax + 1;
}
// 計算右子樹最長節點距離
if(pRoot -> pRight != NULL)
{
int nTempMax = 0;
if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight)
{
nTempMax = pRoot -> pRight -> nMaxLeft;
}
else
{
nTempMax = pRoot -> pRight -> nMaxRight;
}
pRoot -> nMaxRight = nTempMax + 1;
}
// 更新最長距離
if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen)
{
nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;
}
}
求左子樹maxLeft或者右子樹maxRight的深度問題，就涉及一個遞歸問題了。
即我們搜尋 這個樹的深度時，不一直就用着遞歸往下搜尋麼。
好比鑿井，當我們試探性的是往左，還是往右，更深一點，
如果，能往右，那麼遞歸 往右鑿， //即隻要右子樹存在，那麼不斷的遞歸右子樹，找最大深度。
如果，能往左，那麼遞歸 往左鑿。 //即隻要左子樹存在，那麼不斷的遞歸左子樹，找最大深度。
這樣，井是不是 已經鑿 的很深了。
很享受，這種鑿井的過程，
希望，我能與更多的人，一起來鑿井，越鑿越要往深處鑿，鑿的越深越好。
同時，把每一道題目，解釋的越簡單易懂，則是我的目标之一。
謝謝。:)
39.
網易有道筆試：
(2).
求一個有向連通圖的割點，割點的定義是，如果除去此節點和與其相關的邊，
有向圖不再連通，描述算法。
網友回複，有誤，指正：
求無向連通圖的割點集
mysword
最簡單的，删掉一個點然後判斷連通性，不就可以了？ //這句話，道出了割點的定義。
BlueSky2008
可以更簡單一些：
在深度優先樹中，根結點為割點，當且僅當他有兩個或兩個以上的子樹。
其餘結點v為割點，當且僅當存在一個v的後代結點s，s到v的祖先結點之間沒有反向邊。
記發現時刻dfn(v)為一個節點v在深度優先搜尋過程中第一次遇到的時刻。
記标号函數low(v) = min(dfn(v), low(s), dfn(w))
s是v的兒子，(v,w)是反向邊。
low(v) 表示從v或v的後代能追溯到的标号最小的節點。
則非根節點v是割點，當且僅當存在v的一個兒子s，low(s) > = dfn(v)
40.百度研發筆試題
引用自：zp155334877
1)設計一個棧結構，滿足一下條件：min，push，pop操作的時間複雜度為O(1)。
2)一串首尾相連的珠子(m個)，有N種顔色(N<=10)，
設計一個算法，取出其中一段，要求包含所有N中顔色，并使長度最短。
并分析時間複雜度與空間複雜度。
3)設計一個系統處理詞語搭配問題，比如說 中國 和人民可以搭配，
則中國人民 人民中國都有效。要求：
*系統每秒的查詢數量可能上千次；
*詞語的數量級為10W；
*每個詞至多可以與1W個詞搭配
當使用者輸入中國人民的時候，要求傳回與這個搭配詞組相關的資訊。
40.百度研發筆試題
引用自：zp155334877
1)設計一個棧結構，滿足一下條件：min，push，pop操作的時間複雜度為O(1)。……
是以，此題的第1小題，即是借助輔助棧，儲存最小值，
且随時更新輔助棧中的元素。
如先後，push 2 6 4 1 5
stack A stack B（輔助棧）
4: 5 1 //push 5,min=p->[3]=1 ^
3: 1 1 //push 1,min=p->[3]=1 | //此刻push進A的元素1小于B中棧頂元素2
2: 4 2 //push 4,min=p->[0]=2 |
1: 6 2 //push 6,min=p->[0]=2 |
0: 2 2 //push 2,min=p->[0]=2 |
push第一個元素進A，也把它push進B，
當向Apush的元素比B中的元素小， 則也push進B，即更新B。否則，不動B，儲存原值。
向棧A push元素時，順序由下至上。
輔助棧B中，始終儲存着最小的元素。
然後，pop棧A中元素，5 1 4 6 2
A B ->更新
4: 5 1 1 //pop 5,min=p->[3]=1 |
3: 1 1 2 //pop 1,min=p->[3]=2 | //下文指的是這裡錯了。
2: 4 2 2 //pop 4,min=p->[0]=2 |
1: 6 2 2 //pop 6,min=p->[0]=2 |
0: 2 2 NULL //pop 2,min=p->[0]=NULL v
當pop A中的元素小于B中棧頂元素時，則也要pop B中棧頂元素。
index 貌似錯了，修正下，
是以，此題的第1小題，即是借助輔助棧，儲存最小值，
且随時更新輔助棧中的元素。
如先後，push 2 6 4 1 5
stack A stack B（輔助棧）
4: 5 1 //push 5,min=p->[3]=1 ^
3: 1 1 //push 1,min=p->[3]=1 | //此刻push進A的元素1小于B中棧頂元素2
2: 4 2 //push 4,min=p->[0]=2 |
1: 6 2 //push 6,min=p->[0]=2 |
0: 2 2 //push 2,min=p->[0]=2 |
push第一個元素進A，也把它push進B，
當向Apush的元素比B中的元素小， 則也push進B，即更新B。否則，不動B，儲存原值。
向棧A push元素時，順序由下至上。
輔助棧B中，始終儲存着最小的元素。
然後，pop棧A中元素，5 1 4 6 2
A B ->更新
4: 5 1 1 //pop 5,min=p->[3]=1 |
3: 1 1 2 //pop 1,min=p->[0]=2 |
2: 4 2 2 //pop 4,min=p->[0]=2 |
1: 6 2 2 //pop 6,min=p->[0]=2 |
0: 2 2 NULL //pop 2,min=NULL v
當pop A中的元素小于B中棧頂元素時，則也要pop B中棧頂元素。
2)一串首尾相連的珠子(m個)，有N種顔色(N<=10)，
設計一個算法，取出其中一段……
2.就是給一個很長的字元串str 還有一個字元集比如{a,b,c} 找出str裡包含{a,b,c}的最短子串。
要求O(n)?
比如，字元集是a,b,c，字元串是abdcaabcx，則最短子串為abc
用兩個變量 front，rear 指向一個的子串區間的頭和尾
用一個int cnt[255]={0}記錄目前這個子串裡 字元集a,b,c 各自的個數，
一個變量sum記錄字元集裡有多少個了。
rear 一直加，更新cnt[]和sum的值，直到 sum等于字元集個數
然後front++,直到cnt[]裡某個字元個數為0，這樣就找到一個符合條件的字串了
繼續前面的操作，就可以找到最短的了。
3.
可以建立一個RDF檔案，利用protege 4.0。或者自己寫的RDF/XML接口也行。
在其中建立兩個“描述對象”一個是國家，一個是人民。 國家之下建立一個中國，
人民。并且在關系中建立一個關系：對每個存在的國家，都have人民。
這樣，每當使用者輸入這兩個詞的時候，
就利用語義架構/接口來判斷一下這兩個詞彙的關系，傳回一個值即可。
--貝葉斯分類--
其實貝葉斯分類更實用一些。 可以用模式識别的貝葉斯算法，
寫一個類并且建立一個詞彙-模式的表。
這個表中每個模式，也就是每個詞彙都設一個域，可以叫做most-fitted word，
然後對這個分類器進行訓練。
![Java經典面試題詳解：帶你手撸紅黑樹總結[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)