數據結構 面試題 4

判斷鏈表是否存在環型鏈表問題
判斷一個鏈表是否存在環例如下面這個鏈表就存在一個環
例如N>N>N>N>N>N就是一個有環的鏈表環的開始結點是N這裡有一個比較簡單的解法
設置兩個指針pp每次循環p向前走一步p向前走兩步直到p碰到NULL指針或者兩個指針相等結束循環如果兩個指針相等則說明存在環
struct link
{
int data;
link* next;
};

bool IsLoop(link* head)
{
link* p=head *p = head;
if (head ==NULL || head>next ==NULL)
{
return false;
}
do{
p= p>next;
p = p>next>next;
} while(p &#;&#; p>next &#;&#; p!=p);
if(p == p)
return true;
else
return false;
}

鏈表反轉的問題
單向鏈表的反轉是一個經常被問到的一個面試題也是一個非常基礎的問題
例如一個鏈表是這樣的 >>>> 通過反轉後成為>>>>最容易想到的方法遍歷一遍鏈表利用一個輔助指針存儲遍歷過程中當前指針指向的下一個元素然後將當前節點元素的指針反轉後利用已經存儲的指針往後面繼續遍歷源代碼如下
struct linka {
int data;
linka* next;
};

void reverse(linka*&#; head)
{
if(head ==NULL)
return;
linka*pre *cur *ne;
pre=head;
cur=head>next;
while(cur)
{
ne = cur>next;
cur>next = pre;
pre = cur;
cur = ne;
}
head>next = NULL;
head = pre;
}
還有一種利用遞歸的方法這種方法的基本思想是在反轉當前節點之前先調用遞歸函數反轉後續節點源代碼如下不過這個方法有一個缺點就是在反轉後的最後一個結點會形成一個環所以必須將函數的返回的節點的next域置為NULL因為要改變head指針所以我用了引用算法的源代碼如下
linka* reverse(linka* plinka*&#; head)
{
if(p == NULL || p>next == NULL)
{
head=p;
return p;
}
else
{
linka* tmp = reverse(p>nexthead);
tmp>next = p;
return p;
}
}

判斷兩個數組中是否存在相同的數字的問題
給定兩個排好序的數組怎樣高效得判斷這兩個數組中存在相同的數字？
這個問題首先想到的是一個O(nlogn)的算法就是任意挑選一個數組遍歷這個數組的所有元素遍歷過程中在另一個數組中對第一個數組中的每個元素進行binary search用C++實現代碼如下
bool findcommon(int a[]int sizeint b[]int size)
{
int i;
for(i=;i;i++)
{
int start=end=sizemid;
while(start<=end)
{
mid=(start+end)/;
if(a[i]==b[mid])
return true;
else if (a[i] end=mid;
else
start=mid+;
}
}
return false;
}
後來發現有一個 O(n)算法因為兩個數組都是排好序的所以只要一次遍歷就行了首先設兩個下標分別初始化為兩個數組的起始地址依次向前推進推進的規則是比較兩個數組中的數字小的那個數組的下標向前推進一步直到任何一個數組的下標到達數組末尾時如果這時還沒碰到相同的數字說明數組中沒有相同的數字
bool findcommon(int a[] int size int b[] int size)
{
int i=j=;
while(i &#;&#; j)
{
if(a[i]==b[j])
return true;
if(a[i]>b[j])
j++;
if(a[i] i++;
}
return false;
}

最大子序列問題
給定一整數序列A A An （可能有負數）求A~An的一個子序列Ai~Aj使得Ai到Aj的和最大
例如整數序列 的最大子序列的和為
對於這個問題最簡單也是最容易想到的那就是窮舉所有子序列的方法利用三重循環依次求出所有子序列的和然後取最大的那個當然算法復雜度會達到O(n^)顯然這種方法不是最優的下面給出一個算法復雜度為O(n)的線性算法實現算法的來源於Programming Pearls一書 在給出線性算法之前先來看一個對窮舉算法進行優化的算法它的算法復雜度為O(n^)其實這個算法只是對對窮舉算法稍微做了一些修改其實子序列的和我們並不需要每次都重新計算一遍假設Sum(i j)是A[i] A[j]的和那麼Sum(i j+) = Sum(i j) + A[j+]利用這一個遞推我們就可以得到下面這個算法
int max_sub(int a[]int size)
{
int ijvmax=a[];
for(i=;i {
v=;
for(j=i;j {
v=v+a[j];//Sum(i j+) = Sum(i j) + A[j+]
if(v>max)
max=v;
}
}
return max;
}
那怎樣才能達到線性復雜度呢？這裡運用動態規劃的思想先看一下源代碼實現
int max_sub(int a[] int size)
{
int imax=temp_sum=;
for(i=;i {
temp_sum+=a[i];
if(temp_sum>max)
max=temp_sum;
else if(temp_sum<)
temp_sum=;
}
return max;
}

按單詞反轉字符串的問題
並不是簡單的字符串反轉而是按給定字符串裡的單詞將字符串倒轉過來就是說字符串裡面的單詞還是保持原來的順序這裡的每個單詞用空格分開
例如Here is
經過反轉後變為
is Here
如果只是簡單的將所有字符串翻轉的話可以遍歷字符串將第一個字符和最後一個交換第二個和倒數第二個交換依次循環其實按照單詞反轉的話可以在第一遍遍歷的基礎上再遍歷一遍字符串對每一個單詞再反轉一次這樣每個單詞又恢復了原來的順序
char* reverse_word(const char* str)
{
int len = strlen(str);
char* restr = new char[len+];
strcpy(restrstr);
int ij;
for(i=j=len;ij)
{
char temp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
}
int k=;
while(k {
i=j=k;
while(restr[j]!= &#;&#; restr[j]!= )
j++;
k=j+;
j;
for(;ij)
{
char temp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
}
}
return restr;
}
如果考慮空間和時間的優化的話當然可以將上面代碼裡兩個字符串交換部分改為異或實現
例如將
char temp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
改為
restr[i]^=restr[j];
restr[j]^=restr[i];
restr[i]^=restr[j];

刪除數組中重復的數字問題
一個動態長度可變的數字序列以數字為結束標志要求將重復的數字用一個數字代替
例如將數組 轉變成 問題比較簡單要注意的是這個數組是動態的所以避免麻煩我還是用了STL的vector
#include
#include
using namespace std;
//remove the duplicated numbers in an intger array the array was end with ;
//eg &#;>
void static remove_duplicated(int a[] vector&#; _st)
{
_stpush_back(a[]);
for(int i=;_st[_stsize()]!=;i++)
{
if(a[i]!=a[i])
_stpush_back(a[i]);
}
}
當然如果可以改變原來的數組的話可以不用STL僅需要指針操作就可以了下面這個程序將修改原來數組的內容
void static remove_duplicated(int a[])
{
if(a[]== || a==NULL)
return;
int insert=current=;
while(a[current]!=)
{
if(a[current]!=a[current])
{
a[insert]=a[current];
insert++;
current++;
}
else
current++;
}
a[insert]=;
}

如何判斷一棵二叉樹是否是平衡二叉樹問題
判斷一個二叉排序樹是否是平衡二叉樹 解決方案根據平衡二叉樹的定義如果任意節點的左右子樹的深度相差不超過那這棵樹就是平衡二叉樹
首先編寫一個計算二叉樹深度的函數利用遞歸實現
template
static int Depth(BSTreeNode* pbs)
{
if (pbs==NULL)
return ;
else
{
int ld = Depth(pbs>left);
int rd = Depth(pbs>right);
return + (ld >rd ? ld : rd);
}
}
下面是利用遞歸判斷左右子樹的深度是否相差來判斷是否是平衡二叉樹的函數
template
static bool isBalance(BSTreeNode* pbs)
{
if (pbs==NULL)
return true;
int dis = Depth(pbs>left) &#; Depth(pbs>right);
if (dis> || dis< )
return false;
else
return isBalance(pbs>left) &#;&#; isBalance(pbs>right);
}

From:http://tw.wingwit.com/Article/program/sjjg/201405/30935.html